Проблема устранения левой рекурсии

Итак, у меня есть эта левая рекурсивная грамматика

E → E Op1 E2 | E2

В нынешнем виде это левая рекурсия, поэтому я устранил левую рекурсию, добавив еще один шаг:

E → X E2
X → E Op1 E2 | ε

Однако у меня есть подозрение, что я удалил его неправильно, потому что, если я отследю его, то ПЕРВЫЙ набор E все равно будет начинаться с E. Я прав? Или я что-то упускаю? Этот вопрос является частью более крупного набора грамматик, FYI.


person Doh    schedule 05.05.2014    source источник
comment
Вы реализуете какой-то компилятор? Или это просто общий вопрос?   -  person rpax    schedule 05.05.2014
comment
Ваши рассуждения кажутся правильными; однако я бы посчитал этот вопрос не относящимся к теме, поскольку он в первую очередь касается теоретической информатики, а не программирования в строгом смысле.   -  person Codor    schedule 05.05.2014
comment
В конечном итоге мне придется реализовать эти наборы грамматики в синтаксическом анализаторе, а затем написать программу, реализующую этот синтаксический анализатор, поэтому я подумал, что это уместно.   -  person Doh    schedule 05.05.2014


Ответы (1)


Чего вам не хватает, так это второй части устранения рекурсии: вместо

X → E Op1 E2 | ε

тебе нужно

X → Op1 E2 X | ε
person András Hummer    schedule 07.05.2014