Генерация таблицы синтаксического анализа LL(1) для данного CFG

CFG выглядит следующим образом:

S -> SD|SB
B -> b|c
D -> a|dB

Метод, который я пробовал, выглядит следующим образом:

Я удалил недетерминизм из первой продукции (S->SD|SB) методом левого факторинга.

Итак, CFG после применения левого факторинга выглядит следующим образом:

S -> SS'
S'-> D|B
B -> b|c
D -> a|dB

Мне нужно найти первый из S для производства, т. е. S -> SS', чтобы продолжить. Может ли кто-нибудь помочь или посоветовать?


parsing ll context-free-grammar
person aliza    schedule 19.12.2015    source источник
comment
Вы не можете решить эту проблему, используя левый факторинг. Однако если вы проанализируете структуру, то увидите, что она эквивалентна S -> S'S.   -  person Willem Van Onsem    schedule 19.12.2015

Ответы (1)


arrow_upward
1
arrow_downward

Вы не можете преобразовать эту грамматику таким образом в синтаксический анализатор LL(1): грамматика леворекурсивная, поэтому вам придется выполнить удаление левой рекурсии . Дело в том, что вы можете проделать следующий трюк: поскольку единственным правилом для S является S -> SS' и S -> (эпсилон), это означает, что вы просто обращаете порядок и, таким образом, вводите правило S -> S'S. Итак, теперь грамматика:

S -> S'S
S'-> D|B
B -> b|c
D -> a|dB

Теперь мы можем построить first: first(B)={b,c}, first(D)={a,d}, < em>first(S')={a,b,c,d} и first(S)={a,b,c,d}.

person Willem Van Onsem    schedule 19.12.2015
comment
Спасибо, но у меня есть сомнения, а именно: - person aliza; 19.12.2015
comment
@alisa: пожалуйста, [edit] ваш вопрос. - person Willem Van Onsem; 19.12.2015
comment
Спасибо за ответ. Я сомневаюсь. Как вы упомянули, дело в том, что вы можете выполнить следующий трюк: поскольку единственным правилом для S является S -> SS' и S -> (эпсилон), это означает, что вы просто обращаете порядок и, таким образом, вводите правило S - > SS. Не могли бы вы также уточнить это? Кроме того, S-›(эпсилон) не является произведением в исходной данной грамматике, как можно было добавить его? Пожалуйста, порекомендуйте. - person aliza; 19.12.2015
comment
@alisa: в большинстве грамматик есть это правило неявно: иначе ваш S сгенерировал бы бесконечное количество S'es. - person Willem Van Onsem; 19.12.2015