編譯原理C語法分析器

1、課程設計報告課程名稱：編譯原理課程設計題目：語法分析器姓 名：系：計算機專 業(yè)：計算機科學與技術年 級：2009級學 號：指導教師：職 稱：20102011學年第一學期評語：成績：指導教師簽字：任務下達日期：評定日期：目 錄1 正則表達式11.1 正則表達式11.2 確定化(化簡)后的狀態(tài)轉換圖11.3 分析程序代碼11.4 程序運行截圖41.5 小結42 LL(1)分析52.1 LL(1)文法52.2 LL(1)預測分析表52.3 分析程序代碼52.4 程序運行截圖72.5 小結73 算符優(yōu)先分析83.1 算符優(yōu)先文法83.2 算符優(yōu)先關系表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)* (注：該正規(guī)式為示例，可更改）1.2 確定化(化簡)后的狀態(tài)轉換圖 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();      /構造函數(shù),初始化nf

6、a      int FindAdj(char c);       /返回c狀態(tài)的在鄰接表中的序號      void AlpAdd(char c);       /向字母表集合中添加表中沒有的新元素c      void Ini

7、tVisit();           /初始化Visited集合      void e_closure(int index);  /求單一狀態(tài)c的e-閉包      void e_closure(int a);    /重載的狀態(tài)集合的e-閉包  

8、;    void move(int I,char a);    /單一狀態(tài)I的a弧轉換      void move(int I,char a);  /重載的狀態(tài)集合的a弧轉換      void Nfa:Visit_I(int *Temp); /Visited轉換為集合 &#

9、160;    void Insert(int I,int a); /向狀態(tài)集合中添加新元素      int TAdd(int I);          /狀態(tài)矩陣T中加入新狀態(tài)集合      void Resault(int i);  

10、    void Nfa_Dfa();  private:      int K;              /狀態(tài)數(shù)      int TMaxMax;        

11、/狀態(tài)子集矩陣      VNode AdjListMax;         /nfa,鄰接表的數(shù)據(jù)結構存儲      VNode DfaMax;             /dfa     

12、 bool VisitedMax;      /存e-閉包結果      char AlpMax;      /字母表,0號單元用于存放個數(shù)      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 小結平時的學習需要通過實踐來檢驗，通過這次實驗我能發(fā)現(xiàn)自身存在的一些問題，并且加以改正，同時通過實驗加強了自己的動手能力，并且增強了對于正則表達式的理解，并不只在于應試方面。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) / 踩空，或者出現(xiàn)非法字符break;els

32、e if(datacurk0 != '-') /不是，進棧繼續(xù)推導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)文法的深刻認識，掌握程序實現(xiàn)文法判斷、鏈表的使用等多種問題的基本方法，進一步提高了綜合運用所學知識的能力。 3 算符優(yōu)先分析3.1 算符優(yōu)先文法 ET | E+T | E-T (注：該文法為示例，可更改） TF | T*F | T/F F(E) | i3.2 算符優(yōu)先關系

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、忽略語法變量而產(chǎn)生的錯誤，在規(guī)約時檢驗終結符是否帶了應有的操作對象。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' / 說明是有應有的操作對象，所以進行規(guī)約。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); / 要忽略變量，直接對終結符進行比較優(yōu)先級。while(si = ' ') / 跳過空格i+;k = exch(si);if( cur=k&&cur=7)tot = 0; / 規(guī)約成功，結束標記。 else if( k<0 | comcurk = '-' ) / 踩空或者輸入非法符tot = -1; else if( comcurk != '>&#

41、39; ) / 遇到>'，準備規(guī)約if(statot = 'N') / 這里一個小問題就是變量N是要在'<'左邊還是右邊呢，這要取決于終結符是什么，左右兩邊有幾個變量，不過針對本程序方法，只需全部放在右邊。statot = comcurk;sta+tot = 'N'else sta+tot = comcurk;sta+tot =si+;else if( (tot = confirm( sta,tot )=0 ) /檢驗終結符是否帶了應有的變量。沒有，就規(guī)約失敗 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 小結通過這次課程設計，我發(fā)現(xiàn)之前沒發(fā)現(xiàn)的問題。算符優(yōu)先分析方法有一定的局限性由于算符優(yōu)先分析法去掉了單非終結符之間的歸約，盡管在分析過程中，當決定是否為句柄時采取一些檢查措施，但仍難完全避免把錯誤的句子得到正確的歸約。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