编译原理课程设计(JAVA)-语法分析器

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

2、 算符优先文法33.2 算符优先关系表33.3 分析程序代码33.4 程序运行截图33.5 小结34 LR分析44.1 LR文法44.2 LR分析表44.3 分析程序代码44.4 程序运行截图44.5 小结4参考文献：41 正则表达式1.1 正则表达式 (a|b)*(aa|bb)(a|b)* (注：该正规式为示例，可更改）1.2 确定化(化简)后的状态转换图 1.3 分析程序代码 #include <iostream>  #include <string>  using namespace 

3、std;    const int Max=20;                 typedef struct ArcNode      int adjvex;/该弧所指向的顶点的位置      char i

4、nfo;  /权      struct ArcNode *nextarc;/指向下一条弧的指针  ArcNode;  typedef struct VNode      char data;               

5、;   /顶点信息      ArcNode *firstarc;          /指向第一条依附该顶点的弧的指针  VNode;    class Nfa    public:      Nfa();  

6、    /构造函数,初始化nfa      int FindAdj(char c);        /返回c状态的在邻接表中的序号      void AlpAdd(char c);        /向字母表集合中添加表中没有的新元素c&#

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

8、#160;   /重载的状态集合的e-闭包      void move(int I,char a);    /单一状态I的a弧转换      void move(int I,char a);  /重载的状态集合的a弧转换      void Nfa:Visi

9、t_I(int *Temp);                                         /Visited转换为集合   

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

11、#160; void Nfa_Dfa();  private:      int K;              /状态数      int TMaxMax;        /状态子集矩阵 

12、     VNode AdjListMax;         /nfa,邻接表的数据结构存储      VNode DfaMax;             /dfa      bool

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

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

15、.data=c;          AdjListK.firstarc=new ArcNode;          AdjListK.firstarc->nextarc=NULL;          K+;      

16、60;     getline(cin,line);            while(getline(cin,line)&&line!="#")                int index=FindAdj(line0

17、);          if(index!=-1)                        p=AdjListindex.firstarc;         

18、60;    while(p->nextarc)                  p=p->nextarc;              p->nextarc=new ArcNode;  &#

19、160;           p->nextarc->nextarc=NULL;              p->nextarc->adjvex=FindAdj(line4);            

20、60; p->nextarc->info=line2;              AlpAdd(p->nextarc->info);                      cout<<&qu

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

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

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

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

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

26、c;                    if(i<K&&AdjListi.firstarc->nextarc)              cout<<endl;    

27、0;       cout<<"-"<<endl;      for(int i=0;i<Max;i+)          Ti0=0;      int Nfa:FindAdj(char c)   

28、     for(int i=0;i<K;i+)          if(c=AdjListi.data)              return i;           

29、/返回序号      return -1;                  /没有查找到则返回-1      void Nfa:AlpAdd(char c)        if(c=

30、9;*') return;      for(int i=1;i<=(int)Alp0;i+)          if(c=Alpi)              return;     /集合中已含有 &#

31、160;    Alp+Alp0=c;    void Nfa:e_closure(int index)        ArcNode *p;      Visitedindex=true;      p=AdjListindex.firstarc->nextarc; &#

32、160;    while(p)                if(!Visitedp->adjvex&&p->info='*')              e_closure(p->adjvex);

33、0;         p=p->nextarc;          void Nfa:e_closure(int a)        InitVisit();      for(int i=1;i<=a0;i+) &#

34、160;        e_closure(ai);      void Nfa:InitVisit()        for(int i=0;i<K;i+)          Visitedi=false;    

35、;  void Nfa:move(int I,char a)        ArcNode *p;      p=AdjListI.firstarc->nextarc;      while(p)           

36、60;    if(p->info=a)              Visitedp->adjvex=true;          p=p->nextarc;          void Nf

37、a:move(int I,char a)        InitVisit();      for(int i=1;i<=I0;i+)          move(Ii,a);      void Nfa:Insert(int I,int

38、60;index)        /I0表示元素个数;      int flag=0;      for(int i=1;i<=I0;i+)                if(index=Ii) &#

39、160;   /状态集合中已有index状态              return;          else if(index>Ii)              fla

40、g=i;         /标记待插入位置            I0+;flag+;      for(int i=I0;i>flag;i-)          Ii=Ii-1;   

41、;   Iflag=index;      int Nfa:TAdd(int I)  /T00当前集合的个数      int i=1;      for(;i<=T00;i+)             

42、   if(I0=Ti0)             int j=1;              for(;j<=I0;j+)             &#

43、160;    if(Ij!=Tij)                      break;              if(j=(I0+1)    

44、0;    /说明矩阵T中已有I集合,并返回位置                  return i;                      &#

45、160;  T00+;      for(i=0;i<=I0;i+)          TT00i=Ii;      return -1;                 &

46、#160;    /说明矩阵T中没有I集合,插入并返回-1      void Nfa:Visit_I(int *Temp)        Temp0=0;      for(int i=0;i<K;i+)          

47、;if(Visitedi)              Temp+Temp0=i;    void Nfa:Resault(int i)        int j,k;      ArcNode *p;   &#

48、160;  cout<<"Nfa To Dfa:"<<endl;      for(j=0;j<i;j+)                cout<<(int)Dfaj.data<<"="     

49、;     for(k=1;k<Tj+10;k+)              cout<<AdjListTj+1k.data<<","          cout<<AdjListTj+1k.data<<"/t/t"

50、          if(j+1)%2=0)              cout<<endl;            if(j+1)%2=0)  cout<<endl;  &#

51、160;   cout<<endl;        cout<<"S="      for(int j=0;j<i-1;j+)          cout<<(int)Dfaj.data<<","  

52、60;   cout<<(int)Dfai-1.data<<"."<<endl;      cout<<"="      for(int j=1;j<(int)Alp0;j+)          cout<<Alpj<<&

53、quot;,"      cout<<AlpAlp0<<"."<<endl;      for(int j=0;j<i;j+)                p=Dfaj.firstarc;    

54、      p=p->nextarc;          while(p)                        cout<<"D("<<(i

55、nt)Dfaj.data<<","<<p->info<<")="<<p->adjvex<<"  "              p=p->nextarc;            

56、60;       if(j<i&&Dfaj.firstarc->nextarc)              cout<<endl;            cout<<"Finished."<

57、<endl;      cout<<"-"<<endl;    void Nfa:Nfa_Dfa()        int TempMax,i=0,j=1;      ArcNode *p;      InitVisit

58、();      e_closure(0);   /选择第一个状态K0      Visit_I(Temp);      TAdd(Temp);/Dfa中加入第一个状态      i+;j+;    /将选择的第一个状态的e-闭包加入C矩阵中/并标记   &#

59、160;  while(i!=j)                Dfai-1.data=i-1;          Dfai-1.firstarc=new ArcNode;          Dfai-1.f

60、irstarc->nextarc=NULL;            for(int ii=1;ii<=Alp0;ii+)                        for(int jj=0;jj<=

61、Ti0;jj+)                  Tempjj=Tijj;                  move(Temp,Alpii);        

62、;      Visit_I(Temp);              if(Temp0)                          

63、      e_closure(Temp);                  Visit_I(Temp);                  int flag=TAdd

64、(Temp);                  if(flag=-1)                             

65、           j+;                      p=Dfai-1.firstarc;             

66、60;        while(p->nextarc)                      p=p->nextarc;             

67、60;        p->nextarc=new ArcNode;                      p->nextarc->adjvex=T00-1;         &

68、#160;            p->nextarc->info=Alpii;                      p->nextarc->nextarc=NULL;     &

69、#160;                              else                  

70、60;                     p=Dfai-1.firstarc;                      while(p->nextarc)&

71、#160;                     p=p->nextarc;                      p->nextarc=new

72、0;ArcNode;                      p->nextarc->adjvex=flag-1;                     

73、 p->nextarc->info=Alpii;                      p->nextarc->nextarc=NULL;                 

74、                                     i+;            Res

75、ault(i-1);    int main()        Nfa nfa;      nfa.Nfa_Dfa();      return 0;    1.4 程序运行截图1.5 小结平时的学习需要通过实践来检验，通过这次实验我能发现自身存在的一些问题，并且加以改正，同时通过实验加强

76、了自己的动手能力，并且增强了对于正则表达式的理解，并不只在于应试方面。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'E'E'TTFT'TFT'T'T'T'*FT'T'T'FFiF(E)2.3 分析程序代码 输入文法： EE+T|T TT*F|F Fi|(E)代码：（1

77、） 计算非终结符的First集：void first(edge ni,edge *n,int x)/ni为一个产生式，n为整个文法int i,j;for(j=0;j<SUM;j+)if(ni.getlf()=nj.getlf()if(NODE.find(nj.getro()<NODE.length()/非终结符的情况for(i=0;i<SUM;i+)if(ni.getlf()=nj.getro()first(ni,n,x);elsenx.newfirst(nj.getro();/终结符的情况（2） 计算非终结符的Follow集：void follow(edge ni,edge

78、 *n,int x) /计算followint i,j,k,s;string str;for(i=0;i<ni.getrlen();i+) s=NODE.find(ni.getrg()i);if(s<NODE.length()&&s>-1) /是非终结符if(i<ni.getrlen()-1) /不在最右for(j=0;j<SUM;j+)if(nj.getlf().find(ni.getrg()i)=0)if(NODE.find(ni.getrg()i+1)<NODE.length() for(k=0;k<SUM;k+)if(nk.ge

79、tlf().find(ni.getrg()i+1)=0) nj.newfollow(nk.getfirst(); if(nk.getfirst().find("*")<nk.getfirst().length() nj.newfollow(ni.getfollow();elsestr.erase(); str+=ni.getrg()i+1; nj.newfollow(str);（3） 输出预测分析表的主要代码： void outgraph(edge *n,string (*yc)50) int i,j,k;bool flag;for(i=0;i<ENODE.le

80、ngth();i+)if(ENODEi!='*')outfu(10," ");cout<<ENODEi; outfu(10," ");cout<<"#"<<endl;int x;for(i=0;i<NODE.length();i+)outfu(4," ");cout<<NODEi;outfu(5," ");for(k=0;k<ENODE.length();k+) flag=1;for(j=0;j<SUM;j+)if

81、(NODEi=nj.getlf()0)x=nj.getselect().find(ENODEk);if(x<nj.getselect().length()&&x>-1) cout<<"->"<<nj.getrg();ycik=nj.getrg();outfu(9-nj.getrlen()," ");flag=0;/x=nj.getselect().find('#');if(k=ENODE.length()-1&&x<nj.getselect().length(

82、)&&x>-1)cout<<"->"<<nj.getrg();ycij=nj.getrg(); if(flag&&ENODEk!='*')outfu(11," ");cout<<endl; public static void analyse(String Vn, String Vt, String M) / 句型分析函数int i, m, p, q, len, t, step, j; / ,记录栈顶指针位置(s),记录产生式右部的长度(len),记录分析步骤

83、数(step)String a, A; / a用于记录剩余输入串的第一个元素,A记录分析栈的栈顶元素String str = null; / 记录要分析的字符串boolean flag1 = true, flag2 = true;Scanner in = new Scanner(System.in);OPT0: while (flag1) flag1 = false;str = in.nextLine(); / 输入要分析的字符串，且以#结束if (str = null | "".equals(str) System.out.print("请输入要分析的字符串，且

84、以#结束:");flag1 = true;continue OPT0;for (i = 0; i < str.length(); i+) if (!findString(str.charAt(i) + "", Vt) / 判断输入的字符串是否有误System.out.println("输入字符串不是文法的句型!请重新输入!");flag1 = true;continue OPT0; / 跳转向OPTO重新输入字符串s = 0;j = 0;String st = new StringConstantValue.MAXVN;sts = &qu

85、ot;#"st+s = Vn0;step = 1; / 步骤序号从1开始a = str.charAt(0) + ""System.out.println("步骤 分析栈 剩余输入串 所用产生式或匹配");/ 显示符号串分析过程OPT1: while (flag2) flag2 = false;System.out.print(step + " "); / 显示步骤step+;showStack(st); / 显示分析栈中内容System.out.print(" ");for (t = j; t <

86、str.length(); t+) System.out.print(str.charAt(t); / 显示剩余字符串System.out.print(" ");A = sts-; / 上托栈顶符号放入Aif (findString(A, Vt) && A.charAt(0) != '#') / 假设A为终结符，但是不为#if (A.charAt(0) = a.charAt(0) / 分析栈的栈顶元素和剩余输入串的第一个元素相比较System.out.println("'" + A + "' 匹配

87、");j+;a = str.charAt(j) + ""flag2 = true;continue OPT1; elseerror(); else if (findString(A, Vt) && A.charAt(0) = '#') if (A.charAt(0) = a.charAt(0) System.out.println("接受!"); elseerror(); else / 当A 属于Vn，则以A及a组成的符号对(A，a)查分析表M。p = location(A, Vn); / 调用前面的定位函数，指

88、出字符所在位置q = location(a, Vt);String S1 = "NULL", S2 = "null"if (Mpq.equals(S1) | Mpq.equals(S2) / 查找二维数组中的产生式error();else String str1 = Mpq;System.out.println(A+ "->" + str1);/ 显示对应的产生式if (str1.equals("&")flag2 = true;continue OPT1; else len = str1.length

89、(); / 产生式逆序进栈for (m = len - 1; m >= 0; m-) if("'".equals(str1.charAt(m)+"")m-;st+s=str1.charAt(m)+"'"elsest+s=str1.charAt(m)+""flag2 = true;continue OPT1;2.4 程序运行截图 2.5 小结 实践实践验证里的唯一标准，这次课程设计主要巩固了我对LL(1)文法的深刻认识，掌握程序实现文法判断、链表的使用等多种问题的基本方法，进一步提高了综合运用所

90、学知识的能力。 3 算符优先分析3.1 算符优先文法 ET | E+T | E-T (注：该文法为示例，可更改） TF | T*F | T/F F(E) | i3.2 算符优先关系表+-*/()i#+-*/()i#3.3 分析程序代码package com.op.core;import java.math.BigDecimal;import java.util.Stack;import com.op.util.StringUtil;import com.op.util.IOUtil;public class OperatorPriority private Stack<Character

91、> optrStack; /符号栈private Stack<Float> opndStack; /操作数栈private String input; /待分析的算术表达式/* * 构造函数 * param input */public OperatorPriority(String input) super();optrStack = new Stack<Character>();opndStack = new Stack<Float>();optrStack.push('#');this.input = input;/* * 操作两

92、个数 * param a 操作数1 * param b 操作数2 * param op 操作符 * return 运算结果 */public float operateTwoNum(float a, float b, char op) BigDecimal da = new BigDecimal(Float.toString(a); BigDecimal db = new BigDecimal(Float.toString(b); switch (op) case '*':return da.multiply(db).floatValue();case '+':

93、return da.add(db).floatValue();case '-':return db.subtract(da).floatValue();case '/':return db.divide(da,7,BigDecimal.ROUND_HALF_UP).floatValue(); /除不尽的情况取7位精确值。case '':return db.pow(int)a).floatValue();return 0;/* * 判断是否为操作符 * param ch 被判断字符 * return 布尔值 */public boolean isO

94、perator(char ch) if (ch = '+' | ch = '-' | ch = '*' | ch = '/' | ch = '('| ch = ')' | ch = '#'|ch='')return true;elsereturn false;/* * 扫描字符串，判断是否对应文法，并计算出结果 * return 计算结果 * throws Exception 如果不符合文法，或者除数等于0，都将抛出异常 */public String scanner() throws Exception int postion = 0; / 字符串上指示的指针char operator = 0; / 操作符