实验二 语法分析程序设计与实现.doc

_实验二 语法分析程序设计与实现一、实验目的任选一种有代表性的语法分析方法，如算符优先法、递归下降法、LL(1)、SLR(1)、LR(1)等，通过设计、编制、调试实现一个典型的语法分析程序，对实验一所得扫描器提供的单词序列进行语法检查和结构分析，实现并进一步掌握常用的语法分析方法。二、基本实验内容与要求选择对各种常见高级程序设计语言都较为通用的语法结构算术表达式的一个简化子集作为分析对象，根据如下描述其语法结构的BNF定义G2，任选一种学过的语法分析方法，针对运算对象为无符号常数和变量的四则运算，设计并实现一个语法分析程序。G2： | + | - | * | / | ()若将语法范畴、和分别用E、T、F和i代表，则G2可写成：G2E：E T | E+T | E-T T F | T*F | T/F F i | (E)输入：由实验一输出的单词串，例如：UCON，PL，UCON，MU，ID 输出：若输入源程序中的符号串是给定文法的句子，则输出“RIGHT”，并且给出每一步分析过程；若不是句子，即输入串有错误，则输出“ERROR”，并且显示分析至此所得的中间结果，如分析栈、符号栈中的信息等，以及必要的出错说明信息。要求:1、确定语法分析程序的流程图，同时考虑相应的数据结构，编写一个语法分析源程序。2、将词法、语法分析合在一起构成一个完整的程序，并调试成功。3、 供测试的例子应包括符合语法规则的语句，及分析程序能判别的若干错例。对于所输入的字符串，不论对错，都应有明确的信息输出。三、问题分析及源程序LL1文法:改写文法为:E- TG e G +TG gT- FS tF- -TG g1G- g2S- *FS sT- /FS s1S- s2F- (E) fG- i f1分析表：i+-*/()#EeeGgg1g2g2TttSs2s2ss1s2s2Ff1fLL1源程序#include#include #include#includechar A30; /*分析栈*/char B30; /*剩余串*/char v120=i,+,-,*,/,(,),#; /*终结符*/char v220=E,G,T,S,F; /*非终结符*/ int j=0,b=0,top=0,l; /*L为输入串长度*/class type /*产生式类型定义*/public:char origin; /*大写字符*/char array5; /*产生式右边字符 */int length; /*字符个数*/;type e,t,g,g1,g2,s,s1,s2,f,f1; /*类对象*/type C1010; /*预测分析表*/void print() /*输出分析栈*/int a;for(a=0;a=top+1;a+)coutAa;couttt;void print1() /*输出剩余串*/int j;for(j=0;jb;j+) /*输出对齐符*/cout ;for(j=b;j=l;j+)coutBj;coutttt;void main()int m,n,k=0,flag=0,finish=0;char ch,x;type cha; /*用来接受Cmn*/*把文法产生式赋值结构体*/e.origin=E;strcpy(e.array,TG);e.length=2;t.origin=T;strcpy(t.array,FS);t.length=2;g.origin=G;strcpy(g.array,+TG);g.length=3;g1.origin=G;strcpy(g1.array,-TG);g1.length=3;g2.origin=G;g2.array0=;g2.length=1; s.origin=S;strcpy(s.array,*FS);s.length=3;s1.origin=S;strcpy(s1.array,/FS);s1.length=3;s2.origin=S;s2.array0=;s2.length=1;f.origin=F;strcpy(f.array,(E);f.length=3;f1.origin=F;f1.array0=i;f1.length=1;for(m=0;m=4;m+) /*初始化分析表*/for(n=0;n=7;n+)Cmn.origin=N; /*全部赋为空*/ /*填充分析表*/ C00=e;C05=e; C11=g;C12=g1;C16=g2;C17=g2; C20=t;C25=t; C31=s2;C32=s2;C33=s;C34=s1;C36=s2;C37=s2; C40=f1;C45=f; cout提示:本程序只能对由i,+,-,*,/,(,)构成的以#结束的字符串进行分析,n; coutch; if (ch!=i) &(ch!=+)&(ch!=-)&(ch!=*)&(ch!=/)&(ch!=()&(ch!=)&(ch!=#) cout输入串中有非法字符n; exit(1); /强制退出程序 Bj=ch; j+; while(ch!=#); l=j;/*分析串长度*/ ch=B0;/*当前分析字符*/ Atop=#; A+top=E;/*#,E进栈*/ cout步骤tt分析栈 tt剩余字符 tt所用产生式 n; do x=Atop-;/*x为当前栈顶字符*/ coutk+; couttt; for(j=0;j=7;j+)/*判断是否为终结符*/ if(x=v1j) flag=1; break; if(flag=1)/*如果是终结符*/ if(x=#) finish=1;/*结束标记*/ coutacc!endl;/*接受 */ getchar(); exit(1); /退出程序 /*if*/ if(x=ch) print(); print1(); cout匹配endl; ch=B+b;/*下一个输入字符*/ flag=0;/*恢复标记*/ else/*出错处理*/ print(); print1(); cout出错endl;/*输出出错终结符*/ exit(1); else/*非终结符处理*/ for(j=0;j=4;j+)if(x=v2j)m=j;/*行号*/break; for(j=0;j=7;j+)if(ch=v1j)n=j;/*列号*/break; cha=Cmn; if(cha.origin!=N)/*判断是否为空*/ print();print1();coutcha.origin; /*输出产生式*/for(j=0;jcha.length;j+) coutcha.arrayj;cout=0;j-) /*产生式逆序入栈*/A+top=cha.array