Является ли эта грамматика LL (1)?

Question

я вывел следующую грамматику:

S -> a | aT 
T -> b | bR 
R -> cb | cbR 

Я понимаю, что для того, чтобы грамматики, чтобы быть LL (1) он должен быть не неоднозначным и правой рекурсии. Проблема в том, что я не совсем понимаю концепцию леворекурсивных и правильно-рекурсивных грамматик. Я не знаю, правильно ли рекурсивна следующая грамматика. Я бы очень оценил простое объяснение концепции леворекурсивных и правильно-рекурсивных грамматик, и если моя грамматика LL (1).

Большое спасибо.

Answer 1

Эта грамматика не LL (1). В синтаксическом анализаторе LL (1) всегда должно быть возможно определить, какое производство следует использовать дальше, исходя из текущего нетерминального символа и следующего знака входа.

Давайте посмотрим на эту продукцию, например:

S → а | aT

Теперь предположим, что я сказал вам, что текущий нетерминальный символ - S, а следующий символ ввода - a. Не могли бы вы определить, какую продукцию использовать?К сожалению, без дополнительного контекста вы не могли этого сделать: возможно, вы должны использовать S → a, и, возможно, вы должны использовать S → aT. Используя аналогичные рассуждения, вы можете видеть, что все другие постановки имеют схожие проблемы.

Это не имеет ничего общего с левой или правой рекурсией, а скорее тем фактом, что никакие два произведения для одного и того же нетерминала в грамматике LL (1) не могут иметь непустой общий префикс. Фактически, простая эвристика для проверки того, является ли грамматика не LL (1) - это посмотреть, можете ли вы найти два таких производственных правила.

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

Answer 2

Грамматика имеет только одно рекурсивное правило: последнее, где R - символ слева, а также появляется справа. Это правильно-рекурсивно, потому что в правиле грамматики R является самым правым символом. Правило относится к R, и эта ссылка является самой правой.

язык является LL (1). Как мы знаем, это то, что мы можем легко построить рекурсивный синтаксический анализатор спуска, который не использует никакого обратного отсчета и не более одного знака lookahead.

Но такой синтаксический анализатор будет основан на слегка модифицированной версии грамматики.

Например, два производства: S -> a и S -> a T могут быть объединены в один, который может быть выражен EBNF S -> a [ T ]. (S получает a, а затем дополнительно T). Это правило может обрабатываться с помощью одной функции синтаксического анализа для распознавания S.

Функция соответствует a, а затем ищет необязательный T, который будет обозначаться следующим символом ввода: b.

Мы можем написать LL (1) грамматикой для этого вдоль этих линий:

S -> a T_opt 
T_opt -> b R_opt 
T_opt -> <empty> 
... et cetera 

необязательность T обрабатывается явным образом, делая T (который мы переименуем в T_opt), способный получения пустого string, а затем сжимается до одного правила для S, так что у нас нет двух фраз, начинающихся с a.

Итак, язык LL (1), но данная грамматика для него не является. Поскольку язык LL (1), можно найти другую грамматику, которая является LL (1), и что грамматика не за горами.