編譯原理C語法分析器

1、課程設(shè)計報告課程名稱：編譯原理課程設(shè)計題目：語法分析器姓 名：系：計算機專 業(yè)：計算機科學(xué)與技術(shù)年 級：2009級學(xué) 號：指導(dǎo)教師：職 稱：20102011學(xué)年第一學(xué)期評語：成績：指導(dǎo)教師簽字：任務(wù)下達日期：評定日期：目 錄1 正則表達式11.1 正則表達式11.2 確定化(化簡)后的狀態(tài)轉(zhuǎn)換圖11.3 分析程序代碼11.4 程序運行截圖41.5 小結(jié)42 LL(1)分析52.1 LL(1)文法52.2 LL(1)預(yù)測分析表52.3 分析程序代碼52.4 程序運行截圖72.5 小結(jié)73 算符優(yōu)先分析83.1 算符優(yōu)先文法83.2 算符優(yōu)先關(guān)系表83.3 分析程序代碼83.4 程序運行截圖103

2、.5 小結(jié)114 LR分析124.1 LR文法124.2 LR分析表124.3 分析程序代碼124.4 程序運行截圖144.5 小結(jié)14參考文獻：141 正則表達式1.1 正則表達式 (a|b)*(aa|bb)(a|b)* (注：該正規(guī)式為示例，可更改）1.2 確定化(化簡)后的狀態(tài)轉(zhuǎn)換圖 1.3 分析程序代碼 #include <iostream>  #include <string>  using namespace std;    const&#

3、160;int Max=20;                 typedef struct ArcNode      int adjvex;/該弧所指向的頂點的位置      char info;  /權(quán)   

4、;   struct ArcNode *nextarc;/指向下一條弧的指針  ArcNode;  typedef struct VNode      char data;                  /頂點信息  

5、;    ArcNode *firstarc;          /指向第一條依附該頂點的弧的指針  VNode;    class Nfa    public:      Nfa();      /構(gòu)造函數(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弧轉(zhuǎn)換      void move(int I,char a);  /重載的狀態(tài)集合的a弧轉(zhuǎn)換      void Nfa:Visit_I(int *Temp); /Visited轉(zhuǎn)換為集合 &#

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ù)結(jié)構(gòu)存儲      VNode DfaMax;             /dfa     

12、 bool VisitedMax;      /存e-閉包結(jié)果      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 小結(jié)平時的學(xué)習(xí)需要通過實踐來檢驗，通過這次實驗我能發(fā)現(xiàn)自身存在的一些問題，并且加以改正，同時通過實驗加強了自己的動手能力，并且增強了對于正則表達式的理解，并不只在于應(yīng)試方面。2 LL(1)分析2.1 LL(1)文法 ETE' (注：該文法為示例，可更改） E'+TE'| TFT' T'*FT'| F(E)|i2.2 LL(1)預(yù)測分析表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; /字符串結(jié)束標(biāo)志代表'

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) / 推導(dǎo)出相同字符，出棧k=exch(s+i);else if(k < 0 | datacurk0 = 0) / 踩空，或者出現(xiàn)非法字符break;els

32、e if(datacurk0 != '-') /不是，進棧繼續(xù)推導(dǎo)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 小結(jié) 實踐實踐驗證里的唯一標(biāo)準，這次課程設(shè)計主要鞏固了我對LL(1)文法的深刻認識，掌握程序?qū)崿F(xiàn)文法判斷、鏈表的使用等多種問題的基本方法，進一步提高了綜合運用所學(xué)知識的能力。 3 算符優(yōu)先分析3.1 算符優(yōu)先文法 ET | E+T | E-T (注：該文法為示例，可更改） TF | T*F | T/F F(E) | i3.2 算符優(yōu)先關(guān)系

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; /字符串結(jié)束標(biāo)志代表# default: return -1;char expre65="N+N","N-N","N*N","N/N","(=N)","i" /為了挽回因

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

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