语法分析（三）自底向上parser

发表于 | 分类于

自底向上语法分析是一种反向最右推导的parse方法。LR的含义是

  • left to right scanning
  • reverse right-most derivation

1. 如何理解反向最右推导

考虑自顶向下的最右推导，从最右侧的第一个non-termianl向下推导，直到叶子，然后回溯，找到下一个最右侧的non-terminal继续推导。然而，如果我们反向自底向上的考虑，则就是从最左侧的叶子开始向上规约。

考虑到scanner自左向右给出token，自左规约也就正好符合了token给出的这种规律。因此称为反向最右推导。

2. 术语

2.1. Handle(句柄)

Def: a pair, <$A\to\beta$, k>, such that $\beta$ appears in the frontier with its right end at position k and replacing $\beta$ with A is the next step in the parse.

A handle of a right sentential form $\gamma$ (= $abc$) is a production rule $A\to b$ and a position of $\gamma$ where the string b may be found and replaced by A to produce the previous right-sentential form in a rightmost derivation of $\gamma$.

\[S*\to aAc \to abc\]

所以handle由一个产生式规则和一个对应的右句型的位置组成。通过该产生式在对应位置将字符串进行规约就可以得到上一个右句型。

2.2. Sentential Form(句型)

Def: any string derivable from the start symbol.

可能均为终结符也可能包含(全为)非终结符。

2.3. Right Sentential Form

Def: A right-sentential form is a sentential form that occurs in a step of rightmost derivation

2.4. Sentence

Def: A sentential form consisting only of terminals.

2.5. Configuration

Def: A configuration of a LR parsing is:

\[(S_0, X_1, S_1, ... S_m||a_i, a_{i+1},...,a_n$)\]

分开来看，左侧部分对应着分析栈，右侧部分对应着剩余的输入token。

整体上看LR parsing的配置对应着右句型。通过查表，$S_m$和$a_i$决定着下一步执行shift或者reduce操作。($S_m$即编码了当前状态)

  • shift操作：将下一个token压栈
  • reduce操作: 从栈顶弹出两个符号，并将规约符号A和对应的状态$S=goto[S_{old}, A]$压入栈。同时输出规约的产生式。如下，

reduce.png

3. LR parser的模板实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
push $;
push start state s0;
word = NextWord();
while (true) {
    state = top of stack;
    if Action[state, word] = "reduce A->β" {
        pop 2 x |β| symbols;
        // 状态回退
        state = top of stack;
        // 压入规约符号
        push A;
        // 下一个状态
        push Goto[state, A];
    }
    else if Action[state, word] = "shift si" {
        push word;
        push si;
        word = NextWord();
    }
    else if Action[state, word] = "acc" {
        break;
    }
    else error();
}

4. SLR(1)

4.1. 构造SLR(1)表

LR(0) item of a grammar G is a production of G with a dot at some position of the right side. 例如，$A\to.aBb$或者$A\to a.Bb$, $A\to aB.b$.

LR(0)items由一系列LR(0)集合构成，统称为标准LR(0)集合，每个集合对应parse过程中的一个状态。

4.1.1. closure操作

设I为某个LR(0)集合的初始状态。通过以下规则扩展该集合：

If $A\to a.Bb$ is in closure(I) and $B\to c$ is a production rule of G; then $B\to .c$ will be in the closure(I).

这一步意义在于构造等价的状态集合。

4.1.2. goto操作

设I为某个LR(0)集合经过closure操作后的状态，并且X为某个文法符号（可能是终结符也可能为非终结符）则goto(I, X)被定义为

If $A\to a.Xb$ is in I, then every item in closure({$A\to aX.b$}) will be in goto(I, X)

这一步意义在于描述状态转换的情况。

4.1.3. 标准LR(0)集合的构造方法如下

1
2
3
4
5
6
7
8
9
# 首先引入一条增强产生式：$S'\to S$
C is {closure({S' -> .S})};
repeat the followings until no more set of LR(0) items can be added to C {
    for each I in C and each grammar symbol X {
        if goto(I, X) is not empty and not in C {
            add goto(I, X) to C;
        }
    }
}

接着构造SLR parsing table

4.1.4. 建表

  1. 构造标准LR(0)集合
  2. 创建goto表
    • 对于所有非终结符A，若goto($I_i$, A)=$I_j$，则goto[i, A]=j
  3. 创建action表
    • 若a为终结符，且有goto($I_i$, a)=$I_j$，则action[i, a]为shift j
    • 若状态$I_i$含$A\to a.$，则对任意在follow(A)中的符号b，有action[i, b]为reduce A->a.
    • 若状态$I_i$含$S’\to S.$，则action[i, $]为accept
  4. 其它未定义的表项为error
  5. 初始状态设置为$S’\to .S$

5. LR(1)

SLR(1)中，当lookahead符号a位于Follow(A)且$A\to b.$位于当前状态中就可以进行规约操作。然而，某些情况下，当前分析栈中的前缀$\beta A$后接a并不构成右句型因而不能进行这样的规约。例如，

为了避免无效的规约，LR(1)items的状态中包含了更多信息。一个LR(1)item如下：

$A\to a.B, c$ where c is the look-ahead of the LR(1) item.(c is a terminal or end-marker)

增加该信息的目的是，当某个状态中存在($(A\to a, c)$)时，仅当look-ahead符号为c时，才能进行规约。其它情况和LR(0)相同。

5.1. 计算closure

if $A\to\alpha.B\beta,a$ in closure(I) and production $B\to\gamma$ is in G, then $B\to.\gamma, b$ will be in the closure(I) for each terminal b in First($\beta a$).

这里之所以使用First($\beta a$)的原因在于

  • LR(1) item第二部分仅在规约(reduce)时使用，即若只有在lookahead符号和第二部分相同时，才能进行规约
  • 因此该要求目的在于，从$A\to\alpha.B\beta,a$扩展到$B\to.\gamma, b$，需要保证后期$B$在规约成功时，lookahead符号为First($\beta a$)才能有$A\to\alpha B.\beta,a$

5.2. 计算goto

设I为某个LR(0)集合经过closure操作后的状态，并且X为某个文法符号（可能是终结符也可能为非终结符）则goto(I, X)被定义为

if $A\to \alpha.X\beta$ in I, then every item in closure({$A\to\alpha X.\beta, a$}) will be in goto(I, X)

5.3. 表生成

标准LR(1)集合初始集合为${closure({S’\to.S,$})}$，其余都和SLR算法相同。

注：当LR(1)item仅lookahead符号不同，产生式相同时，可以简写为$A\to a.b, c1/c2/c3…/cn$

对于表生成，goto表完全相同，action表的reduce操作需要根据look-ahead符号，而非根据Follow集合。

6. LALR(1)

LALR表示的是LookAhead LR.其目的是为了减少LR(1)中的状态数量。但是LALR分析能力强于SLR。

LALR的状态同样由LR(1)items组成。

6.1. the core of a set of LR(1) Items

定义LR(1)items集合的核心为所有item的第一部分(产生式部分)。LALR将具有相同核的LR(1)items集合合并为1个状态。例如：

1
2
3
4
I1: L->id.,=
I2: L->id.,$
合并后为
I12: L->id.,=/$

对标准LR(1)集合进行如上操作后，状态数核SLR状态数相同。

6.2. 建表

  1. 创建标准LR(1)集合
  2. 找到所有具有相同核的状态并合并
  3. 和LR(1)使用相同方法创建表

这种状态化简，可能会引入reduce/reduce冲突。但是不会引入shift/reduce冲突。

证：假设引入shift/reduce冲突。则LALR的某个状态为

$A\to\alpha., a$ 且$B\to\beta.a\gamma, b$

这意味着标准LR(1)集合的某个状态一定有(根据核相同)

$A\to\alpha., a$ 且$B\to\beta.a\gamma, c$

这说明LR(1)parser具有冲突。(本质在于：shift操作和lookahead符号无关，若此时有conflict，说明原本的LR(1)也有)

7. bottom-up parsing和top-down parsing的比较

  • The weakness of top-down LL(k) parsing techniques is that they must predict which production to use, having seen only the first k tokens in the right side.
  • bottom-up LR(k) parsing is able to postpone the decision until it has seen
    • input tokens corresponding to the entire right side of the production
    • and k lookahead tokens beyond

8. 自底向上语法分析的一些个人理解

对于自底向上语法分析，我的理解主要有三：

  1. 采用shift-reduce语法分析栈，shift操作对应状态转移，reduce操作对应找到handle同时状态回退
  2. 输入token流的各个前缀序列是一个regular language，即可以用DFA判断是否合法
  3. 为了避免每次reduce操作后需要重新跑一遍DFA，所以将经过的状态也压栈，reduce时出栈即相当于状态回退

分析能力LR(1) > LALR(1) > SLR(1)，但是SLR(1)的分析能力不一定比LL(1)强。