农林大学-编译原理课程设计

1、福建农林大学计算机与信息学院计算机类课程设计结果评定评语：成绩：指导教师签字：任务下达日期：评定日期：目 录1 正则表达式11.1 正则表达式11.2 确定化(化简)后的状态转换图11.3 分析程序代码11.4 程序运行截图11.5 小结22 LL(1)分析错误！未定义书签。2.1 LL(1)文法32.2 LL(1)预测分析表32.3 分析程序代码42.4 程序运行截图62.5 小结73 算符优先分析73.1 算符优先文法83.2 算符优先关系表83.3 分析程序代码83.4 程序运行截图173.5 小结184 LR分析194.1 LR文法194.2 LR分析表194.3 分析程序代码194.

2、4 程序运行截图224.5 小结22参考文献：221 正则表达式1.1 正则表达式 (a|b)*(aa|bb)(a|b)* (注：该正规式为示例，可更改）1.2 确定化(化简)后的状态转换图 1.3 分析程序代码 # include stdio.hint s72=1,2,3,2,1,4,3,5,6,4,6,4,3,5;/状态转换图void main() printf( 有限自动机 n);printf(文法规则：n);printf(a|b)*(aa|bb)*(a|b)*nn); printf(-n);printf(请输入字符串：n); char ch; int i,j,t,flag;i=0;t=

3、1;/判断输入是否正确flag=0;/判断句子是否正确while(ch=getchar()!=n) if(ch=a) j=0;if(ch=b) j=1;if(ch!=a&ch!=b) t=0;/输入有误break; i=sij; flag=i;if(flag=3&t)/flag2时可终结printf(n输入字符串正确！nn);elseprintf(n输入字符串错误！nn);1.4 程序运行截图1、输入正确的字符串：2、输入错误的字符串：1.5 小结 在这次课程设计，对正则文法和状态转换图和有限自动机的理论有了更深的了解，将理论应用于实际应用中。2、LL(1)分析2.1 LL(1)文法 ETE

4、(注：该文法为示例，可更改） E+TE| TFT T*FT| F(E)|i2.2 LL(1)预测分析表i+*()#EETEETEEE+TEEETTFTTFTTTT*FTTTFFiF(E)2.3 分析程序代码#include #include #include #include #include using namespace std;/存储分析预测表每个位置对应的终结符，非终结符，产生式 struct Node1 char vn; char vt;char s10;MAP20;int k;/用R代表E,W代表T,e代表空char G1010=E-TR,R-+TR,R-e,T-FW,W-*FW,

5、W-e,F-(E),F-i;/存储文法中的产生式 char VN6=E,R,T,W,F;/存储非终结符 char VT6=i,+,*,(,),#;/存储终结符 char SELECT1010=(,i,+,),#,(,i,*,+,),#,(,i;/存储文法中每个产生式对应的SELECT集 char Right108=-TR,-+TR,-e,-FW,-*FW,-e,-(E),-i;stack stak,stak1,stak2;bool compare(char *a,char *b) /比较字符 int i,la=strlen(a),j,lb=strlen(b); for(i=0;ila;i+)

6、for(j=0;jlb;j+) if(ai=bj) return 1; return 0; char *Find(char vn,char vt) int i; for(i=0;ik;i+) if(MAPi.vn=vn & MAPi.vt=vt) return MAPi.s; return error; char * Analyse(char * word) char p,action10,output10; int i=1,j,l=strlen(word),k=0,l_act,m; while(!stak.empty() stak.pop(); stak.push(#); stak.push

7、(E); printf(_n); printf(n 对符号串%s的分析过程n,word); printf( 步骤 栈顶元素 剩余输入串 推到所用产生式或匹配n); p=stak.top(); while(p!=#) printf(%7d ,i+); p=stak.top(); stak.pop(); printf(%6c ,p); for(j=k,m=0;j1;j-) stak.push(actionj); if(strcmp(output,#)!=0) return 错误; int main () char source100; int i,j,flag,l,m;printf( LL(1)文

8、法 n); printf(n 为了区分E和后面的”，用R表示E,W表示T,e表示空字符串 nn); printf(该文法的产生式如下：n); for(i=0;i8;i+) printf( %sn,Gi); printf(-n); /判断是否是LL(1)文法 flag=1; for(i=0;i8;i+) for(j=i+1;j8;j+) if(Gi0=Gj0) if(compare(SELECTi,SELECTj) flag=0;break; if(j!=8) break; if(flag) printf(n有相同左部产生式的SELECT集合的交集为空，所以文法是LL（1）文法。n); else

9、 printf(n有相同左部产生式的SELECT集合的交集不为空，所以文法不是LL（1）文法。n); printf(-n); /预测分析表 for(i=0,k=0;i8;i+) l=strlen(SELECTi); for(j=0;jl;j+=2) MAPk.vn=Gi0; MAPk.vt=SELECTij; strcpy(MAPk.s,Righti); k+; printf(n LL(1)文法的预测分析表如下：nn); printf( ); for(i=0;i6;i+) printf(%10c,VTi); printf(n); for(i=0;i5;i+) printf( -n); prin

10、tf(%10c,VNi);for(j=0;j6;j+) for(m=0;msource) printf(n分析结果：%snn,Analyse(source); while(1) char d;coutd; if(d=Y|d=y) printf(n); printf(在输入字符串时要在后面加一个#，否则程序将无法正常运行!nn); printf(n); printf(请输入一个测试的字符串: ); break; if(d=n|d=N) return 0 ; return 0;2.4 程序运行截图1、初始界面：2、成功的字符串：（i）#成功的字符串：i+i*i #3、不成功的字符串：i i*#2.

11、5 小结 在这次课程设计中，对LL（1）算法中基础理论和基本知识的有了更深的理解，能更灵活应用的所学的知识。不仅学会程序实现文法判断、结构体和数组的使用等多种问题的基本方法，能将所学的理论知识应用于实践中。3 算符优先分析3.1 算符优先文法 ET | E+T | E-T (注：该文法为示例，可更改） TF | T*F | T/F F(E) | i3.2 算符优先关系表+-*/()i#+-*/()i#3.3 分析程序代码#include#include#include #define row 50#define col 50#define SIZE 50/两个重要结构体的定义/FIRSTVT表

12、或LASTVT表中一个表项（A,a）结构体的初始化typedef struct char nonterm; /非终结符char term; /终结符StackElement;/存放（A,a）的栈的初始化typedef struct StackElement *top;StackElement *bottom;int stacksize;stack;/初始化（A,a）栈void InitStack(stack &S) S.bottom = new StackElementSIZE; if(!S.bottom) cout存储空间分配失败！=S.stacksize)cout栈已满，无法插入！nont

13、erm=e.nonterm; S.top-term=e.term; S.top+;/弹出栈顶（A,a）元素StackElement Pop(stack &S) StackElement e;e.nonterm = 0;e.term = 0;if(S.top=S.bottom) cout栈为空，无法进行删除操作！nonterm; e.term=S.top-term; return e; /终结符与非终结符的判断函数（布尔类型）bool TerminalJud(char c) if(c=A&c=Z)return false; /非终结符返回falseelse return true; /终结符返回

14、true/判断非终结符在first表中是否已存在bool ItemJud(char firstcol,int frist_len,char C) for(int i=0;ifrist_len;i+) if(firsti0=C) return true; /如果first表中已存在此非终结符，则返回truereturn false;/读文件函数int readfile(char sencol) char addr50;cout请输入算符优先文法的描述的地址：addr;ifstream fin;fin.open(addr,ios:in);if(!fin) coutCannot open file!

15、nseni;coutseniendl;return i;/FIRSTVT表和LASTVT表中表项（非终结符）的初始化void ItemInit(char sencol,char firstcol,char lastcol,int sen_len,int &frist_len) int i;frist_len=1;first00=sen00;last00=sen00;for(i=1;isen_len;i+) if(TerminalJud(seni0)=false & ItemJud(first,frist_len,seni0)=false) /k是当前first和last表的长度 firstfr

16、ist_len0=seni0;lastfrist_len0=seni0;frist_len+;void FirstVt(char sencol,char firstcol,int sen_len,int frist_len) / frist_len 是 first 表的行数 sen_len是产生式的个数 StackElement DFS,recordSIZE;stack Operator; /创建存放（A，a）的栈InitStack(Operator); int i,j,r=0;for(i=0;isen_len;i+) /第一次扫描，将能直接得出的first（A，a）放进栈中 for(j=3;

17、senij!=0;j+) if(TerminalJud(senij)=true) /遇到的第一个终结符压入 int exist=0;DFS.nonterm=seni0;DFS.term=senij;for(int i1=0;ir;i+) if(recordi1.nonterm=seni0&recordi1.term=senij) exist=1;break;recordr.nonterm=seni0;recordr.term=senij;if(exist=0) Insert(Operator,DFS);/A-aB A-aC (A,a)压栈两次?recordr.nonterm=seni0;rec

18、ordr.term=senij;r+;break;int locationcol; /辅助数组，用来记录first表中放入终结符的位置for(i=0;ifrist_len;i+) locationi=1;while(!ifEmpty(Operator)int exist=0; /标志位，记录即将入栈的元素是否已经存在StackElement IDElement,DElement;DElement=Pop(Operator); /弹出栈顶元素for(i=0;ifrist_len;i+)if(firsti0=DElement.nonterm) int n=locationi;firstin=DEl

19、ement.term; /将终结符填入相应的first表中locationi+;break;for(j=0;jsen_len;j+) if(senj3=DElement.nonterm) /找出能推出当前非终结符的产生式的左部 IDElement.nonterm=senj0;IDElement.term=DElement.term;/判断将要放进栈里的元素曾经是否出现过，若没有，才压入栈for(int r0=0;r0r;r0+) /r记录record数组中的元素个数 if(recordr0.nonterm=IDElement.nonterm & recordr0.term=IDElement.

20、term) exist=1;break; if(exist=0) Insert(Operator,IDElement);recordr.nonterm=IDElement.nonterm;recordr.term=IDElement.term;r+;void LastVt(char sencol,char lastcol,int sen_len,int frist_len) /firstvt表与lastvt表行数一样 first_len表示last 表的行数 int i,j,i1,j1;char c,recordrowcol=0;for(i=0;isen_len;i+)for(j=0;seni

21、j!=0;j+) recordij=senij;j=j-1;for(i1=3,j1=j;i1j1;i1+,j1-) /做翻转，就可以用求first的方法求last c=recordii1;recordii1=recordij1;recordij1=c;FirstVt(record,last,sen_len,frist_len);/判断非终结符在term表中是否已存在bool TermTableJud(char termcol,int term_len,char C) for(int i=0;iterm_len;i+) if(termi=C) return true; /如果first表中已存在

22、此非终结符，则返回1return false;/构造算符优先关系表bool OpPriotable(char sencol,char firstcol,char lastcol,char opTablecol,int sen_len,int first_len,int &opTable_len) int i,j,term_len=0;int i2,i3,opr,opc;char c1,c2,c3;char termSIZE=0;for(i=0;isen_len;i+) /一维数组term记录关系表中存在的所有终结符for(j=3;senij!=0;j+)if(TerminalJud(senij

23、)=true)if(TermTableJud(term,term_len,senij)=false) /term_len记录term表的长度 termterm_len=senij; term_len+; /得到终结符表for(i=0;iterm_len+1;i+) /给优先关系表赋初值，都等于空for(j=0;jterm_len+1;j+)opTableij= ;for(i=1;iterm_len+1;i+) /设置优先关系表的表头 opTablei0=termi-1; opTable0i=termi-1; for(i=0;isen_len;i+) /找等于关系 for(j=5;senij!=

24、0;j+)if(TerminalJud(senij-2)=true&TerminalJud(senij-1)=false&TerminalJud(senij)=true) c1=senij-2; c2=senij; for(opr=1;oprterm_len+1;opr+) /在opTable表中找到该存入的行标opr if(opTableopr0=c1)break;for(opc=1;opcterm_len+1;opc+) /在opTable表中找到该存入的列标opc if(opTable0opc=c2)break; if(opTableopropc!= ) cout不是算符优先文法！end

25、l;return false;else opTableopropc=;for(j=4;senij!=0;j+) if(TerminalJud(senij-1)=true&TerminalJud(senij)=true) c1=senij-1;c2=senij;for(opr=1;oprterm_len+1;opr+) /在opTable表中找到该存入的行标oprif(opTableopr0=c1)break; for(opc=1;opcterm_len+1;opc+) /在opTable表中找到该存入的列标j2 if(opTable0opc=c2)break;if(opTableopropc!

26、= )cout不是算符优先文法！endl;return false;elseopTableopropc=; for(i=0;isen_len;i+) /找小于关系 for(j=3;senij!=0;j+) if(TerminalJud(senij)=true&TerminalJud(senij+1)=false) c1=senij; /c1记录终结符c2=senij+1; /c2记录非终结符 for(opr=1;oprterm_len+1;opr+) /在opTable表中找到该存入的行标opr if(opTableopr0=c1)break;for(opc=0;opcfirst_len;op

27、c+) /找出非终结符在first表中的列标opc if(firstopc0=c2)break;for(i2=1;firstopci2!=0;i2+)c3=firstopci2;for(i3=1;i3term_len+1;i3+)if(opTable0i3=c3) if(opTableopri3!= )cout不是算符优先文法！endl;return false;elseopTableopri3=;break; for(i=0;isen_len;i+) /找大于关系for(j=3;senij!=0;j+)if(TerminalJud(senij)=false&senij+1!=0&Termin

28、alJud(senij+1)=true) c1=senij; /c1记录非终结符c2=senij+1; /c2记录终结符 for(opr=1;oprterm_len+1;opr+) /在opTable表中找到该存入的列标j1 if(opTable0opr=c2)break; for(opc=0;opcfirst_len;opc+) /找出非终结符在last表中的行标j2 if(lastopc0=c1)break; for(i2=1;lastopci2!=0;i2+) c3=lastopci2;for(i3=1;i3term_len+1;i3+)if(opTablei30=c3) if(opTa

29、blei3opr!= ) cout不是算符优先文法！; break; opTable_len=term_len+1;return true; /判断两算符优先关系并给出类型供构造分析表int RelationshipJud(char c1,char c2,char opTablecol,int opTable_len) int i,j;for(i=1;iopTable_len;i+) if(opTablei0=c1)break; for(j=1;jopTable_len;j+) if(opTable0j=c2) break; if(opTableij=) return 3;else retur

30、n 4; /判断输入串是不是优先文法bool PrioGramJud(char sencol,int sen_len) int i,j;for(i=0;isen_len;i+) for(j=4;senij!=0;j+) if(TerminalJud(senij-1)=false&TerminalJud(senij)=false) cout输入的不是算符文法!endl;return false; return true; /开始分析输入串void InputAnalyse(char opTablecol,char stringcol,int opTable_len) /opTable_len是o

31、pTable表的长度 char a,Q,SSIZE=0; /S是分析栈 char cho1,cho2;int i,j,relation;int k=0;Sk=#;cho2=y;couttttt分析过程如下：endl;cout-endl;/cout 栈t当前字符t优先关系t移进或规约endl;/cout分析过程如下：endl;cout.width(10);cout栈;cout.width(15);cout当前字符;cout.width(20);cout剩余符号串;cout.width(15);cout优先关系;cout.width(15);cout移进或规约a cout.setf(ios:lef

32、t);cout.width(10);coutS;cout.unsetf(ios:left);cout.width(15);couta;cout.width(20);coutp;cout.width(15);cout;do Q=Sj; if(TerminalJud(Sj-1)=true) j=j-1; else j=j-2; while(RelationshipJud(Sj,Q,opTable,opTable_len)!=1);/cout Sj归约endl;cout.width(11);coutSj;cout.width(4);cout归约endl;k=j+1; Sk=N;for(int l=k

33、+1;lSIZE;l+) Sl=0; else if(relation=1) /Sja cho1=y; /cout St att tt 移进endl; cout.setf(ios:left);cout.width(10); coutS;cout.unsetf(ios:left);cout.width(15);couta;cout.width(20);coutp;cout.width(15);cout;cout.width(15);cout移进endl;k=k+1; Sk=a; else if(relation=2) /Sj=a cho1=y; /cout St att =tt;cout.setf(ios:left);cout.width(10); coutS;cout.unsetf(ios:left);cout.width(15);couta;cout.width(20);coutp;cout.width(15);cout=;cout.width(15); if(RelationshipJud(Sj,#,opTable,opTa