编译原理课程设计语法分析器

1、福建农林大学计算机与信息学院计算机类课程设计报告课程名称：编译原理课程设计题目：语法分析器姓 名：系：专 业：年 级：2学 号：指导教师：职 称：20102011学年第一学期福建农林大学计算机与信息学院计算机类课程设计结果评定评语：成绩：指导教师签字：任务下达日期：评定日期：目 录1 正则表达式11.1 正则表达式11.2 确定化(化简)后的状态转换图11.3 分析程序代码11.4 程序运行截图11.5 小结22 ll(1)分析32.1 ll(1)文法32.2 ll(1)预测分析表32.3 分析程序代码32.4 程序运行截图52.5 小结63 算符优先分析73.1 算符优先文法73.2 算符优

2、先关系表73.3 分析程序代码73.4 程序运行截图103.5 小结104 lr分析114.1 lr文法114.2 lr分析表114.3 分析程序代码114.4 程序运行截图164.5 小结16参考文献：161 正则表达式1.1 正则表达式 (a|b)*(aa|bb)(a|b)* (注：该正规式为示例，可更改）1.2 确定化(化简)后的状态转换图 1.3 分析程序代码#includestdio.hvoid main()int s42=1,2,3,2,1,3,3,3;char c100;scanf(%s,c); int i=0; intk=0;int x;while(ci!=0)switch(c

3、i) case a: x=0;break; case b: x=1;break; default: x=-1;if(x0)break;k=skx;i+;if(k=3) printf(成功!n);else printf(出错了!n);1.4 程序运行截图输入abab出错输入abaaa1.5 小结通过本次实验熟悉了正则表达式程序实现方法和进一步熟悉了由正规式到dfa的转换2 ll(1)分析2.1 ll(1)文法 ete (注：该文法为示例，可更改） e+te| tft t*ft| f(e)|i2.2 ll(1)预测分析表i+*()#eeteeteee+teeettfttftttt*ftttffif

4、(e)2.3 分析程序代码#include#include#include #include using namespace std;char vn=e,e,t,t,f; char vt=i,+,*,(,),#; int lenvt=sizeof(vt);void showstack(stack st) int i,j; char ch100; j=st.size(); for(i=0;i=0;i-) coutchi; st.push(chi); int find(char c,char array,int n) int i; int flag=0; for(i=0;in;i+) if(c=a

5、rrayi) flag=1; return flag;int location(char c,char array) int i; for(i=0;c!=arrayi;i+); return i;void error() cout 出错!endl;void analyse(char vn,char vt,string m56,string str) int i,j,p,q,h,flag=1; char a,x; stack st; /定义堆栈 st.push(#); st.push(vn0); /#与识别符号入栈 j=0; h=1; a=strj; cout步骤 分析栈 剩余输入串 所用产生式

6、endl; while(flag=1) couth ; h+; showstack(st); cout ; for(i=j;istr.size();i+) coutstri; x=st.top(); if(find(x,vt,lenvt)=1) if(x=a) if (x!=#) cout x匹配endl; st.pop(); a=str+j; else cout 接受!endlendl; flag=0; elseerror();break;elsep=location(x,vn); q=location(a,vt); string s1(null),s2(null); if(mpq=s1 |

7、 mpq=s2) error();break; elsestring str0=mpq; cout xstr0=0;i-) st.push(str0i); main() string m56=te ,null,null,te, null,null, null,+te ,null,null,$, $,ft, null,null,ft, null,null,null,$, *ft, null,$, $,i, null,null,(e), null,null; /预测分析表 string str; int errflag,i; coute+t|t t-t*f|f f-(e)|iendl; cout请

8、输入分析串（以#结束）：str; for(i=0;istr.size();i+) if(!find(stri,vt,lenvt) cout输入串中包含有非终结符stri(输入错误)!endl; errflag=1; while(errflag=1); /判断输入串的合法性 analyse(vn, vt, m,str); return 0; 2.4 程序运行截图输入i+i#2.5 小结通过本次实验，巩固了关于文法分析的相关知识，进一步掌握ll(1)文法中first集和follow集的求法，以及ll(1)文法预测分析表的构造方法。3 算符优先分析3.1 算符优先文法 et | e+t | e-t

9、(注：该文法为示例，可更改） tf | t*f | t/f f(e) | i3.2 算符优先关系表+-*/()i#+-*/()i#3.3 分析程序代码#include #include using namespace std;typedef struct ochar char char_ch; struct ochar *next; opgchar;opgchar *temp,*top,*z;int i,j,m,n,e;string str;int push(char pchar) /压栈 temp=(opgchar*)malloc(sizeof(opgchar); temp-char_ch=

10、pchar; temp-next=top; top=temp; return 0; int pop() /弹栈 if(top-char_ch!=#) top=top-next; return 0; /* 预测分析表*/char table88 = /* o a n ( ) t f # */ , /o , /a , /n ,=,0,0,0,0, /) ,0,0,0,0, /t ,0,0,0,0, /f ,0,char_ch=#&strn=#)coutchar_ch)confirmij(strn); switch(t) case :push(strn);n+=1;cout:pop();cout归约

11、n; break; case =:pop();n+=1;coutchar_ch; z=z-next; h+; for(int i=h-1;i=0;i-)coutai; coutt;return 0;/* 显示剩余输入串 */ int showchuan() for(int i=n+1;i=str.length();i+) coutstri; couttt; return 0;int main(int argc,char *argv) int s=0;coutstr; for(int i=0;istr.length();i+) if(stri!=+&stri!=-&stri!=/&stri!=(

12、&stri!=)&stri!=*&stri!=i&stri!=#) coutn输入有误，请重新输入:endl; s=1; break; while(s); push(#); coutn步骤t符号栈t当前符号t剩余输入串t移进或归约endlendl; while(strn) cout+mt; zhan(); coutstrntt; showchuan(); yazhan(); if(e) coute+te-tt-t*ft-ff-(e)f-i4.2 lr分析表步骤状态栈符号栈输入串动作说明10#i+i*i#5压栈20 5#i+i*i#3入栈30 3#f+i*i#2入栈40 2#t+i*i#1入栈5

13、0 1#e+i*i#6压栈60 1 6#e+i*i#5压栈70 1 6 5#e+i*i#3入栈80 1 6 3#e+f*i#9入栈90 1 6 9#e+t*i#7压栈100 1 6 9 7#e+t*i#5压栈110 1 6 9 7 5#e+t*i#10入栈120 1 6 9 7 10#e+t*f#9入栈130 1 6 9#e+t#1入栈140 1#e#acc:分析成功4.3 分析程序代码#include #include #include #define max 15typedef struct /定义状态栈int datamax; int sttop; /top指针ststack;ststa

14、ck st; /产生一个状态栈sttypedef struct /定义字符栈char datamax; int chtop;chstack;chstack ch; /产生字符栈chvoid main()/界面及提示信息printf(tttlr(1)文法分析n);printf(n);printf(tt本程序的文法：n);printf(tt1.e-e+tn);printf(tt2.e-tn);printf(tt3.t-t*fn);printf(tt4.t-fn);printf(tt5.f-(e)n);printf(tt6.f-in);printf(n);/输入字符程序段char in20; /用i

15、n数组保存输入的字符串信息printf(请输入所要分析的式子:);scanf(%s,in);int loc; /loc表示数组in的位置loc=0;/默认为第一个字符i/定义action表int action126=5,-1,-1,4,-1,-1, -1,6,-1,-1,-1,200, -1,102,7,-1,102,102, -1,104,104,-1,104,104, 5,-1,-1,4,-1,-1, -1,106,106,-1,106,106, 5,-1,-1,4,-1,-1, 5,-1,-1,4,-1,-1, -1,6,-1,-1,11,-1, -1,101,7,-1,101,101,

16、 -1,103,103,-1,103,103, -1,105,105,-1,105,105;/定义goto表int goto123=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;/处理过程/1.置空状态栈与字符栈st.sttop=-1; /置空状态栈ch.chtop=-1; /置空字符栈/2.将0和#压入状态栈和字符栈int stfirst=0; /状态栈第一压入的字符char chfirst=#; /字符栈第一个压入的字符st.sttop+;st.datast.sttop

17、=stfirst; /把0压入状态栈ch.chtop+;ch.datach.chtop=chfirst; /把#压入字符栈 /3.求action所对应的值int a,b; /a,b表示action表的位置char deal; /deal表示待处理的字符while(1) a=st.datast.sttop; /取状态栈的栈顶，作为action表的行号 deal=inloc; /将待处理的字符传给deal switch(deal) /求出action表的对应列号 casei:b=0;break; case+:b=1;break; case*:b=2;break; case(:b=3;break;

18、case):b=4;break; case#:b=5;break; default:printf(n分析失败：非法字符！n);exit(0); int actvalue; actvalue=actionab; /5.主要过程 int c,d; /c,d表示goto表的位置 /5.1对应的表格无数值，则报错 if(actvalue=-1) printf(n分析失败：不符合文法n); exit(0); /5.2若取到的值落在0到100，则移进 else if(actvalue0&actvalue100&actvalue200) switch(actvalue) case 101: /若为第一个式子

19、 st.sttop=st.sttop-3; /归约时,弹出三个栈元素 ch.chtop=ch.chtop-3; c=st.datast.sttop; /将状态栈的栈顶赋给c,作为goto表的行号 ch.chtop+; ch.datach.chtop=e; /将字符e压入字符栈 d=0; break; /下同 case 102: st.sttop-; ch.chtop-; c=st.datast.sttop; ch.chtop+; ch.datach.chtop=e; d=0; break; case 103: st.sttop=st.sttop-3; ch.chtop=ch.chtop-3; c=st.datast.sttop; ch.chtop+; ch