Разве LR(0) парсер тоже не использует lookaheads?
LL(1)-парсеру нужен символ предпросмотра, чтобы иметь возможность решить, какую продукцию использовать. Это причина, по которой я всегда думал, что термин "lookahead" используется, когда анализатор смотрит на следующий входной токен, не "потребляя" его (т.е. он все еще может быть прочитан из ввода следующим действием). Однако парсеры LR(0) заставили меня усомниться в том, что это правильно:
Каждый пример LR(0)-парсеров, которые я видел, также использует следующий входной токен для решения, сдвигать или уменьшать. В случае сокращения входной токен не расходуется.
Я использовал бесплатный инструмент "ParsingEmu" для генерации LR-таблицы и выполнения оценки LR ниже для слова "aab". Как видите, заголовок столбца содержит токены. Из оценки вы можете увидеть, что анализатор решает, какой столбец использовать, просматривая следующий входной токен. Но когда синтаксический анализатор уменьшается в шагах 4 - 6, входные данные не изменяются (хотя синтаксический анализатор должен знать следующий входной токен "$" при выполнении перехода в следующее состояние).
Грамматика:
S -> A
A -> aA
A -> b
Таблица:
Оценка:
Теперь я сделал следующие предположения по причине моей путаницы:
Мое предположение для определения "lookahead" (lookahead = входной токен не используется) неверно. Lookahead просто означает две разные вещи для LL-парсеров или LR-парсеров. Если так, то как же тогда определить "предвидение"?
LR-синтаксические анализаторы имеют (с теоретической точки зрения, когда вы будете использовать push-down автомат) дополнительные внутренние состояния, когда они потребляют входной токен, помещая его в стек, и, следовательно, способны принимать решение об уменьшении или сдвиге, просто просматривая в стеке.
Оценка, показанная выше, является LR(1). Если это правда, как будет выглядеть оценка LR(0)?
Что теперь правильно, 1, 2 или 3 или что-то совершенно другое?
1 ответ
Важно быть точным:
Анализатор LR(k) использует текущее состояние синтаксического анализатора и k символов предпросмотра, чтобы решить, следует ли уменьшить, и если да, то каким образом.
Он также использует таблицу сдвига сдвига, чтобы решить, в какое состояние анализа он должен перейти после сдвига следующего входного токена. Таблица сдвига сдвига определяется текущим состоянием и (одиночным) токеном, который сдвигается, независимо от значения k.
Если в заданном состоянии синтаксического анализатора было бы возможно выполнить и сдвиг, и действие уменьшения, то синтаксический анализатор имеет конфликт сдвиг / уменьшение, и он недопустим. Следовательно, два вышеупомянутых определения теоретически могут быть сделаны недетерминированно.
Если в данном состоянии синтаксического анализатора уменьшение невозможно, и следующий входной символ не может быть сдвинут (то есть нет перехода для этого состояния с этим входным символом), то анализ завершился неудачно, и алгоритм завершился.
Если, с другой стороны, сдвиговый переход приводит к указанному состоянию Принять, то анализ завершается успешно, и алгоритм завершается.
Все, что это означает, - то, что прогноз используется, чтобы предсказать, какое, если таковое имеется, сокращение должно применяться. В синтаксическом анализаторе LR(0) решение о смещении (точнее, о попытке смещения) должно приниматься до чтения следующего входного токена, но вычисление состояния для перехода выполняется после чтения токена, при котором указать, что это будет сигнализировать об ошибке, если смещение невозможно.
ПарсерыLL(k) должны предсказать, какой продукт заменит нетерминал, как только они увидят нетерминал. Основной алгоритм LL начинается со стека, содержащего [S, $] (сверху вниз), и до тех пор, пока не будет выполнено:
Если вершина стека не является терминальной, замените вершину стека одной из продукций для этого нетерминала, используя следующие k входных символов, чтобы решить, какой из них (не перемещая курсор ввода), и продолжайте.
Если вершина стека является терминалом, прочитайте следующий входной токен. Если это тот же терминал, вытолкните стек и продолжайте. В противном случае, анализ не пройден, и алгоритм завершается.
Если стек пуст, анализ выполнен успешно, и алгоритм завершает работу. (Мы предполагаем, что в конце ввода есть уникальный EOF-маркер $.)
В обоих случаях предвидение имеет одинаковое значение: оно состоит из просмотра входных токенов без перемещения курсора ввода.
Если k равно 0, то:
Синтаксический анализатор LR(k) должен решить, следует ли уменьшить, не изучая входные данные, что означает, что ни в одном состоянии не может быть двух разных действий уменьшения или действия уменьшения и сдвига.
Синтаксический анализатор LL(k) должен решить, какое производство данного нетерминала применимо, без изучения входных данных. На практике это означает, что каждый нетерминал может иметь только одну продукцию, что означает, что язык должен быть конечным.