В синтаксическом анализаторе сдвига / уменьшения просмотр не используется для определения того, какая продукция рассматривается, а скорее для того, чтобы решить, должен ли анализатор сдвинуть следующий токен или предпринять какое-либо действие сокращения.Если бы у вас был парсер сдвига / уменьшения для вышеуказанной грамматики, парсер всегда сдвигал четыре токена, прежде чем решить, уменьшать или нет;помните, что в синтаксических анализаторах 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
Обратите внимание, какLookahead необходим, чтобы предсказать, какую продукцию использовать, поэтому синтаксический анализатор должен иметь четыре токена Lookahead.В парсере LR парсер работает, проверяя больше токенов, пока не станет удобно, что он увидит то, что ищет, затем уменьшит (сдвиг / уменьшение парсинга).В этом случае не требуется никакого предварительного просмотра.Lookahead требуется только в синтаксическом анализаторе LR, чтобы определить, видел ли анализатор конец дескриптора (строка для сокращения), или он находится в середине дескриптора и должен продолжать сдвиг.Вот почему, например, некоторые интересные грамматики могут быть показаны как LR (0), но единственными грамматиками, которые являются LL (0), являются грамматики, в которых каждый нетерминал имеет ровно одну связанную продукцию;упреждающий анализ имеет принципиально иное применение при синтаксическом анализе «сверху вниз» и «снизу вверх».
Вообще говоря, синтаксические анализаторы «сверху вниз» могут обрабатывать меньше грамматик, чем анализаторы «снизу вверх», и фактически любая грамматика LL (k) гарантирована.быть LR (k), но не наоборот.
Надеюсь, это поможет!