编译原理C语法分析器

1、课程设计报告课程名称：编译原理课程设计题目：语法分析器姓 名：系：计算机专 业：计算机科学与技术年 级：2009级学 号：指导教师：职 称：20102011学年第一学期评语：成绩：指导教师签字：任务下达日期：评定日期：目 录1 正则表达式11.1 正则表达式11.2 确定化(化简)后的状态转换图11.3 分析程序代码11.4 程序运行截图41.5 小结42 LL(1)分析52.1 LL(1)文法52.2 LL(1)预测分析表52.3 分析程序代码52.4 程序运行截图72.5 小结73 算符优先分析83.1 算符优先文法83.2 算符优先关系表83.3 分析程序代码83.4 程序运行截图103

2、.5 小结114 LR分析124.1 LR文法124.2 LR分析表124.3 分析程序代码124.4 程序运行截图144.5 小结14参考文献：141 正则表达式1.1 正则表达式 (a|b)*(aa|bb)(a|b)* (注：该正规式为示例，可更改）1.2 确定化(化简)后的状态转换图 1.3 分析程序代码 #include <iostream>  #include <string>  using namespace std;    const&#

3、160;int Max=20;                 typedef struct ArcNode      int adjvex;/该弧所指向的顶点的位置      char info;  /权   

4、;   struct ArcNode *nextarc;/指向下一条弧的指针  ArcNode;  typedef struct VNode      char data;                  /顶点信息  

5、;    ArcNode *firstarc;          /指向第一条依附该顶点的弧的指针  VNode;    class Nfa    public:      Nfa();      /构造函数,初始化nf

6、a      int FindAdj(char c);       /返回c状态的在邻接表中的序号      void AlpAdd(char c);       /向字母表集合中添加表中没有的新元素c      void Ini

7、tVisit();           /初始化Visited集合      void e_closure(int index);  /求单一状态c的e-闭包      void e_closure(int a);    /重载的状态集合的e-闭包  

8、;    void move(int I,char a);    /单一状态I的a弧转换      void move(int I,char a);  /重载的状态集合的a弧转换      void Nfa:Visit_I(int *Temp); /Visited转换为集合 &#

9、160;    void Insert(int I,int a); /向状态集合中添加新元素      int TAdd(int I);          /状态矩阵T中加入新状态集合      void Resault(int i);  

10、    void Nfa_Dfa();  private:      int K;              /状态数      int TMaxMax;        

11、/状态子集矩阵      VNode AdjListMax;         /nfa,邻接表的数据结构存储      VNode DfaMax;             /dfa     

12、 bool VisitedMax;      /存e-闭包结果      char AlpMax;      /字母表,0号单元用于存放个数      Nfa:Nfa()        K=Alp0=0;    

13、;  char c;      string line;      ArcNode *p;      while(cin>>c&&c!='#')               &

14、#160;AdjListK.data=c;          AdjListK.firstarc=new ArcNode;          AdjListK.firstarc->nextarc=NULL;          K+;    &#

15、160;       getline(cin,line);            while(getline(cin,line)&&line!="#")                int index=

16、FindAdj(line0);          if(index!=-1)                        p=AdjListindex.firstarc;       &#

17、160;      while(p->nextarc)                  p=p->nextarc;              p->nextarc=new ArcNode;&

18、#160;             p->nextarc->nextarc=NULL;              p->nextarc->adjvex=FindAdj(line4);          &#

19、160;   p->nextarc->info=line2;              AlpAdd(p->nextarc->info);                      co

20、ut<<"-"<<endl;      cout<<"Initialization completely."<<endl;      cout<<"K="      for(int i=0;i<K-1;i+)     

21、60;    cout<<AdjListi.data<<","      cout<<AdjListK-1.data<<"."<<endl;      cout<<"="      for(int i=1;i<(int)Alp0;i

22、+)          cout<<Alpi<<","      cout<<AlpAlp0<<"."<<endl;      for(int i=0;i<K;i+)        &

23、#160;       p=AdjListi.firstarc;          p=p->nextarc;          while(p)               

24、;         cout<<"f("<<AdjListi.data<<","<<p->info<<")="<<p->adjvex<<"  "              p

25、=p->nextarc;                    if(i<K&&AdjListi.firstarc->nextarc)       #include<stdio.h>int exch42=1,2,3,2,1,3,3,3;void judge(char *s) int

26、cur = 0, i = 0;while(si)if(si-'a' > 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"

27、); printf("请输入字符串： "); gets(str); judge(str);1.4 程序运行截图1.5 小结平时的学习需要通过实践来检验，通过这次实验我能发现自身存在的一些问题，并且加以改正，同时通过实验加强了自己的动手能力，并且增强了对于正则表达式的理解，并不只在于应试方面。2 LL(1)分析2.1 LL(1)文法 ETE' (注：该文法为示例，可更改） E'+TE'| TFT' T'*FT'| F(E)|i2.2 LL(1)预测分析表i+*()#EETE'ETE'E'E'+TE

28、'E'E'TTFT'TFT'T'T'T'*FT'T'T'FFiF(E)2.3 分析程序代码 输入文法：ETE' (注：该文法为示例，可更改） E'+TE'| TFT' T'*FT'| F(E)|i代码：#include<stdio.h>#include<string.h> char data5610= "12","","","12",""

29、,"", "","12+","","","-","-", "34","","","34","","", "","-","34*","","-","-", "i","","

30、",")0(","","",;/ 第一维0-4分别代表 EE'TT'F ，第二维0-5代表i+*()# -代表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; /字符串结束标志代表'

31、#'. default: return -1;void judge(char *s)int tot=0,i=0,cur,k=exch(s0);char sta100;sta+tot='0'while(tot>0)cur = statot - '0'if(si = ' ') / 去空格+tot,k=exch(s+i);else if(cur+'0' = si) / 推导出相同字符，出栈k=exch(s+i);else if(k < 0 | datacurk0 = 0) / 踩空，或者出现非法字符break;els

32、e 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("判断符号串是否符合文法：nntETE'nt");printf("E'+TE'|ntTFT'ntT

33、9;*FT'|ntF(E)|inn");while(printf("输入符号串: ")&&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) | i3.2 算符优先关系

34、表+-*/()i#+-*/()i#3.3 分析程序代码#include<stdio.h>#include<string.h>char com88= '>', '>', '<', '<', '<', '>', '<', '>', '>', '>', '<', '<', '<', '&

35、gt;', '<', '>', '>', '>', '>', '>', '<', '>', '<', '>', '>', '>', '>', '>', '<', '>', '<', '>', &#

36、39;<', '<', '<', '<', '<', '=', '<', ' ', '>', '>', '>', '>', '-', '>', '-', '>', '>', '>', '>', '>&

37、#39;, '-', '>', '-', '>', '<', '<', '<', '<', '<', '-', '<', '=',; / 0-7 分别代表+ - * / ( ) i #int exch(char ch)switch(ch) case '+': return 0; case '-': return 1; case

38、 '*': return 2; case '/': return 3; case '(': return 4; case ')': return 5; case 'i': return 6; case 0 : return 7; /字符串结束标志代表# default: return -1;char expre65="N+N","N-N","N*N","N/N","(=N)","i" /为了挽回因

39、忽略语法变量而产生的错误，在规约时检验终结符是否带了应有的操作对象。int confirm(char *sta,int t) /检验终结符是否带了应有的变量。int i,n=t; while( n>0&&stan!='<')n-; if(n>0)for(i=0;i<6;i+)if(memcmp(exprei,sta+n+1,sizeof(char)*(t-n)=0)stan = 'N' / 说明是有应有的操作对象，所以进行规约。return n;return 0;void judge(char *s) char sta10

40、0;int tot=0,cur,m,k,i=0;sta+tot=0;while(tot>0)m=tot;do cur=exch(stam-);while(cur<0); / 要忽略变量，直接对终结符进行比较优先级。while(si = ' ') / 跳过空格i+;k = exch(si);if( cur=k&&cur=7)tot = 0; / 规约成功，结束标记。 else if( k<0 | comcurk = '-' ) / 踩空或者输入非法符tot = -1; else if( comcurk != '>&#

41、39; ) / 遇到>'，准备规约if(statot = 'N') / 这里一个小问题就是变量N是要在'<'左边还是右边呢，这要取决于终结符是什么，左右两边有几个变量，不过针对本程序方法，只需全部放在右边。statot = comcurk;sta+tot = 'N'else sta+tot = comcurk;sta+tot =si+;else if( (tot = confirm( sta,tot )=0 ) /检验终结符是否带了应有的变量。没有，就规约失败 tot = -1;if(tot=0) printf("

42、%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 小结通过这次课程设计，我发现之前没发现的问题。算符优先分析方法有一定的局限性由于算符优先分析法去掉了单非终结符之间的归约，尽管在分析过程中，当决定是否为句柄时采取一些检查措施，但仍难完全避免把错误的句子得到正确的归约。4 LR分析4.1 LR文法 (0) S'S (注：该文法为示例，可更改） (1) SBB (2) BaB (3) Bb4.2 LR分析表ACTIONGOTOab#SB0S3S4121acc2S3S453S3S464r3r3r35r1r1r16r2r2r24.3 分析程序代码#include<stdio.h>#include<string.h> int a