Устранение левой рекурсии

Я пытаюсь удалить левую рекурсию из следующей грамматики:

S -> id = E
S -> id [ E ] = E
E -> E [ E ]
E -> id

Я попытался следовать алгоритму удаления левой рекурсии, который представлен на https://en.wikipedia.org/wiki/Left_recursion, но строка E -> E [ E ] вызывает у меня проблемы, как с этим обращаться? Я не хочу получать полное решение для этого, просто несколько подсказок, чтобы я действительно мог узнать, как это работает.

Что я пробовал до сих пор, так это:

E -> E [ E ]
E -> id

становится:

E -> id E'
E' -> [ E ] E'

Что неверно. Я вообще на правильном пути?


grammar left-recursion
person atsa    schedule 29.09.2014    source источник

Ответы (1)


arrow_upward
4
arrow_downward

Следуя алгоритму, с которым вы связались, вы хотите A -> A | и у вас есть

E -> E [ E ] | id

так что А - это E, это [ E ] и id. Результатом удаления левой рекурсии будет A -> A 'и A' -> | A ', так что вы понимаете правила:

E -> id E'
E' -> ε | [ E ] E'

Похоже, вы получили правильный результат, вы просто пропустили правило E '-> ...

person Chris Dodd    schedule 29.09.2014
comment
Спасибо. Правило эпсилона отсутствовало, как вы и сказали, и в этом была проблема. - person atsa; 29.09.2014