編譯原理實(shí)驗(yàn)報(bào)告5-語(yǔ)法分析程序的設(shè)計(jì)(2)

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

2、; Sk:=#;REPEAT 把下一個(gè)輸入符號(hào)讀進(jìn)a中； IF SkVT THEN j:=k ELSE j:=k-1; WHILE Sj a DO BEGIN REPEAT Q:=Sj; IF Sj-1VT THEN j:=j-1 ELSE j:=j-2 UNTIL Sj Q 把Sj+1Sk歸約為某個(gè)N； k:=j+1; Sk:=N; END OF WHILE; IF Sj a OR Sj a THEN BEGIN k:=k+1;Sk:=a END ELSE ERROR UNTIL a=# 1、 根據(jù)給出算法，利用適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)算符優(yōu)先分析程序；2、 利用算符優(yōu)先分析程序完成下列功能：1）

3、 手工將測(cè)試的表達(dá)式寫入文本文件，每個(gè)表達(dá)式寫一行，用“；”表示結(jié)束；2） 讀入文本文件中的表達(dá)式；3） 調(diào)用實(shí)驗(yàn)2中的詞法分析程序搜索單詞；4） 把單詞送入算法優(yōu)先分析程序，判斷表達(dá)式是否正確（是否是給出文法的語(yǔ)言），若錯(cuò)誤，應(yīng)給出錯(cuò)誤信息；5） 完成上述功能，有余力的同學(xué)可以對(duì)正確的表達(dá)式計(jì)算出結(jié)果。 四、實(shí)驗(yàn)環(huán)境PC微機(jī)DOS操作系統(tǒng)或 Windows 操作系統(tǒng)Turbo C 程序集成環(huán)境或 Visual C+ 程序集成環(huán)境 五、實(shí)驗(yàn)步驟1、 分析文法中終結(jié)符號(hào)的優(yōu)先關(guān)系；2、 存放優(yōu)先關(guān)系或構(gòu)造優(yōu)先函數(shù)；3、利用算符優(yōu)先分析的算法編寫分析程序；4、寫測(cè)試程序，包括表

4、達(dá)式的讀入和結(jié)果的輸出；5、程序運(yùn)行效果，測(cè)試數(shù)據(jù)可以參考下列給出的數(shù)據(jù)。 六、測(cè)試數(shù)據(jù) 輸入數(shù)據(jù)：編輯一個(gè)文本文文件expression.txt，在文件中輸入如下內(nèi)容：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é)果：（1）10;輸出：正確（2）1+2;輸出：正確（3）(1+2)*3+(5+6*7); 輸出：正確（4）(1+2)*3+4輸出：錯(cuò)誤（5）1+2+3+(*4+5)輸出：錯(cuò)誤（6）(a+b)*(c+d)輸出：正確（7）(ab3+de4)*5)+1輸出：錯(cuò)誤七、實(shí)驗(yàn)報(bào)告

5、要求實(shí)驗(yàn)報(bào)告應(yīng)包括以下幾個(gè)部分：1、 給定文法優(yōu)先關(guān)系和存放方式；+*()i#+ *(e1)e2e2 ie2e2#e3e4引入“#”，將句型包含起來(lái)并填入出錯(cuò)標(biāo)記。使用二維數(shù)組將其存放。2、 算符優(yōu)先分析程序的算法和結(jié)構(gòu)；程序從文本文件中逐行讀取表達(dá)式，每行以“；”做標(biāo)記。調(diào)用詞法分析程序?qū)⑦@行數(shù)據(jù)分析出由一個(gè)個(gè)的單詞組成的表達(dá)式，再逐個(gè)分析單詞。另外，由于文法中沒寫入關(guān)于標(biāo)識(shí)符和常數(shù)的產(chǎn)生式，所以在對(duì)單詞符號(hào)進(jìn)行語(yǔ)法分析時(shí)，會(huì)將標(biāo)識(shí)符和常數(shù)自動(dòng)規(guī)約為“i”。數(shù)據(jù)結(jié)構(gòu)：優(yōu)先關(guān)系表R：二維數(shù)組，存儲(chǔ)了終結(jié)符+、*、（、）、i、#的優(yōu)先關(guān)系。符號(hào)W：結(jié)構(gòu)體，有四個(gè)成員，包括：ch：char類型，非

6、終結(jié)符與終結(jié)符的字符標(biāo)記；po：int類型，只對(duì)終結(jié)符有效，與在R中的位置有關(guān)，有詞法分析器提供；對(duì)于非終結(jié)符，其po無(wú)效；val：string類型，綜合屬性；對(duì)終結(jié)符i，其值由詞法分析器提供；對(duì)非終結(jié)符，其值由規(guī)約時(shí)對(duì)應(yīng)的產(chǎn)生式的規(guī)則計(jì)算得到；對(duì)界符或運(yùn)算符，val無(wú)效；type：int類型，標(biāo)記屬性值類型，0為標(biāo)識(shí)符，不可計(jì)算；1為可計(jì)算的數(shù)值；由詞法分析器提供；注意：程序內(nèi)部數(shù)值的計(jì)算和標(biāo)記一律使用十進(jìn)制，文本中的表達(dá)式必須為十進(jìn)制整數(shù)，即如果在文本中使用八進(jìn)制或十六進(jìn)制，詞法分析器分析后不會(huì)添加至緩沖區(qū)，在表達(dá)式語(yǔ)法正確且其中不含標(biāo)志符時(shí)，計(jì)算得到的結(jié)果一律使用十進(jìn)制。例：對(duì)于文本中十

7、進(jìn)制數(shù)字10，其對(duì)應(yīng)的初始結(jié)構(gòu)體成員的值ch=i，po=5，val=”10”，type=1。符號(hào)棧S：符號(hào)結(jié)構(gòu)體的一維數(shù)組。算法：說明 ：GE E->T|E+T; T->F|T*F; F->i|(E);算符優(yōu)先文法并未對(duì)非終結(jié)符定義優(yōu)先關(guān)系，無(wú)法對(duì)單非產(chǎn)生式進(jìn)行規(guī)約，所以實(shí)際上在規(guī)約時(shí)，上面的E->T，T->F基本沒有使用，而且規(guī)約時(shí)并不嚴(yán)格按照產(chǎn)生式的右部規(guī)約，只要待規(guī)約項(xiàng)符合句型#N1a1N2a2NnanNn+1#（每個(gè)ai都是終結(jié)符，Ni是可有可無(wú)的非終結(jié)符），并且相對(duì)產(chǎn)生式，在相同位置有相同的非終結(jié)符即可規(guī)約，這樣算符優(yōu)先文法規(guī)約很快，但有些語(yǔ)法錯(cuò)誤將無(wú)法

8、識(shí)別，在本實(shí)驗(yàn)中，只要在要規(guī)約的地方準(zhǔn)確的判斷可規(guī)約的項(xiàng)，即符合句型，在不嚴(yán)格要求非終結(jié)符相同而終結(jié)符位置符號(hào)相同時(shí)，存在可匹配文法的產(chǎn)生式，即可規(guī)約，例如：F * F 可以匹配T*F繼而規(guī)約為T。定義用Wch表示字符名為ch的符號(hào)；實(shí)際程序中關(guān)于終結(jié)符優(yōu)先關(guān)系的比較是利用R獲取優(yōu)先關(guān)系標(biāo)志的，算法中為了可讀性，直接將結(jié)構(gòu)體進(jìn)行比較了。從文本文件讀入一行數(shù)據(jù)，反復(fù)調(diào)用scanP()得到符號(hào)集合，用符號(hào)結(jié)構(gòu)體數(shù)組E存儲(chǔ)；k = 1; i = 0;Sk = W#;Do A = Ei+;if（Sk 是終結(jié)符）j = k;elsej = k 1;while(Sj > A) Do Q = Sj;I

9、f(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#);程序功能說明： 程序從文本文件讀入表達(dá)式，判斷語(yǔ)法是否正確，正確則輸出結(jié)果，其中有標(biāo)識(shí)符的話，結(jié)果還是含有標(biāo)識(shí)符的原表達(dá)式，語(yǔ)法錯(cuò)誤的話，則輸出錯(cuò)誤信息。源程序：程序中文本文件在桌面文件名為expression.txt#include<iostream>#inclu

10、de<string>#include<stdlib.h>using namespace std;#define NULL 0#define MAXSIZE 30/單行表達(dá)式的符號(hào)總數(shù)最大值typedef struct grammar_symbol/文法符號(hào)char ch;int po;string val;int type;W;char pre66 = /優(yōu)先關(guān)系表 '>', '<', '<', '>', '<','>' , '&g

11、t;', '>', '<', '>', '<', '>' , '<', '<', '<', '=', '<', '1' , '>', '>', '2', '>', '2', '>' , '>', '>

12、9;, '2', '>', '2', '>' , '<', '<', '<', '3', '<', '=' ;char GetChar(FILE* fp) /讀取文件中的一個(gè)字符char ch;ch = fgetc(fp);return ch;char GetBC(FILE* fp) /讀取文件的字符直至ch不是空白char ch;do ch = GetChar(fp); while (ch = &#

13、39; ' | ch = 't' | ch = 'n');return ch;void Concat(char ch, char strToken) /將ch中的字符連接到strToken之后char str2;int len = strlen(strToken);strTokenlen = ch;strTokenlen + 1 = '0'int IsLetter(char ch) /布爾函數(shù)，判斷ch中的字符是否為字母,是返回1，否則返回0int flag = 0;if (ch >= 'a' &&

14、ch <= 'z')flag = 1;return flag;int IsDigit(char ch) /布爾函數(shù)，判斷ch中的字符是否為數(shù)字,是返回1，否則返回0int flag = 0;if (ch >= '0' && ch <= '9')flag = 1;return flag;int Reserve(char strToken) /整型函數(shù)，對(duì)strToken中的字符串查找保留字表，若它是一個(gè)保留字則返回它的編碼，否則返回0int code = 0, i;char keyWord66 = "if

15、", "then", "else", "while", "do" ;for (i = 0; i < 5; i+) if (strcmp(strToken, keyWordi) = 0) code = i + 1;break;return code;int SearchOP(char ch) /整型函數(shù)，對(duì)strToken中的字符串查找運(yùn)算符和界符，若它是一個(gè)運(yùn)算符或界符，則返回它的編碼，否則返回0int code = 0, i;char OP10 = '+', '*'

16、,' (', ')', '-', '/', '<', '>', '=', '' ;for (i = 0; i < 10; i+) if (ch = OPi) code = i + 1;break;return code;char Retract(FILE* fp, char ch) /子函數(shù)，將搜索指示器回調(diào)一個(gè)字符位置，將ch置為空白字符ch = ' 'fseek(fp, -1L, 1);return ch;void ProErro

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

18、 IsDigit(ch) Concat(ch, strToken);ch = GetChar(fp);ch = Retract(fp, ch);if (Reserve(strToken) /判斷關(guān)鍵字printf("<%s,->n", strToken);else /判斷標(biāo)識(shí)符printf("%s", strToken);w.ch = 'i'w.po = 4;w.val = strToken;w.type = 0;Enum = w;else if (ch >= '1' && ch <

19、= '9') /判斷十進(jìn)制整數(shù)while (IsDigit(ch) Concat(ch, strToken);ch = GetChar(fp);ch = Retract(fp, ch);printf("%s", strToken);w.ch = 'i'w.po = 4;w.val = strToken;w.type = 1;Enum = w;else if (ch = '0') ch = GetChar(fp);if (ch >= '1' && ch <= '7')

20、/判斷八進(jìn)制整數(shù)while (ch >= '0' && ch <= '7') Concat(ch, strToken);ch = GetChar(fp);ch = Retract(fp, ch);printf("<2,%s>n", strToken);else if (ch = 'x') /判斷十六進(jìn)制整數(shù)ch = GetChar(fp);while (IsDigit(ch) | ch >= 'a' && ch <= 'f')

21、Concat(ch, strToken);ch = GetChar(fp);ch = Retract(fp, ch);printf("<3,%s>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) /判斷運(yùn)算符和界符printf("%c", ch);int po =

22、SearchOP(ch) - 1;w.ch = ch;w.po = po;Enum = w;else /出錯(cuò)ProError();return 1;bool checkVt(char ch) bool flag = false;int i;char Vt6 = '+', '*', '(', ')', 'i', '#' ;for (i = 0; i < 6; i+) if (ch = Vti) flag = true;return flag;W Statute(W* S, int s, int

23、e) /規(guī)約子函數(shù)，將S中j+1到k的符號(hào)規(guī)約為NW N;if (Ss.ch = 'i' && s = e) N.ch = 'F'N.val = Ss.val;N.type = Ss.type;else if (Ss.ch = '(' && !(checkVt(Ss + 1.ch) && Se.ch = ')') if (Ss + 1.type = 1) N.ch = 'F'N.val = Ss + 1.val;N.type = Ss + 1.type;else N.

24、ch = 'F'N.val = '('+ Ss + 1.val + ')'N.type = Ss + 1.type;else if (!(checkVt(Ss.ch) && Ss + 1.ch = '+' && !(checkVt(Se.ch) N.ch = 'E'if (Ss.type = 1 && Se.type = 1) N.type = 1;int v = atoi(Ss.val.data() + atoi(Se.val.data();char l30;spr

25、intf_s(l,30,"%d", v);N.val = l;else N.type = 0;N.val = Ss.val + Ss + 1.ch + Se.val;else if (s != e) && !(checkVt(Ss.ch) && Ss + 1.ch = '*' && !(checkVt(Se.ch) N.ch = 'T'if (Ss.type = 1 && Se.type = 1) N.type = 1;int v = atoi(Ss.val.data() * a

26、toi(Se.val.data();char l30;sprintf_s(l, 30,"%d", v);N.val = l;else N.type = 0;N.val = Ss.val + Ss + 1.ch + Se.val;else if(Ss.ch = 'T' && s = e)N.ch = 'E'N.val = Ss.val;N.type = Ss.type;else N.ch = '#'N.po = 4;return N;void error(char errnum) /錯(cuò)誤處理子函數(shù)if (errn

27、um = '1') printf("錯(cuò)誤，非法左括號(hào)nn");else if(errnum = '2')printf("錯(cuò)誤，缺少運(yùn)算符nn");else if (errnum = '3')printf("錯(cuò)誤，非法右括號(hào)nn");else if (errnum = '4')printf("錯(cuò)誤，缺少表達(dá)式nn");int syntax(W* E,int num) /算法對(duì)應(yīng)的主要實(shí)現(xiàn)程序W SMAXSIZE;int k = 1, i = 0, j;W

28、 border, A, Q;border.ch = '#'border.po = 5;Enum = border;Sk = border;do A = Ei+;if (checkVt(Sk.ch)/判斷Sk是終結(jié)符j = k;elsej = k - 1;while (preSj.poA.po = '>') 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 (

29、N.ch = '#') 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

30、* fp;errno_t err;if (err = fopen_s(&fp,"C:UsersAdministratorDesktopexpression.txt", "r") != NULL) /以只讀方式打開文件，失敗則退出程序printf("file can not open!");exit(0);int n = 0;printf("語(yǔ)法分析結(jié)果如下：nn");while (!feof(fp) /若不是文件尾則執(zhí)行循環(huán)int num = 0;W EMAXSIZE;/存儲(chǔ)一行表達(dá)式GetBC(fp);if (!feof(fp) n+;fs