Как сделать эту грамматику 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' такие же, как и EE' мы можем просто удалить эту продукцию, чтобы мы остались с.

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