Иллюстрировать самый левый вывод в потоке токенов

Question

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

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

Давайте продолжать использовать следующую грамматику из вышеуказанной ссылке:

И данной лексемы последовательности: 1 2 3

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

1 2 3 
-> D D D 
-> N D D (rewrite the *left-most* D to N according to the rule N->D.) 
-> N D (rewrite the *left-most* N D to N according to the rule N->N D.) 
-> N (same as above.) 

Но есть и другие способы применения правил грамматики:

1 2 3 -> DDD -> NDD -> NND -> NNN

ИЛИ

1 2 3 -> DDD -> NDD -> NND -> НН

Но только первый вывод заканчивается в одном не-терминале.

По мере увеличения длины последовательности токенов может быть еще много способов. Я думаю, вывести правильную происходящие шаги необходимы 2 предпосылок:

• отправного/корень правило
• лексемы последовательность

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

Answer 1

Общий процесс LL синтаксического анализа состоит из многократно:

• Предскажите производства для верхнего символа грамматики в стеке, если этот символ не является терминалом, и заменить этот символ с правая часть производства.

• Матч символ верхней грамматики в стеке со следующим символом ввода, отбрасывающий их оба.

Действие матча является непроблематичным, но для прогнозирования может потребоваться оракул. Однако для целей этого объяснения механизм, посредством которого выполняется предсказание, не имеет значения, если он работает. Например, может быть, что для небольшого целого числа k каждая возможная последовательность входных символов k согласуется только с максимально возможным производством, и в этом случае вы можете использовать справочную таблицу.В этом случае мы говорим, что грамматика равна LL(k). Но вы можете использовать любой механизм, включая магию. Нужно только, чтобы предсказание всегда было точным.

На любом этапе этого алгоритма частично полученная строка представляет собой потребляемый вход, добавленный в стек. Первоначально нет потребляемого ввода, и стек состоит исключительно из символа начала, так что частично производная строка (которая имела 0 производных отведений). Поскольку потребленный вход состоит исключительно из терминалов, и алгоритм только когда-либо модифицирует верхний (первый) элемент стека, ясно, что серия частично полученных строк представляет собой самый левый вывод.

Если синтаксический анализ завершен, весь вход будет потреблен, и стек будет пустым, поэтому синтаксический анализ приведет к самому левому выводу ввода из символа начала.

Вот полный синтаксический анализ для примера:

Consumed   Unconsumed Partial  Production 
Input  Stack input  derivation or other action 
-------- ----- ---------- ---------- --------------- 
      N  1 2 3  N   N → N D 
      N D  1 2 3  N D   N → N D 
      N D D 1 2 3  N D D  N → D 
      D D D 1 2 3  D D D  D → 1 
      1 D D 1 2 3  1 D D  -- match -- 
1   D D  2 3  1 D D  D → 2 
1   2 D  2 3  1 2 D  -- match -- 
1 2  D   3  1 2 D  D → 3 
1 2  3   3  1 2 3  -- match -- 
1 2 3  --   --  1 2 3  -- success -- 

Если вы читали последние два столбца, вы можете увидеть процесс деривации, начиная с N и заканчивая 1 2 3. В этом примере предсказание может быть сделано только с помощью магии, потому что правило N → N D не LL (k) для любых k; с помощью правой рекурсии правила N → D N вместо позволил бы LL (2) процедура принятия решений (например, «использовать N → D N, если есть по крайней мере два неизрасходованные входные лексемы, в противном случае N → D».)

схему, которую Вы пытаетесь произвести , который начинается с 1 2 3 и заканчивается N, является снизу вверх синтаксический разбор. Искомые анализы с использованием алгоритма LR соответствуют самым правым выводам, но вывод необходимо прочитать назад, так как он заканчивается символом начала.