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

Я чувствую себя довольно ностальгическим, поэтому я решил написать создателя приключенческой игры, который позволяет вводить сложные предложения для пользователя.Удаление левой рекурсии

У меня есть руки скрутили лексер и синтаксический анализатор, который использует шаблон посетителя и она работает очень хорошо, пока я не столкнулся с левой рекурсией вопроса с одним из моих BNF (Бэкус-Наур) правил:

object   ::= {adjective} noun 
        | object AND {adjective} noun

После удаления левой рекурсии by following this wiki entry это выглядит правильно?

object  ::= {adjective} noun object2 
object2  ::= AND {adjective noun} 
       | !Empty

Отредактировано:

Я рука прокатка лексера и анализатор с использованием C#, следуя инструкции, данные here. Я не использую генераторы парсеров для этого упражнения.

Кроме того, я получил правила BNF для синтаксического анализатора от this website.

источник

2013-07-15 Intrepid

Было бы полезно, если бы вы объяснили, какие инструменты или алгоритмы вы используете для синтаксического анализа. Поскольку у вас возникают проблемы с левой рекурсией, я выводю, что вы используете рекурсивный спуск, что хорошо, но было бы полезно знать наверняка и какой генератор парсера (если таковой имеется) вы используете. –

Я обновил свой оригинальный вопрос с дополнительной информацией. – Intrepid

Есть ли причина предпочесть левую рекурсию по правильной рекурсии в этом случае? Не будет ли проще:

object ::= {adjective} noun | 
      {adjective} noun AND object

Если вы действительно хотите, чтобы сделать работу решения, вам нужно сделать object2 правой рекурсии:

object  ::= {adjective} noun object2 
object2  ::= AND {adjective noun} object2 | 
       !Empty

источник

2013-07-15 08:24:04

Использование левого рекурсии приводит к ошибке переполнения стека, и мне пришлось изменить правило, чтобы использовать право-рекурсию, чтобы обойти это. Исходное правило BNF для 'object' допускает только один' AND', поэтому я не сделал 'object2' правильным рекурсивным. – Intrepid

Первое правило BNF в вашем вопросе допускает одно или несколько повторений. Он не ограничивает ввод двумя повторениями. –

Rob: На самом деле, да, вы совершенно правы, это позволяет или или больше повторений. Виноват! Я принимаю ваш второй ответ после изменения моего кода, чтобы следовать этому правилу, и теперь он работает. Благодаря! – Intrepid

Обычно, когда у меня есть это правило (ваши):

object   ::= {adjective} noun | 
        object AND {adjective} noun

применяет следующие преобразования:

1-й этап (до сих пор остались рекурсии) -

object   ::= ad_noun | 
        object AND ad_noun 

ad_noun   ::= {adjective} noun

Этап 2 (изменение правой рекурсии) -

object   ::= ad_noun | 
        ad_noun AND object 

ad_noun   ::= {adjective} noun

источник

2013-07-15 08:32:41

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

ответ

Смежные вопросы