LL(1)-парсеру нужен предпросмотр-символ, чтобы иметь возможность решить, какую продукцию использовать. Это причина, по которой я всегда думал, что термин «упреждающий просмотр» используется, когда синтаксический анализатор просматривает следующий входной токен, не «потребляя» его (т.е. он все еще может быть прочитан из ввода следующим действием). Однако синтаксические анализаторы LR(0) заставили меня усомниться в правильности этого:
Каждый пример LR(0)-парсеров, которые я видел, также использует следующий входной токен для принятия решения о сдвиге или уменьшении. В случае сокращения входной токен не расходуется.
Я использовал бесплатный инструмент «ParsingEmu» для создания таблицы LR и выполнения приведенной ниже оценки LR для слова «aab». Как видите, заголовок столбца содержит токены. Из оценки вы можете видеть, что синтаксический анализатор решает, какой столбец использовать, просматривая следующий входной токен. Но когда синтаксический анализатор сокращает на шагах 4–6, входные данные не меняются (хотя синтаксическому анализатору необходимо знать следующий входной токен «$» при выполнении перехода в следующее состояние).
Грамматика:
S -> A
A -> aA
A -> b
Таблица:
Оценка:
Теперь я сделал следующие предположения по причине моего замешательства:
Мое предположение об определении «предварительного просмотра» (предварительный просмотр = входной токен не используется) неверно. Lookahead просто означает две разные вещи для LL-парсеров или LR-парсеров. Если да, то как тогда можно определить «упреждающий просмотр»?
LR-парсеры имеют (с теоретической точки зрения, когда вы будете использовать автомат с проталкиванием вниз) дополнительные внутренние состояния, в которых они потребляют входной токен, помещая его в стек, и поэтому могут принимать решение о сдвиге-уменьшении, просто взглянув на него. в стеке.
Показанная выше оценка — это LR(1). Если да, то как будет выглядеть оценка LR(0)?
Теперь, что правильно, 1, 2 или 3 или что-то совсем другое?