Нисходящий Parser хочет иметь приличный пример case-left-recursion в 'Code' - PullRequest
Новая
       36

Нисходящий Parser хочет иметь приличный пример case-left-recursion в 'Code'

5 голосов
/ 24 октября 2010

Здравствуйте, коллега по стеку для членов потока.

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

Вопросы,

a) Я понимаю, что правильный анализатор Top-Down равен LLи Bottom-Up Parser равен LR?

b) Я обнаружил, что левая рекурсия - это правило, которое вызывает себя ex) Expr: == Expr '+' Term |Термин, который может вызвать бесконечный цикл, чтобы найти Expr.Но, во всяком случае, любой пример кода рассматривает ввод в C или Java?(Мне не нужен код синтаксического анализатора или сканера) Мне нужен пример кода случая с формой предложения, которая возникает в бесконечном цикле с помощью левой рекурсии.

c) Что на самом деле имеет значение в способе использования правой рекурсии в Top-Down Parser?

ANS c) Устранение необходимости возврата.но что-то еще?

ANS b) x - 2 * y но также что-то еще?потому что этот работает с методом обратного анализа.

Пример, в котором я обнаружил как левостороннюю рекурсию, так и левую рекурсию.

Грамматика левой рекурсии 

A -> Ax

Нелевая левая грамматика рекурсии 

A -> Bx
B -> Ay

Оба находятся в бесконечном цикле.

Спасибо и ценим за всех ваших экспертов.

1 Ответ

6 голосов
/ 25 октября 2010

а) Правильно ли я понимаю, что анализатор сверху вниз равен LL, а анализатор снизу равен LR?да

Парсеры сверху вниз попадают в бесконечный цикл с левой рекурсией, так как в коде записи выглядят так: 

A() {
  A(); match(x);
}

A вызывает себя навсегда и никогда ничего не удаляет из входного потока.

Левая рекурсия не должна быть немедленной, поэтому ваша "не левая рекурсивная грамматика" все еще остается рекурсивной: 

A -> Bx | z
B -> Ay

Вы можете увидеть, что она остается рекурсивной, если вы замените Bпо его производству: 

A -> Ayx | z

Вот пример правильного преобразования леворекурсивной грамматики в праворекурсивную грамматику: Левая рекурсивная: 

E -> E + T | T

Правая рекурсивная: 

E -> T B
B -> + T B | Lambda

E -> TB, поскольку в правиле E -> E + T |T, T ВСЕГДА появится слева от вас после завершения применения правила.Так как E -> TB заботится о самой левой стороне, мы можем построить правую часть строки, которую мы делаем с B -> + T B. Нам нужно лямбда-производство, чтобы дать нам точку остановки длярекурсия.

A -> Ax и A -> xA будут эквивалентными грамматиками, только одна левая, а другая рекурсивная справа.

...