Не является парсером LR (0) с использованием lookaheads?

Question

LL (1) -парсер нуждается в символе lookahead для определения того, какую продукцию использовать. Именно по этой причине я всегда считал, что термин «lookahead» используется, когда парсер смотрит на следующий входной токен, не «потребляя» его (т. Е. Он все еще может быть прочитан с ввода следующим действием). Однако аналитики LR (0) не сомневались, что это правильно:

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

Я использовал бесплатный инструмент «ParsingEmu» для создания LR-таблицы и выполнения оценки LR ниже для слова «aab». Как видите, в заголовке столбца есть токены. Из оценки вы можете видеть, что синтаксический анализатор решает, какой столбец использовать, просматривая следующий токен ввода. Но когда парсер уменьшает шаги с 4 по 6, вход не изменяется (хотя парсеру необходимо знать следующий входной токен «$» при выполнении перехода к следующему состоянию).

Грамматика:

S -> A 
A -> aA 
A -> b 

Таблица:

Оценка:

Теперь я сделал следующие предположения по причине моего замешательства:

1. Мое предположение для определения «lookahead» (lookahead = входной токен, который не потребляется) неверен. Lookahead просто означает две разные вещи для LL-парсеров или LR-парсеров. Если да, то каким образом можно определить «lookahead»?

2. LR-синтаксические анализаторы имеют (с теоретической точки зрения, когда вы будете использовать push-down automaton) дополнительные внутренние состояния, в которых они потребляют входной токен, помещая его в стек и, следовательно, могут сделать shift-reduce - решение, просто глядя на стек.

3. Оценка, показанная выше, представляет собой LR (1). Если это так, будет выглядеть оценка LR (0)?

Теперь, что правильно, 1, 2 или 3 или что-то совсем другое?

Answer 1

Важно, чтобы быть точным:

LR (к) анализатор использует curent состояние анализатора и к символов LOOKAHEAD решить, следует ли уменьшить, и если да, то где производство ,

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

Если в заданном состоянии синтаксического анализа было возможно произвести как действие сдвига, так и уменьшения, тогда синтаксический анализатор имеет конфликт сдвига/уменьшения и недействителен. Следовательно, указанные выше два определения теоретически можно было бы сделать недетерминированно.

Если в заданном состоянии синтаксического анализа невозможно уменьшить уменьшение, а следующий входной символ не может быть сдвинут (то есть переход для этого состояния с этим входным символом отсутствует), тогда синтаксический анализ не завершился и алгоритм завершится.

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

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

---

LL (к) парсеры должны предсказать, производство которых заменить не-терминал с, как только они видят не-терминала. Основной алгоритм LL начинается с стека, содержащего [S, $] (сверху вниз) и делает какой из следующих действий применима пока не сделано:

• Если в верхней части стека не является -терминал, замените верхнюю часть стека на одну из производств для этого нетерминала, используя следующие входные символы k, чтобы решить, какой из них (без перемещения курсора ввода), и продолжить.

• Если верхняя часть стека является терминалом, прочитайте следующий токен ввода. Если это тот же терминал, поместите стек и продолжайте. В противном случае синтаксический анализ завершился неудачей, и алгоритм завершится.

• Если стек пуст, синтаксический анализ завершен и алгоритм завершается. (. Мы предполагаем, что существует единственный EOF габаритный $ в конце ввода)

---

В обоих случаях опережения имеет тот же смысл: оно состоит из глядя на входных лексем без перемещение курсора ввода.

Если к равен 0, то:

• LR (к) анализатор должен решить, следует ли или нет, чтобы уменьшить без рассмотрения ввода, что означает, что ни одно государство не может иметь либо два различные действия по снижению или уменьшение и сдвиг.

• LL (к) анализатор должен решить, какой производство данного не-терминала appicable без рассмотрения ввода. На практике это означает, что каждый нетерминал может иметь только одну постановку, а это означает, что язык должен быть конечным.

Answer 2

Анализатор LR (0), буквально LR (0), не использовал бы символ «вперед».
Парсер LR (0) полезен в некоторых случаях, таких как пользовательские интерфейсы, или языки LR (0).

Анализаторы SLR (1) и LALR (1) построены из конечного автомата LR (0). Наверное, поэтому их называют парсерами LR (0), но они являются не в буквальном смысле парсеров LR (0).