Разница между сдвигом и прогнозом

Question

Учитывая простую грамматику, как

rule1
    := token1 token2 token3 token4
    || token1 token2 token3 token3;

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

Answer 1

В синтаксическом анализаторе сдвига / уменьшения просмотр не используется для определения того, какая продукция рассматривается, а скорее для того, чтобы решить, должен ли анализатор сместить следующий токен или предпринять какое-либо действие сокращения. Если бы у вас был парсер сдвига / уменьшения для вышеуказанной грамматики, парсер всегда сдвигал четыре токена, прежде чем решить, уменьшать или нет; помните, что в синтаксических анализаторах LR сокращения выполняются только тогда, когда соответствующий набор символов находится над стеком синтаксического анализа. Заглядывание вперед будет необходимо только в том случае, если парсер не сможет определить, следует ли ему уменьшить четыре токена, которые он имеет, или продолжать смещать больше символов и уменьшать их в дальнейшем.

В частности, парсер, вероятно, будет делать что-то вроде этого:

Stack                           Input                        Action
-------------------------------------------------------------------------------
                                token1 token2 token3 token4  Shift
token1                                 token2 token3 token4  Shift
token1 token2                                 token3 token4  Shift
token1 token2 token3                                 token4  Shift
token1 token2 token3 token4                                  Reduce, Option 1
rule1                                                        Accept

Или же

Stack                           Input                        Action
-------------------------------------------------------------------------------
                                token1 token2 token3 token3  Shift
token1                                 token2 token3 token3  Shift
token1 token2                                 token3 token3  Shift
token1 token2 token3                                 token3  Shift
token1 token2 token3 token3                                  Reduce, Option 2
rule1                                                        Accept

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

Stack                           Input                             Action
----------------------------------------------------------------------------------
rule1                           token1 token2 token3 token4 $$$$  Predict, Option 1
token1 token2 token3 token4     token1 token2 token3 token4 $$$$  Match
token2 token3 token4            token2 token3 token4 $$$$         Match
token3 token4                   token3 token4 $$$$                Match
token4                          token4 $$$$                       Match
                                $$$$                              Accept

Или же

Stack                           Input                             Action
----------------------------------------------------------------------------------
rule1                           token1 token2 token3 token3 $$$$  Predict, Option 2
token1 token2 token3 token3     token1 token2 token3 token3 $$$$  Match
token2 token3 token3            token2 token3 token3 $$$$         Match
token3 token3                   token3 token3 $$$$                Match
token3                          token3 $$$$                       Match
                                $$$$                              Accept

Обратите внимание, что предварительный просмотр необходим, чтобы предсказать, какую продукцию использовать, поэтому анализатор должен иметь четыре маркера просмотра. В парсере LR парсер работает, проверяя больше токенов, пока не станет удобно, что он увидит то, что ищет, затем уменьшит (сдвиг / уменьшение парсинга). В этом случае не требуется никакого предварительного просмотра. Lookahead требуется только в синтаксическом анализаторе LR, чтобы определить, видел ли анализатор конец дескриптора (строку, которую нужно уменьшить), или он находится в середине дескриптора и должен продолжать смещение. Вот почему, например, некоторые интересные грамматики могут быть показаны как LR(0), но единственными грамматиками, которые являются LL(0), являются грамматики, в которых каждый нетерминал имеет ровно одну связанную продукцию; у lookahead есть принципиально иное применение при разборе сверху вниз и снизу вверх.

Вообще говоря, анализаторы сверху вниз могут обрабатывать меньше грамматик, чем анализаторы снизу вверх, и фактически любая грамматика LL(k) гарантированно будет LR(k), но не наоборот.

Надеюсь это поможет!