Левая рекурсия исключения для E: = EE + | EE- | id

Как избавиться от левой рекурсии для следующей грамматики?

E := EE+|EE-|id

Используя обычную процедуру:

A := Aa|b

переводится на:

A := b|A'
A' := ϵ| Aa

Применяя это к исходной грамматике, мы получаем:

A = E, a = (E+|E-) and b = id

Следовательно:

E := id|E'
E' := ϵ|E(E+|E-)

Но эта грамматика кажется неправильной, потому что

ϵE+ -> ϵ id +

будет действительным, но это неправильное постфиксное выражение.


parsing compiler-construction grammar lexical-analysis context-free-grammar
person TheOne    schedule 25.10.2009    source источник
comment
Возможно, вам стоит упомянуть, что e на самом деле ϵ. Во всяком случае, обманул меня.   -  person Konrad Rudolph    schedule 25.10.2009
comment
У вас проблема с переводом на определение: вы ввели неопределенный термин «е». Вероятно, вы сможете что-то сделать, перегруппировав оригинал как 'E: = (EE (+ | -)) | id'. Ваш последний комментарий «это неправильное постфиксное выражение» несколько размашистый; почему "e id +" неверный? Похоже, «толкни е; push id; оценить + ', что обычно нормально.   -  person Jonathan Leffler    schedule 25.10.2009
comment
@Konrad: а-а - «е» пусто? ... это имеет значение.   -  person Jonathan Leffler    schedule 25.10.2009
comment
Не знал, как ввести эпсилон. :)   -  person TheOne    schedule 25.10.2009
comment
@ Absolute0: нет проблем - если вы объясните используемые обозначения.   -  person Jonathan Leffler    schedule 25.10.2009
comment
Не следует ли перенести такие вопросы в теоретическую информатику?   -  person Pale Blue Dot    schedule 16.07.2012

Ответы (1)


arrow_upward
11
arrow_downward

Ваша «обычная процедура» цитируется неправильно. Взято из Книги Дракона:

A := Aα | β

становится

A  := βA′
A′ := αA′ | ϵ

… что дает:

E  := id E′
E′ := (E + | E -) E′ | ϵ
person Konrad Rudolph    schedule 25.10.2009
comment
Как вы вводите математические символы ?? - person TheOne; 25.10.2009
comment
Absolute0: простой трюк: я использую таблицу символов. Я использую OS X, в которой есть инструмент для этого. В Windows вы можете использовать charmap.exe, который скрыт в главном меню «Стандартные» (однако необходимо переключиться на Unicode). - person Konrad Rudolph; 25.10.2009