编译原理 实验三 LR(1)分析法 Java
1. 实验目的
构造 LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解 LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。
2. 实验内容
对下列文法，用 LR（1）分析法对任意输入的符号串进行分析：
（1）E-> E+T
（2）E->T
（3）T-> T*F
（4）T->F
（5）F-> (E)
（6）F-> i
3. LR(1)分析法设计思想及算法
本LR(1)分析器能够实现完整的LR(1)分析，在GUI界面中显示读取的当前文法、分析得到的First集、所有的项目集规范族、规范LR分析表以及分析过程步骤表。首先通过GUI中的“打开文件”按钮读取文法文件，“显示文法”按钮将文法显示在GUI上，并将文法保存在相应的数据结构中，最后一键“开始LR(1)分析”按钮自动执行相应，完成分析。本分析器分析过程如下：
- 根据文法第一个识别到的非终结符（视为开始符号，假设为 S），增加产生式项目“S’->·S，#”;
- 利用“S’->·S，#”为I0，求Closure(I0)，获得I0；
- 利用Closure(I0)，计算I0 中所有非终结符的展望符，遍历所有的X（X指所有I0中“·”后的文法符号）,利用GOTO（I0，X），产生新的状态集Ix；随后计算新产生的状态
- 遍历每一个 Ix，利用 GOTO（Ix，X），并计算非终结符的展望符，完成完整的 LR（1）项目集族构建；
- 根据完整的LR（1）项目集族，构建项目分析表；
- 获取分析表后，启动分析程序，结合分析表对读入的输入串进行语句分析，并以表格的形式将分析表、分析过程显示到GUI相应位置；
图1 LR分析器结构
图2 LR(1)算 法流程图
3.1 主程序设计基本思路
1.LR(1)分析法的主要思想
- 进行最左归约（识别句柄并归约它）
- 将识别句柄的过程划分为由若干状态控制,每个状态控制识别出句柄的一个符号
- 分析栈:存放已识别的文法符号和状态,描述分析过程中的历史和展望信息
- 由一个总控程序来控制整个识别过程
2.LR(1)分析法的构造方法
(1) 构造LR(1)项目集I的闭包函数 CLOSURE(I)
a)I的任何项目都属于 CLOSURE(I)；
b) 若项目(A•B,a)属于CLOSURE(I)，B是一个产生式，则对于F IRST(a)中的每个终结符b，如果(B•,b)原来不在CLOSURE(I)中，则把它加进去；
c) 重复步骤 b)直到CLOSURE(I)不再扩大为止。
(2) 构造GO函数
令I是一个LR(1)项目集，X是一个文法符号，函数GO(I,X)定义为： GOTO(I,X)=CLOSURE(J)，其中J={(AX•,a)|(A•X,a)I}。(在执行GOTO时,搜索符并不改变)
(3) 构造项目集族(伪代码表示)
{ C={CLOSURE({(S’• S,#)})};
DO{FOR C 中的每个项目集I和每个文法符号X
IF GO(I,X) 非空且不属于 C
把 GO(I,X) 加入 C 中；
}WHILE C 依然扩大；
}
(4) LR(1)分析表的构造
假定LR(1)项目集规范族C={I0, I1, …… ，In}，令每个项目集Ik的下标 k为分析器的一个状态，G’的LR(1)分析表含有状态0，1，…… ，n。
令那个含有项目[S’→·S，#]的Ik的下标k为状态0（初态），ACTION 表和GOTO表可按如下方法构造：
- 若项目[A→α·,b]属于Ik，那么置ACTION[k,b]为“用产生式 A →α进行规约”，简记为rj(假定A→α为文法G’的第j个产生式)。
- 若项目[A→α·aβ，b]属于Ik且GO(Ik, a)= Ij,则置ACTION[k,a]为 “把状态j和符号a移进栈”，简记为 sj 。
- 若项目[S’→S·,#]属于Ik,则置ACTION[k, #]为“接受”，简记为 acc。
- 若GOTO(Ik, A)= Ij，A为非终结符，则置 GOTO(k, A)=j，分析表中凡不能用规则1至5填入信息的空白格均置上“出错标志 ”(空)。
按上述算法构造的含有ACTION和GOTO两部分的分析表，如果每个入口不含多重定义，则称它为文法G的一张规范的LR(1)分析表。
3.2 主要变量和函数定义
使用Eclipse的UML插件AmaterasUML直接列出相关变量以及函数如下：
下面对部分关键函数进行说明：
public void Get_First() // 求出单个非终结符FIRST集合函数
// 寻找First集合元素的子过程(对产生式右部的所有符号)
public void KeFind_First(char s[], int j, int i)
public void First_Finally()//优化当前求得的first集合(去掉重复符号)
public String Get_First_String(String str)//求字符串的First集
//返回最小为空的下标函数(针对二维数组)
public int index_Null(String temp[][], int m)
//求解项目集函数
public String Get_Projects(String temp, char c)
//获得该产生式FIRST集(展望)函数(针对二维数组)
public String Get_RightFir(String temp[][], int a, int b)
//获得该产生式FIRST集(展望)函数(针对一维数组)
public String Get_RightFir(String str[], int i)
//求解CLOSURE函数
public void CLOSURE(int a) public void CLOSURE1(String str[])
//截取到小圆点后一位符号的字符串函数
public String Get_Behind(String temp[][], int i)
//求新的项目集
public String[] Get_New(String temp[][], int i, char X)
public int GOTO(int a, char X) //构建GOTO函数
public void main_CloGo() //求解CLOSURE和GOTO的主函数
public void Get_Action() //构建action表函数
3.3 关键数据结构
private char VN[] = new char[999]; //定义终结符数组
private char VT[] = new char[999]; //定义非终结符数组
private char Total[] = new char[999]; //终结符+非终结符集合
private String temp_Str[] = new String[999]; //临时字符串数组(用来临时存放文法产生式等等)
private String[] First = new String[VN.length]; //单个非终结符的first集
private String Projects[][] = new String[999][999]; //项目集合
private String ACtion[][] = new String[999][VT.length]; //存放ACtion的数组
private int temp_Goto[][] = new int[999][999]; //临时存放GOTO表，便于操作
private int Goto[][] = new int[999][Total.length]; //存放GOTO表
private int Flag = 6666; // 一个判断字符是否属于某个数组的判断标志
private boolean Visited[] = new boolean[999]; //定义布尔型访问数组
3.4 源程序关键代码(Java实现)
(完整源程序位于见 LR1.java )
//求解项目集函数
public String Get_Projects(String temp, char c) {
StringBuilder strBuf = new StringBuilder(); //实例化一个StringBuilder对象，便于对字符串进行操作
int j;
for(j = 0; j < 3; j++) {
strBuf.append(temp.charAt(j)); //产生式左部和箭头添加进strBuf中
}
strBuf.append('·'); //给产生式右部添加小圆点
//跳过产生式左部及箭头，对右部进行遍历
for(j = 3; j < temp.length(); j++) {
strBuf.append(temp.charAt(j)); //产生式右部符号添加进strBuf中去
}
strBuf.append(','); //逗号隔开项目与展望
strBuf.append(c); //添加上该项目的展望
return strBuf.toString(); //返回该项目字符串
}
//获得该产生式FIRST集(展望)函数(针对二维数组)
public String Get_RightFir(String temp[][], int a, int b) {
int j = 3; //从产生式右部开始
StringBuilder strB = new StringBuilder(); //实例化StringBuilder对象
//跳过小圆点
while(temp[a][b].charAt(j) != '·' && j < temp[a][b].length()) {
j++;
}
j++; //加1，j指向小圆点后的第一个字符
//如果下一个字符是非终极符的话
if(IsInVn(temp[a][b].charAt(j)) != Flag && j < temp[a][b].length()) {
j++; //看该字符的下一个字符(因为要求该字符的First集)
//循环遍历
while(temp[a][b].charAt(j) != ',' && j < temp[a][b].length()) {
strB.append(temp[a][b].charAt(j));
j++;
}
j++; //跳过逗号
strB.append(temp[a][b].charAt(j)); //加入展望
} else {
if(temp[a][b].charAt(j) == ',') {//下一个字符是逗号的话
j++; //指向展望下标
strB.append(temp[a][b].charAt(j)); //添加
}
}
return Get_First_String(strB.toString()); //返回
}
//获得该产生式FIRST集(展望)函数(针对一维数组)
public String Get_RightFir(String str[], int i) {
int j = 3; //老样子，跳过产生式左部和箭头符号从产生式右部开始
StringBuilder strB = new StringBuilder(); //实例化StringBuilder对象
//遍历循环，最终实现j指向当前项目的小圆点位置
while(str[i].charAt(j) != '·' && j < str[i].length()) {
j++;
}
j++;
j++;
while(str[i].charAt(j) != ',' && j < str[i].length()) {
strB.append(str[i].charAt(j));
j++;
}
j++;
strB.append(str[i].charAt(j));
return Get_First_String(strB.toString());
}
//求解CLOSURE函数
public void CLOSURE(int a) {//a为对应CLOSURE闭包序号
int i;
int j, k, m;
int h = 0;
/*
* Projects二维数组中的项目格式形如 :S->A·Bb,展望
*/
for(i = 0; i < Projects[a].length; i++) {
//如果当前对应项目的数组不为空的话
if(Projects[a][i] != null) {
j = 3; //跳过产生式左部和箭头符号
while(Projects[a][i].charAt(j) != '·' && j < Projects[a][i].length()) {
//循环遍历使j指向项目中小圆点的位置
j++;
}
j++; //指向小圆点的下一个符号
if(IsInVn(Projects[a][i].charAt(j)) != Flag) {//如果该符号是非终极符的话
for(k = 0; k < temp_Str.length; k++) {//遍历文法中所有产生式
if(temp_Str[k] != null) {//如果当前产生式不为空的话
if(temp_Str[k].charAt(0) == Projects[a][i].charAt(j)) {//如果当前文法的某个产生式左部
String temp = Get_RightFir(Projects, a, i);
for(m = 0; m < temp.length(); m++) {
if(IsInI(Get_Projects(temp_Str[k], temp.charAt(m)), Projects, a) == false) {
h = index_Null(Projects, a); //定位到
Projects[a][h] = Get_Projects(temp_Str[k], temp.charAt(m));
}
}
}
}
}
}
}
}
}
//求解CLOSURE函数(针对字符串)
public void CLOSURE1(String str[]) {
int i;
int j, k, m;
int h = 0;
//同样，str字符串格式形如：S->A·Bb,展望
for(i = 0; i < str.length; i++) {
if(str[i] != null) {//如果字符串非空
j = 3; //j指向项目左部
while(str[i].charAt(j) != '·' && j < str[i].length()) {//遍历循环，直至j指向小圆点
j++;
}
j++; //指向小圆点的后一位符号
//下面参照教材P115，使用求解LR(1)闭包的步骤进行求解
if(j < str[i].length()) {
if(IsInVn(str[i].charAt(j)) != Flag) {//当前j指向的符号是非终结符
for(k = 0; k < temp_Str.length; k++) {
if(temp_Str[k] != null) {//文法中k指向的产生式不为空的话
if(temp_Str[k].charAt(0) == str[i].charAt(j)) {//并且该产生式就是j指向的非终结符的话(步骤2)
String temp = Get_RightFir(str,i); //得到当前的First集合
for(m = 0; m < temp.length(); m++) {
if(IsInI(Get_Projects(temp_Str[k], temp.charAt(m)), str) == false) {
h = index_Null1(str);
str[h] = Get_Projects(temp_Str[k],temp.charAt(m));
}
}
}
}
}
}
}
}
}
}
//求新的项目集
public String[] Get_New(String temp[][], int i, char X) {
String tem[] = new String[999];
int j = 0, f = 0;
int k;
StringBuilder strB = new StringBuilder(); //实例化StringBuilder对象
while(j < temp[i].length) {//循环生成每个项目集的所有项目
if(temp[i][j] != null) {//如果当前项目不为空
k = 0;
while(temp[i][j].charAt(k) != '·' && k < temp[i][j].length()) {//循环遍历直到k指向小圆点
strB.append(temp[i][j].charAt(k)); //小圆点前的符号通通装进strB中
k++;
}
k++; //指向小圆点后一个符号
if(k < temp[i][j].length() && temp[i][j].charAt(k) == X) {
strB.append(temp[i][j].charAt(k)); //将该符号加入进strB中
strB.append('·'); //小圆点进入(相当于小圆点后移一位)
k++; //当前k指向小圆点
while(k < temp[i][j].length()) {//循环遍历，将原来后面的所有符号(包括展望)全部接在strB后面
strB.append(temp[i][j].charAt(k));
k++;
}
tem[f] = strB.toString(); //一个新的项目成功生成
f++; //加1，下一个
strB.replace(0, strB.length(), ""); //清空
} else {
strB.replace(0, strB.length(), ""); //清空
}
}
j++;
}
return tem;
}
3.5 效果图
3.6 完整代码