Будет ли этот «алгоритм» для nullable и first работать (в парсере)? - PullRequest
Новая
       43

Будет ли этот «алгоритм» для nullable и first работать (в парсере)?

4 голосов
/ 25 января 2010

Работа через это для удовольствия: http://www.diku.dk/hjemmesider/ansatte/torbenm/Basics/

Пример вычисления значения nullable и сначала используется расчет с фиксированной запятой. (см. раздел 3.8)

Я делаю вещи в Схеме и очень полагаюсь на рекурсию.

Если вы попытаетесь реализовать nullable или сначала с помощью рекурсии, должно быть ясно, что вы будете бесконечно повторяться в такой работе, как

N -> N a b

где N - нетерминал, а a, b - терминалы.

Может ли это быть решено рекурсивно, поддерживая набор нетерминалов, видимых в левой части производственных правил, и игнорируя их после того, как мы их учли один раз?

Кажется, это работает для nullable. Как насчет первого?

РЕДАКТИРОВАТЬ: Это то, что я узнал из игры вокруг. Ссылка на исходный код внизу.

Нетерминалы нельзя игнорировать при вычислении first, если они не обнуляются.

Рассмотрим: 

N -> N a
N -> X
N ->

Здесь мы можем игнорировать N в N a, потому что N обнуляем. Мы можем заменить N -> N a на N -> a и сделать вывод, что a является членом first(N).

Здесь мы не можем игнорировать N: 

N -> N a
N -> M
M -> b

Если бы мы игнорировали N в N -> N a, мы бы пришли к выводу, что a находится в first(N), что неверно. Вместо этого мы видим, что N не может обнуляться, и, следовательно, при первом вычислении мы можем опустить любое производство, где N находится в качестве первого символа в RHS.

Это дает: 

N -> M
M -> b

, что говорит нам b в first(N).

Исходный код: http://gist.github.com/287069

Так ... это звучит нормально?

1 Ответ

1 голос
/ 08 марта 2011

Предлагаю продолжить читать:)

3.13 Rewriting a grammar for LL(1) parsing и особенно 3.13.1 Eliminating left-recursion.

Просто чтобы заметить, что вы также можете столкнуться с косвенной левой рекурсией: 

A -> Bac
B -> A
B -> _also something else_

Но решение здесь очень похоже на устранение прямой левой рекурсии, как в первом примере.

Возможно, вы захотите проверить эту статью , которая объясняет это немного более простым способом. Меньше теории:)

...