实现一个SLR（1）语法分析器，近期忙于他事，项目集和语法分析表暂时采用手动输入，有空再填坑，后附源码。
SLR是基于LR（0）实现的，故先进行LR（0）分析。
Tips:
龙书给的4.36算法伪代码写得过于简略，容易造成误导，本文给出具体算法和分析过程。
代码在
https://github.com/monimm/LLandLR
SLR（1）分析流程
- 输入文法
- 求first集
- 求follow集
- 构造LR（0）项目集
- 构造DFA
先上结果截图
自底向上分析
-
自底向上分析法，又称为
移进-归约
法。
目前流行的自底向上的语法分析器都基于LR（k）语法分析： L表示从左至右，R表示向左推导，k表示决定时向前看的符号个数 - LR分析是表格驱动的
对输入符号串自左向右进行扫描，并将输入符逐个移入一个先进后出栈中，边移进边分析，一旦栈顶符号串形成某个句型的可归约串时，就用相应产生式的左部非终结符代替此可归约串。重复这一过程，直到归约到栈中只剩下文法的开始符号时分析成功。
冲突
移进-归约冲突
即使知道了栈的所有内容以及接下来的k个输入符号，仍然无法判断应该进行移进还是归约操作
归约-归约冲突
无法在可能的多个归约方法中选择正确的归约动作。
LR(0)分析
增广文法
如果G是一个以S开始符号的文法，那么G的增广文法G’就是在G中加上新开始符号S’和产生式S’ → S而得到的文法。
目的是告诉分析器何时停止语法分析
LR(0)自动机
- 每一个项目集是有限状态自动机的一个状态
- 假设文法符号串γ使LR(0)自动机当前状态是j，那么如果下一个输入符号是a，且状态j有一个在a上的转换，就移进a，否则选择归约。
项目
文法G中的LR（0）项目由产生式和 · 组成
如产生式A→XYZ，产生四个项目
A→·XYZ A→X·YZ A→XY·Z A→XYZ·
产生式A→ε 生成一个项： A→·
项目集
- 各个项的集合
- 每个项集对应有限状态自动机的一个状态
项目集I的闭包：内核项集的闭包
- 将I中的各个项加入 closure(I)
- 若 A→α·Bβ在 closure(I)，且 B→γ是产生式，将 B→·γ添加到 closure(I) 中
通俗的理解是相当于一次
等价替换
项集族
- 各个项目集的集合
goto 函数
- goto [ I, X ]= closure (A→αX·β)，其中 A→α·Xβ在 I 中
- 定义文法的LR(0)自动机的状态转换，当前状态I，输入为X
- 通俗理解为，处理了X符号之后进入的状态
LR（0）分析过程
1.对产生式进行编号
2.构造规范的 LR(0)项目集族
- 见龙书图-4.33
3.构造LR(0)语法分析表
- Action函数.：有两个参数，状态i和终结符a或$
- Goto函数：goto函数的扩展，允许X可以为非终结符号
Action[i, a]结果
- 移进j，即把输入符号a移进栈，并进入j状态。记为sj。
- 归约A→β ：把栈顶的β归约为A。记为rk，k为A→β 的编号。
- 接受：acc
- 报错
Goto[i, X]结果
- 状态j
- X为终结符
4.执行语法分析程序
s为状态栈顶状态，a为待处理符号，将状态0入状态栈
执行循环{
如果查表为移进状态t，即st，
- 把t入状态栈
- a入符号栈
- 令a为下一个符号
如果查表为归约A→ β，即rt，t为状态
- 符号栈弹出| β |个状态
- 状态栈弹出| β |个状态
- goto返回的状态进状态栈
- 符号栈A进栈
}
源码：
public void analyzeLR() {
action = "";
index = 0;
stackState.push("0");
char a = strInput.charAt(index);
System.out.println("****************LR分析过程**********");
System.out.println(" State Symbol Input Action");
this.displayLR();
while (true) {
String s = stackState.peek();
// 查表为移进
if (Action(s, a).charAt(0) == 's') {
stackState.push(Action(s, a).substring(1));
stackSymbol.push(a);
a = strInput.charAt(++index);
action = "shift ";
displayLR();
}
// 查表为归约
else if (Action(s, a).charAt(0) == 'r') {
// 获取文法串
String str = LRGS[Integer.parseInt(Action(s, a).substring(1)) - 1];
int len = str.substring(3).length();
// 弹出右部长度的符号和状态
for (int i = 0; i < len; i++) {
stackSymbol.pop();
stackState.pop();
}
// goto的值进栈
String t = stackState.peek();
stackState.push(Action(t, str.charAt(0)));
stackSymbol.push(str.charAt(0));
action = "reduce:" + str;
displayLR();
} else if (Action(s, a) == "acc")
break;
else
return;
}
System.out.println("analyze LR successfully");
System.out.println("****************LR分析过程**********");
}
SLR（1）分析过程
1.构造SLR分析表
- 若 A→α·aβ属于Ii，且 goto [Ii，a]= Ij，则 action[i，a]= sj
- 若 Ii 包含 A→α· ，则action[i，x]= rj，x属于FOLLOW(A)，j为产生式 A→α的编号
- 若 Ii 包含 S’→S · ，则action[i，$]= acc
- 若 goto [Ii，A]= Ij，则 goto[i，A]= j
2.同LR(0)
SLR描述能力有限
- 存在移进/归约冲突