Как переписать грамматику без контекста, чтобы она была LR(1)?

Question

Для данной контекстной свободной грамматики:

S -> G $
G -> PG | P
P -> id : R
R -> id R | epsilon

Как мне переписать грамматику так, чтобы она была LR(1)?
У текущей грамматики есть конфликты сдвига / уменьшения при разборе ввода "id: .id", где "." является входным указателем для парсера.
Эта грамматика производит язык, удовлетворяющий регулярному выражению (id:(id)*)+

Answer 1

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

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

(id:id*)+

чтобы:

id(:id+)*:id*

который вызывает грамматику:

S  → id G $ 
G  → P G | P'
P' → : R'
P  → : R
R' → ε | id R'
R  → ε | id R

который является LALR(1).

По сути, мы просто сместили все произведения на один токен вправо, и есть общий алгоритм, который можно использовать для создания LR(1) грамматика из LR(k+1) грамматика для любого k≥1, (Версия этого алгоритма, которую я использую, взята из теории парсинга С. Сиппу и Э. Сойсалона-Сойнинена, том II, раздел 6.7.)

Нетерминалы новой грамматики будут иметь вид (x, V, y) где V является символом из исходной грамматики (терминальной или нетерминальной) и x а также y являются терминальными последовательностями максимальной длины k такой что:

y ∈ FOLLOWk(V)
x ∈ FIRSTk(Vy)

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

Нетерминал (x, V, y) будет генерировать x-производное строк, полученных из Vy из оригинальной грамматики. Неофициально вся грамматика сдвинута k жетоны справа; каждый нетерминал соответствует строке, в которой отсутствует первый k токены, но дополнены следующими k жетоны.

Продукция генерируется механически из оригинальной продукции. Сначала мы добавляем новый начальный символ, S' с производствами:

S' → x (x, S, ε)

для каждого x ∈ FIRSTk(S), Тогда для каждого производства

T → V0 V1 … Vm

мы генерируем множество производств:

(x0,T,xm+1) → (x0,V0,x1) (x1,V1,x2) … (xm,Vm,xm+1)

и для каждого терминала A мы генерируем множество производств

(Ax,A,xB) → B    if |x| = k
(Ax,A,x) → ε     if |x| ≤ k

Поскольку существует очевидный гомоморфизм между продукцией в новой грамматике и продукцией в старой грамматике, мы можем напрямую создать исходное дерево разбора, хотя нам нужно поиграть в некоторые приемы с семантическими значениями, чтобы правильно прикрепить их к синтаксическому анализу. дерево.