編譯原理實驗報告5-語法分析程序的設(shè)計

1、-. z.實驗5 語法分析程序的設(shè)計2一、實驗?zāi)康耐ㄟ^設(shè)計、編制、調(diào)試一個典型的語法分析程序，實現(xiàn)對詞法分析程序所提供的單詞序列進(jìn)展語法檢查和構(gòu)造分析，進(jìn)一步掌握常用的語法分析中算法優(yōu)先分析方法。二、實驗容設(shè)計一個文法的算法優(yōu)先分析程序，判斷特定表達(dá)式的正確性。三、實驗要求1、給出文法如下： GE E-T|E+T; T-F|T*F; F-i|(E);可以構(gòu)造算符優(yōu)先表如下：+*()i+*()i2、計算機中表示上述優(yōu)先關(guān)系，優(yōu)先關(guān)系的機存放方式有兩種1直接存放，2為優(yōu)先關(guān)系建立優(yōu)先函數(shù)，這里由學(xué)生自己選擇一種方式；給出算符優(yōu)先分析算法如下：k:=1; Sk:=#;REPEAT 把下一個輸入符號讀

2、進(jìn)a中；IF SkVT THEN j:=k ELSE j:=k-1;WHILE Sj a DOBEGINREPEATQ:=Sj;IF Sj-1VT THEN j:=j-1 ELSE j:=j-2UNTIL Sj Q 把Sj+1Sk歸約為*個N；k:=j+1;Sk:=N;END OF WHILE; IF Sj a OR Sj a THENBEGINk:=k+1;Sk:=aENDELSE ERRORUNTIL a=#根據(jù)給出算法，利用適當(dāng)?shù)臄?shù)據(jù)構(gòu)造實現(xiàn)算符優(yōu)先分析程序；利用算符優(yōu)先分析程序完成以下功能：手工將測試的表達(dá)式寫入文本文件，每個表達(dá)式寫一行，用；表示完畢；讀入文本文件中的表達(dá)式；調(diào)用實驗

3、2中的詞法分析程序搜索單詞；把單詞送入算法優(yōu)先分析程序，判斷表達(dá)式是否正確是否是給出文法的語言，假設(shè)錯誤，應(yīng)給出錯誤信息；完成上述功能，有余力的同學(xué)可以對正確的表達(dá)式計算出結(jié)果。四、實驗環(huán)境PC微機DOS操作系統(tǒng)或 Windows 操作系統(tǒng)Turbo C 程序集成環(huán)境或 Visual C+ 程序集成環(huán)境五、實驗步驟分析文法中終結(jié)符號的優(yōu)先關(guān)系；存放優(yōu)先關(guān)系或構(gòu)造優(yōu)先函數(shù)；3、利用算符優(yōu)先分析的算法編寫分析程序；4、寫測試程序，包括表達(dá)式的讀入和結(jié)果的輸出；5、程序運行效果，測試數(shù)據(jù)可以參考以下給出的數(shù)據(jù)。六、測試數(shù)據(jù) 輸入數(shù)據(jù)：編輯一個文本文文件e*pression.t*t，在文件中輸入如下容

4、：10;1+2;(1+2)*3+(5+6*7);(1+2)*3+4;1+2+3+(*4+5);(a+b)*(c+d);(ab3+de4)*5)+1;正確結(jié)果：110;輸出：正確21+2;輸出：正確3(1+2)*3+(5+6*7);輸出：正確4(1+2)*3+4輸出：錯誤51+2+3+(*4+5)輸出：錯誤6(a+b)*(c+d)輸出：正確7(ab3+de4)*5)+1輸出：錯誤七、實驗報告要求實驗報告應(yīng)包括以下幾個局部：給定文法優(yōu)先關(guān)系和存放方式；+*()i#+*(e1)e2e2 ie2e2#e3e4引入#，將句型包含起來并填入出錯標(biāo)記。使用二維數(shù)組將其存放。算符優(yōu)先分析程序的算法和構(gòu)造；程序

5、從文本文件中逐行讀取表達(dá)式，每行以；做標(biāo)記。調(diào)用詞法分析程序?qū)⑦@行數(shù)據(jù)分析出由一個個的單詞組成的表達(dá)式，再逐個分析單詞。另外，由于文法中沒寫入關(guān)于標(biāo)識符和常數(shù)的產(chǎn)生式，所以在對單詞符號進(jìn)展語法分析時，會將標(biāo)識符和常數(shù)自動規(guī)約為i。數(shù)據(jù)構(gòu)造：優(yōu)先關(guān)系表R：二維數(shù)組，存儲了終結(jié)符+、*、i、#的優(yōu)先關(guān)系。符號W：構(gòu)造體，有四個成員，包括：ch：char類型，非終結(jié)符與終結(jié)符的字符標(biāo)記；po：int類型，只對終結(jié)符有效，與在R中的位置有關(guān)，有詞法分析器提供；對于非終結(jié)符，其po無效；val：string類型，綜合屬性；對終結(jié)符i，其值由詞法分析器提供；對非終結(jié)符，其值由規(guī)約時對應(yīng)的產(chǎn)生式的規(guī)則計算得

6、到；對界符或運算符，val無效；type：int類型，標(biāo)記屬性值類型，0為標(biāo)識符，不可計算；1為可計算的數(shù)值；由詞法分析器提供；注意：程序部數(shù)值的計算和標(biāo)記一律使用十進(jìn)制，文本中的表達(dá)式必須為十進(jìn)制整數(shù)，即如果在文本中使用八進(jìn)制或十六進(jìn)制，詞法分析器分析后不會添加至緩沖區(qū)，在表達(dá)式語確且其中不含標(biāo)志符時，計算得到的結(jié)果一律使用十進(jìn)制。例：對于文本中十進(jìn)制數(shù)字10，其對應(yīng)的初始構(gòu)造體成員的值ch=i，po=5，val=10，type=1。符號棧S：符號構(gòu)造體的一維數(shù)組。算法：說明 ：GE E-T|E+T; T-F|T*F; F-i|(E);算符優(yōu)先文法并未對非終結(jié)符定義優(yōu)先關(guān)系，無法對單非產(chǎn)生式

7、進(jìn)展規(guī)約，所以實際上在規(guī)約時，上面的E-T，T-F根本沒有使用，而且規(guī)約時并不嚴(yán)格按照產(chǎn)生式的右部規(guī)約，只要待規(guī)約項符合句型#N1a1N2a2NnanNn+1#每個ai都是終結(jié)符，Ni是可有可無的非終結(jié)符，并且相對產(chǎn)生式，在一樣位置有一樣的非終結(jié)符即可規(guī)約，這樣算符優(yōu)先文法規(guī)約很快，但有些語法錯誤將無法識別，在本實驗中，只要在要規(guī)約的地方準(zhǔn)確的判斷可規(guī)約的項，即符合句型，在不嚴(yán)格要求非終結(jié)符一樣而終結(jié)符位置符號一樣時，存在可匹配文法的產(chǎn)生式，即可規(guī)約，例如：F * F 可以匹配T*F繼而規(guī)約為T。定義用Wch表示字符名為ch的符號；實際程序中關(guān)于終結(jié)符優(yōu)先關(guān)系的比擬是利用R獲取優(yōu)先關(guān)系標(biāo)志的，

8、算法中為了可讀性，直接將構(gòu)造體進(jìn)展比擬了。從文本文件讀入一行數(shù)據(jù)，反復(fù)調(diào)用scanP()得到符號集合，用符號構(gòu)造體數(shù)組E存儲；k=1;i= 0;Sk = W#;DoA = Ei+;ifSk 是終結(jié)符j = k;elsej = k 1;while(Sj A) Do Q = Sj;If(Sj - 1 是終結(jié)符)j = j 1;elsej = j 2;while(Sj Q);N = Statute(S,j + 1,k);k = j + 1；Sk = N；If(Sj A | Sj = A) k+;Sk = A;else error(Sj.po,A.po);while(A = W#);程序功能說明：程序

9、從文本文件讀入表達(dá)式，判斷語法是否正確，正確則輸出結(jié)果，其中有標(biāo)識符的話，結(jié)果還是含有標(biāo)識符的原表達(dá)式，語法錯誤的話，則輸出錯誤信息。源程序：程序中文本文件在桌面文件名為e*pression.t*t#include#include#includeusing namespace std;#define NULL 0#define MA*SIZE 30/單行表達(dá)式的符號總數(shù)最大值typedef struct grammar_symbol/文法符號char ch;int po;string val;int type;W;char pre66 = /優(yōu)先關(guān)系表 , , , , , , , , , ,

10、, =, , , 2, , 2, , , , 2, , 2, , , , , 3, = a & ch = 0 & ch = 9)flag = 1;return flag;int Reserve(char strToken) /整型函數(shù)，對strToken中的字符串查找保存字表，假設(shè)它是一個保存字則返回它的編碼，否則返回0int code = 0, i;char keyWord66 = if, then, else, while, do ;for (i = 0; i 5; i+) if (strcmp(strToken, keyWordi) = 0) code = i + 1;break;ret

11、urn code;int SearchOP(char ch) /整型函數(shù)，對strToken中的字符串查找運算符和界符，假設(shè)它是一個運算符或界符，則返回它的編碼，否則返回0int code = 0, i;char OP10 = +, *, (, ), -, /, , =, ; ;for (i = 0; i 10; i+) if (ch = OPi) code = i + 1;break;return code;char Retract(FILE* fp, char ch) /子函數(shù)，將搜索指示器回調(diào)一個字符位置，將ch置為空白字符ch = ;fseek(fp, -1L, 1);return c

12、h;void ProError() /錯誤處理函數(shù)printf(輸入錯誤！n);return;int scan(FILE* fp,W* E,int num) W w;char ch;char strToken10;strToken0 = 0;/置strToken為空串ch = GetBC(fp); /先讀取一個非空白的字符if (feof(fp)return 0;if (ch = ;)printf(;);return 0;/判斷表達(dá)式尾，是則返回調(diào)用程序if (IsLetter(ch) /判斷標(biāo)識符while (IsLetter(ch) | IsDigit(ch) Concat(ch, str

13、Token);ch = GetChar(fp);ch = Retract(fp, ch);if (Reserve(strToken) /判斷關(guān)鍵字printf(n, strToken);else /判斷標(biāo)識符printf(%s, strToken);w.ch = i;w.po = 4;w.val = strToken;w.type = 0;Enum = w;else if (ch = 1 & ch = 1 & ch = 0 & ch = 7) Concat(ch, strToken);ch = GetChar(fp);ch = Retract(fp, ch);printf(n, strToke

14、n);else if (ch = *) /判斷十六進(jìn)制整數(shù)ch = GetChar(fp);while (IsDigit(ch) | ch = a & ch = f) Concat(ch, strToken);ch = GetChar(fp);ch = Retract(fp, ch);printf(n, strToken);else /判斷十進(jìn)制的0ch = Retract(fp, ch);printf(0);w.ch = i;w.po = 4;w.val = 0;w.type = 0;Enum = w;else if (SearchOP(ch) != 0) /判斷運算符和界符printf(%

15、c, ch);int po = SearchOP(ch) - 1;w.ch = ch;w.po = po;Enum = w;else /出錯ProError();return 1;bool checkVt(char ch) bool flag = false;int i;char Vt6 = +, *, (, ), i, # ;for (i = 0; i ) do Q = Sj;if (checkVt(Sj - 1.ch)j = j - 1;elsej = j - 2; while (preSj.poQ.po != );W N = Statute(S, j + 1, k);if (N.ch =

16、 #) error(4);return 0;k = j + 1;Sk = N;if (preSj.poA.po = | preSj.poA.po = =) k+;Sk = A;else error(preSj.poA.po);return 0; while (A.ch != #);if (A.ch = #) printf(正確，結(jié)果為：%snn, Sk - 1.val.data();return 0;int main() FILE* fp;errno_t err;if (err = fopen_s(&fp,C:UsersAdministratorDesktope*pression.t*t, r

17、) != NULL) /以只讀方式翻開文件，失敗則退出程序printf(file can not open!);e*it(0);int n = 0;printf(語法分析結(jié)果如下：nn);while (!feof(fp) /假設(shè)不是文件尾則執(zhí)行循環(huán)int num = 0;W EMA*SIZE;/存儲一行表達(dá)式GetBC(fp);if (!feof(fp) n+;fseek(fp, -1L, 1);printf(%d), n);else break;while (1) /只讀一行，行末標(biāo)志為；int flag = scan(fp, E,num);if (flag = 0)break;num+;p

18、rintf(n輸出：);synta*(E,num);fclose(fp); /關(guān)閉文件fp = NULL;/防止指向非法存程序運行流程；輸入表達(dá)式到文本程序開場是否是文件尾讀取一行文本否調(diào)用synta*()判斷語法是否正確輸出結(jié)果是否輸出錯誤返回退出程序是程序的測試結(jié)果和問題；實驗報告源數(shù)據(jù)：其它數(shù)據(jù)：問題：實驗時是根據(jù)實驗報告提供的算法編程的，但是原算法使用了類似Pascal的語言，而我用的是C，算法實現(xiàn)時具體的語法不同，例如Pascal的repeatuntil與C語言的dowhile并一樣，實驗時不注意會使程序出錯，二者的循環(huán)條件是相反的。編程時，誤將終結(jié)符數(shù)組的左右括號輸入成了中文的括號，導(dǎo)致在判斷是否為終結(jié)符時，英文的左右括號無法與中文的括號匹配，程序出現(xiàn)了錯誤，雖然調(diào)試時很容易就發(fā)現(xiàn)了，但這樣的細(xì)節(jié)問題不應(yīng)該費時間要調(diào)試才解決，這提醒我編程時更應(yīng)該認(rèn)真仔細(xì)，效率才能得到保證。另外，語法錯誤時，這一行表達(dá)式的分析就可以直接終止但此時程序是在兩層循環(huán)里面，只有跳出這兩層循環(huán)才會終止，而break則只能跳出一層，假設(shè)在最后一層使用標(biāo)志，再跳出一層，這就導(dǎo)致之后的每一行都會多做一次判斷，而我又不想使用goto，所以最后我決定使用子函數(shù)，將語法分析的主要程序段放在子函數(shù)中，有語法錯