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

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

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), так как таблица синтаксического анализа, сгенерированная этим, будет иметь несколько записей для нескольких терминалов. Что мне кажется не хватает?


parsing compiler-construction grammar ll theory
person Dillon Drobena    schedule 18.03.2015    source источник

Ответы (1)


arrow_upward
1
arrow_downward

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

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'
person Dillon Drobena    schedule 24.03.2015