LL文法語法分析-編譯原理課程設(shè)計(jì)

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

2、。4、對(duì)輸入給定的文法，由程序自動(dòng)構(gòu)造FIRST、FOLLOW集合和select集合。5、對(duì)于遇到的語法錯(cuò)誤，能夠做出簡(jiǎn)單的錯(cuò)誤處理，給出簡(jiǎn)單的錯(cuò)誤提示，保證順利完成語法分析過程?！娟P(guān)鍵詞】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 預(yù)期目標(biāo) PAGEREF _Toc250827581 h 1 HYPERLINK l _Toc250827582 2系統(tǒng)設(shè)計(jì) PAGEREF _Toc250827582 h 2 HYPERLINK l _Toc250827583 基本設(shè)計(jì) PAGEREF _Toc250827583 h 2 HYPERLINK l _Toc250827584 程序流程圖 PAGEREF _Toc250827584

4、h 4 HYPERLINK l _Toc250827585 3系統(tǒng)實(shí)現(xiàn) PAGEREF _Toc250827585 h 5 HYPERLINK l _Toc250827586 上機(jī)編程 PAGEREF _Toc250827586 h 5 HYPERLINK l _Toc250827587 運(yùn)行結(jié)果 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 找出各終結(jié)符的First和Follow集 PAGEREF _Toc250827590 h 10 HYPERLINK l _Toc250827591 找出各產(chǎn)生式的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總結(jié)與感想 PAGEREF _Toc250827595 h 12 HYPERLINK l _Toc250827596 參考文獻(xiàn) PAGEREF _Toc250827596 h 131系統(tǒng)分析選題要求根據(jù)某一文法編制調(diào)試LL(1) 文法語法分分析程序，以便對(duì)任意輸入的符號(hào)串進(jìn)行分析。本次課程設(shè)計(jì)的目的主要是加深對(duì)預(yù)測(cè)分析LL(1)文法語法分析法的理解。預(yù)期目標(biāo)構(gòu)造LL(1)文法語法分析程序，任意輸入一個(gè)文法符號(hào)串，并判斷它是否為文法的一個(gè)句子。程序要求為該文法構(gòu)造預(yù)測(cè)分析表，并按照預(yù)測(cè)分析算法對(duì)輸入串進(jìn)行語法分析

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

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

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

10、;typedef struct Jo_P_Node *Jo_P_PNode;struct Jo_P_Node/存儲(chǔ)產(chǎn)生式的結(jié)點(diǎn) Jo_P_PNode link; short num; Pr_PNode next;struct LinkLead/產(chǎn)生式結(jié)點(diǎn)的頭部 Jo_P_PNode knot;typedef struct LinkLead *PLinkLead;/*/*隊(duì)列*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有無在隊(duì)列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)/進(jìn)棧 S_PN

13、ode p; p = (S_PNode)malloc(sizeof(struct S_Node); if(p = NULL) printf(空間申請(qǐng)失敗!n); else p-info = x; p-link = plstack-top; plstack-top = p; void push_str_link(PLinkStack plstack,char x)/將分析串x存入plstack堆棧中,要求從字符串的尾部開始進(jìn)棧 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(空間申請(qǐng)失敗!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(剩余輸入串 推導(dǎo)所用產(chǎn)生式或匹配n); /C語言里允許使用函數(shù)名相同,但參數(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); /插入若干空格（取個(gè)） 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有錯(cuò)n); printf(剩余輸入串“); printStack_link(plst2); printf(”用此產(chǎn)生式組無法推出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在推導(dǎo)過程中出現(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(對(duì)不起,你所輸入的符號(hào)串中不能由之前的文件里的文法得出n); break; t+; if(t != 0 & s_tt = 0) break; printf(nn請(qǐng)另輸入一個(gè)待分析的字符串:n); if(s_tt-1 != #) printf( 你輸入的分析字符串沒有以“#”作為結(jié)束標(biāo)志；n系統(tǒng)自動(dòng)在分析字符串后加上“#”nn); push_link(plstack2,#); /將分析串存入plstack2堆棧中 push_str_link(plstack2,s

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