Как синтаксический анализ LR выбирает подходящую грамматическую продукцию (для построения дерева синтаксического анализа из листьев)?

Я читаю учебник по разбору LR. В учебнике используется пример грамматики здесь:

S -> aABe
A -> Abc | b
B -> d

Затем, чтобы проиллюстрировать, как работает алгоритм синтаксического анализа, в руководстве показан процесс синтаксического анализа слова abcde ниже.

введите здесь описание изображения

Я понимаю, что на каждом шаге алгоритма ищется уточняющая продукция (а именно правило грамматики, показанное в столбце 2 в таблице), чтобы соответствовать сегменту строки. Но как анализатор LR выбирает среди набора подходящих продуктов (показано в столбце 3 в таблице)?


parsing lr
person zell    schedule 22.08.2020    source источник
comment
По стечению обстоятельств я только что написал этот ответ. Возможно, это поможет и в этом вопросе.   -  person rici    schedule 24.08.2020

Ответы (1)


arrow_upward
1
arrow_downward

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

Конкретный механизм, с помощью которого синтаксические анализаторы LR на самом деле делают это, включает использование автомата синтаксического анализа, который отслеживает, где в грамматических порождениях происходит синтаксический анализ, а также некоторую предварительную информацию. Существует несколько разновидностей синтаксического анализатора LR (LR(0), SLR(1), LALR(1), LR(1) и т. д.), которые различаются структурой автомата и использованием упреждающей информации. Возможно, вам будет полезно поискать учебник о том, как работают эти автоматы, так как это суть того, как на самом деле работают парсеры LR.

person templatetypedef    schedule 23.08.2020