У меня есть некоторая проблема в преобразовании следующей грамматики не LL (1) в грамматику LL (1). Можно ли трансформироваться?Проблемы с преобразованием грамматики LL (1)
> A ::= B | A ; B
> B ::= C | [ A ]
> C ::= D | C , D
> D ::= x | (C)
где;, x, (,), [,] - терминалы.
Основными проблемами здесь являются производство
→ A; В
и
С → С, D
, которые остались рекурсии. В обоих случаях эти произведения будут генерировать строку объектов, разделенных какой-то разделитель (точка с запятой в первом случае, запятая во втором), так что вы можете переписать их так:
→ B;
C → D, C
Это дает грамматику
A → B | B; A
B → C | [A]
C → D | D, C
D → x | (C)
Проблема в том, что существуют производные для A и C, которые имеют общий префикс. Но в этом нет ничего страшного: мы можем слева фактор их следующим образом:
→ B H
H → & эпсилон; | ; A
B → C | [А]
С → D I
я → & эпсилон; | C
D → x | (C)
Я считаю, что эта грамматика теперь LL (1).