【编译原理】LR(1)分析法：C/C++实现
1. 编译原理之LR(1)分析法概念
1.1 编译原理
编译原理是计算机科学领域的一个重要分支，它研究如何将高级编程语言的源代码转化成计算机能够执行的机器代码或中间代码的过程。编译原理涵盖了编译器的设计和实现，其中编译器是一种将源代码翻译成目标代码的软件工具。编译器的主要任务包括语法分析、词法分析、语义分析、优化和代码生成等环节。
1.2 LR(1)分析法
LR(1)（Left-to-Right, Rightmost derivation with 1 symbol lookahead）分析法是一种用于构建分析器的语法分析方法，通常用于分析上下文无关文法的语法结构，属于LR分析法的一种变种。它是一种强大的自底向上语法分析方法，适用于具有一定复杂性的上下文无关文法，通过使用向前查看符号来处理文法中的二义性，使得可以更精确地分析和理解输入。
2. 逆波兰式的产生及计算
2.1 实验目的
（1）构造LR(1)分析程序，并进行语法分析，判断给出的符号串是否为该文法识别的句子；
（2）了解LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。
2.2 实验要求
1.对下列文法，用LR（1）分析法对任意输入的符号串进行分析：
（0）E->S （1）S->BB （2）B->aB （3）B->b
2.LR(1)分析表为：
(1)若输入
baba#
则输出为：
(2)若输入
bb#
则输出为：
2.3.1 算法流程图
2.3.2 参考程序代码
参考代码（不完整）：
/* ACTION表*/
char *action[10][3]={"S3#","S4#",NULL,
NULL,NULL,"acc",
"S6#","S7#",NULL,
"S3#","S4#",NULL,
"r3#","r3#",NULL,
NULL,NULL,"r1#",
"S6#","S7#",NULL,
NULL,NULL,"r3#",
"r2#","r2#",NULL,
NULL,NULL,"r2#"};
/* GOTO表*/
int goto1[10][2]={1,2,
0,0,
0,5,
0,8,
0,0,
0,0,
0,9,
0,0,
0,0,
0,0};
char vt[3]={'a','b','#'}; /*存放终结符*/
char vn[2]={'S','B'}; /*存放非终结符*/
char *LR[4]={"E->S#","S->BB#","B->aB#","B->b#"}; /*存放产生式*/
/*输出状态栈、输出符号栈、输出输入串*/
do{ y=z;m=0;n=0; /*y,z指向状态栈栈顶*/
g=top;j=0;k=0;
x=c[top];
count++; printf("%d\t",count);
while(m<=top1) /*输出状态栈*/
{printf("%d",a[m]); m=m+1; } printf("\t\t");
while(n<=top2) /*输出符号栈*/
{printf("%c",b[n]); n=n+1; } printf("\t\t");
while(g<=top3) /*输出输入串*/
{printf("%c",c[g]); g=g+1; } printf("\t\t");
……
}while(action[y][j]!="acc");
/*查动作表*/
if（x= ='a'）j=0；
if（x= ='b'）j=1；
if（x= ='#'）j=2；
if(action[y][j]==NULL)
{ printf("error\n"); return; }
else
strcpy(copy,action[y][j]);
/*处理移进*/
if(copy[0]=='S')
{ z=copy[1]-'0';
top1=top1+1; top2=top2+1; a[top1]=z; b[top2]=x; top=top+1; i=0; while(copy[i]!='#')
{printf("%c",copy[i]);i++;} printf("\n");
}
/*处理归约*/
if(copy[0]=='r')
{ i=0;
while(copy[i]!='#')
{ printf("%c",copy[i]); i++; }
h=copy[1]-'0';
strcpy(copy1,LR[h]);
if（copy1[0]= ='S'）k=0；
if（copy1[0]= ='B'）k=1；
l=strlen(LR[h])-4;
top1=top1-l+1; top2=top2-l+1; y=a[top1-1];
p=goto1[y][k]; a[top1]=p; b[top2]=copy1[0]; z=p;
printf("\t\t");
printf("%d\n",p);
}2.3 实验内容
2.3.1 实验解决代码
根据参考代码修改如下：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
/* ACTION表*/
char *action_table[10][3]={"S3","S4",NULL,
NULL,NULL,"acc",
"S6","S7",NULL,
"S3","S4",NULL,
"r3","r3",NULL,
NULL,NULL,"r1",
"S6","S7",NULL,
NULL,NULL,"r3",
"r2","r2",NULL,
NULL,NULL,"r2"};
/* GOTO表*/
int goto_table[10][2]={1,2,
0,0,
0,5,
0,8,
0,0,
0,0,
0,9,
0,0,
0,0,
0,0};
char vt[3]={'a','b','#'}; /*存放终结符*/
char vn[2]={'S','B'}; /*存放非终结符*/
struct Production{ //产生式类型定义
char alp; //大写字符
char array[10]; //产生式右边字符
int length; //字符个数
};
Production production[4]; //存放产生式
int statueStack[10]; //状态栈
char symbolStack[10]; //符号栈
char input_string[10]; //输入串
int statueStackPointer = -1; //状态栈的指针
int symbolStackPointer = -1; //符号栈的指针
int inputStringPointer = 0; //输入串的指针
int input_string_length = 0; //输入串的长度
int proce = 1;
bool input_judge();
void printAll();
void analyse();
void init();
int main(){
bool input_right = false;
while(!input_right){
input_right = input_judge();
}
init();
printf("步骤\t\t状态栈\t\t符号栈\t\t输入串\t\t");
printf("Action\t\t");
printf("Goto\n");
printAll();
analyse();
}
void printAll(){
printf("%d\t\t",proce++);
for(int i=0; i<=statueStackPointer;i++){ //输出状态栈
printf("%d",statueStack[i]);
}
printf("\t\t");
for(int i=0; i<=symbolStackPointer;i++){ /*输出符号栈*/
printf("%c",symbolStack[i]);
}
printf("\t\t");
for(int i=inputStringPointer; i<input_string_length;i++){ /*输出输入栈*/
printf("%c",input_string[i]);
}
printf("\t\t");
}
void analyse(){
int stop = 0;
while(!stop){
char store[10];
char input = input_string[inputStringPointer]; //获取输入串的第一个字符
int col = -1;
int row = statueStack[statueStackPointer];
/*查action表*/
if(input=='a'){
col=0;
}
if(input=='b'){
col=1;
}
if(input=='#'){
col=2;
}
if(action_table[row][col]==NULL){
printf("err\n");
exit(0);
}
else{
strcpy(store,action_table[row][col]);
}
if(strcmp(store,"acc")==0){
printf("acc\n");
stop = 1;
break;//结束
}
/*移进*/
else if(store[0]=='S'){
statueStack[++statueStackPointer]=store[1]-'0';
symbolStack[++symbolStackPointer]=input_string[inputStringPointer];
inputStringPointer+=1;
printf("%s\n",store);
printAll();
}
/*归约*/
else if(store[0]=='r'){
int col = -1;
int index=store[1]-'0';
if(production[index].alp=='S'){
col=0;
}
else if(production[index].alp=='B'){
col=1;
}
else{
printf("err");
exit(0);
}
int length = production[index].length; //表达式的字符长度
statueStackPointer-=length; //状态栈出栈
symbolStackPointer-=length; //符号栈出栈
int row = statueStack[statueStackPointer]; //获取状态栈在出栈操作后的栈顶状态
statueStack[++statueStackPointer]=goto_table[row][col]; //goto表中的状态进入状态栈
symbolStack[++symbolStackPointer]=production[index].alp; //表达式的左边的大写字母进入符号栈
printf("%s\t\t",store);
printf("%d\n",goto_table[row][col]);
printAll();
}
else{
printf("err!\n");
exit(0);
}
}
}
void init(){
struct Production a1,a2,a3,a4;
a1.alp = 'E';
strcpy(a1.array,"S");
a1.length = 1;
a2.alp = 'S';
a2.length = 2;
strcpy(a3.array,"BB");
a3.alp = 'B';
a3.length = 2;
strcpy(a3.array,"aB");
a4.alp = 'B';
a4.length = 1;
strcpy(a4.array,"b");
production[0] = a1;
production[1] = a2;
production[2] = a3;
production[3] = a4;
statueStack[++statueStackPointer] = 0; //0
symbolStack[++symbolStackPointer] = '#';//#
}
bool input_judge(){
int j=0;
char ch;
printf("Input：");
while(true){
ch = getchar();
if(ch=='\n'){
break;
}
input_string[j++] = ch;
}
for(int i=0; i<j; i++){
ch = input_string[i];
if(!((ch=='a')||(ch=='b'))){
printf("输入有误\n");
return false;
}
}
input_string[j++] = '#';
input_string_length = j;
return true;
}输入正确的输入串：
abab
运行结果：
输入错误的输入串：
abbaab
运行结果：
程序分析：
1.定义了ACTION表和GOTO表，用于LR分析器的移进和归约操作，ACTION表和GOTO表使用二维数组表示，每个元素对应一个状态和终结符（ACTION表）或非终结符（GOTO表），存储了相应的操作信息。 2.定义了一些变量和数据结构，包括产生式结构体struct Production、状态栈statueStack、符号栈symbolStack、输入串input_string等。这些数据结构和变量在分析过程中用于保存中间状态和结果。 3. printAll函数用于打印当前分析步骤的状态栈、符号栈和输入串等信息。在每一步分析完成后，调用该函数打印出当前的状态。 4. analyse函数是LR分析的核心部分。通过一个while循环来不断执行移进和归约操作，直到达到终止条件。在每一步中，根据输入字符在ACTION表中查找相应的操作，并执行相应的移进或归约操作。如果遇到错误情况，则会输出错误信息并退出程序。 5. init函数用于初始化LR分析器的状态栈和符号栈，并定义了文法的产生式。在该函数中，首先定义了四个产生式，并将它们存储在production数组中。然后将初始状态0压入状态栈，并将终结符#压入符号栈。 6. input_judge函数用于获取输入串，并进行输入合法性检查。在函数中，首先通过getchar函数逐个读取字符，并存储在input_string数组中。读取过程会检查字符的合法性，只允许包含终结符a和b，否则会输出错误信息并返回false。最后，将终结符#添加到输入串的末尾，并更新输入串的长度。 7.在main函数中，首先进行输入串的合法性判断，然后进行初始化，并调用printAll函数打印初始状态。接着调用analyse函数执行LR分析，并且使用while循环来确保输入的字符串合法，即调用input_judge函数判断输入串是否符合要求。只有当输入串合法时，才会进行后续的初始化和分析过程。
LR分析的关键函数analyse函数：
void analyse(){
int stop = 0;
while(!stop){
char store[10];
char input = input_string[inputStringPointer]; //获取输入串的第一个字符
int col = -1;
int row = statueStack[statueStackPointer];
/*查action表*/
if(input=='a'){
col=0;
}
if(input=='b'){
col=1;
}
if(input=='#'){
col=2;
}
if(action_table[row][col]==NULL){
printf("err\n");
exit(0);
}
else{
strcpy(store,action_table[row][col]);
}
if(strcmp(store,"acc")==0){
printf("acc\n");
stop = 1;
break;//结束
}
/*移进*/
else if(store[0]=='S'){
statueStack[++statueStackPointer]=store[1]-'0';
symbolStack[++symbolStackPointer]=input_string[inputStringPointer];
inputStringPointer+=1;
printf("%s\n",store);
printAll();
}
/*归约*/
else if(store[0]=='r'){
int col = -1;
int index=store[1]-'0';
if(production[index].alp=='S'){
col=0;
}
else if(production[index].alp=='B'){
col=1;
}
else{
printf("err");
exit(0);
}
int length = production[index].length; //表达式的字符长度
statueStackPointer-=length; //状态栈出栈
symbolStackPointer-=length; //符号栈出栈
int row = statueStack[statueStackPointer]; //获取状态栈在出栈操作后的栈顶状态
statueStack[++statueStackPointer]=goto_table[row][col]; //goto表中的状态进入状态栈
symbolStack[++symbolStackPointer]=production[index].alp; //表达式的左边的大写字母进入符号栈
printf("%s\t\t",store);
printf("%d\n",goto_table[row][col]);
printAll();
}
else{
printf("err!\n");
exit(0);
}
}
}2.3.2 程序解释
1.int stop = 0; 声明并初始化一个变量stop，用于控制分析过程的终止条件。 2.while(!stop) 是一个循环，只有当stop为假时才执行循环体内的代码，即进行分析操作。 3.char store[10]; 声明一个字符数组store，用于存储从ACTION表中查找到的操作。 4.char input = input_string[inputStringPointer]; 获取输入串的第一个字符，并将其赋值给变量input。input_string[inputStringPointer]用于从输入串中获取当前位置的字符。 5.int col = -1; 初始化变量col为-1，用于记录当前字符在ACTION表中的列号。 6.int row = statueStack[statueStackPointer]; 获取状态栈的栈顶元素，即当前状态。 7.根据input的值来确定col的值，判断当前字符是终结符a、b还是结束符#。根据不同的情况，将col的值设置为相应的列号。 8.if(action_table[row][col]==NULL) 判断ACTION表中对应位置是否为空。如果为空，表示没有对应的操作，输出错误信息并退出程序。 9.else 分支执行当找到对应的操作时。 10.strcmp(store, "acc") == 0 判断是否是接受状态，即完成语法分析，成功匹配输入串。如果是接受状态，输出"acc"，将stop设置为1，结束循环。 11.else if(store[0] == 'S') 判断是否是移进操作。如果是移进操作，执行以下操作：
- statueStack[++statueStackPointer] = store[1] - '0'; 将移进的状态压入状态栈。
- symbolStack[++symbolStackPointer] = input_string[inputStringPointer]; 将当前输入字符压入符号栈。
- inputStringPointer += 1; 将输入串指针向后移动一位。
- 输出移进操作的内容。
- 调用printAll函数打印当前分析步骤的状态。
12.else if(store[0] == 'r') 判断是否是归约操作。如果是归约操作，执行以下操作：
- int index = store[1] - '0'; 获取归约产生式的索引。
- 根据产生式的左部字符确定列号col。
- 获取归约产生式的长度length。
- 状态栈和符号栈出栈，出栈的个数为产生式的长度。
- 获取状态栈在出栈操作后的栈顶状态row。
- 将`goto_table[row][col]赋值给状态栈，表示归约后的新状态。
- 将产生式的左部字符压入符号栈。
- 输出归约操作的内容。
- 输出goto_table[row][col]，即归约后的状态。
- 调用printAll函数打印当前分析步骤的状态。
13.else 分支表示无法识别的操作，输出错误信息并退出程序。 14.在循环的下一次迭代中，会继续执行分析过程，直到达到接受状态或发生错误导致程序退出。
函数analyse实现了LR分析表中的移进-归约算法。通过查找ACTION表中的操作，根据输入字符和当前状态来执行相应的操作。移进操作将状态和输入字符压入栈中，归约操作根据产生式进行出栈操作，并将新状态和产生式左部字符压入栈中。这个过程会一直进行，直到接受状态或发生错误。函数中的打印语句和调用printAll函数用于展示每一步的状态变化和操作。
2. 实验心得
在实验的代码实现过程中，定义了ACTION表和GOTO表，这两个表是LR(1)分析表的核心部分，其中ACTION表用于记录移进和归约操作，GOTO表用于记录状态之间的转移。这些表提供了对输入串和状态栈的操作指导。接着定义了产生式结构体，并初始化了产生式数组、状态栈、符号栈和输入串等变量。这些变量在分析过程中起着关键的作用。
主要的分析过程在函数analyse()中实现。这个函数使用了循环来逐步分析输入串，直到达到接受状态或发生错误。在每一步中，根据输入字符和当前状态，在ACTION表中查找相应的操作。如果是移进操作，将状态和输入字符压入栈中，并打印当前步骤的状态。如果是归约操作，根据产生式进行出栈操作，并将新状态和产生式左部字符压入栈中，并打印当前步骤的状态。如果无法识别操作，则输出错误信息并退出程序。
通过这次实验，我实现了基于LR(1)分析法的代码，深入理解了LR(1)分析法的过程和原理：LR(1)分析法能够处理具有一定复杂性的上下文无关文法，通过构建分析表和状态栈的运算来对输入串进行逐步分析和归约，最终确定是否能够根据给定的文法产生输入串。
3.致各位
许我人间三百年，更兼风雪路八千
腾讯云开发者
