Являются ли регулярные выражения

Если у меня есть грамматика типа 3, она может быть представлена ​​в автомате (без каких-либо операций со стеком), поэтому я могу представлять регулярные выражения с использованием контекстно-свободных языков. Но могу ли я знать, что грамматика типа 3 - это , L L ( 1 ) , S L R ( 1 ) и т. Д. Без построения таблиц разбора?$LR(1)$$LL(1)$$SLR(1)$

Все обычные языки имеют грамматику LL (1). Чтобы получить такую ​​грамматику, возьмите любой DFA для обычного языка (возможно, выполняя конструкцию подмножества для NFA, полученного из регулярного выражения), а затем преобразуйте его в правильную рекурсивную регулярную грамматику. Тогда эта грамматика - LL (1), потому что любая пара производств для одного и того же нетерминала либо начинается с разных символов, либо генерирует ε и имеет $ в качестве маркера предварительного просмотра. Следовательно, все регулярные языки также являются LR (1), поскольку любая грамматика LL (1) является LR (1). Кроме того, используя важный результат из этой статьи , вы можете показать, что любой язык LR (1) имеет грамматику SLR (1), что означает, что любой обычный язык имеет грамматику SLR (1).

Тем не менее, обычные языки не все LR (0). Языки LR (0) имеют очень специфические свойства - в частности, они должны быть без префиксов. Таким образом, обычный язык {a, aa} не является LR (0), хотя он явно регулярен (регулярное выражение a | (aa)). Однако языки LR (0) неправильно содержатся в обычных языках; эта грамматика для {0 ⁿ 21 ⁿ | n ≥ 1} является LR (0), но язык не является регулярным:

S -> E
E -> 0E1 | 2

Надеюсь это поможет!

(Простой старый) синтаксис регулярного выражения (вы сказали «представление») - это LR (0). Вам не нужно искать, чтобы разобрать строку, представляющую регулярное выражение. Вы можете легко решить это, запустив генератор синтаксического анализатора для грамматики для регулярных выражений: -} Вы также можете легко закодировать простой анализатор рекурсивного спуска (LL (0)) для регулярных выражений; все, что является LL (0), является LR (0).

Я не знаю, похож ли синтаксис более сложных так называемых «регулярных выражений», таких как Perl; но регулярные выражения Perl строго более мощные, чем регулярные выражения, поэтому они не являются простыми старыми регулярными выражениями.

Чтобы определить, есть ли у грамматики какое-либо свойство, вы должны запустить какой-то предикат. Чтобы определить, является ли это (S) LR (k), вы должны запустить предикат, который может проверять это свойство. По сути, любой такой предикат должен фактически создавать таблицы разбора из-за способа их определения.