文章目录
4.10 LR(0) 分析算法
4.10.1 LL(I) 分析算法的评价
LL(1) 分析法：从左（L）向右读入程序，最左（L）推 导，采用一个（1）前看符号
- 优点：
- 算法运行高效
- 有现成工具可使用
- 缺点：
- 能分析的文法类型受限
- 往往需要文法的改写
4.10.2 自底向上分析算法
LR 分析算法（移进-归约算法）的特点：
- 算法运行高效
- 有现成的工具可用
- 是目前应该广泛的一类语法分析器的自动生成器中采用的算法
- 比 LL(1) 分析的文法范围广，不需要改写
（1）自底向上分析的基本思想
从叶子结点开始构建语法树，并使树向根的方向增长
在每一步：
- 在语法分析树的上边缘处识别出一个连续的子串
- 该子串与某个产生式的右侧匹配
- 构建一个结点表示该产生式的左侧，并将其连接到树中
（2）点记号
为了方便标记语法分析器已经读入了多少输入，我们可以引入一个点记号 •
加入点号的产生式叫做项目，若干项目构成项目集 。
（3）两个步骤
移进：取一个记号到栈顶上。
归约：栈顶上的 n 个符号（某产生式的右部）到左部的非终结符。
（4）核心的问题
如何确定移进和归约的时机？
4.10.3 算法思想
（1）引入新的开始符号 S’
引入一个符号 S’ → \rightarrow → S$，形成增广/拓广文法。有两个目的：
- 告诉语法分析器何时应该停止分析并宣称接受输入串，$（或#）相当于 EOF 等文件描述符，当且仅当要使用规则 S’ → \rightarrow → S$ 进行归约时，输入串被接受
- 保证开始符号不出现在右部
（2）构造 DFA
- 项 A → \rightarrow → • XYZ 表明我们希望接下来在输入中看到一个从 XYZ 推导得到的串。
- 项 A → \rightarrow → X • YZ 说明我们刚在输入中看到了一个可以由 X 推导得到的串，希望接下来看到一个能从 YZ 推导得到的串。
- 项 A → \rightarrow → XYZ • 表示我们已经看到了产生式体 XYZ，是时候把 XYZ 归约到 A 了。
观察：
- 状态中点号后面如果是非终结符，将非终结符开始的产生式也加入。
- 项目集中会有多个项目，会有多个转出，对应转移函数。
构造 DFA：
（3）分析过程演示
- 整个分析过程是沿着自动机先向前走，然后回溯，能到达接受状态，串就是合法的串。
- 自动机的构造：在每个项目集上看后继是什么，可以是读入的终结符和归约后的非终结符。
4.10.4 LR(0) 分析表
s：shift 移进
r：reduce 归约
g：goto 转移
s2：2 是状态编号，新状态写入栈
r2：2 是规则编号
g5：5 是状态编号，新状态写入栈
状态 1 读入 x：s2，即将 x 移进，转为状态 2。
r2 即把 y 弹出压入 T，因为状态的存在，实际弹出 2 倍个元素；压入非终结符后看转移
4.10.5 算法实现
（1）LR(0) 分析算法
stack = [];
push($); // $: end of file
push(1); // 1: initial state
token t = nextToken();
while (true) {
state s = stack[top];
if (ACTION[s, t] == “si”) { // "si" : 状态编号
push(t); push(i);
t = nextToken(); // 取下一个字符
}
else if (ACTION[s, t] == “rj”) { // "rj" : 文法编号
pop(the right hand of production “j: X -> β”);
s = stack[top]; // 更新当前状态
push(X); push(GOTO[s, X]);
}
else if (ACTION[s, t] == “accept”)
return success;
else error(...);
}
（2）LR(0) 分析表构造算法
C0 = closure(S1 -> • S$); // 初始 closure
set = {C0}; // 状态集
Q = enQueue(C0); // 队列，查看那些状态没有被计算
while (Q not empty) {
C = deQueue(Q);
foreach (x in (N ∪ T)) { // 终结符和非终结符的并集集合
D = goto(C, x); // 函数，见下文，每个可能的终结符和非终结符引出一条边
if (x in T)
ACTION[C, x] = D;
else GOTO[C, x] = D;
if (D not in set) {
set ∪= {D};
enQueue(D);
}
}
}
- 若状态包含点号在最后的项，对于任何终结符和 $ 都进行归约
- 特殊情况：包含 S’ → \rightarrow → S • 的状态，输入是 $ 时，设为 accept
（3）goto 和 closurre
goto(C, x) {
temp = {};
foreach (item i of C : A -> β · x γ)
temp ∪= {A -> β x · γ}; // 将向前走一步的项目加入，并求闭包
return closure(temp);
}
closure(C) {
while (C is still changing) {
foreach (item i of C : A -> β · B γ)
C ∪= {B -> ...};
}
}
4.11 SLR 分析算法
4.11.1 LR(0) 分析算法的评价
LR(0) 分析算法：从左（L）向右读入程序，最右（L）推 导，不用前看符号来决定产生式的选择（0 个前看符号）
- 优点：容易实现
- 缺点：
- 能分析的文法有限
- 延迟了发现错误的时机
- 包含冲突
（1）错误定位
对于下面 LR(0) 的例子，如果我们用其来分析句子 “xxyx$”：
-
“• xxyx$”，操作：初始化
t , s = 1 , 1 $ t, \qquad s=1, \qquad \begin{array}{|c|} \\ \hline 1\\ \hline \$\\ \hline \end{array} t,s=1,1$ -
“x • xyx$”，操作：s2
t = x , s = 2 , 2 x 1 $ t=x, \qquad s=2, \qquad \begin{array}{|c|} \\ \hline 2\\ \hline x\\ \hline 1\\ \hline \$\\ \hline \end{array} t=x,s=2,2x1$ -
“xx • yx$”，操作：s2
t = x , s = 2 , 2 x 2 x 1 $ t=x, \qquad s=2, \qquad \begin{array}{|c|} \\ \hline 2\\ \hline x\\ \hline 2\\ \hline x\\ \hline 1\\ \hline \$\\ \hline \end{array} t=x,s=2,2x2x1$ -
“xxy • x$”，操作：s3
t = y , s = 3 , 3 y 2 x 2 x 1 $ t=y, \qquad s=3, \qquad \begin{array}{|c|} \\ \hline 3\\ \hline y\\ \hline 2\\ \hline x\\ \hline 2\\ \hline x\\ \hline 1\\ \hline \$\\ \hline \end{array} t=y,s=3,3y2x2x1$ -
“xxSx •$”，操作：r2、g5
t = x , s = 5 , 5 S 2 x 2 x 1 $ t=x, \qquad s=5, \qquad \begin{array}{|c|} \\ \hline 5\\ \hline S\\ \hline 2\\ \hline x\\ \hline 2\\ \hline x\\ \hline 1\\ \hline \$\\ \hline \end{array} t=x,s=5,5S2x2x1$ -
“xSx • $”，操作：r2、g5
t = x , s = 5 , 5 S 2 x 1 $ t=x, \qquad s=5, \qquad \begin{array}{|c|} \\ \hline 5\\ \hline S\\ \hline 2\\ \hline x\\ \hline 1\\ \hline \$\\ \hline \end{array} t=x,s=5,5S2x1$ -
“Sx • $”，操作：r1、g4
t = x , s = 4 , 4 S 1 $ t=x, \qquad s=4, \qquad \begin{array}{|c|} \\ \hline 4\\ \hline S\\ \hline 1\\ \hline \$\\ \hline \end{array} t=x,s=4,4S1$ -
“Sx • $”，操作：null，因为表格中 ACTION[4, x] 没有对应的操作，因此返回失败。
从上面的步骤可以看出，我们一共进行了 8 步才判断出来 “xxyx$” 不匹配。事实上，在第 4 步时，我们就可以判断出该串不匹配。因为从文法可以看出，S 后面的跟随集 FOLLOW = {$}，而下面一个读取的字符 t = x，因此表便可以结束了。也就是说，表格 ACTION[3, y] 应该为空。
（2）冲突
4.11.2 SLR 与 LR(0)
SLR 和 LR(0) 分析算法基本步骤相同，仅区别于对归约的处理：
- 对于状态 i 上的项目 X → \rightarrow → α \alpha α •，仅对 y ∈ \in ∈ FOLLOW(X) 添加 ACTION[i, y] = rk（k 为规则编号）
更正上述的例子：