编译原理C++语法分析器36884.pdf

《编译原理C++语法分析器36884.pdf》由会员分享，可在线阅读，更多相关《编译原理C++语法分析器36884.pdf（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、课程设计报告 课程名称：编译原理 课程设计题目：语法分析器 姓 名：系：计算机 专 业：计算机科学与技术 年 级：2009 级 学 号：指导教师：职 称：20102011 学年第一学期 评语：成绩：指导教师签字：任务下达日期：评定日期：目 录 1 正则表达式 1 1.1 正则表达式 1 1.2 确定化(化简)后的状态转换图 1 1.3 分析程序代码 1 1.4 程序运行截图 4 1.5 小结 4 2 LL(1)分析 5 2.1 LL(1)文法 5 2.2 LL(1)预测分析表 5 2.3 分析程序代码 5 2.4 程序运行截图 7 2.5 小结 7 3 算符优先分析 8 3.1 算符优先文法

2、8 3.2 算符优先关系表 8 3.3 分析程序代码 8 3.4 程序运行截图 10 3.5 小结 11 4 LR 分析 12 4.1 LR 文法 12 4.2 LR 分析表 12 4.3 分析程序代码 12 4.4 程序运行截图 112 4.5 小结 114 参考文献：114 1 正则表达式 1.1 正则表达式 (a|b)*(aa|bb)(a|b)*(注：该正规式为示例，可更改）1.2 确定化(化简)后的状态转换图 1.3 分析程序代码#include#include using namespace std;const int Max=20;typedef struct ArcNode in

3、t adjvex;/该弧所指向的顶点的位置 char info;/权 struct ArcNode*nextarc;/指向下一条弧的指针 ArcNode;typedef struct VNode char data;/顶点信息 ArcNode*firstarc;/指向第一条依附该顶点的弧的指针 VNode;class Nfa public:Nfa();/构造函数,初始化 nfa int FindAdj(char c);/返回 c 状态的在邻接表中的序号 void AlpAdd(char c);/向字母表集合中添加表中没有的新元素 c void InitVisit();/初始化 Visited

4、集合 void e_closure(int index);/求单一状态 c 的 e-闭包 void e_closure(int a);/重载的状态集合的 e-闭包 void move(int I,char a);/单一状态 I 的 a 弧转换 void move(int I,char a);/重载的状态集合的 a 弧转换 void Nfa:Visit_I(int*Temp);/Visited 转换为集合 void Insert(int I,int a);/向状态集合中添加新元素 int TAdd(int I);/状态矩阵 T 中加入新状态集合 void Resault(int i);void

5、Nfa_Dfa();private:int K;/状态数 int TMaxMax;/状态子集矩阵 VNode AdjListMax;/nfa,邻接表的数据结构存储 VNode DfaMax;/dfa bool VisitedMax;/存 e-闭包结果 char AlpMax;/字母表,0 号单元用于存放个数 ;Nfa:Nfa()K=Alp0=0;char c;string line;ArcNode*p;while(cinc&c!=#)AdjListK.data=c;AdjListK.firstarc=new ArcNode;AdjListK.firstarc-nextarc=NULL;K+;g

6、etline(cin,line);while(getline(cin,line)&line!=#)int index=FindAdj(line0);if(index!=-1)p=AdjListindex.firstarc;while(p-nextarc)p=p-nextarc;p-nextarc=new ArcNode;p-nextarc-nextarc=NULL;p-nextarc-adjvex=FindAdj(line4);p-nextarc-info=line2;AlpAdd(p-nextarc-info);cout-endl;coutInitialization completely.

7、endl;coutK=;for(int i=0;iK-1;i+)coutAdjListi.data,;coutAdjListK-1.data.endl;cout=;for(int i=1;i(int)Alp0;i+)coutAlpi,;coutAlpAlp0.endl;for(int i=0;inextarc;while(p)coutf(AdjListi.data,info)=adjvexnextarc;if(inextarc)#include int exch42=1,2,3,2,1,3,3,3;void judge(char*s)int cur=0,i=0;while(si)if(si-a

8、 1|si a)break;cur=exchcur si+-a;if(si=0&cur=3)printf(%s Right！nn,s);else printf(%s Wrong！nn,s);int main()char str100;while(1)printf(有限自动机，判断是否符合(a|b)*(aa|bb)(a|b)*n);printf(请输入字符串：);gets(str);judge(str);1.4 程序运行截图 1.5 小结 平时的学习需要通过实践来检验，通过这次实验我能发现自身存在的一些问题，并且加以改正，同时通过实验加强了自己的动手能力，并且增强了对于正则表达式的理解，并不只在

9、于应试方面。2 LL(1)分析 2.1 LL(1)文法 ETE (注：该文法为示例，可更改）E+TE|TFT T*FT|F(E)|i 2.2 LL(1)预测分析表 i+*()#E ETE ETE E E+TE E E T TFT TFT T T T*FT T T F Fi F(E)2.3 分析程序代码 输入文法：ETE (注：该文法为示例，可更改）E+TE|TFT T*FT|F(E)|i 代码：#include#include char data5610=12,12,12+,-,-,34,34,-,34*,-,-,i,)0(,;/第一维 0-4 分别代表 EETTF，第二维 0-5 代表 i+

10、*()#-代表 int exch(char ch)switch(ch)case i:return 0;case+:return 1;case*:return 2;case(:return 3;case):return 4;case 0:return 5;/字符串结束标志代表#.default:return-1;void judge(char*s)int tot=0,i=0,cur,k=exch(s0);char sta100;sta+tot=0;while(tot0)cur=statot-0;if(si=)/去空格 +tot,k=exch(s+i);else if(cur+0=si)/推导出相

11、同字符，出栈 k=exch(s+i);else if(k 0|datacurk0=0)/踩空，或者出现非法字符 break;else if(datacurk0!=-)/不是，进栈继续推导 strcpy(sta+tot,datacurk);tot+=strlen(datacurk);-tot;if(tot=0)printf(%s Right！nn,s);else printf(%s Wrong！nn,s);int main()char str100;printf(判断符号串是否符合文法：nntETEnt);printf(E+TE|ntTFTntT*FT|ntF(E)|inn);while(pri

12、ntf(输入符号串:)&gets(str)&str0)judge(str);return 0;2.4 程序运行截图 2.5 小结 实践实践验证里的唯一标准，这次课程设计主要巩固了我对 LL(1)文法的深刻认识，掌握程序实现文法判断、链表的使用等多种问题的基本方法，进一步提高了综合运用所学知识的能力。3 算符优先分析 3.1 算符优先文法 ET|E+T|E-T (注：该文法为示例，可更改）TF|T*F|T/F F(E)|i 3.2 算符优先关系表 +-*/()i#+-*/()i#3.3 分析程序代码#include#include char 88=,=,-,-,-,-,-,0&stan!=0)f

13、or(i=0;i0)m=tot;do cur=exch(stam-);while(cur0);/要忽略变量，直接对终结符进行比较优先级。while(si=)/跳过空格 i+;k=exch(si);if(cur=k&cur=7)tot=0;/规约成功，结束标记。else if(k)/遇到，准备规约 if(statot=N)/这里一个小问题就是变量 N 是要在左边还是右边呢，这要取决于终结符是什么，左右两边有几个变量，不过针对本程序方法，只需全部放在右边。statot=curk;sta+tot=N;else sta+tot=curk;sta+tot=si+;else if(tot=confirm(

14、sta,tot)=0)/检验终结符是否带了应有的变量。没有，就规约失败 tot=-1;if(tot=0)printf(%s Right！nn,s);else printf(%s Wrong！nn,s);int main()char str100;printf(判断符号串是否符合文法：nntET|E+T|E-TntTF|T*F|T/FntF(E)|inn);while(printf(输入符号串:)&gets(str)&str0)judge(str);return 0;3.4 程序运行截图 3.5 小结 通过这次课程设计，我发现之前没发现的问题。算符优先分析方法有一定的局限性由于算符优先分析法去掉

15、了单非终结符之间的归约，尽管在分析过程中，当决定是否为句柄时采取一些检查措施，但仍难完全避免把错误的句子得到正确的归约。4 LR 分析 4.1 LR 文法 (0)SS (注：该文法为示例，可更改）(1)SBB (2)BaB (3)Bb 4.2 LR 分析表 ACTION GOTO a b#S B 0 S3 S4 1 2 1 acc 2 S3 S4 5 3 S3 S4 6 4 r3 r3 r3 5 r1 r1 r1 6 r2 r2 r2 4.3 分析程序代码#include#include int action75=3,4,0,1,2,0,0,-4,0,0,3,4,0,0,5,3,4,0,0,6

16、,-3,-3,-3,0,0,-1,-1,-1,0,0,-2,-2,-2,0,0 ;/负数代表此时可规约，即 r，第二维 0-5 分别代表 a b#S B,-4表示 acc intt=0,S*10+2,B*10+2,B*10+1;/表示 ri 的产生式的左边变量和右边长度 int exch(char ch)switch(ch)case a:return 0;case b:return 1;case#:case0:return 2;/字符串结束标志代表#.case S:return 3;case B:return 4;default:return-1;void judge(char*s)int i

17、nt_stack100,ti=0,tc=0,i=1,cur,k=exch(s0);char char_stack100;int_stack+ti=0;while(ti0)cur=int_stackti;if(k0)/入栈，等待规约 int_stack+ti=actioncurk;/数字栈 char_stack+tc=si;/字符栈 k=exch(si+);else if(actioncurk=-4)/规约完成，说明是符合要求 ti=0;else /可以规约 -i;/说明输入的字符 si-1还没有用，此时它不进栈，故 i-，以便下次取到的是要 si-1;ti-=t-actioncurk%10;/

18、取 ri 的长度，出栈这么多个的字符 tc-=t-actioncurk%10;char_stack+tc=t-actioncurk/10;/取产生式的左边变量，进行规约。k=exch(char_stacktc);if(ti=0)printf(%s Right！nn,s);else printf(%s Wrong！nn,s);int main()char str100;printf(判断符号串是否符合如下文法：nntSBBntBaBntBbnn);while(printf(输入符号串:)&gets(str)&str0)judge(str);return 0;4.4 程序运行截图 4.5 小结 LR(0)分析器规约没有平时学的那么轻松，在实验的过程中我还是借助了老师、同学以及参考书的力量来完成改课程设计的。从该次课程设计中我可以发现自身能力的不足之处，今后会努力的。参考文献：1 德芳主编.编译原理实用教程M.：中国水利水电，2007 2 宗礼 守旭 编著 编译原理，：高等教育，2010