LR1分析法.docx
- 文档编号:10674524
- 上传时间:2023-05-27
- 格式:DOCX
- 页数:18
- 大小:278.67KB
LR1分析法.docx
《LR1分析法.docx》由会员分享,可在线阅读,更多相关《LR1分析法.docx(18页珍藏版)》请在冰点文库上搜索。
LR1分析法
课程:
编译原理
实验报告
系
专业
班级
姓名
学号
指导教师
学年学期
实验2.3LR
(1)分析法
1.实验目的
1.构造LR
(1)分析程序,利用它进行语法分析,判断给出的符号串是否为该文法识别的句子.
2.实验平台
Windows+VC+Win32Console
范例程序:
“4-LR1.c”
3.实验过程和指导
1.调试范例程序
范例程序目前还不能对所有输入串进行正确的分析.
输出格式如下:
步骤
状态栈
符号栈
输入串
Action
Goto
(1)请输出完整的分析过程。
即详细输出每一步骤状态栈和符号栈的变化情况.
(2)请输出最终的分析结果,即输入串“合法”或“非法”.
2.对一个新的文法实现LR
(1)分析。
4.程序代码
第一种文法
#include
#include
char*action[10][3]={"S3#","S4#",NULL,/*ACTION表*/
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#"};
intgoto1[10][2]={1,2,/*QOTO表*/
0,0,
0,5,
0,8,
0,0,
0,0,
0,9,
0,0,
0,0,
0,0};
charvt[3]={'a','b','#'};/*存放非终结符*/
charvn[2]={'S','B'};/*存放终结符*/
char*LR[4]={"E->S#","S->BB#","B->aB#","B->b#"};/*存放产生式*/
inta[10];
charb[10],c[10],c1;
inttop1,top2,top3,top,m,n;
voidmain(){
intg,h,i,j,k,l,p,y,z,count;
charx,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");
getchar();
}
测试一
(1)测试bb#
(2)测试abb#
(3)测试abbb#
第二种文发
#include
#include
usingnamespacestd;
stack
stack
charsen[50];
charsym[12][6]={//符号表
{'s','e','e','s','e','e'},
{'e','s','e','e','e','a'},
{'r','r','s','r','r','r'},
{'r','r','r','r','r','r'},
{'s','e','e','s','e','e'},
{'r','r','r','r','r','r'},
{'s','e','e','s','e','e'},
{'s','e','e','s','e','e'},
{'e','s','e','e','s','e'},
{'r','r','s','r','r','r'},
{'r','r','r','r','r','r'},
{'r','r','r','r','r','r'}
};
charsnum[12][6]={//数字表
{5,1,1,4,2,1},
{3,6,5,3,2,0},
{2,2,7,2,2,2},
{4,4,4,4,4,4},
{5,1,1,4,2,1},
{6,6,6,6,6,6},
{5,1,1,4,2,1},
{5,1,1,4,2,1},
{3,6,5,3,11,4},
{1,1,7,1,1,1},
{3,3,3,3,3,3},
{5,5,5,5,5,5}
};
intgo2[12][3]={//goto表
{1,2,3},
{0,0,0},
{0,0,0},
{0,0,0},
{8,2,3},
{0,0,0},
{0,9,3},
{0,0,10},
{0,0,0},
{0,0,0},
{0,0,0},
{0,0,0}
};
voidaction(inti,char*&a,char&how,int&num,char&A,int&b)//action函数[i,a]
{
intj;
switch(*a)
{
case'i':
j=0;break;
case'+':
j=1;break;
case'*':
j=2;break;
case'(':
j=3;break;
case')':
j=4;break;
case'#':
j=5;break;
default:
j=-1;break;
}
if(j!
=-1)
{
how=sym[i][j];
num=snum[i][j];
if(how=='r')
{
switch(num)
{
case1:
A='E',b=3;
cout<<"按E->E+T规约"< break; case2: A='E',b=1; cout<<"按E->T规约"< break; case3: A='T',b=3; cout<<"按T->T*F规约"< break; case4: A='T',b=1; cout<<"按T->F规约"< break; case5: A='F',b=3; cout<<"按F->(E)规约"< break; case6: A='F',b=1; cout<<"按F->id规约"< break; default: break; } } } } intgo(intt,charA)//goto[t,A] { switch(A) { case'E': returngo2[t][0];break; case'T': returngo2[t][1];break; case'F': returngo2[t][2];break; } } voiderror(inti,intj,char*&a)//error处理函数 { cout<<"error"< switch(j) { case1: //期望输入id或左括号,但是碰到+,*,或$,就假设已经输入id了,转到状态5 state.push(5); symbol.push('i');//必须有这个,如果假设输入id的话,符号栈里必须有.... cout<<"缺少运算对象id"< break; case2: //从输入中删除右括号 a++; cout<<"不配对的右括号"< break; case3: //期望碰到+,但是输入id或左括号,假设已经输入算符+,转到状态6 state.push(6); symbol.push('+'); cout<<"缺少运算符"< break; case4: //缺少右括号,假设已经输入右括号,转到状态11 state.push(11); symbol.push(')'); cout<<"缺少右括号"< break; case5: a++; cout<<"*号无效,应该输入+号! "< case6: a++; } } intmain() { ints; char*a; charhow; intnum; intb; charA; while (1) { cin>>sen; a=sen; state.push(0);//先输入0状态 while(*a! ='\0') { b=0;num=0;how='\0';A='\0'; s=state.top(); action(s,a,how,num,A,b); if(how=='s')//移进 { cout<<"移进"< symbol.push(*a); state.push(num); //if(*a=='i') //a++;//在这里忽略i后面的d a++; } elseif(how=='r')//规约 { for(inti=0;i { if(! state.empty()) state.pop(); if(! symbol.empty()) symbol.pop(); } intt=state.top(); symbol.push(A); state.push(go(t,A)); } elseif(how=='a')//接受 break; else { error(s,num,a);//错误处理 } } cout<<"成功接受"< } return0; } 文法二说明 1.使用如下文法: EE+T|T TT*F|F F(E)|id 2.对于任意给定的输入串(词法记号流)进行语法分析,采用LR分析器来完成。 手工构造LR分析表,利用移进-归约分析算法,输出对应的动作部分。 如: 输入: id*+id/(id+id)# 输出: 移进 按F->id归约 移进 error 3.有一定的错误处理功能。 即对错误能提示,并且能在一定程度上忽略尽量少的记号来进行接下来的分析。 例如: 从状态0开始的记号流为: bm 将b移进之后,栈里的情况应该为: 0b2 此时查表发现action[2,m]=error 输出打印: error 把A和状态1相继压入栈,用户指针后移到FOLLOW(A)对应的元素继续分析。 测试一 (1)测试i+(i*i)# (2)测试i+i# (3)测试i+# 5.实验心得 经过这个实验的练习,通过对程序的分析,让我进一步了解LR (1)算法的思想以及它的进一步程序实现,让我对它的了解从简单的理论上升到程序实现的级别,有理论上升到实际,让我更清楚它的用途。 6.实验体会及思考 在对实验的分析的时候,也遇到很多的问题,刚开始根本想不到用程序怎么实现这么繁杂的LR (1)文法,后来看了程序才知道,才转过来弯,通过对这个程序的分析与揣摩,让自己对这方面文法的实现有了一定的头绪,对以后的的一些文法的程序实现会有很大的帮助,通过练习我也感到理论仅留在理论是远远不行的,用通过一定方式实现才有实用价值。 学会了,合理利用网络资源! 7.文法中的缺陷 首先,文法一,只是利用例子文法,没有加入自己思想,文法二没有实现减法,和除法。 并且文法没有按照文法一那样输出,表现效果不如文法一好。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- LR1 分析