#parsing #reduce #lr #bottom-up
#синтаксический анализ #уменьшить #lr #снизу вверх
Вопрос:
насколько я знаю (читал) о создании таблиц LR-Parsing, столбцы (= токен), в которых действие reduce записывается в ячейку для определенного состояния, зависят от терминалов, которые находятся в ПОСЛЕДУЮЩЕМ наборе уменьшенного символа.
Это правильно?*
Если это так, то следующий вопрос, который приходит мне в голову, таков: что определяет следующее состояние, в которое должен произойти переход после сокращения.
Например, в состоянии 5 r6 означает уменьшение символа, а затем переход в состояние 6 (и там, возможно, рассмотрим таблицу переходов, в какое состояние переходить дальше)
Состояния таблицы синтаксического анализа или DFA, которыми является LR-Parser, являются путями в графическом представлении. Как восходящий синтаксический анализатор, LR-Parser работает, находя путь обратно к исходному символу / принимающему состоянию. Таблица синтаксического анализа пытается найти каждый такой путь.
И мне кажется сложным последовательно выбирать правильные состояния сокращения.
Потому что это тесно зависит от состояний / наборов элементов, которые предшествовали текущему состоянию, а также от состояний, которые в совокупности следуют за текущим состоянием в зависимости от еще непрочитанных входных токенов.
По сравнению с reduce-actions, действия shift и goto кажутся простыми, поскольку они представляют собой всего лишь переходы, которые появляются при перемещении позиции точки.
Спасибо
PS: * Если это правильно, то не является ли «двойной проблемой» генерировать элементы LR1 с ПОСЛЕДУЮЩИМ набором в качестве дополнительной функции?
Комментарии:
1. Разве я еще не ответил на это? Состояние, используемое для перехода, — это состояние, которое отображается путем удаления правой части продукта из стека. (Стек — это именно то, как анализатор отслеживает историю синтаксического анализа.)
2. Используете ли вы стек значений? В примерах конфигурационных диаграмм используются только состояния в стеке, как в таблице синтаксического анализа. Две другие возможности: 1) Использование комбинации обоих. 2) Использование стека значений при создании таблицы синтаксического анализа. С уважением PS: Не могли бы вы ответить на вопрос в нашем чате?
3. Значения могут быть помещены в стек или параллельный стек, но это имеет мало общего с синтаксическим анализом. Мой комментарий касался состояний. Поскольку текущее состояние помещается в стек каждый раз, когда выполняется переход (с помощью сдвига или перехода), символ rhs естественным образом соответствует состоянию (состоянию непосредственно перед тем, как символ был сдвинут / goto’d). И это состояние появляется при уменьшении rhs.
4. Просто совпадение. Действие reduce сокращает производство 6 (F-> id), rhs которого имеет один символ. Таким образом, одно состояние извлекается из стека, и машина возвращается в состояние 0. Теперь он ищет F в таблице goto состояния 0 и следует этому переходу. Должно быть ясно, почему он возвращается в состояние 0. Он находился в состоянии 0, когда запускался в рабочей среде 6 (F) путем сдвига идентификатора. Когда он возвращается в состояние 0, он завершил F, поэтому теперь он может покинуть состояние с помощью действия goto вместо действия shift.
5. Хорошо, я сделаю ответ из некоторых из этих комментариев.