Как мне сделать эту грамматику LL(1)?

Question

Допустим, у меня есть эта грамматика

E -> T+Ex | F
T -> T*Fy | w
F -> E | z | ε

Теперь мне нужно сделать это LL(1). Я следовал за шагами, но решение, которое я придумал, кажется не совсем правильным. Кулак позволяет устранить ε-производства

E -> T+Ex | F | T+x
T -> T*Fy | w | T*y
F -> E | z

Теперь мы будем устранять циклы

E -> T+Ex | T+x | z
T -> T*Fy | w | T*y
F -> T+Ex | T+x | z

Нет, мы ликвидируем немедленную левую рекурсию

E -> T+Ex | T+x | z
T -> wT'
T' -> *FyT' | *yT' | ε
F -> T+Ex | T+x | z

Наконец, мы заменим определенные RHS производства, где T произошло

E -> wT'+Ex | wT'+x | z
T -> wT'
T' -> *FyT' | *yT' | ε
F -> wT'+Ex | wT'+x | z

Теперь это не похоже на LL (1) для меня, так как сгенерированная таблица разбора будет иметь несколько записей для нескольких терминалов. Чего мне не хватает?

Answer 1

Я разобрался, как это сделать, поэтому на последнем шаге у нас есть эта конфигурация

E -> wT'+Ex | wT'+x | z
T -> wT'
T' -> *FyT' | *yT' | ε
F -> wT'+Ex | wT'+x | z

Теперь нам нужно выполнить левую факторизацию для удаления продукций вида

S -> aB | aC

И сделать их в правильном виде

S -> aA
A -> B | C

Используя это, мы можем преобразовать нашу грамматику в

E -> wT'+E' | z
E' -> Ex | x
T -> wT'
T' -> *T'' | ε
T'' -> FyT' | yT'
F -> wT'+F' | z
F' -> Ex | x

поскольку F а также F' такие же как E а также E' мы можем просто удалить это производство, чтобы мы остались с.

E -> wT'+E' | z
E' -> Ex | x
T -> wT'
T' -> *T'' | ε
T'' -> EyT' | yT'