编译原理 笔记 2

自底向上语法分析

自底向上的思想是从要分析的终结符串开始，每一步规约都是将一个子串用一个产生式替换，直到达到开始符号或报错

基本改进方法

与自顶向下相似，直接分析的版本不确定性太高，因此需要进行限制

选择可规约串

对于一个句型，可规约串定义为该句型的短语

对于文法G=(VN,VT,P,S)G = (V_{N}, V_{T}, P, S)，设α,β,δ∈(VN∪VT)∗,w∈VT∗\alpha, \beta, \delta\in(V_{N}\cup V_{T})^{*}, w\in V_{T}^{*}：

  • 若S⇒∗αAδS\mathop{\Rightarrow}\limits^{*}\alpha A\delta且A⇒+βA\mathop{\Rightarrow}\limits^{+}\beta，则称β\beta是句型αβδ\alpha\beta\delta相对非终结符AA的短语
  • 若S⇒∗αAδS\mathop{\Rightarrow}\limits^{*}\alpha A\delta且A⇒βA\Rightarrow\beta，则称β\beta是句型αβδ\alpha\beta\delta相对非终结符AA的直接短语
  • 若S⇒rm∗αAwS\mathop{\Rightarrow}\limits_{rm}^{*}\alpha Aw且A⇒βA\Rightarrow\beta，则称β\beta是右句型αβw\alpha\beta w相对非终结符AA的句柄

短语可以理解为可以被规约的子串，直接短语就是可以通过一步就能规约到的子串，而句柄是所有直接短语中最靠左的一个（因为在句柄的定义中要求了最右推导，因此右边的直接短语已经被推导完了）

例如对于文法：

S→ABA→aAA→εB→bB→bB\begin{align*} S &\to AB \\ A &\to aA \\ A &\to \varepsilon \\ B &\to b \\ B &\to bB \end{align*}

则：

  • 句子aaabaaab的短语包括ε,a,aa,aaa,aaab,b\varepsilon, a, aa, aaa, aaab, b，直接短语包括ε,b\varepsilon, b，句柄为ε\varepsilon
  • 句型aaAbaaAb的短语包括aA,aaA,aaAb,baA, aaA, aaAb, b，直接短语包括aA,baA, b，句柄为aAaA

如果文法是二义的，则右句型的最右推导可能有多个，则句柄也可能会有多个

最右推导与最左规约
最右推导与最左规约

通常采用移进-规约分析

与自顶向下分析比较

  • 功能较强：规约的时候可以获取完整的串信息，而推导只能获得局部信息
  • 利于出错处理
  • 有成熟的自动化技术

移进-规约分析

有一个分析引擎和下推栈，分析引擎能完成的动作包括：

  • Reduce：按照确定的方式对栈顶短语进行规约
  • Shift：从输入序列移进一个单词到栈顶
  • Error：发现错误，进行处理或恢复
  • Accept：分析成功
移进-规约分析例子
移进-规约分析例子

上图中的步骤逆向过来就是一种最右推导，称之为规范推导

移进-规约冲突

到达一个既可移进又可规约的状态，例如文法：

S→if E then S ∣ if E then S else S\begin{align*} S &\to \text{if } E \text{ then } S \,|\, \text{if } E \text{ then } S \text { else } S \end{align*}

则对于串if E then if E then S else S\text{if } E \text{ then if } E \text{ then } S \text { else } S即可移进又可规约

规约-规约冲突

到达了一个状态，可能有多种短语可以用于规约，例如产生式：

A→aA ∣ aaAA \to aA \,|\, aaA

则对于aaabaaab时，对于栈中的aaAaaA，无法确定该用哪一个短语

表驱动方法

解决上面两个冲突的方法，即通过一张分析表来决定状态机的下一步行为，常见的表有LR分析中的LR分析表、算符优先分析中的算法优先分析表

LR分析

代表从左（L）到右扫描输入序列，产生最右（R）推导，是一种表驱动的移进-规约分析

LR分析表构造

主要是构造两张表ACTION表和GOTO表：

  • ACTION表：根据栈顶状态和当前输入符号来确定下一步动作
  • GOTO表：根据栈顶状态和规约用的非终结符决定下一个状态

每一个状态为一个set<pair>，每一个pair代表了在当前状态下，消耗的栈顶符号与去掉这个符号后下一步允许什么串进入，本质上是一个大型状态转移图

LR分析表对应的状态转移图实例
LR分析表对应的状态转移图实例

这张表具体的构造方法按照分析方法不同分别讨论

LR分析算法

1
2
3
4
5
6
7
8
9
10
11
12
13
if (ACTION[i, a] == sj) { // shift
    PUSH j; // push state j to stack
    READ w; // read one symbol in the input
}
else if (ACTION[i, a] == rj) { // reduce 
    // the j-th formula is A -> beta
    POP len(beta); // pop |beta| states from the tiop of stack
    PUSH GOTO[k, A]; // k is the current stack top
}
else if (ACTION[i, a] == acc) { // accept
    return;
}
else exit(1); // error

带符号栈的LR分析算法

除了状态栈之外，还有一个符号栈，存储的读入但是没有规约的符号，算法修改为：

1
2
3
4
5
6
7
8
9
10
11
12
13
if (ACTION[i, a] == sj) { // shift
    PUSH (j, a); // push state j and symbol a to stack
    READ w; // read one symbol in the input
}
else if (ACTION[i, a] == rj) { // reduce 
    // the j-th formula is A -> beta
    POP len(beta); // pop |beta| states from the tiop of stack
    PUSH (GOTO[k, A], A); // k is the current stack top
}
else if (ACTION[i, a] == acc) { // accept
    return;
}
else exit(1); // error

LR(0)分析

首先引入一些概念

对于文法G=(VN,VT,P,S)G = (V_{N}, V_{T}, P, S)，增加产生式S′→SS'\to S，其中S′∉VN∪VTS'\notin V_{N}\cup V_{T}，则得到增广文法G′=(VN,VT,P,S′)G' = (V_{N}, V_{T}, P, S')

对于文法G=(VN,VT,P,S)G = (V_{N}, V_{T}, P, S)，以及串α,β∈(VN∪VT)∗,w∈VT∗\alpha, \beta\in(V_{N}\cup V_{T})^{*}, w\in V_{T}^{*}，其中S⇒∗αβwS \Rightarrow^{*} \alpha\beta w，且β\beta为句柄，则αβ\alpha\beta任何前缀γ\gamma称为文法GG的活前缀

对于增广文法，原开始符号SS是G′G'的活前缀

LR(0) FSM

LR(0)分析的主要工具，是一个以VN∪VTV_{N}\cup V_{T}为字母表的DFA，可以通过增广后的文法直接构造

可以证明，GG的LR(0)FSM对应的语言是G′G'所有活前缀的集合

FSM的状态

LR(0) FSM的状态是一个特殊的LR(0)项集，一个LR(0)项是指在右端某一位置有圆点的产生式，圆点代表着已分析过的串与该产生式匹配的位置

项有如下分类：

  • 移进项：A→α.aβA\to \alpha .a\beta
  • 待约项：A→α.BβA\to \alpha .B\beta
  • 规约项：A→α.A\to \alpha .
  • 接收项：S′→S.S'\to S .

我们将LR(0) FSM的每一项定义为一个项集的闭包(CLOSURE)

1
2
3
4
5
6
7
8
9
def CLOSURE(I):
    J = I
    while (1):
        for (j, p) in zip(J, P): # P is all the generation formula
            if j.hasform("A -> α.Bβ") and p.hasform("B -> γ"):
                J.append("B -> .γ")
        if J.hasNotChanged():
            break
    return J

则其状态转移函数定义为：

GO(I,X)=CLOSURE(J)J={A→αX.β ∣ A→α.Xβ∈I}\begin{align*} GO(I, X) &= \text{CLOSURE}(J) \\ J &= \{A\to \alpha X.\beta \,|\, A\to \alpha.X\beta \in I \} \end{align*}

则构造状态集合的方法就是从{CLOSURE({S′→.S})}\{\text{CLOSURE}(\{S'\to .S\})\}开始，利用上述的状态转移函数逐步扩展状态集合

LR(0)FSM的构造举例
LR(0)FSM的构造举例

增广文法的每个活前缀都有唯一与之相对应的状态

LR(0)分析表的构造

令状态集合为C={I0,…,In}C = \{I_{0} ,\dots,I_{n}\}，则构造ACTION与GOTO表的方法为：

  • GOTO(k,A)=j⇔GO(Ik,A)=Ij\mathrm{GOTO}(k, A) = j \Leftrightarrow \mathrm{GO}(I_{k}, A) = I_{j}
  • ACTION(k,a)=sj⇔A→α.aβ∈Ik & GO(Ik,a)=Ij\mathrm{ACTION}(k, a) = sj \Leftrightarrow A\to\alpha.a\beta \in I_{k} \,\&\, \mathrm{GO}(I_{k}, a) = I_{j}
  • ACTION(k,a)=rj⇔A→α.∈Ik\mathrm{ACTION}(k, a) = rj \Leftrightarrow A\to\alpha.\in I_{k}
  • ACTION(k,#)=acc⇔S′→S.∈Ik\mathrm{ACTION}(k, \#) = acc \Leftrightarrow S'\to S. \in I_{k}

LR(0)文法

按照上述定义构造的分析表，如果各表项均没有多重定义，则称为LR(0)文法，等价于要求每个状态满足：

  • 不同时含有移进和规约项（不能有移进-规约冲突）
  • 不含有两个以上规约项（不能有规约-规约冲突）

一个非LR(0)文法的例子为：

E→E+T ∣ TT→T∗F ∣ FF→(E) ∣ v ∣ d\begin{align*} E &\to E + T \,|\, T \\ T &\to T * F \,|\, F \\ F &\to (E) \,|\, v \,|\, d \end{align*}

短语TT即存在移进-规约冲突

SLR(1)分析

由于LR(0)限制非常严格（要求看到栈顶状态就能决定动作），因此做一些条件的放松，常见的是允许向前查看一个符号成为LR(1)，首先来研究其简化版本SLR(1)

SLR(1)通过判断下一个输入符号是否属于要规约的非终结符的Follow集合，来解决移进-规约冲突和规约-规约冲突

  • 如果一个状态中规约项的非终结符的Follow集两两无交，则可以解决规约-规约冲突
  • 如果一个状态中所有规约项中要规约的非终结符的Follow集与所有要移进的符号集互不相交，则可以解决移进-规约冲突

SLR(1)分析表

其分析表的构造相对于LR(0)来说只用做简单的修改，也即在填充ACTION(k,a)=rj\mathrm{ACTION}(k, a) = rj时，需要保证a∈Follow(A)a\in \mathrm{Follow}(A)

按照上述定义构造的分析表，如果各表项均没有多重定义，则称为SLR(1)文法，等价于要求每个状态满足：

  • 对于任意两项A→α.A\to \alpha.与B→β.B\to \beta.，有Follow(A)∩Follow(B)=∅\mathrm{Follow}(A) \cap \mathrm{Follow}(B) = \emptyset
  • 对于任意两项A→α.aβA\to \alpha.a\beta与B→γ.B\to \gamma.，均有a∉Follow(B)a\notin \mathrm{Follow}(B)

一个非SLR(1)文法的例子为：

E→(L,E) ∣ FL→L,E ∣ EF→(F) ∣ d\begin{align*} E &\to (L,E) \,|\, F \\ L &\to L,E \,|\, E \\ F &\to (F) \,|\, d \end{align*}

短语(F)(F)会被错误的规约为(E)(E)

LR(1)分析

在SLR(1)的基础上进一步改进，将传统的项增加一个终结符，表示产生式右端完整匹配后所允许留在符号串中的下一个终结符，即项会形如：

A→α.β , aA\to \alpha.\beta\,,\,a

其中a∈VT∪{#}a\in V_{T}\cup\{\#\}

对于形如A→α. , aA\to \alpha.\,,\,a的项，只有当下一个输入为aa的时候才能进行规约

LR(1)FSM

LR(1)FSM的状态是LR(1)项集的闭包，闭包算法为：

1
2
3
4
5
6
7
8
9
def CLOSURE(I):
    J = I
    while (1):
        for (j, p) in zip(J, P):
            if j.hasform("[A -> α.Bβ, a]") and p.hasform("B -> γ"):
                J.append("[B -> .γ, b]") for b in First(βa)
        if J.hasNotChanged():
            break
    return J

初态定义为I0=CLOSURE({[S′→.S,#]})I_{0} = \mathrm{CLOSURE}(\{[S'\to .S, \#]\})

状态转移函数定义为：

GO(I,X)=CLOSURE(J)J={[A→αX.β , a] ∣ [A→α.Xβ , a]∈I}\begin{align*} GO(I, X) &= \text{CLOSURE}(J) \\ J &= \{[A\to \alpha X.\beta\,,\, a] \,|\, [A\to \alpha.X\beta \,,\, a] \in I \} \end{align*}

从初态开始利用上述转移函数扩展，可以得到项集规范族

在上述非SLR(1)的例子中，E→F.E\to F.所期待的下一个输入符号没有))，因此(F)(F)中的FF不会被规约为EE，而是会选择移进

LR(1) 分析表构造

  • GOTO(k,A)=j⇔GO(Ik,A)=Ij\mathrm{GOTO}(k, A) = j \Leftrightarrow \mathrm{GO}(I_{k}, A) = I_{j}
  • ACTION(k,a)=sj⇔[A→α.aβ , b]∈Ik & GO(Ik,a)=Ij\mathrm{ACTION}(k, a) = sj \Leftrightarrow [A\to\alpha.a\beta\,,\,b] \in I_{k} \,\&\, \mathrm{GO}(I_{k}, a) = I_{j}
  • ACTION(k,b)=rj⇔[A→α. , b]∈Ik\mathrm{ACTION}(k, b) = rj \Leftrightarrow [A\to\alpha.\,,\, b]\in I_{k}
  • ACTION(k,#)=acc⇔[S′→S. , #]∈Ik\mathrm{ACTION}(k, \#) = acc \Leftrightarrow [S'\to S.\,,\, \#] \in I_{k}

LR(1)文法

按上述算法构造的分析表若每项都无重复定义，则称为LR(1)文法，其FSM每一个状态都满足：

  • 对于任意两个项目[A→α.aβ , b][A\to \alpha.a\beta\,,\, b]与[B→γ.,c][B\to \gamma., c]，一定有a≠ca\neq c
  • 对于任意两个项目[A→α. , a][A\to \alpha.\,,\, a]与[B→β. , b][B\to \beta.\,,\, b]，一定有a≠ba\neq b

LR(k)文法

可以扩展到LR(k)文法，但是状态机的复杂度过高，无实际意义，并且可以证明LR(N+)\mathrm{LR}(\mathbb{N}^{+})都是等价的

LALR(1)分析

是一个LR(1)与SLR(1)的折中版本

将LR(1)的项的第一部分称为芯，如果LR(1)FSM的两个状态的芯构成的集合完全相同，那么我们称其为同芯的状态

将LR(1)FSM中的同芯状态合并，如果得到的新状态没有规约-规约冲突，则得到的新文法是LALR(1)文法

LALR(1)FSM

构造方法为brute-force方法：

  • 构造增广文法的LR(1)FSM状态集
  • 合并同芯状态
  • LALR(1)FSM状态的后继状态是其合并前所有同芯状态的后继状态的并

LALR(1)FSM状态数与LR(0)状态数相同，但是其能力强于SLR(1)

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。