实验三预测分析.doc

实验三：预测分析1.实验目的：掌握预测分析程序的分析、设计与实现的基本技术与一般方法。2.实验题目： 编写并上机调试完成识别由下列文法所定义的表达式的预测分析程序。EE+T | E-T | TTT*F | T/F |FF(E) | i 3.实验步骤分析消除左递归文法转化为： E-TEE- +T E|-TE| T-FT T-*FT|/FT|F-(E)|i矚慫润厲钐瘗睞枥庑赖賃軔朧。2，判断是否为LL(1)文法：(1)求First()，Follow(),Select()集First(E)=(,i Follow(E)=),# First(E)=+,-, Follow(E)=),# First(T)=(,i Follow(T)=+,-,),# First(T)=*,/, Follow(T)=+,-,),# First(F)=(,i Follow(F)=*,/,+,-,),# Select(E-TE)=(,i Select(E- +T E)=+ Select(E- -T E)=- Select(E-) =,),# Select(T-FT)=(,i Select(T-*FT)=*Select(T-/FT)=/ Select(T-)=,+,),# Select(F-(E)=( Select(F-i)=i由上可知，相同的左部产生式的Select集的交集为空，所以为LL(1)文法由Select集构造预测分析表i+-*/()#E-TE0-TE5E- +T E11- -TE12-T-FT20-FT25T-*FT33-/FT34-F-i40-(E)45(2) 设计算法流程框图：程序参考源码/*/*程序名称：LL(1)文法分析程序*/*程序用途：编译原理实验(三) */*编写日期：20XX年11月9日*/*实验题目：识别下列表达式*/*E-E+T|E-T|T*/*T-T*F|T/F|F*/*F-(E)|i*/*程序版本：1.0Final*/*程序作者：黄记瑶 B0226047*/*作者邮箱：*/*/*/* 程序相关说明*/*A=E B=T*/*0=E1=E 2=T 3=T 4=F*/*0=i 1=+ 2=- 3=* 4=/ 5=( 6=) 7=#*/*/#include stdio.h#include malloc.hstruct Lcharchar char_ch;struct Lchar *next;Lchar,*p,*h,*temp,*top,*base;char curchar;/存储当前待比较字符char curtocmp;/存储当前栈顶字符int right;/定义开关项int table58=1,0,0,0,0,1,0,0,0,1,1,0,0,0,1,1,1,0,0,0,0,1,0,0,0,1,1,1,1,0,1,1,1,0,0,0,0,1,0,0;/存储预测分析表，1为有产生式，0为没有int i,j;void push(char pchar)/入栈函数temp=malloc(sizeof(Lchar);temp-char_ch=pchar;temp-next=top;top=temp;void pop(void) /出栈函数curtocmp=top-char_ch;if(top-char_ch!=#)top=top-next;void doforpush(int t)/根据数组下标计算的值产生式入栈switch(t)case 0:push(A);push(T);break;case 5:push(A);push(T);break;case 11:push(A);push(T);push(+);break;case 12:push(A);push(T);push(-);break;case 20:push(B);push(F);break;case 25:push(B);push(F);break;case 33:push(B);push(F);push(*);break;case 34:push(B);push(F);push(/);break;case 40:push(i);break;case 45:push();push(E);push();void changchartoint()/根据curchar,curtocmp转为数字以判断是否有产生式聞創沟燴鐺險爱氇谴净祸測樅。switch(curtocmp)case A:i=1;break;case B:i=3;break;case E:i=0;break;case T:i=2;break;case F:i=4;switch(curchar)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;case ):j=6;break;case #:j=7;void dosome(void)/算法函数int t;for(;)pop();curchar=h-char_ch;printf(n%ct%cn,curchar,curtocmp);if(curtocmp=# & curchar=#)break;if(curtocmp=A|curtocmp=B|curtocmp=E|curtocmp=T|curtocmp=F)残骛楼諍锩瀨濟溆塹籟婭骒東。 /当前字符为非终结符if(curtocmp!=#)/当前比较字符不为#changchartoint();if(tableij)/有产生式t=10*i+j; /计算产生式在数组中的位置doforpush(t);continue;Else/没有产生式right=0; /出错break;else/当前比较字符为#if(curtocmp!=curchar)right=0; /出错break;elsebreak;/正确Else/当前字符为终结符if(curtocmp!=curchar)right=0;/出错break;elseh=h-next;/读取下一个字符continue;void main(void)char ch;right=1;/开关项为1base=malloc(sizeof(Lchar);/初始化堆栈base-next=NULL;base-char_ch=#;temp=malloc(sizeof(Lchar);temp-next=base;temp-char_ch=E;top=temp;/初始化堆栈h=malloc(sizeof(Lchar);h-next=NULL;p=h;do/初始化字符串ch=getch();putch(ch);if(ch=i|ch=+|ch=-|ch=*|ch=/|ch=(|ch=)|ch=#)/输入合法字符酽锕极額閉镇桧猪訣锥顧荭钯。temp=malloc(sizeof(Lchar);temp-next=NULL;temp-char_ch=ch;h-next=temp;h=h-next;Else/输入不合法字符temp=p-next;printf(nInput a wrong char!Input again:n);for(;) /打印当前字符串if (temp!=NULL)prin