遞歸下降語法分析程序設(shè)計

1、精選文檔編譯方法 實 驗 報 告實驗名稱：簡單的語法分析程序設(shè)計實驗要求1. 功能：對簡單的賦值語句進行語法分析隨機輸入賦值語句，輸出所輸入的賦值語句與相應(yīng)的四元式2. 采用遞歸下降分析程序完成（自上而下的分析）3. 確定各個子程序的功能并畫出流程圖4. 文法如下：5. 編碼、調(diào)試通過采用標(biāo)準(zhǔn)輸入輸出方式。輸入輸出的樣例如下：【樣例輸入】x:=a+b*c/d-(e+f)【樣例輸出】(說明，語句和四元式之間用5個空格隔開)T1:=b*c     (*,b,c,T1)T2:=T1/d     (/,T1,d,T2)T3:=a+T2    

2、  (+,a,T2,T3)T4:=e+f     (+,e,f,T4)T5:=T3-T4     (-,T3,T4,T5)x:=T5     (:=,T5,-,x)  【樣例說明】程序除能夠正確輸出四元式外，當(dāng)輸入的表達式錯誤時，還應(yīng)能檢測出語法錯誤，給出相應(yīng)錯誤提示。6. 設(shè)計3-5個賦值語句測試實例，檢驗程序能否輸出正確的四元式；當(dāng)輸入錯誤的句子時，檢驗程序能夠給出語法錯誤的相應(yīng)提示信息。7. 報告內(nèi)容包括：遞歸程序的調(diào)用過程，各子程序的流程圖和總控流程圖，詳細(xì)設(shè)計，3-5個測試用例的程序運行截圖及相

3、關(guān)說明，有詳細(xì)注釋的程序代碼清單等。目錄1.語法分析遞歸下降分析算法51.1背景知識51.2消除左遞歸62.詳細(xì)設(shè)計及流程圖62.1 函數(shù)void V( ) / V -> a|b|c|d|e.|z62.2 函數(shù)void A( ) / A -> V:=E72.3 函數(shù)void E() /E -> TE'72.4函數(shù)void T( ) / T -> FT'82.5函數(shù)void E1( ) /E'-> +TE'|-TE'|null82.6函數(shù)void T1() / T'-> *FT'|/FT'|nul

4、l93.測試用例及截圖93.1測試用例1及截圖93.2測試用例2及截圖103.3測試用例3及截圖11代碼清單111.語法分析遞歸下降分析算法1.1背景知識無回溯的自上向下分析技術(shù)可用的先決條件是：無左遞歸和無回溯。 無左遞歸：既沒有直接左遞歸，也沒有間接左遞歸。無回溯：對于任一非終結(jié)符號U的產(chǎn)生式右部x1|x2|xn，其對應(yīng)的字的首終結(jié)符號兩兩不相交。如果一個文法不含回路，也不含以為右部的產(chǎn)生式，那么可以通過執(zhí)行消除文法左遞歸的算法消除文法的一切左遞歸（改寫后的文法可能含有以為右部的產(chǎn)生式）。文法的左遞歸消除算法： 1、將文法G的所有非終結(jié)符排序為U1 ,U2 , ,Un; 2、For(i=1

5、；i+；in) for j1 to i-1 把產(chǎn)生式UiUj替換成Ui1| 2|m； 其中：Uj 1| 2 | |m 消除Ui產(chǎn)生式中的直接左遞歸； 3.化簡改寫之后的文法，刪除多余產(chǎn)生式。文法的直接左遞歸消除公式： 直接左遞歸形式：UUx|y； 其中：x，y（VNVT）* ，y不以U打頭。 直接左遞歸的消除： UyU UxU| 直接左遞歸的一般形式：UUx1|Ux2|Uxm|y1|y2|yn； 其中：xi ,yi都不以U打頭。 一般形式直接左遞歸的消除: Uy1U| y2U | ynUUx1U| x2U| | xmU| 回溯的消除的前提是文法不得含有左遞歸，可提左因子來消除回溯。1.2消除左

6、遞歸根據(jù)實驗中給出的文法，進行消除左遞歸及回溯，得到下列的式子A -> V:=EE -> TE'E'-> +TE'|-TE'|nullT -> FT'T'-> *FT'|/FT'|nullF -> V|(E)V -> a|b|c|d|e.|z2.詳細(xì)設(shè)計及流程圖根據(jù)消除左遞歸后的文法，可以編寫相應(yīng)的函數(shù)。2.1 函數(shù)void V( ) / V -> a|b|c|d|e.|zvoid V() / V -> a|b|c|d|e.|z函數(shù)設(shè)計主要用來識別小寫字母的，如果是小寫字母的話

7、，放入字符表，不是的話，輸出語法錯誤。函數(shù)比較簡單，代碼如下：if(islower(ssym)Tablelist_n0 = ssym; /把讀取的小寫字母存入符號表，便于分析是生成中間代碼Tablelist_n1 = '0'list_n+;sym+;elseprintf("Operand Errors!n"); /運算對象錯誤SIGN=1;exit(0);2.2 函數(shù)void A( ) / A -> V:=Evoid A() / A -> V:=E 函數(shù)主要用來實現(xiàn)賦值的操作，流程圖如圖1所示。 圖1 A( ) 函數(shù)流程圖2.3 函數(shù)void E

8、() /E -> TE'函數(shù)E（）里面主要遞歸調(diào)用函數(shù)T( )和E'( )。當(dāng)沒有出現(xiàn)語法錯誤時就可正常的運行。函數(shù)比較簡單，代碼如下：if(SIGN=0)T();E1();2.4函數(shù)void T( ) / T -> FT'函數(shù)T( )里面主要遞歸調(diào)用函數(shù)F ( )和T''( )。當(dāng)沒有出現(xiàn)語法錯誤時就可正常的運行。函數(shù)比較簡單，代碼如下：if(SIGN=0)F();T1();2.5函數(shù)void E1( ) /E'-> +TE'|-TE'|null函數(shù)void E1() /E'-> +TE'

9、|-TE'|null，主要用來實現(xiàn)加減法的語義分析。流程圖如圖2所示。 圖2 E1 ( ) 函數(shù)流程圖2.6函數(shù)void T1() / T'-> *FT'|/FT'|null函數(shù)void T1() / T'-> *FT'|/FT'|null，主要用來實現(xiàn)乘除法的語義分析。流程圖如圖3所示。 圖3 T1 ( ) 函數(shù)流程圖3.測試用例及截圖3.1測試用例1及截圖 用例1為實驗要求上的的用例。測試結(jié)果圖4所示。 圖4 測試用例1及結(jié)果截圖3.2測試用例2及截圖 用例2為出現(xiàn)大寫字母，出現(xiàn)報錯。測試結(jié)果圖5所示。 圖5 測試用例2及

10、結(jié)果截圖3.3測試用例3及截圖 用例3為隨意編寫用例。測試結(jié)果圖6所示。 圖6 測試用例3及結(jié)果截圖代碼清單#include<stdio.h>#include<stdlib.h>#include<string.h>#include <ctype.h>void A(); / A -> V:=Evoid E(); / E -> TE'void T(); / T -> FT'void E1(); / E'-> +TE'|-TE'|nullvoid T1(); / T'-> *

11、FT'|/FT'|nullvoid F(); / F -> V|(E)void V(); / V -> a|b|c|d|e.|zchar s50,n='1' /s50用于存放輸入的賦值表達式char Table503; /產(chǎn)生中間代碼所需的符號表int SIGN,sym; /sym為s50中當(dāng)前讀入符號的下標(biāo)int list_n=0; /符號表的下標(biāo)/*消除左遞歸及回溯A -> V:=EE -> TE'E'-> +TE'|-TE'|nullT -> FT'T'-> *FT&

12、#39;|/FT'|nullF -> V|(E)V -> a|b|c|d|e.|z*/int main()SIGN = 0; /SIGN用于指示賦值表達式是否出現(xiàn)錯誤sym=0;scanf("%s",&s);if( s0 = '0') /沒有輸入的情況直接退出return 0;A();if(ssym!='0'&&SIGN=0)printf("ERROR!n");exit(0);return 0;void A() / A -> V:=EV();if(ssym=':&#

13、39;&&ssym+1='=') /判斷賦值號是否有拼寫錯誤sym+=2;E();printf("%s:=%s",Tablelist_n-2,Tablelist_n-1);printf(" (:=,%s,-,%s)n",Tablelist_n-1,Tablelist_n-2);elseprintf("The assignment Symbol spelling mistakes!n"); /賦值號拼寫錯誤SIGN=1;exit(0);void V() / V -> a|b|c|d|e.|zif(i

14、slower(ssym)Tablelist_n0 = ssym; /把讀取的小寫字母存入符號表，便于分析是生成中間代碼Tablelist_n1 = '0'list_n+;sym+;elseprintf("Operand Errors!n"); /運算對象錯誤SIGN=1;exit(0);void E() /E -> TE'if(SIGN=0)T();E1();void T() / T -> FT'if(SIGN=0)F();T1();void E1() /E'-> +TE'|-TE'|nullint

15、p;if(SIGN=0)if(ssym = '+'|ssym='-')p=sym; /用p記錄出現(xiàn)'+'或'-'時sym的值sym+;T();char ch3;ch0 = 'T'ch1 = n; ch2 = '0' if(sp = '+') printf("%s:=%s+%s",ch,Tablelist_n-2,Tablelist_n-1); /輸出三地址代碼printf(" (+,%s,%s,%s)n", Tablelist_n-2,Tabl

16、elist_n-1,ch); /輸出四元式elseprintf("%s:=%s-%s",ch,Tablelist_n-2,Tablelist_n-1); /輸出三地址代碼printf(" (-,%s,%s,%s)n", Tablelist_n-2,Tablelist_n-1,ch); /輸出四元式strcpy(Tablelist_n-2,ch); /將當(dāng)前結(jié)果歸結(jié)式放在符號表中l(wèi)ist_n-;n+;E1(); void T1() / T'-> *FT'|/FT'|null int p;if(SIGN=0)if(ssym =

17、'*'|ssym='/')p=sym; sym+;F();char ch3;ch0 = 'T' ch1 = n;ch2 = '0'if(sp = '*') printf("%s:=%s*%s",ch,Tablelist_n-2,Tablelist_n-1); /輸出三地址代碼printf(" (*,%s,%s,%s)n", Tablelist_n-2,Tablelist_n-1,ch);/輸出四元式elseprintf("%s:=%s/%s",ch,Tablelist_n-2,Tablelist_n-1); /輸出三地址代碼printf(" (/,%s,%s,%s)n", Tablelist_n-2,Tablelist_n-1,ch);/輸出四元式 strcpy(Tabl