LL文法語法分析-編譯原理課程設計

1、湖北大學本科課程設計 題 目 LL(1)文法語法分析 課 程 編譯原理 姓 名 劉歡 學 號 2007221104210519專業(yè)年級 計算機科學與技術2007級 指導教師 張萬山 職 稱 2010年 1 月 8日摘 要選題要求：根據(jù)某一文法編制調試LL(1) 文法語法分分析程序，以便對任意輸入的符號串進行分析。本次課程設計的目的主要是加深對預測分析LL(1)文法語法分析法的理解。具體如下：1、對語法規(guī)則有明確的定義；2、編寫的分析程序能夠對給定文法進行正確的語法分析；3、對輸入給定的文法，手工計算FIRST、FOLLOW集合和select集合，應能判斷識別是否為給定文法的句子，并給出推導過程

2、。4、對輸入給定的文法，由程序自動構造FIRST、FOLLOW集合和select集合。5、對于遇到的語法錯誤，能夠做出簡單的錯誤處理，給出簡單的錯誤提示，保證順利完成語法分析過程?！娟P鍵詞】LL(1)文法 語法分析 FIRST FOLLOW select 目錄 TOC o 1-3 h z u HYPERLINK l _Toc250827577 摘 要 PAGEREF _Toc250827577 h I HYPERLINK l _Toc250827578 目錄 PAGEREF _Toc250827578 h II HYPERLINK l _Toc250827579 1系統(tǒng)分析 PAGEREF _

3、Toc250827579 h 1 HYPERLINK l _Toc250827580 選題要求 PAGEREF _Toc250827580 h 1 HYPERLINK l _Toc250827581 預期目標 PAGEREF _Toc250827581 h 1 HYPERLINK l _Toc250827582 2系統(tǒng)設計 PAGEREF _Toc250827582 h 2 HYPERLINK l _Toc250827583 基本設計 PAGEREF _Toc250827583 h 2 HYPERLINK l _Toc250827584 程序流程圖 PAGEREF _Toc250827584

4、h 4 HYPERLINK l _Toc250827585 3系統(tǒng)實現(xiàn) PAGEREF _Toc250827585 h 5 HYPERLINK l _Toc250827586 上機編程 PAGEREF _Toc250827586 h 5 HYPERLINK l _Toc250827587 運行結果 PAGEREF _Toc250827587 h 8 HYPERLINK l _Toc250827588 讀入ll(1)文法 PAGEREF _Toc250827588 h 9 HYPERLINK l _Toc250827589 優(yōu)化ll(1)文法 PAGEREF _Toc250827589 h 9

5、HYPERLINK l _Toc250827590 找出各終結符的First和Follow集 PAGEREF _Toc250827590 h 10 HYPERLINK l _Toc250827591 找出各產生式的Select集 PAGEREF _Toc250827591 h 10 HYPERLINK l _Toc250827592 填寫分析表 PAGEREF _Toc250827592 h 10 HYPERLINK l _Toc250827593 語法分析 PAGEREF _Toc250827593 h 11 HYPERLINK l _Toc250827594 完成 PAGEREF _Toc

6、250827594 h 11 HYPERLINK l _Toc250827595 4總結與感想 PAGEREF _Toc250827595 h 12 HYPERLINK l _Toc250827596 參考文獻 PAGEREF _Toc250827596 h 131系統(tǒng)分析選題要求根據(jù)某一文法編制調試LL(1) 文法語法分分析程序，以便對任意輸入的符號串進行分析。本次課程設計的目的主要是加深對預測分析LL(1)文法語法分析法的理解。預期目標構造LL(1)文法語法分析程序，任意輸入一個文法符號串，并判斷它是否為文法的一個句子。程序要求為該文法構造預測分析表，并按照預測分析算法對輸入串進行語法分析

7、，判別程序是否符合已知的語法規(guī)則，如果不符合（編譯出錯），則輸出錯誤信息。2系統(tǒng)設計基本設計在這個源程序中涉及到以下種重要數(shù)據(jù)結構：圖1 隊列結構圖圖2 堆棧結構圖圖3 產生式結構圖圖4 存儲First或Follow集的結構圖圖5 表結構圖程序流程圖開始讀入ll(1)文法文件，并顯示出所有讀取的產生式優(yōu)化并顯示新的產生式找出并顯示各非終結符的First集找出各產生式的Select集構造并顯示分析表進行語法分析，判斷是否匹配？結束YN找出并顯示各非終結符的Follow集輸入待分析的字符串顯示分析過程是否繼續(xù)分析下一條句子？NY3系統(tǒng)實現(xiàn)（出于篇幅考慮，此處僅列出核心語法分析代碼）#include

8、 #include #include #define maxlen 13#define idle 5 /用來代表的字符 /*產生式*struct Fl_Node;typedef struct Fl_Node *Fl_PNode;struct Fl_Node/存儲FIRST集與FoLLOW集的終結符 char info; Fl_PNode link;struct Jo_F_Node;typedef struct Jo_F_Node *Jo_F_PNode;struct Jo_F_Node/存儲FIRST集與FoLLOW集的結點(非終結符) Jo_F_PNode link; char F; Fl_

9、PNode next;struct LinkF_F/存儲FIRST集與FoLLOW集的頭 Jo_F_PNode knot;typedef struct LinkF_F *PLinkF_F;struct Pr_Node;typedef struct Pr_Node *Pr_PNode;struct Pr_Node/存儲產生式 char head; /超能力存儲這是個大問題，用到靜態(tài)存儲時，一定要給它分配足夠的空間 char infomaxlen+1;/為什么在這里我只定義了9個，在底下它卻具有存儲11個的能力 Fl_PNode fl; Pr_PNode link;struct Jo_P_Node

10、;typedef struct Jo_P_Node *Jo_P_PNode;struct Jo_P_Node/存儲產生式的結點 Jo_P_PNode link; short num; Pr_PNode next;struct LinkLead/產生式結點的頭部 Jo_P_PNode knot;typedef struct LinkLead *PLinkLead;/*/*隊列*struct Q_Node;typedef struct Q_Node *Q_PNode;struct Q_Node char info; Q_PNode link;struct LinkQueue Q_PNode f;

11、Q_PNode r;typedef struct LinkQueue *PLinkQueue;/*/*堆棧*struct S_Node;typedef struct S_Node *S_PNode;struct S_Node char info; S_PNode link;struct LinkStack S_PNode top;typedef struct LinkStack *PLinkStack;/*/*表格*struct T_Node;typedef struct T_Node *T_PNode;struct T_Node char row; char column; char inf

12、omaxlen; T_PNode down; T_PNode right;struct LinkTable T_PNode tab;typedef struct LinkTable *PLinkTable;/*bool judgeQueue_link(PLinkQueue plqu,char x)/判斷字符x有無在隊列plqu中 Q_PNode p; p = plqu-f; while(p) if(p-info = x) return true; p = p-link; return false;void push_link(PLinkStack plstack,char x)/進棧 S_PN

13、ode p; p = (S_PNode)malloc(sizeof(struct S_Node); if(p = NULL) printf(空間申請失敗!n); else p-info = x; p-link = plstack-top; plstack-top = p; void push_str_link(PLinkStack plstack,char x)/將分析串x存入plstack堆棧中,要求從字符串的尾部開始進棧 short i = 0; S_PNode p; while(xi != 0) i+; while(-i) = 0) p = (S_PNode)malloc(sizeof(

14、struct S_Node); if(p = NULL) printf(空間申請失敗!n); else p-info = xi; p-link = plstack-top; plstack-top = p; void print_result(PLinkTable pltable,PLinkStack plst1,PLinkStack plst2) short i=1,k,j; char smaxlen;/ S_PNode p1,p2; void pop_link(PLinkStack plstack); char top_link(PLinkStack plstack); void prin

15、tStackStr(short m,short n); void printConStack_link(PLinkStack plstack); void push_str_link(PLinkStack plstack,char x); printf(步驟 分析棧 );/); p2 = plst2-top; k = 0; while(p2) k+; p2 = p2-link; if(k10) printStackStr(10,k); printf(剩余輸入串 推導所用產生式或匹配n); /C語言里允許使用函數(shù)名相同,但參數(shù)不同的兩函數(shù)同時存在 while(plst1-top-link | t

16、op_link(plst1) != #) if(itop; j = 0; while(p1) j+; p1 = p1-link; printStackStr(j,12); printf( ); p2 = plst2-top; j = 0; while(p2) j+; p2 = p2-link; if(k10) printStackStr(j,k); else printStackStr(j,10); /插入若干空格（取個） printStack_link(plst2); printf( ); if(top_link(plst1) = top_link(plst2) printf(“%c”匹配,

17、top_link(plst1); pop_link(plst1); pop_link(plst2); else strcpy(s,findTable_link(pltable,top_link(plst1),top_link(plst2); if(s0 = 0) printf(nn有錯n); printf(剩余輸入串“); printStack_link(plst2); printf(”用此產生式組無法推出nn); return; else if(!strcmp(s,)/注意在這邊不能用s0 = 來作為判斷條件 printf(%c%c%c%c%c,top_link(plst1),161,250

18、,166,197); /： ： pop_link(plst1); else printf(%c%s,top_link(plst1),s); pop_link(plst1); push_str_link(plst1,s); printf(n); i+; if(top_link(plst1) = #) if(i10) printStackStr(1,k); else printf( ); printf(# 接受nn); else printf(nn在推導過程中出現(xiàn)問題nn); void main() while(true) scanf(%s,s_t); getchar(); t = 0; whil

19、e(s_tt != 0) /判斷數(shù)組s_t里有無非法字符 if(!judgeQueue_link(plqu2,s_tt) printf(對不起,你所輸入的符號串中不能由之前的文件里的文法得出n); break; t+; if(t != 0 & s_tt = 0) break; printf(nn請另輸入一個待分析的字符串:n); if(s_tt-1 != #) printf( 你輸入的分析字符串沒有以“#”作為結束標志；n系統(tǒng)自動在分析字符串后加上“#”nn); push_link(plstack2,#); /將分析串存入plstack2堆棧中 push_str_link(plstack2,s

20、_t); print_result(pltable,plstack1,plstack2); 該程序是在以下編寫的，里面沒有用到C+的知識，純C編寫的代碼.在運行之前，先將要分析的文法寫入一個文本文檔*.txt里，如：SAABDDiBDDBCEE+CEEC)A*C(注意：只有這里用到兩個符號與，其中在特殊符號里、在希臘字母里，此處將上面這樣的產生式組存放在eq.txt這個文本文檔里作為示例。下面顯示語法分析進行個步驟。讀入ll(1)文法開始運行后，根據(jù)提示輸入文件名“”后按Enter鍵繼續(xù)，顯示如下:優(yōu)化ll(1)文法按任意鍵繼續(xù)，顯示如下：找出各終結符的First和Follow集按任意鍵繼續(xù)，顯示如下：3.2.4找出各產生式的Select集按任意鍵繼續(xù)，顯示如下：3.2.5填寫分析表按任意鍵繼續(xù)，顯示如下：3.2.6語法分析按提示，輸入待分析的句子，按Enter鍵繼續(xù)，顯示如下：3.2.7完成 按提示，輸入y，分析下一條句子；或者輸入n，結束，分別顯示如下：4總結與感想因為要考試的原因，所有想盡快把這個課程設計做完，可是越急越容易出錯，做起來很不順手，特別是編程的時候，雖然借鑒了幾篇類似的試驗或課程設計，但完成這一設計仍不是一件簡單的事情。在設計過程中主要遇到以下兩個問題：1數(shù)據(jù)結構問題。在此程序中，用到隊列，堆棧等形式的數(shù)據(jù)結構，各節(jié)點鏈接復雜