Слияние состояний LR для формирования наборов для анализа грамматики LALR

Если предположить, что у меня есть следующие состояния:

I1: S->TaV.,$

T -> V.,a

I2: T -> V.,a|$

я объединяю эти состояния?

По сути, я хочу знать, что является ядром I1. Является {S->TaV. , T->V.} ядро ​​I1 или я скажу, что I1 содержит два ядра - S->TaV & T->V?

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

Теперь, если {S->TaV. , T->V.} является ядром I1, то я не буду объединять наборы. Но для ядра T->V. и I1, и I2 содержат ядро ​​и, следовательно, должны быть заменены их объединением.

Так мне объединять наборы или нет?

некоторые справочные данные, которые могут быть полезны:

исходная грамматика для начала была

G: S->TaV | T

T->V | b

V->Ta | c


context-free-grammar lalr
person user3515684    schedule 09.04.2014    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Генератор парсеров LALR(1) не объединяет состояния буквально. Он проверяет, не было ли уже создано вновь созданное состояние. Он сравнивает новое состояние со всеми другими состояниями, сравнивая основные элементы. Если основные элементы идентичны (одинаковое количество элементов и одинаковые элементы), то вновь созданное состояние отбрасывается, и следует перейти к старому состоянию.

Генератор синтаксического анализатора LALR(1) строит конечный автомат LR(0) и не заботится о прогнозировании в процессе построения состояния. Все, о чем он заботится, это наборы предметов. Таким образом, ответ НЕТ, эти два состояния не следует объединять, потому что в I1 есть 2 основных элемента, а в I2 — 1 основной элемент.

Идея слияния состояний применима к построению минимального состояния LR(1), что является более сложным процессом, чем построение состояния LR(0).

Это проблема анализа грамматики LALR, а не разбора грамматики.

person Community    schedule 13.05.2014