算術(shù)表達(dá)式的語(yǔ)法及語(yǔ)義分析程序設(shè)計(jì).doc

算術(shù)表達(dá)式的語(yǔ)法及語(yǔ)義分析程序設(shè)計(jì)概述1.1設(shè)計(jì)題目算術(shù)表達(dá)式的語(yǔ)法及語(yǔ)義分析程序設(shè)計(jì)。1.2設(shè)計(jì)目的通過(guò)設(shè)計(jì)、編制、調(diào)試一個(gè)算術(shù)表達(dá)式的語(yǔ)法及語(yǔ)義分析程序，加深對(duì)語(yǔ)法語(yǔ)義分析原理的理解，并實(shí)現(xiàn)詞法分析程序?qū)卧~序列的詞法檢查和分析。1.3設(shè)計(jì)任務(wù)內(nèi)容(1)利用遞歸下降分析方法和思想對(duì)某些語(yǔ)句進(jìn)行語(yǔ)法分析與語(yǔ)義分析，生成相應(yīng)的中間代碼。(2)學(xué)會(huì)正確運(yùn)用語(yǔ)法規(guī)則，并能應(yīng)用所學(xué)的方法解決存在的問(wèn)題，給出語(yǔ)法分析方法及中間代碼形式的描述、文法和屬性文法的設(shè)計(jì)。2設(shè)計(jì)環(huán)境與工具本課程設(shè)計(jì)程序采用VC+開(kāi)發(fā)，其可執(zhí)行文件能在Window界面上運(yùn)行良好。3設(shè)計(jì)原則3.1語(yǔ)法分析方法采用遞歸下降分析方法進(jìn)行語(yǔ)法分析。3.2中間代碼形式描述在描述中間代碼的時(shí)候，應(yīng)用四元式。3.3文法和屬性文法設(shè)計(jì)算術(shù)表達(dá)式的文法：無(wú)符號(hào)整數(shù) 數(shù)字?jǐn)?shù)字標(biāo)識(shí)符 字母字母數(shù)字表達(dá)式項(xiàng)加法運(yùn)算符項(xiàng)項(xiàng) 因子乘法運(yùn)算符因子因子 標(biāo)識(shí)符無(wú)符號(hào)整數(shù)（表達(dá)式）加法運(yùn)算符 乘法運(yùn)算符 4簡(jiǎn)要分析與概要設(shè)計(jì)4.1簡(jiǎn)要分析首先應(yīng)該把用文字表示的文法改寫(xiě)為數(shù)學(xué)符號(hào)。（其中關(guān)于無(wú)符號(hào)整數(shù)和標(biāo)識(shí)符，由于可以在詞法分析的過(guò)程中給以確定，所以就不必抽象其表達(dá)式。）設(shè)：indentifer：標(biāo)識(shí)符digit :無(wú)符號(hào)整數(shù)E：表達(dá)式T：項(xiàng)F：因子則一個(gè)簡(jiǎn)單的術(shù)表達(dá)式的文法G1中包含以下產(chǎn)生式：E - E+E | E-E | E*E | E/E | (E) | indentifer | digit為了明確運(yùn)算符的優(yōu)先權(quán)（括號(hào)的優(yōu)先權(quán)高于乘除法，乘除法的優(yōu)先權(quán)高于加減法），可改寫(xiě)文法G1如下：改寫(xiě)后的文法G2:E - E+T | E-T | TT - T*F | T/F | FF - (E) |indentifer | digit為了避免左遞歸的發(fā)生，可進(jìn)一步將文法改成：文法GE：（1）E - +|-TG（2）G - +TG|TG（3）G -（4）T - FS（5）S - *FS|/FS（6）S -（7）F - (E)（8）F - indentifer | digit4.2概要設(shè)計(jì)由于程序在執(zhí)行的過(guò)程中分為詞法、語(yǔ)法、語(yǔ)義，故在程序設(shè)計(jì)的時(shí)候也按照這種方式，把整個(gè)程序分成三個(gè)大的部分，即詞法分析部分，語(yǔ)法分析部分和語(yǔ)義分析部分。而且在各個(gè)部分的內(nèi)部采用模塊化設(shè)計(jì)，再分成各個(gè)小塊，各自完成其相對(duì)應(yīng)的功能。5源程序清單void yuyi_main()/語(yǔ)義分析主函數(shù)cifa_p = cifa_head;yuyi_head = new yuyi;yuyi_head - next = NULL;yuyi_end = yuyi_head;coutnext);cout語(yǔ)義分析產(chǎn)生的四元式如下：endl;coutendl-endl;advance();E1();yuyi_sys_disp();coutendl-語(yǔ)義分析結(jié)束-endl;/*主函數(shù)*void main()/主函數(shù)int len;int f=1;coutendl請(qǐng)輸入一個(gè)算術(shù)表達(dá)式(請(qǐng)?jiān)谝恍袃?nèi)完成輸入且每個(gè)項(xiàng)的長(zhǎng)度不大于10)：endl;gets(str);len = strlen(str);strlen = ;coutendl;system(pause);coutendl;cout*詞法分析開(kāi)始*endl;f = cifa_main();if ( f = 0 ) return;coutendl;system(pause);coutendl;cout*語(yǔ)法分析開(kāi)始*endl;f = yufa_main();if (f= 0) return;coutendl;system(pause);coutendl;cout*語(yǔ)義分析開(kāi)始*endl;yuyi_main();coutendl;system(pause);cout (E) | 標(biāo)識(shí)符 | 無(wú)符號(hào)整數(shù)if (strcmp(cifa_p-word,() = 0 ) )advance();strcpy(F_name,cifa_p-word);strcpy(E_name,F_name);E1();if (strcmp(cifa_p-word,) = 0 ) )advance();strcpy(F_name,E_name);return (1);elsecoutERRORtype = 1 | cifa_p-type = 2)strcpy(F_name,cifa_p-word);advance();return (1);else return 0;int T1()/T - F*T | F/T | Fyuyi *p = new yuyi;F1();strcpy(p-op1,F_name);if (strcmp(cifa_p-word,*) = 0)advance();T1();p-next =NULL;p-op = *;strcpy(p-op2,T_name);T_name0 = t;T_name1 = +count;T_name2 = 0;strcpy(p-result,T_name);yuyi_add(p);return(1);else if (strcmp(cifa_p-word,/) = 0)advance();T1();p-next =NULL;p-op = /;strcpy(p-op2,T_name);T_name0 = t;T_name1 = +count;T_name2 = 0;strcpy(p-result,T_name);yuyi_add(p);return(1);elsestrcpy(T_name,F_name);return(1);int E1()/E - T+E | T-E | Tyuyi *p = new yuyi;T1();strcpy(p-op1,T_name);if (strcmp(cifa_p-word,+) = 0)advance();E1();p-next =NULL;p-op = +;strcpy(p-op2,E_name);E_name0 = t;E_name1 = +count;E_name2 = 0;strcpy(p-result,E_name);yuyi_add(p); return (1);else if (strcmp(cifa_p-word,-) = 0)advance();E1();p-next =NULL;p-op = -;strcpy(p-op2,E_name);E_name0 = t;E_name1 = +count;E_name2 = 0;strcpy(p-result,E_name);yuyi_add(p);return(1);elsestrcpy(E_name,T_name);return(1);int yufa_main() /語(yǔ)法分析主程序int n;cifa *p = new cifa;strcpy(p - word ,#);/對(duì)詞法分析產(chǎn)生的結(jié)果鏈表進(jìn)行處理p - type =-1;p - next = NULL;cifa_add(p);cifa_p = cifa_head;coutnext);cout的遞歸分析過(guò)程如下：endl;coutendl-endl;coutt步驟tt產(chǎn)生式endl;advance();n = E();if (n = 0)couttftt輸入串不是該文法的一個(gè)句子！endl;coutendl-語(yǔ)法分析結(jié)束-endl;return (0);else if (n = 1)couttftt輸入串是該文法的一個(gè)句子！endl;coutendl-語(yǔ)法分析結(jié)束-next = p ;yuyi_end = p;return yuyi_head;void yuyi_sys_disp() /輸出四元式鏈表yuyi *p;p = yuyi_head-next;while(p!=NULL)cout(top,top1,top2,tresultt)next;cout (E) | 標(biāo)識(shí)符 | 無(wú)符號(hào)整數(shù) 子函數(shù)int m;if (strcmp(cifa_p-word,() = 0 ) )couttf+tt (E)word,) = 0 ) )advance();return (1);elsecoutERRORtype = 1 | cifa_p-type = 2)/數(shù)字或是標(biāo)識(shí)符couttf+tt 標(biāo)識(shí)符|無(wú)符號(hào)整數(shù) *FS | /FS | 子函數(shù)int t,g;if (strcmp(cifa_p-word,*) = 0)couttf+tt *FSword,/) = 0)couttf+tt /FSword,+) = 0 |(strcmp(cifa_p-word,-) = 0)|(strcmp(cifa_p-word,#) = 0)|(strcmp(cifa_p-word,) = 0)couttf+tt FS 子函數(shù)int t,g;couttf+tt FSword,+) = 0)couttf+tt +TGword,-) = 0)couttf+tt -TGword,) = 0 | strcmp(cifa_p-word,#) = 0)couttf+tt +|-TG 子函數(shù)int t,g;if (strcmp(cifa_p-word,+) = 0)| (strcmp(cifa_p-word,-) = 0) advance();couttf+tt +|-TGendl;t = T();if (t = 0) return (0);g = G();if (g = 0) return (0);else return (1);void yufa_zfc_disp(cifa *p) /輸出字符串while(p!=NULL)coutword ;p = p-next;/cout next;int test(void) /識(shí)別相關(guān)符號(hào)char temp3;int i=0;int type;switch (ch)case ; :/識(shí)別 ;tempi+ = ch;GetChar();if (ch = ) tempi+ = ;tempi = 0;type = 4;break;case + :/識(shí)別 +tempi+ = ch;GetChar();if (ch = ) tempi+ = ;tempi = 0;type = 3;break;case - :/識(shí)別 -tempi+ = ch;GetChar();if (ch = ) tempi+ = ;tempi = 0;type = 3;break;case * :/識(shí)別 *tempi+ = ch;GetChar();if (ch = )tempi+ = ;tempi = 0;type = 3;break;case / :/識(shí)別 /tempi+ = ch;GetChar();if (ch = )tempi+ = ;tempi = 0;type = 3;break;case ( :/識(shí)別 (tempi+ = ch; GetChar();if (ch = )tempi+ = ;tempi = 0;type = 4;break;case ) :/ 識(shí)別)tempi+ = ch; GetChar();if (ch = )tempi+ = ; tempi = 0;type = 4; break;default :coutch;cout無(wú)法識(shí)別，出錯(cuò)！ next = NULL;p - type = type;strcpy(p-word,temp);cifa_add(p);return (1);int cifa_main()/詞法分析主函數(shù)int f;cifa_head = new cifa;cifa_head - type = -1;cifa_head - next = NULL;cifa_end = cifa_head;cout單詞種類(lèi)定義如下：endlendl;cout標(biāo)識(shí)符的種類(lèi)編碼 1 :endlendl;cout常數(shù)的種類(lèi)編碼 2 :endlendl;cout運(yùn)算的種類(lèi)編碼 3 :+ ,- ,* ,/ endlendl;cout界限符的種類(lèi)編碼 4 : (,),;endl;GetChar();notock();cout-endl詞法分析結(jié)果如下：endl;while ( nn = a & ch = A & ch = 0 & ch = 9) f=number(); /數(shù)字串 else f=test();/其他符號(hào)if (f = 0) return (0);cifa_disp(cifa_head);coutendl-詞法分析結(jié)束-endl;return (1);int number(void) /識(shí)別數(shù)字int type=2; int i=0;char temp10; while(0= ch & ch = 9) tempi = ch;i+;GetChar(); tempi=0;if (ch = ) notock(); else if (ch != & ch != + & ch != - & ch != ; & ch != * & ch != / & ch != (& ch != ) couttemp接錯(cuò)誤后綴，出錯(cuò) next = NULL;p - type = type;strcpy(p-word,temp);cifa_add(p);return (1);int alph(void) /識(shí)別標(biāo)識(shí)符int i=0;char temp10;int type = 1;tempi = ch;i+;GetChar();while (ch = a & ch = A & ch = 0 & ch = 9)tempi = ch;i+;GetChar();tempi = 0;if (ch = ) notock(); else if (ch != & ch != + & ch != - & ch != ; &ch != * & ch != / & ch != (& ch != ) couttemp接錯(cuò)誤后綴，出錯(cuò) next = NULL;p - type = type;strcpy(p-word,temp);cifa_add(p);return (1);cifa *cifa_add(cifa *p)/在分析結(jié)果列表尾添加一個(gè)新接點(diǎn)cifa_end - next = p;cifa_end = cifa_end - next;return cifa_head;void cifa_disp(cifa *cifa_head)/輸出詞法分析結(jié)果cifa *p;p = cifa_head - next ;while ( p != NULL)cout(ttypet,twordt)next;void GetChar()/取字符ch = strnn;nn+;void notock()/去掉空格if ( ch = )while ( ch = )GetChar();char E_name10,T_name10,F_name10,temp_name10;/在求四元式的時(shí)候用來(lái)傳遞信息yuyi *yuyi_add(yuyi *p); /在四元式鏈表末添加一個(gè)結(jié)點(diǎn)void yuyi_sys_disp(); /輸出四元式鏈表int E1();/E - T+E | T-E | Tint T1();/T - F*T | F/T | Fint F1();/F - (E) | 標(biāo)識(shí)符 | 無(wú)符號(hào)整數(shù)void yuyi_main();/語(yǔ)義分析主函數(shù)/*詞法分析部分*/*語(yǔ)義分析部分?jǐn)?shù)據(jù)結(jié)構(gòu)及函數(shù)定義*struct yuyi/語(yǔ)義結(jié)構(gòu)體char op;/操作符char op110;/第一個(gè)操作數(shù)char op210;/第二個(gè)操作數(shù)char result10;/結(jié)果yuyi *next;yuyi *yuyi_head,*yuyi_end,*yuyi_q,*yuyi_vt;/yuyi隊(duì)列/*語(yǔ)法分析部分函數(shù)定義*void advance();/取詞法分析產(chǎn)生列表中的結(jié)點(diǎn)作語(yǔ)法分析int E();/ E - +|-TG 子函數(shù)int G();/ G -+TG | -TG |子函數(shù)int T();/ T - FS 子函數(shù)int S();/ S - *FS | /FS | 子函數(shù)int F();/ F - (E) | 標(biāo)識(shí)符 | 無(wú)符號(hào)整數(shù) 子函數(shù)int yufa_main();/語(yǔ)法分析主函數(shù)cifa *cifa_add(cifa *p);/在分析結(jié)果列表尾添加一個(gè)新接點(diǎn)void cifa_disp(cifa *cifa_head);/輸出詞法分析結(jié)果void GetChar();/取字符void notock();/去掉空格int alph(void); /識(shí)別標(biāo)識(shí)符int number(void);/識(shí)別數(shù)字int test(void);/識(shí)別相關(guān)符號(hào)int cifa_main();/詞法分析主函數(shù)#include#include#include#include#include#include#include#include#include#includecharstr100;/輸入的算術(shù)表達(dá)式字符串charch;intnn=0;/字符串計(jì)數(shù)器intf=0;charcount=0;/四元式臨時(shí)變量計(jì)數(shù)器/*詞法分析部分?jǐn)?shù)據(jù)結(jié)構(gòu)及函數(shù)定義*struct cifa/詞法結(jié)構(gòu)體int type;/類(lèi)型char word10;/字符串內(nèi)容cifa *next;cifa *cifa_head,*cifa_end,*cifa_p; /cifa隊(duì)列1 語(yǔ)言子集的詞法描述：設(shè)文法GE:E := E + T | TT := T * F | FF := (E) | i2程序的功能按照文法符號(hào)（終結(jié)符和非終結(jié)符）的優(yōu)先關(guān)系確定句柄，通過(guò)不斷的歸約，或是移進(jìn)來(lái)進(jìn)行分析。3算法描述算符優(yōu)先分析的基本思想是只規(guī)定算符(廣義為終結(jié)符之間的優(yōu)先關(guān)系，也就是只考慮終結(jié)符之間的優(yōu)先關(guān)系，不考慮非終結(jié)符之間的優(yōu)先關(guān)系。在歸約過(guò)程中只要找到可歸約串就歸約，并不考慮歸約到那個(gè)非終結(jié)符名，算符優(yōu)先分析的可歸約串不一定是規(guī)范句型的句柄，所以算符優(yōu)先歸約不是規(guī)范歸約。算符優(yōu)先分析的可歸約串是當(dāng)前符號(hào)棧中的符號(hào)和剩余的輸入符號(hào)構(gòu)成句型的最左素短語(yǔ)。在上述的整個(gè)歸約過(guò)程中，起決定作用的是相鄰兩個(gè)終結(jié)符的優(yōu)先關(guān)系，所以應(yīng)用算符優(yōu)先分析法自底向上地分析句子，解決了前面提到的兩個(gè)問(wèn)題，即： 1)可以只根據(jù)相鄰運(yùn)算符的優(yōu)先關(guān)系，就能方便地并且唯一地確定歸約的“句柄”； 2)可以用來(lái)分析二義性文法所產(chǎn)生的語(yǔ)言。4源程序清單void main()cout設(shè)文法GE:endl;cout tE:=E+T|Tendl;cout tT:=T*F|Fendl;cout tF:=(E)|iendl;coutendl文法GE合法句子舉例: (i+i)* i;coutendl*endlendl;coutstr;len = strlen(str);strlen = #;coutendltt符號(hào)串str 分析過(guò)程如下：endlendl;cout-endl;cout 符號(hào)棧S t t 關(guān)系 t 輸入流 t t 最左素短語(yǔ)endl;opg();coutendlendl 按任意數(shù)字或字母鍵，回車(chē)退出!len;void opg(void)/分析過(guò)程char l=;char ch1;char lsdy4;int i=0;int p;s0 = #;cout s t t l t str ;GetChar();while ( ch != # | sm-1 != E | s3 !=