parsing - 如何重写上下文无关语法使其成为 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. （我使用的这个算法的版本来自S. Sippu 和 E. Soisalon-Soininen 的Parsing Theory，第二卷，第 6.7 节。）

新文法的非终结符将具有形式(x, V, y)where Vis a symbol from the original syntax（终结符或非终结符），x并且y是最大长度的终结序列，k使得：

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

（因此，如果输入的结尾包含在后续集合中，则yand的长度x可能会更短。有些人通过添加结束符号来避免这个问题，但我认为这个版本同样简单。）kk

非终结符(x, V, y)将生成x源自Vy原始语法的字符串的 -derivative。非正式地，整个语法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

由于新语法中的产生式与旧语法中的产生式之间存在明显的同态性，因此我们可以直接创建原始解析树，尽管我们需要对语义值进行一些技巧才能正确地将它们附加到解析中树。