编译原理报告二LR分析器.doc

(完整word版)编译原理报告二LR分析器
LR分析器
一、 目的和要求
通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析方法。
1、选择最有代表性的语法分析方法，如LL(1) 语法分析程序、算符优先分析程序和LR分析分析程序，并至少完成两个题目。
2、选择对各种常见程序语言都用的语法结构，如赋值语句（尤指表达式）作为分析对象，并且与所选语法分析方法要比较贴切。
⑴ 实验前的准备
按实验的目的和要求，编写语法分析程序，同时考虑相应的数据结构。
⑵ 调试
调试例子应包括符合语法规则的算术表达式，以及分析程序能够判别的若干错例。
⑶ 输出
对于所输入的算术表达式，不论对错，都应有明确的信息告诉外界。
⑷ 扩充
有余力的同学，可适当扩大分析对象。譬如：
① 算术表达式中变量名可以是一般标识符，还可含一般常数、数组元素、函数调用等等。
② 除算术表达式外，还可扩充分析布尔、字符、位等不同类型的各种表达式。③加强语法检查，尽量多和确切地指出各种错误。
⑸ 编写上机实习报告。
二、背景知识
※ 自下而上分析技术－LR(K)方法
LR(K)方法是一种自下而上的语法分析方法，是当前最广义的无回溯的“移进- 归约”方法。它根据栈中的符号串和向前查看的k(k³0)个输入符号，就能唯一确定分析器的动作是移进还是归约，以及用哪个产生式进行归约。
优点：文法适用范围广；识别效率高；查错能力强；可自动构造。
逻辑组成：总控程序＋LR分析表
LR分析器的结构：
一个LR分析器实际是一个带先进后出存储器（栈）的确定下推自动机，它由一个输入串、一个下推栈和一个带有分析表的总控程序组成。栈中存放着由“历史”和“展望”材料抽象而来的各种“状态”。任何时候，栈顶的状态都代表了整个的历史和已推测出的展望。为了有助于明确归约手续，我们把已归约出的文法符号串也同时放进栈里。LR分析器的每一动作都由栈顶状态和当前输入符号所唯一确定。

LR分析器模型图
分析器的任何一次移动都是根据栈顶状态Sm和当前输入符号ai，去查看ACTION表并执行ACTION（ Sm，ai）规定的动作，直至分析成功或失败。
LR分析表有两个部分：动作部分ACTION和状态转换部分GOTO。
ACTION[S,a]表明当前状态S面临输入符号a时应该采取的动作：
1、移入：将S,y的下一个状态S以及当前符号入栈。
2、归约：对栈顶的符号串按照某个规则进行归约。
3、接受：宣布输入符号串为一个句子。
4、报错：宣布输入符号串不是句子。
GOTO[S,U]表示当前状态S和非终结符号匹配的时候所转换到的下一个状态。
LR总控程序：

LR总控程序示意图
LR分析器的工作过程是由总控程序根据分析表，使得分析器构型从一种构型向另一种构型变化的过程。初始构型：（S0，a1a2…an $）， S0为分析器的初态，$为输入串的括号。
分析过程的每步结果可表示为：（S0X1S1…XmSm，aiai+1…an$）。
分析器的下一次动作是由栈顶状态Sm和当前输入符号ai所唯一确定的，即：执行ACTION[Sm，ai]规定的动作。经执行各种可能的动作后，分析器的构型可如下变化：
1、若ACTION(Sm，ai)=“移进S”，则分析器构型变为（S0X1S1…XmSmaiS，ai+1…an$）。
2、若ACTION(Sm，ai)=“归约A→β ”，则分析器构型变为（S0X1S1…Xm-rSm-rAS，aiai+1…an$）,其中S＝GOTO(Sm-r，A)，|β|=r 。
3、若ACTION(Sm，ai)=“接受”，则分析成功，正常停止。
4、若ACTION(Sm，ai)=“ERROR”，语法出错，进行出错处理。

LR分析表的构造：
LR(0)项目的定义：文法的每一个产生式的右部添加一个圆点（·），则构成文法的一个LR(0)项目。
设I是文法G的任一项目集，则定义和构造CLOSURE(I)的规则如下：
1、属于I的任何项目也属于CLOSURE(I)；
2、若A → α·Bβ 属于CLOSURE(I)，那么，对于任何关于B的产生式B→γ ,项目B→·γ 也属于CLOSURE(I)；
3、重复执行以上两步，直到CLOSURE(I)不再增大为止。
构成识别一个文法活前缀的DFA的项目集（状态）的全体称为这个文法的LR(0) 项目集规范族。构成过程如下：
1、文法拓广；
2、构造拓广文法的LR(0)项目集规范族
3、由初始项目出发，利用CLOSURE和goto函数；
4、将LR(0)项目集规范族中的每个项目集作为FA的状态，将goto函数作为状态转换函数，构造出的FA即为所求。
项目集I的闭包CLOSURE(I)：
设I是文法G的任一项目集，则定义和构造CLOSURE(I)的规则如下：
1、属于I的任何项目也属于CLOSURE(I)；
2、若A → α .Bβ 属于CLOSURE(I)，那么，对于任何关于B的产生式B→ γ ,项目B→ .γ 也属于CLOSURE(I)；
3、重复执行以上两步，直到CLOSURE(I)不再增大为止。
LR(0) 文法的判定：
如果文法G’的项目集规范族的每个项目集中不存在下述冲突项目：
1、移进项目和归约项目并存，
2、多个归约项目并存，
则称文法G’为LR(0)文法。只有对于LR(0)文法，才能构造它的LR(0)分析表。
构造LR(0)分析表的步骤如下：
1、若项目A→α.aβ∈ Ii且goto(Ii,a)=Ij,其中a为终结符，置ACTION[i,a]=“把状态j和符号a移进栈”，简记为“sj”;
2、若项目A→α.∈ Ii ,则对于任何输入符a或结束符$，置ACTION[i,a]=“用产生式 A→α进行归约”，简记为“rj”(假定A→α是文法G’的第j条产生式);
3、若项目S’→S.∈ Ii ,则置ACTION[i,$]=“接收”，简记为‘acc’；
4、若goto(I,A)=Ij,A 为非终结符，则置GOTO(i,A)=j
5、分析表中凡不能用规则1－ 4添入信息的元素均置上ERROR。
三、实验内容
要求：
给定分析对象的LR分析表和一个分析对象的句子，输出该句子分析的结果。

否
否
是
是
否
是
0，#分别入状态栈和符号栈
置ip指向w#的第一个符号
令s是状态栈栈顶，
a是ip所指向的符号
action[s，a]=Ss’
action[s,a]=reduce A->β

把a和s’分别推入符号栈和状态栈；使ip前进到下一个字符

分别从栈顶弹出|β|个符号，令s’是当前栈顶状态，把a和goto[s’,A]先后推入栈中，输出产生式A->β
Action[A,a]=accept
结束
出错处理

程序输入/输出示例：
对下列文法，用LR（1）分析法对任意输入的符号串进行分析：
（1）E->E+T
（2）E->E—T
（3）T->T*F
（4）T->T/F
（5）F->(E)
（6）F->i
输出的格式如下：
(1)输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串
(2)输出过程如下：

步骤
状态栈
符号栈
剩余输入串
动作
1
0
#
i+i*i#
移进

(3)输入符号串为非法符号串(或者为合法符号串)

备注：
(1)在“所用产生式”一列中如果对应有推导则写出所用产生式；如果为匹配终结符则写明匹配的终结符；如分析异常出错则写为“分析出错”；若成功结束则写为“分析成功”。
(2) 在此位置输入符号串为用户自行输入的符号串。
注意：
1.表达式中允许使用运算符（+-*/）、分割符（括号）、字符i，结束符#；
2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）；
3.对学有余力的同学，测试用的表达式事先放在文本文件中，一行存放一个表达式，同时以分号分割。同时将预期的输出结果写在另一个文本文件中，以便和输出进行对照；
四、设计思路
模块结构：
（1）定义部分：定义常量、变量、数据结构。
（2）初始化：设立LR(1)分析表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）；
（3）控制部分：从键盘输入一个表达式符号串；
（4）利用LR(1)分析算法进行表达式处理：根据LR(1)分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示错误信息。
五、相关代码
 #include<stdio.h> 
#include<string.h>  
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#"}; 
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#"};/*存放产生式*/ 
 int a[10]; 
char b[10],c[10],c1; 
int top1,top2,top3,top,m,n;  
void main(){  int g,h,i,j,k,l,p,y,z,count;  
char x,copy[10],copy1[10];  
top1=0;top2=0;top3=0;top=0;  
a[0]=0;y=a[0];b[0]='#';  
count=0;z=0; 
 printf("请输入表达式\n"); 
 do{  
scanf("%c",&c1); 
  c[top3]=c1;   
top3=top3+1; 
 }while(c1!='#'); 
 printf("步骤\t状态栈\t\t符号栈\t\t输入串\t\tACTION\tGOTO\n");  
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(x!=vt[j]&&j<=2) j++;   
if(j==2&&x!=vt[j])
{     
printf("error\n"); 
      return;  
} 
 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]);  
while(copy1[0]!=vn[k]) k++; 
   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");    printf("%d\n",p); 
} 
 }
while(action[y][j]!="acc");
 printf("acc\n"); 
}
运行结果：

六、注意事项
1.表达式中允许使用运算符（+-*/）、分割符（括号）、字符I，结束符#；
2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）；
3.对学有余力的同学，可以详细的输出推导的过程，即详细列出每一步使用的产生式。