如何重写上下文无关语法以使其成为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）。

实际上，我们刚刚将所有的生产向右移动了一个标记，并且存在一个通用算法，可用于从任何k≥1的LR(k+1)语法创建LR(1)语法。 （该算法我使用的版本由S. Sippu & E. Soisalon-Soininen，第II卷，第6.7节来自解析理论。）

新语法的非终端将具有形式(x, V, y)其中V是从原来的语法y一个符号（或者一个终端或一非末端）和x和是最大长度的末端序列k使得：

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

（的y长度并因此x威力小于k如果输入的结尾包含在下面的集合中。有些人避免此问题通过添加k年底符号，但是我觉得这个版本是很简单。）

非终端(x, V, y)会产生从Vy从原来的语法派生字符串的x - 衍生物。非正式地说，整个语法都向右移动了k标记;每个非终端匹配缺少第一个k令牌的字符串，但会增加以下k令牌。

制作是从原始制作机械生成的。对于每x ∈ FIRSTk(S)

S' → x (x, S, ε) 

：首先，我们添加一个新的开始符号，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 

的由于存在明显的同态从新语法的产物到旧语法的产物，我们可以直接创建原始的语法树，尽管我们需要用sema来玩一些技巧为了正确地将它们附加到分析树中，需要使用正确的值。