學(xué)過編譯原理課程的同學(xué)應(yīng)該有體會(huì),各種文法、各種詞法語法分析算法,非常消磨人的耐心和興致;中間代碼生成和優(yōu)化,其實(shí)在很多應(yīng)用場(chǎng)景下并不重要(當(dāng)然這一塊對(duì)于“編譯原理”很重要);語義分析要處理很多很多細(xì)節(jié),特別對(duì)于比較復(fù)雜的語言;最后的指令生成,可能需要讀各種手冊(cè),也比較枯燥。
我覺得對(duì)普通的程序員來說,編譯原理里面有實(shí)際用途的,是parser和codegen,但是因?yàn)檫@兩個(gè)領(lǐng)域,到了2016年都沒什么好研究的了,而且也被搞PLT的人所鄙視,所以你們看到的那些經(jīng)典的教材,都沒有好好講。
一、 編譯程序
1、 編譯器是一種翻譯程序,它用于將源語言(即用某種程序設(shè)計(jì)語言寫成的)程序翻譯為目標(biāo)語言(即用二進(jìn)制數(shù)表示的偽機(jī)器代碼寫成的)程序。后者在windows操作系統(tǒng)平臺(tái)下,其文件的擴(kuò)展名通常為.obj。該文件通常還要經(jīng)過進(jìn)一步的連接,生成可執(zhí)行文件(機(jī)器代碼寫成的程序,文件擴(kuò)展名為.exe)。通常有兩種方式進(jìn)行這種翻譯,一種是編譯,另一種是解釋。后者并不生成可執(zhí)行文件,只是翻譯一條語句、執(zhí)行一條語句。這兩種方式相編譯比解釋運(yùn)行的速度要快得多。
2、 編譯過程的5個(gè)階段:詞法分析;語法分析;語義分析與中間代碼產(chǎn)生;優(yōu)化;目標(biāo)代碼生成。
3、 在這五個(gè)階段中,詞法分析的任務(wù)是識(shí)別源程序中的單詞是否有誤,編譯程序中實(shí)現(xiàn)這種功能的部分一般稱為詞法分析器。在編譯器中,詞法分析器通常僅作為語法分析程序的一個(gè)子程序以便在它需要單詞符號(hào)時(shí)調(diào)用。在這一編譯階段中發(fā)現(xiàn)的源程序錯(cuò)誤,稱為詞法錯(cuò)誤。
4、 語法分析階段的目的是識(shí)別出源程序的語法結(jié)構(gòu)(即語句或句子)是否錯(cuò)誤,所以有時(shí)又常為句子分析。編譯程序中負(fù)責(zé)這一功能的程序稱為語法分析器或語法分析程序。在這一階段中發(fā)現(xiàn)的錯(cuò)誤稱為語法錯(cuò)誤。
5、 C語言的(源)程序必須經(jīng)過編譯才能生成目標(biāo)代碼,再經(jīng)過鏈接才能運(yùn)行。PASCAL語言、FORTRAN語言的源程序也要經(jīng)過這樣的過程。通常將C、PASCAL、FORTRAN這樣的語言統(tǒng)稱為高級(jí)語言。而將最終的可執(zhí)行程序稱為機(jī)器語言程序。
6、 在編譯C語言程序的過程中,發(fā)現(xiàn)源程序中的一個(gè)標(biāo)識(shí)符過長(zhǎng),超過了編譯程序允許的范圍,這個(gè)錯(cuò)誤應(yīng)在詞法分析階段發(fā)現(xiàn),這種錯(cuò)誤通常被稱作詞法錯(cuò)誤。
6.1. 詞法分析器的任務(wù)是以詞法規(guī)則為依據(jù)對(duì)輸入的源程序進(jìn)行單詞及其屬性的識(shí)別,識(shí)別出一個(gè)個(gè)單詞符號(hào)。
6.2. 詞法分析的輸入是源程序,輸出是一個(gè)個(gè)單詞的特殊符號(hào),稱為Token(標(biāo)記或符號(hào))。
6.3.語法分析器的類型有:自下而上、自上而下。常用的語法分析器有:遞歸下降分析方法是一種自上而下分析方法, 算符優(yōu)先分析法屬于自下而上分析方法,LR分析法屬于自下而上分析方法等等。
6.4.通常用正規(guī)文法或正規(guī)式來描述程序設(shè)計(jì)語言的詞法規(guī)則,而使用上下文無關(guān)文法來描述程序設(shè)計(jì)語言的語法規(guī)則。
6.5.語法分析階段中,處理的輸入數(shù)據(jù)是來自詞法分析階段的單詞符號(hào)。它們是詞法分析階段的終結(jié)符。
7、 編譯程序總框
8、 在計(jì)算機(jī)發(fā)展的早期階段,內(nèi)存較小的不能一次完成程序的編譯。這時(shí)通常將編譯過程分成若干遍來完成。每一遍完成一部分功能,稱為多遍編譯。
與采用高級(jí)程序設(shè)計(jì)語言寫的詞法分析器相比,用匯編語言寫的詞法分析通常分析速度要快些。
二。 詞法與語法
1、 程序語言主要由語法和語義兩個(gè)方面來定義。
2、 任何語言的程序都可看成是某字符集上的一個(gè)長(zhǎng)字符串。
3、 語言的語法:是指這樣的一組規(guī)則(即產(chǎn)生式),用它可以生成和產(chǎn)生一個(gè)良定的程序。這些規(guī)則的一部分稱為詞法規(guī)則,另一部分稱為語法規(guī)則。
4、 詞法規(guī)則:?jiǎn)卧~符號(hào)的形成規(guī)則;語法規(guī)則:語法單位(句子)的形成規(guī)則。語義規(guī)則:定義程序句子的意義。
5、 一個(gè)程序語言的基本功能是描述數(shù)據(jù)和對(duì)數(shù)據(jù)的運(yùn)算。
6、 高級(jí)語言的分類:強(qiáng)制式語言;應(yīng)用式語言;基于規(guī)則的語言;面向?qū)ο蟮恼Z言。
7、 一個(gè)語言的字母表為{a,b},則字符串a(chǎn)b的前綴有a、ε,其中ε不是真前綴。
8、 字符串的連接運(yùn)算一般不滿足交換率。
9、 文法G是一個(gè)四元組,或者說由四個(gè)元素構(gòu)成,即非終結(jié)符集合VN、非終結(jié)符號(hào)集合VT 、開始符號(hào)S、產(chǎn)生式集合P,它可以形式化地表示成G =(VN,VT,S,P)。
按照文法的定義,這4個(gè)元素中終結(jié)符號(hào)集合是這個(gè)文法所規(guī)定的語言的字母表,產(chǎn)生式集合代表文法所規(guī)定的語言語法實(shí)體的集合。對(duì)上下文無關(guān)文法,通常我們只需要寫出這個(gè)文法的產(chǎn)生式集合就可以確定這個(gè)文法的其他所有元素。其中,第一條產(chǎn)生式的左部符號(hào)為開始符號(hào),而所有產(chǎn)生式的左部符號(hào)構(gòu)成的集合就是該文法的非終結(jié)符集合。
文法的例子:
設(shè)文法G=(VN,VT, S,P),其中P為產(chǎn)生式集合,它的每個(gè)元素的形式為產(chǎn)生式。
10、如果文法G的一個(gè)句子存在兩棵不同的最左語法分析樹,則這個(gè)文法是無二義的。
11、如果文法G的一個(gè)句子存在兩棵不同的最右語法分析樹,則這個(gè)文法是無二義的。
12、如果文法G的一個(gè)句子存在兩棵不同的語法分析樹,則這個(gè)文法是無法判斷是否是二義的。
13、A為非終結(jié)符,如果文法存在產(chǎn)生式 ,則稱 可以推導(dǎo)出 ;反之,稱 可歸約為 。
14、喬姆斯基(Chomsky)將文法分為四類,即0型文法、1文法、2文法、3文法。
按照喬姆斯基對(duì)方法的分類,上下文無關(guān)文法是2型文法,2型文法的描述能力最強(qiáng),3型文法又稱為正規(guī)文法。
15、產(chǎn)生式S→Sa | a產(chǎn)生的語言為L(zhǎng)(G) = {an | n ≥ 1}。
16、確定有限自動(dòng)機(jī)DFA是非確定有限自動(dòng)機(jī)NFA的特例;對(duì)任一非確定有限自動(dòng)機(jī)能找到一個(gè)與之等價(jià)的確定有限自動(dòng)機(jī)。
17、DFA和NFA的主要區(qū)別有三點(diǎn):一、DFA初態(tài)唯一,NFA初態(tài)不唯一;二、DFA弧標(biāo)記為Σ上的元素,NFA弧標(biāo)記為Σ*上的元素;三、DFA的函數(shù)為單射,NFA函數(shù)不是單射。
18、有限自動(dòng)機(jī)中兩個(gè)狀態(tài)S1和S2是等價(jià)的是指,無論是從S1還是S2出發(fā),停于終態(tài)時(shí),所識(shí)別的輸入字的集合相同。
19、自下而上的分析方法,是一個(gè)不斷歸約的過程。
20、遞歸下降分析器:當(dāng)一個(gè)文法滿足LL(1)條件時(shí),我們就可以為它構(gòu)造一個(gè)不帶回溯的自上而下分析程序。這個(gè)分析程序是由一組遞歸過程組成的,每個(gè)過程對(duì)應(yīng)文法的一個(gè)非終結(jié)符。
這個(gè)產(chǎn)生式中含有的左遞歸是直接左遞歸。遞歸下降分析法中,必須要消除所有的左遞歸。遞歸下降分析法中的試探分析法之所以要不斷用一個(gè)產(chǎn)生式的多個(gè)候選式進(jìn)行逐個(gè)試探,最根本的原因是這些候選式有公共左因子。
21、算符優(yōu)先分析法是一種自下而上的分析方法,它適合分析各種程序設(shè)計(jì)語中的表達(dá)式,并宜于手工實(shí)現(xiàn)。目前最廣泛的無回溯的“移進(jìn)—?dú)w約”方法是自下而上分析方法。
22、在表驅(qū)動(dòng)預(yù)測(cè)分析器中,
1)讀入一個(gè)終結(jié)符a,若該終結(jié)符與棧項(xiàng)的終結(jié)符相同,并且不是結(jié)束標(biāo)志$,則此時(shí)棧頂符號(hào)出棧;
2)若此時(shí)棧項(xiàng)符號(hào)是終結(jié)符并且是,并且讀入的終結(jié)符不是,說明源程序有語法錯(cuò)誤;
3)若此時(shí)棧頂符號(hào)為,并且讀入的終結(jié)符也是,則分析成功。
23、算符優(yōu)先分析方法不存在使用形如 這樣的產(chǎn)生式進(jìn)行的歸約,即只要求終結(jié)符的位置與產(chǎn)生式結(jié)構(gòu)一致,從而使得分析速度比LR分析法更快。
24、LR(0)的例子:
產(chǎn)生式E→ E+T對(duì)應(yīng)的LR(0)項(xiàng)目中,待歸約的項(xiàng)目是E→ E+?T,移進(jìn)項(xiàng)目是E→ E?+T,還有兩個(gè)項(xiàng)目為E→ ?E+T和E→ E+T?。
當(dāng)一個(gè)LR(0)項(xiàng)目集中含有兩個(gè)歸約項(xiàng)目時(shí),稱這個(gè)項(xiàng)目集中含有歸約-歸約沖突。
25、LL(1)文法的產(chǎn)生式中一定沒有公共左因子,即LL(1)文法中一定沒有左遞歸。為了避免回溯,在LL(1)文法的預(yù)測(cè)分析表中,一個(gè)表項(xiàng)中至多只有一個(gè)產(chǎn)生式。
預(yù)測(cè)分析方法(即LL(1)方法),由一個(gè)棧,一個(gè)總控程序和一個(gè)預(yù)測(cè)分析表組成。其中構(gòu)造出預(yù)測(cè)分析表是該分析方法的關(guān)鍵。
26、LR(0)與SLR(1)兩種分析方法相比,SLR(1)的能力更強(qiáng)。
27、靜態(tài)語義檢查一般包括以下四個(gè)部分,即類型檢查、控制流檢查、名字匹配檢查、一致性檢查。
C語言編譯過程中下述常見的錯(cuò)誤都屬于檢查的范圍:
a) 將字符型指針的值賦給結(jié)構(gòu)體類型的指針變量:類型檢查。
b)switch語句中,有兩個(gè)case語句中出現(xiàn)了相同的常量:一致性檢查。
c)break語句在既不是循環(huán)體內(nèi)、又不是break語句出現(xiàn)的地方出現(xiàn):控制流檢查。
d)goto語句中的標(biāo)號(hào)在程序的函數(shù)中沒有找到:一致性檢查。
e)同一個(gè)枚舉常量出現(xiàn)在兩個(gè)枚舉類型的定義當(dāng)中:相關(guān)名字檢查。
28、循環(huán)優(yōu)化中代碼外提是指對(duì)循環(huán)中的有些代碼,如果它產(chǎn)生的結(jié)果在循環(huán)過程中是不變的,就把它提到循環(huán)體外來;而強(qiáng)度削弱是指把程序中執(zhí)行時(shí)間較長(zhǎng)的運(yùn)算替換為執(zhí)行時(shí)間較短的運(yùn)算。
解析編譯原理主要過程
第一個(gè)編譯器由機(jī)器語言開發(fā) 然后就有了后來的各種語言寫出來的編譯器
1 編譯過程包括如下圖所示:。
2 詞法分析作用:找出單詞 。如int a=b+c; 結(jié)果為: int,a,=,b,+,c和;
3語法分析作用:找出表達(dá)式,程序段,語句等。如int a=b=c;的語法分析結(jié)果為int a=b+c這條語句。
4語義分析作用:查看類型是否匹配等。
5注意點(diǎn):詞法分析器實(shí)現(xiàn)步驟:正規(guī)式-》NFA-》簡(jiǎn)化后的DFA-》對(duì)應(yīng)程序;語法分析要用到語法樹;語義分析要用到語法制導(dǎo)。
編譯原理一般分為詞法分析,語法分析,語義分析和代碼優(yōu)化及目標(biāo)代碼生成等一系列過程。下面我們結(jié)合來了解一下:
本程序可以同時(shí)在BC和Visual C++下運(yùn)行。我測(cè)試過了的。下面先將代碼貼給大家。其中如果你只想先了解詞法分析部分,你可以將其余的注釋就可以。我建議大家學(xué)習(xí)時(shí)一步一步來,從詞法分析學(xué),然后學(xué)語法分析。其他的就類似了。
如果你在DOS下運(yùn)行,由于使用了漢字,請(qǐng)將其自行換成英文方便您的識(shí)別。
程序中的解釋就是編譯的基本原理。如果還不清楚建議大家看孫悅紅的編譯原理及實(shí)現(xiàn)清華的。
#include 《stdio.h》
#include 《ctype.h》
#include 《conio.h》
#include “stdio.h”
//下面定義保留,為簡(jiǎn)化程序,使用字符指針數(shù)組保存所有保留字。
//如果想增加保留字,可繼續(xù)添加,并修改保留字?jǐn)?shù)目
#define keywordSum 8
#define maxvartablep 500//定義符號(hào)表的容量
char *keyword[keywordSum]={ “if”,“else”,“for”,“while”,“do”,“int”,“read”,“write”};
//下面定義純單分界符,如需要可添加
char singleword[50]=“+-*(){};,:”;
//下面定義雙分界符的首字符
char doubleword[10]=“》《=!”;
//函數(shù)調(diào)用
int TESTparse();
int program();
int compound_stat();
int statement();
int expression_stat();
int expression();
int bool_expr();
int additive_expr();
int term();
int factor();
int if_stat();
int while_stat();
int for_stat();
int write_stat();
int read_stat();
int declaration_stat();
int declaration_list();
int statement_list();
int compound_stat();
int name_def(char *name);
char token[20],token1[40];//token保存單詞符號(hào),token1保存單詞值
char Scanout[300],Codeout[300]; //保存詞法分析輸出文件名
FILE *fp,*fout; //用于指向輸入輸出文件的指針
struct{//定義符號(hào)表結(jié)構(gòu)
char name[8];
int address;
}vartable[maxvartablep];//改符號(hào)表最多容納maxvartablep個(gè)記錄
int vartablep=0,labelp=0,datap=0;
int TESTscan();
char Scanin[300],Errorfile[300]; //用于接收輸入輸出以及錯(cuò)誤文件名
FILE *fin; //用于指向輸入輸出文件的指針
int TESTscan()//詞法分析函數(shù)
{
char ch,token[40]; //ch為每次讀入的字符,token用于保存識(shí)別出的單詞
int es=0,j,n; //es錯(cuò)誤代碼,0表示沒有錯(cuò)誤。j,n為臨時(shí)變量,控制組合單詞時(shí)的下標(biāo)等
printf(“請(qǐng)輸入源程序文件名(包括路徑):”);
scanf(“%s”,Scanin);
printf(“請(qǐng)輸入詞法分析輸出文件名(包括路徑):”);
scanf(“%s”,Scanout);
if ((fin=fopen(Scanin,“r”))==NULL) //判斷輸入文件名是否正確
{
printf(“/n打開詞法分析輸入文件出錯(cuò)!/n”);
return(1);//輸入文件出錯(cuò)返回錯(cuò)誤代碼1
}
if ((fout=fopen(Scanout,“w”))==NULL) //判斷輸出文件名是否正確
{
printf(“/n創(chuàng)建詞法分析輸出文件出錯(cuò)!/n”);
return(2); //輸出文件出錯(cuò)返回錯(cuò)誤代碼2
}
ch=getc(fin);
while(ch!=EOF)
{
while (ch==‘ ’||ch==‘/n’||ch==‘/t’) ch=getc(fin);
if (ch==EOF) break;
if (isalpha(ch)) //如果是字母,則進(jìn)行標(biāo)識(shí)符處理
{
token[0]=ch; j=1;
ch=getc(fin);
while(isalnum(ch)) //如果是字母數(shù)字則組合標(biāo)識(shí)符;如果不是則標(biāo)識(shí)符組合結(jié)束
{
token[j++]=ch; //組合的標(biāo)識(shí)符保存在token中
ch=getc(fin); //讀下一個(gè)字符
}
token[j]=‘/0’; //標(biāo)識(shí)符組合結(jié)束
//查保留字
n=0;
while ((n《keywordSum) && strcmp(token,keyword[n])) n++;
if (n》=keywordSum) //不是保留字,輸出標(biāo)識(shí)符
fprintf(fout,“%s/t%s/n”,“ID”,token); //輸出標(biāo)識(shí)符符號(hào)
else//是保留字,輸出保留字
fprintf(fout,“%s/t%s/n”,token,token); //輸出保留字符號(hào)
} else if (isdigit(ch))//數(shù)字處理
{
token[0]=ch; j=1;
ch=getc(fin); //讀下一個(gè)字符
while (isdigit(ch)) //如果是數(shù)字則組合整數(shù);如果不是則整數(shù)組合結(jié)束
{
token[j++]=ch; //組合整數(shù)保存在token中
ch=getc(fin); //讀下一個(gè)字符
}
token[j]=‘/0’; //整數(shù)組合結(jié)束
fprintf(fout,“%s/t%s/n”,“NUM”,token); //輸出整數(shù)符號(hào)
} else if (strchr(singleword,ch)》0) //單分符處理
{
token[0]=ch; token[1]=‘/0’;
ch=getc(fin);//讀下一個(gè)符號(hào)以便識(shí)別下一個(gè)單詞
fprintf(fout,“%s/t%s/n”,token,token); //輸出單分界符符號(hào)
}else if (strchr(doubleword,ch)》0) //雙分界符處理
{
token[0]=ch;
ch=getc(fin); //讀下一個(gè)字符判斷是否為雙分界符
if (ch==‘=’) //如果是=,組合雙分界符
{
token[1]=ch;token[2]=‘/0’; //組合雙分界符結(jié)束
ch=getc(fin); //讀下一個(gè)符號(hào)以便識(shí)別下一個(gè)單詞
} else//不是=則為單分界符
token[1]=‘/0’;
fprintf(fout,“%s/t%s/n”,token,token); //輸出單或雙分界符符號(hào)
} else if (ch==‘/’) //注釋處理
{
ch=getc(fin); //讀下一個(gè)字符
if (ch==‘*’) //如果是*,則開始處理注釋
{ char ch1;
ch1=getc(fin); //讀下一個(gè)字符
do
{ ch=ch1;ch1=getc(fin);} //刪除注釋
while ((ch!=‘*’ || ch1!=‘/’)&&ch1!=EOF); //直到遇到注釋結(jié)束符*/或文件尾
ch=getc(fin);//讀下一個(gè)符號(hào)以便識(shí)別下一個(gè)單詞
} else //不是*則處理單分界符/
{
token[0]=‘/’; token[1]=‘/0’;
fprintf(fout,“%s/t%s/n”,token,token); //輸出單分界符/
}
} else//錯(cuò)誤處理
{
token[0]=ch;token[1]=‘/0’;
ch=getc(fin); //讀下一個(gè)符號(hào)以便識(shí)別下一個(gè)單詞
es=3; //設(shè)置錯(cuò)誤代碼
fprintf(fout,“%s/t%s/n”,“ERROR”,token); //輸出錯(cuò)誤符號(hào)
}
}
fclose(fin);//關(guān)閉輸入輸出文件
fclose(fout);
return(es); //返回主程序
}
//語法、語義分析及代碼生成
//插入符號(hào)表動(dòng)作@name-def↓n, t的程序如下:
int name_def(char *name)
{
int i,es=0;
if (vartablep》=maxvartablep) return(21);
for(i=vartablep-1;i==0;i--)//查符號(hào)表
{
if (strcmp(vartable[i].name,name)==0)
{
es=22;//22表示變量重復(fù)聲明
break;
}
}
if (es》0) return(es);
strcpy(vartable[vartablep].name,name);
vartable[vartablep].address=datap;
datap++;//分配一個(gè)單元,數(shù)據(jù)區(qū)指針加1
vartablep++;
return(es);
}
//查詢符號(hào)表返回地址
int lookup(char *name,int *paddress)
{
int i,es=0;
for(i=0;i《vartablep;i++)
{
if (strcmp(vartable[i].name,name)==0)
{
*paddress=vartable[i].address;
return(es);
}
}
es=23;//變量沒有聲明
return(es);
}
//語法、語義分析及代碼生成程序
int TESTparse()
{
int es=0;
if((fp=fopen(Scanout,“r”))==NULL)
{
printf(“/n打開%s錯(cuò)誤!/n”,Scanout);
es=10;
return(es);
}
printf(“請(qǐng)輸入目標(biāo)文件名(包括路徑):”);
scanf(“%s”,Codeout);
if((fout=fopen(Codeout,“w”))==NULL)
{
printf(“/n創(chuàng)建%s錯(cuò)誤!/n”,Codeout);
es=10;
return(es);
}
if (es==0) es=program();
printf(“==語法、語義分析及代碼生成程序結(jié)果==/n”);
switch(es)
{
case 0: printf(“語法、語義分析成功并抽象機(jī)匯編生成代碼!/n”);break;
case 10: printf(“打開文件 %s失?。?n”,Scanout);break;
case 1: printf(“缺少{!/n”);break;
case 2: printf(“缺少}!/n”);break;
case 3: printf(“缺少標(biāo)識(shí)符!/n”);break;
case 4: printf(“少分號(hào)!/n”);break;
case 5: printf(“缺少(!/n”);break;
case 6: printf(“缺少)!/n”);break;
case 7: printf(“缺少操作數(shù)!/n”);break;
case 21: printf(“符號(hào)表溢出!/n”);break;
case 22: printf(“變量重復(fù)定義!/n”);break;
case 23: printf(“變量未聲明!/n”);break;
}
fclose(fp);
fclose(fout);
return(es);
}
//program::={《declaration_list》《statement_list》}
int program()
{
int es=0,i;
fscanf(fp,“%s %s/n”,token,token1);
printf(“%s %s/n”,token,token1);
if(strcmp(token,“{”))//判斷是否‘{’
{
es=1;
return(es);
}
fscanf(fp,“%s %s/n”,&token,&token1);
printf(“%s %s/n”,token,token1);
es=declaration_list();
if (es》0) return(es);
printf(“ 符號(hào)表/n”);
printf(“ 名字 地址/n”);
for(i=0;i《vartablep;i++)
printf(“ %s %d/n”,vartable[i].name,vartable[i].address);
es=statement_list();
if (es》0) return(es);
if(strcmp(token,“}”))//判斷是否‘}’
{
es=2;
return(es);
}
fprintf(fout,“ STOP/n”);//產(chǎn)生停止指令
return(es);
}
//《declaration_list》::=
//《declaration_list》《declaration_stat》|《declaration_stat》
//改成《declaration_list》::={《declaration_stat》}
int declaration_list()
{
int es=0;
while (strcmp(token,“int”)==0)
{
es=declaration_stat();
if (es》0) return(es);
}
return(es);
}
//《declaration_stat》↓vartablep,datap,codep -》int ID↑n@name-def↓n,t;
int declaration_stat()
{
int es=0;
fscanf(fp,“%s %s/n”,&token,&token1);printf(“%s %s/n”,token,token1);
if (strcmp(token,“ID”)) return(es=3); //不是標(biāo)識(shí)符
es=name_def(token1);//插入符號(hào)表
if (es》0) return(es);
fscanf(fp,“%s %s/n”,&token,&token1);printf(“%s %s/n”,token,token1);
if (strcmp(token,“;”) ) return(es=4);
fscanf(fp,“%s %s/n”,&token,&token1);printf(“%s %s/n”,token,token1);
return(es);
}
//《statement_list》::=《statement_list》《statement》|《statement》
//改成《statement_list》::={《statement》}
int statement_list()
{
int es=0;
while (strcmp(token,“}”))
{
es=statement();
if (es》0) return(es);
}
return(es);
}
//《statement》::= 《if_stat》|《while_stat》|《for_stat》
// |《compound_stat》 |《expression_stat》
int statement()
{
int es=0;
if (es==0 && strcmp(token,“if”)==0) es=if_stat();//《IF語句》
if (es==0 && strcmp(token,“while”)==0) es=while_stat();//《while語句》
if (es==0 && strcmp(token,“for”)==0) es=for_stat();//《for語句》
//可在此處添加do語句調(diào)用
if (es==0 && strcmp(token,“read”)==0) es=read_stat();//《read語句》
if (es==0 && strcmp(token,“write”)==0) es=write_stat();//《write語句》
if (es==0 && strcmp(token,“{”)==0) es=compound_stat();//《復(fù)合語句》
if (es==0 && (strcmp(token,“ID”)==0||strcmp(token,“NUM”)==0||strcmp(token,“(”)==0)) es=expression_stat();//《表達(dá)式語句》
return(es);
}
//《IF_stat》::= if (《expr》) 《statement 》 [else 《 statement 》]
/*
if (《expression》)@BRF↑label1 《statement 》 @BR↑label2 @SETlabel↓label1
[ else 《 statement 》] @SETlabel↓label2
其中動(dòng)作符號(hào)的含義如下
@BRF↑label1 :輸出 BRF label1,
@BR↑label2:輸出 BR label2,
@SETlabel↓label1:設(shè)置標(biāo)號(hào)label1
@SETlabel↓label2:設(shè)置標(biāo)號(hào)label2
*/
int if_stat(){
int es=0,label1,label2; //if
fscanf(fp,“%s %s/n”,&token,&token1);
printf(“%s %s/n”,token,token1);
if (strcmp(token,“(”)) return(es=5); //少左括號(hào)
fscanf(fp,“%s %s/n”,&token,&token1);
printf(“%s %s/n”,token,token1);
es=expression();
if (es》0) return(es);
if (strcmp(token,“)”)) return(es=6); //少右括號(hào)
label1=labelp++;//用label1記住條件為假時(shí)要轉(zhuǎn)向的標(biāo)號(hào)
fprintf(fout,“ BRF LABEL%d/n”,label1);//輸出假轉(zhuǎn)移指令
fscanf(fp,“%s %s/n”,&token,&token1);
printf(“%s %s/n”,token,token1);
es=statement();
if (es》0) return(es);
label2=labelp++;//用label2記住要轉(zhuǎn)向的標(biāo)號(hào)
fprintf(fout,“ BR LABEL%d/n”,label2);//輸出無條件轉(zhuǎn)移指令
fprintf(fout,“LABEL%d:/n”,label1);//設(shè)置label1記住的標(biāo)號(hào)
if (strcmp(token,“else”)==0)//else部分處理
{
fscanf(fp,“%s %s/n”,&token,&token1);
printf(“%s %s/n”,token,token1);
es=statement();
if (es》0) return(es);
}
fprintf(fout,“LABEL%d:/n”,label2);//設(shè)置label2記住的標(biāo)號(hào)
return(es);
}
//《while_stat》::= while (《expr 》) 《 statement 》
//《while_stat》::=while @SET↑labellabel1(《expression》) @BRF↑label2
// 《statement 》@BR↑label1 @SETlabel↓label2
//動(dòng)作解釋如下:
//@SETlabel↑label1:設(shè)置標(biāo)號(hào)label1
//@BRF↑label2 :輸出 BRF label2,
//@BR↑label1:輸出 BR label1,
//@SETlabel↓label2:設(shè)置標(biāo)號(hào)label2
int while_stat()
{
int es=0,label1,label2;
label1=labelp++;
fprintf(fout,“LABEL%d:/n”,label1);//設(shè)置label1標(biāo)號(hào)
fscanf(fp,“%s %s/n”,&token,&token1);
printf(“%s %s/n”,token,token1);
if (strcmp(token,“(”)) return(es=5); //少左括號(hào)
fscanf(fp,“%s %s/n”,&token,&token1);
printf(“%s %s/n”,token,token1);
es=expression();
if (es》0) return(es);
if (strcmp(token,“)”)) return(es=6); //少右括號(hào)
label2=labelp++;
fprintf(fout,“ BRF LABEL%d/n”,label2);//輸出假轉(zhuǎn)移指令
fscanf(fp,“%s %s/n”,&token,&token1);
printf(“%s %s/n”,token,token1);
es=statement();
if (es》0) return(es);
fprintf(fout,“ BR LABEL%d/n”,label1);//輸出無條件轉(zhuǎn)移指令
fprintf(fout,“LABEL%d:/n”,label2);//設(shè)置label2標(biāo)號(hào)
return(es);
}
//《for_stat》::= for(《expr》,《expr》,《expr》)《statement》
/*
《for_stat》::=for (《expression》;
@SETlabel↓label1《 expression 》@BRF↑label2@BR↑label3;
@SETlabel↓label4 《 expression 》@BR↑label1)
@SETlabel↓label3 《語句 》@BR↑label4@SETlabel↓label2
動(dòng)作解釋:
1. @SETlabel↓label1:設(shè)置標(biāo)號(hào)label1
2. @BRF↑label2 :輸出 BRF label2,
3. @BR↑label3:輸出 BR label3,
4. @SETlabel↓label4:設(shè)置標(biāo)號(hào)label4
5. @BR↑label1:輸出 BR label1,
6. @SETlabel↓label3:設(shè)置標(biāo)號(hào)label3
7. @BR↑label4:輸出 BR label4,
8. @SETlabel↓label2:設(shè)置標(biāo)號(hào)label2
*/
int for_stat()
{
int es=0,label1,label2,label3,label4;
fscanf(fp,“%s %s/n”,&token,&token1);
printf(“%s %s/n”,token,token1);
if (strcmp(token,“(”)) return(es=5); //少左括號(hào)
fscanf(fp,“%s %s/n”,&token,&token1);
printf(“%s %s/n”,token,token1);
es=expression();
if (es》0) return(es);
if (strcmp(token,“;”)) return(es=4); //少分號(hào)
label1=labelp++;
fprintf(fout,“LABEL%d:/n”,label1);//設(shè)置label1標(biāo)號(hào)
fscanf(fp,“%s %s/n”,&token,&token1);
printf(“%s %s/n”,token,token1);
es=expression();
if (es》0) return(es);
label2=labelp++;
fprintf(fout,“ BRF LABEL%d/n”,label2);//輸出假條件轉(zhuǎn)移指令
label3=labelp++;
fprintf(fout,“ BR LABEL%d/n”,label3);//輸出無條件轉(zhuǎn)移指令
if (strcmp(token,“;”)) return(es=4); //少分號(hào)
label4=labelp++;
fprintf(fout,“LABEL%d:/n”,label4);//設(shè)置label4標(biāo)號(hào)
fscanf(fp,“%s %s/n”,&token,&token1);
printf(“%s %s/n”,token,token1);
es=expression();
if (es》0) return(es);
fprintf(fout,“ BR LABEL%d/n”,label1);//輸出無條件轉(zhuǎn)移指令
if (strcmp(token,“)”)) return(es=6); //少右括號(hào)
fprintf(fout,“LABEL%d:/n”,label3);//設(shè)置label3標(biāo)號(hào)
fscanf(fp,“%s %s/n”,&token,&token1);
printf(“%s %s/n”,token,token1);
es=statement();
if (es》0) return(es);
fprintf(fout,“ BR LABEL%d/n”,label4);//輸出無條件轉(zhuǎn)移指令
fprintf(fout,“LABEL%d:/n”,label2);//設(shè)置label2標(biāo)號(hào)
return(es);
}
//《write_stat》::=write 《expression》;
//《write_stat》::=write 《expression》@OUT;
//動(dòng)作解釋:
//@ OUT:輸出 OUT
int write_stat()
{
int es=0;
fscanf(fp,“%s %s/n”,&token,&token1);
printf(“%s %s/n”,token,token1);
es=expression();
if (es》0)return(es);
if (strcmp(token,“;”)) return(es=4); //少分號(hào)
fprintf(fout,“ OUT/n”);//輸出指令
fscanf(fp,“%s %s/n”,&token,&token1);
printf(“%s %s/n”,token,token1);
return(es);
}
//《read_stat》::=read ID;
//《read_stat》::=read ID↑n LOOK↓n↑d @IN@STI↓d;
//動(dòng)作解釋:
//@LOOK↓n↑d:查符號(hào)表n,給出變量地址d; 沒有,變量沒定義
//@IN:輸出IN
//@STI↓d:輸出指令代碼STI d
int read_stat()
{
int es=0,address;
fscanf(fp,“%s %s/n”,&token,&token1);
printf(“%s %s/n”,token,token1);
if (strcmp(token,“ID”)) return(es=3); //少標(biāo)識(shí)符
es=lookup(token1,&address);
if (es》0) return(es);
fprintf(fout,“ IN /n”);//輸入指令
fprintf(fout,“ STI %d/n”,address);//指令
fscanf(fp,“%s %s/n”,&token,&token1);
printf(“%s %s/n”,token,token1);
if (strcmp(token,“;”)) return(es=4); //少分號(hào)
fscanf(fp,“%s %s/n”,&token,&token1);
printf(“%s %s/n”,token,token1);
return(es);
}
//《compound_stat》::={《statement_list》}
int compound_stat(){ //復(fù)合語句函數(shù)
int es=0;
fscanf(fp,“%s %s/n”,&token,&token1);
printf(“%s %s/n”,token,token1);
es=statement_list();
return(es);
}
//《expression_stat》::=《expression》;|;
int expression_stat()
{
int es=0;
if (strcmp(token,“;”)==0)
{
fscanf(fp,“%s %s/n”,&token,&token1);
printf(“%s %s/n”,token,token1);
return(es);
}
es=expression();
if (es》0) return(es);
if (strcmp(token,“;”)==0)
{
fscanf(fp,“%s %s/n”,&token,&token1);
printf(“%s %s/n”,token,token1);
return(es);
} else
{
es=4;
return(es);//少分號(hào)
}
}
//《expression》::=ID↑n@LOOK↓n↑d@ASSIGN=《bool_expr》@STO↓d |《bool_expr》
int expression()
{
int es=0,fileadd;
char token2[20],token3[40];
if (strcmp(token,“ID”)==0)
{
fileadd=ftell(fp); //@ASSIGN記住當(dāng)前文件位置
fscanf(fp,“%s %s/n”, &token2,&token3);
printf(“%s %s/n”,token2,token3);
if (strcmp(token2,“=”)==0) //‘=’
{
int address;
es=lookup(token1,&address);
if (es》0) return(es);
fscanf(fp,“%s %s/n”,&token,&token1);
printf(“%s %s/n”,token,token1);
es=bool_expr();
if (es》0) return(es);
fprintf(fout,“ STO %d/n”,address);
} else
{
fseek(fp,fileadd,0); //若非‘=’則文件指針回到‘=’前的標(biāo)識(shí)符
printf(“%s %s/n”,token,token1);
es=bool_expr();
if (es》0) return(es);
}
} else es=bool_expr();
return(es);
}
//《bool_expr》::=《additive_expr》
// |《 additive_expr 》(》|《|》=|《=|==|!=)《 additive_expr 》
/*
《bool_expr》::=《additive_expr》
|《 additive_expr 》》《additive_expr》@GT
|《 additive_expr 》《《additive_expr》@LES
|《 additive_expr 》》=《additive_expr 》@GE
|《 additive_expr 》《=《 additive_expr 》@LE
|《 additive_expr 》==《 additive_expr 》@EQ
|《 additive_expr 》!=《 additive_expr 》@NOTEQ
*/
int bool_expr()
{
int es=0;
es=additive_expr();
if(es》0) return(es);
if ( strcmp(token,“》”)==0 || strcmp(token,“》=”)==0
||strcmp(token,“《”)==0 || strcmp(token,“《=”)==0
||strcmp(token,“==”)==0|| strcmp(token,“!=”)==0)
{
char token2[20];
strcpy(token2,token);//保存運(yùn)算符
fscanf(fp,“%s %s/n”,&token,&token1);
printf(“%s %s/n”,token,token1);
es=additive_expr();
if(es》0) return(es);
if ( strcmp(token2,“》”)==0 ) fprintf(fout,“ GT/n”);
if ( strcmp(token2,“》=”)==0 ) fprintf(fout,“ GE/n”);
if ( strcmp(token2,“《”)==0 ) fprintf(fout,“ LES/n”);
if ( strcmp(token2,“《=”)==0 ) fprintf(fout,“ LE/n”);
if ( strcmp(token2,“==”)==0 ) fprintf(fout,“ EQ/n”);
if ( strcmp(token2,“!=”)==0 ) fprintf(fout,“ NOTEQ/n”);
}
return(es);
}
//《additive_expr》::=《term》{(+|-)《 term 》}
//《 additive_expr》::=《term》{(+《 term 》@ADD |-《項(xiàng)》@SUB)}
int additive_expr()
{
int es=0;
es=term();
if(es》0) return(es);
while (strcmp(token,“+”)==0 || strcmp(token,“-”)==0)
{
char token2[20];
strcpy(token2,token);
fscanf(fp,“%s %s/n”,&token,&token1);
printf(“%s %s/n”,token,token1);
es=term();
if(es》0) return(es);
if ( strcmp(token2,“+”)==0 ) fprintf(fout,“ ADD/n”);
if ( strcmp(token2,“-”)==0 ) fprintf(fout,“ SUB/n”);
}
return(es);
}
//《 term 》::=《factor》{(*| /)《 factor 》}
//《 term 》::=《factor》{(*《 factor 》@MULT | /《 factor 》@DIV)}
int term()
{
int es=0;
es=factor();
if(es》0) return(es);
while (strcmp(token,“*”)==0 || strcmp(token,“/”)==0)
{
char token2[20];
strcpy(token2,token);
fscanf(fp,“%s %s/n”,&token,&token1);
printf(“%s %s/n”,token,token1);
es=factor();
if(es》0) return(es);
if ( strcmp(token2,“*”)==0 ) fprintf(fout,“ MULT/n”);
if ( strcmp(token2,“/”)==0 ) fprintf(fout,“ DIV/n”);
}
return(es);
}
//《 factor 》::=(《additive_expr》)| ID|NUM
//《 factor 》::=(《 expression 》)| ID↑n@LOOK↓n↑d@LOAD↓d |NUM↑i@LOADI↓i
int factor()
{
int es=0;
if (strcmp(token,“(”)==0)
{
fscanf(fp,“%s %s/n”,&token,&token1);
printf(“%s %s/n”,token,token1);
es=expression();
if (es》0) return(es);
if (strcmp(token,“)”)) return(es=6); //少右括號(hào)
fscanf(fp,“%s %s/n”,&token,&token1);
printf(“%s %s/n”,token,token1);
} else
{
if (strcmp(token,“ID”)==0)
{
int address;
es=lookup(token1,&address);//查符號(hào)表,獲取變量地址
if (es》0) return(es);//變量沒聲明
fprintf(fout,“ LOAD %d/n”,address);
fscanf(fp,“%s %s/n”,&token,&token1);
printf(“%s %s/n”,token,token1);
return(es);
}
if (strcmp(token,“NUM”)==0)
{
fprintf(fout,“ LOADI %s/n”,token1);
fscanf(fp,“%s %s/n”,&token,&token1);
printf(“%s %s/n”,token,token1);
return(es);
}else
{
es=7;//缺少操作數(shù)
return(es);
}
}
return(es);
}
//主程序
void main(){
int es=0;
es=TESTscan();//調(diào)詞法分析
if (es》0) printf(“詞法分析有錯(cuò),編譯停止!”);
else printf(“詞法分析成功!/n”);
if (es==0)
{
es=TESTparse(); //調(diào)語法、語義分析并生成代碼
if (es==0) printf(“語法、語義分析并生成代碼成功!/n”);
else printf(“語法、語義分析并生成代碼錯(cuò)誤!/n”);
}
}
下面我們可以進(jìn)行測(cè)試:如下我挑了幾個(gè)典型的。大家可以看看。
下面就是一個(gè)從高級(jí)語言到低級(jí)語言的轉(zhuǎn)變過程:
Lexical.txt:
{
int a;
int bb;
/*this is a test*/
a=20;
bb=10*a;
}
Grammar.txt:
{ {
int int
ID a
; ;
int int
ID bb
; ;
ID a
= =
NUM 20
; ;
ID bb
= =
NUM 10
* *
ID a
; ;
} }
Translation.txt:
LOADI 20
STO 0
LOADI 10
LOAD 0
MULT
STO 1
STOP
從前面的圖中我們可以看到a對(duì)應(yīng)的內(nèi)存地址單元為0,b為1。LOADI 20 讀入20這個(gè)立即數(shù), STO 0將20存入內(nèi)存地址為0的 單元,LOADI 10 讀入10這個(gè)立即數(shù)。讀出內(nèi)存地址為0的單元內(nèi)容,MULT 進(jìn)行乘法運(yùn)算,STO 1 存入內(nèi)存地址為1的單元。STOP 程序運(yùn)行結(jié)束。
下面是程序部分在VC內(nèi)的內(nèi)存存儲(chǔ):
- code 0x0012a028
+ [0] 0x0012a028 “LOADI”
+ [1] 0x0012a03c “20”
+ [2] 0x0012a050 “STO”
+ [3] 0x0012a064 “0”
+ [4] 0x0012a078 “LOADI”
+ [5] 0x0012a08c “10”
+ [6] 0x0012a0a0 “LOAD”
+ [7] 0x0012a0b4 “0”
+ [8] 0x0012a0c8 “MULT”
+ [9] 0x0012a0dc “STO”
+ [10] 0x0012a0f0 “1”
+ [11] 0x0012a104 “STOP”
+ [12] 0x0012a118 “*****”
- [0] 0x0012a028 “LOADI”
?。?] 0x4c ‘L’
?。?] 0x4f ‘O’
[2] 0x41 ‘A’
?。?] 0x44 ‘D’
?。?] 0x49 ‘I’
?。?] 0x00 ‘’
?。?] 0xcc ‘?
?。?] 0xcc ’?
[8] 0xcc ‘?
?。?] 0xcc ’?
?。?0] 0xcc ‘?
?。?1] 0xcc ’?
?。?2] 0xcc ‘?
?。?3] 0xcc ’?
?。?4] 0xcc ‘?
?。?5] 0xcc ’?
?。?6] 0xcc ‘?
[17] 0xcc ’?
?。?8] 0xcc ‘?
?。?9] 0xcc ’?
+ [1] 0x0012a03c “20”
//《for_stat》::= for(《expr》,《expr》,《expr》)《statement》
/*
《for_stat》::=for (《expression》;
@SETlabel↓label1《 expression 》@BRF↑label2@BR↑label3;
@SETlabel↓label4 《 expression 》@BR↑label1)
@SETlabel↓label3 《語句 》@BR↑label4@SETlabel↓label2
動(dòng)作解釋:
1. @SETlabel↓label1:設(shè)置標(biāo)號(hào)label1
2. @BRF↑label2 :輸出 BRF label2,
3. @BR↑label3:輸出 BR label3,
4. @SETlabel↓label4:設(shè)置標(biāo)號(hào)label4
5. @BR↑label1:輸出 BR label1,
6. @SETlabel↓label3:設(shè)置標(biāo)號(hào)label3
7. @BR↑label4:輸出 BR label4,
8. @SETlabel↓label2:設(shè)置標(biāo)號(hào)label2
*/
{
int a;
int b;
a=0;
b=0;
for(a=0;a《=10;a=a+1)
{
b=b+a;
}
}
詞法分析
{ {
int int
ID a
; ;
int int
ID b
; ;
ID a
= =
NUM 0
; ;
ID b
= =
NUM 0
; ;
for for
?。?(
ID a
= =
NUM 0
; ;
ID a
《= 《=
NUM 10
; ;
ID a
= =
ID a
+ +
NUM 1
?。?)
{ {
ID b
= =
ID b
+ +
ID a
; ;
} }
} }
語義分析:
LOADI 0
STO 0
LOADI 0
STO 1
LOADI 0
STO 0
LABEL0:
LOAD 0
LOADI 10
LE
BRF LABEL1
BR LABEL2
LABEL3:
LOAD 0
LOADI 1
ADD
STO 0
BR LABEL0
LABEL2:
LOAD 1
LOAD 0
ADD
STO 1
BR LABEL3
LABEL1:
STOP
//《IF_stat》::= if (《expr》) 《statement 》 [else 《 statement 》]
/*
if (《expression》)@BRF↑label1 《statement 》 @BR↑label2 @SETlabel↓label1
?。?else 《 statement 》] @SETlabel↓label2
其中動(dòng)作符號(hào)的含義如下
@BRF↑label1 :輸出 BRF label1,
@BR↑label2:輸出 BR label2,
@SETlabel↓label1:設(shè)置標(biāo)號(hào)label1
@SETlabel↓label2:設(shè)置標(biāo)號(hào)label2
*/
IF
If.txt
{
int a;
a=3;
if(a!=1)
{
a=1;
}
}
Ifp.txt
{ {
int int
ID a
; ;
ID a
= =
NUM 3
; ;
if if
?。?(
ID a
??!= !=
NUM 1
?。?)
{ {
ID a
= =
NUM 1
; ;
} }
} }
Ift.txt
LOADI 3
STO 0
LOAD 0
LOADI 1
NOTEQ
BRF LABEL0
LOADI 1
STO 0
BR LABEL1
LABEL0:
LABEL1:
STOP
While
//《while_stat》::= while (《expr 》) 《 statement 》
//《while_stat》::=while @SET↑labellabel1(《expression》) @BRF↑label2
// 《statement 》@BR↑label1 @SETlabel↓label2
//動(dòng)作解釋如下:
//@SETlabel↑label1:設(shè)置標(biāo)號(hào)label1
//@BRF↑label2 :輸出 BRF label2,
//@BR↑label1:輸出 BR label1,
//@SETlabel↓label2:設(shè)置標(biāo)號(hào)label2
While.txt
{
int a;
a=0;
while(a《5)
{
a=a+1;
}
}
Whilep.txt
{ {
int int
ID a
; ;
ID a
= =
NUM 0
; ;
while while
?。?(
ID a
《 《
NUM 5
?。?)
{ {
ID a
= =
ID a
+ +
NUM 1
; ;
} }
} }
Whilet.txt
LOADI 0
STO 0
LABEL0:
LOAD 0
LOADI 5
LES
BRF LABEL1
LOAD 0
LOADI 1
ADD
STO 0
BR LABEL0
LABEL1:
STOP
Wirte
{
int a;
a=10;
write a;
}
//語義
LOADI 10
STO 0
LOAD 0
OUT
STOP
Read
{
int a;
a=1;
read a;
}
LOADI 1
STO 0
IN
STI 0
STOP
在如上的分析后,我們就看到其已經(jīng)轉(zhuǎn)換為類似匯編語言格式的語言。結(jié)合前面的精簡(jiǎn)計(jì)算機(jī)系統(tǒng),這樣我們就可以明白了它是怎么在計(jì)算機(jī)中運(yùn)行的了。在孫悅紅的書中還有Test語言的模擬機(jī)。大家可以看看,其實(shí)程序的基本運(yùn)行原理也是類似。
?
Lexical.txt:
{
int a;
int bb;
/*this is a test*/
a=20;
bb=10*a;
}
Grammar.txt:
{ {
int int
ID a
; ;
int int
ID bb
; ;
ID a
= =
NUM 20
; ;
ID bb
= =
NUM 10
* *
ID a
; ;
} }
Lexical.txt:
{
int a;
int bb;
/*this is a test*/
a=20;
bb=10*a;
}
Grammar.txt:
{ {
int int
ID a
; ;
int int
ID bb
; ;
ID a
= =
NUM 20
; ;
ID bb
= =
NUM 10
* *
ID a
; ;
} }
Lexical.txt:
{
int a;
int bb;
/*this is a test*/
a=20;
bb=10*a;
}
Grammar.txt:
{ {
int int
ID a
; ;
int int
ID bb
; ;
ID a
= =
NUM 20
; ;
ID bb
= =
NUM 10
* *
ID a
; ;
} }
最后,我們來看看前面的for循環(huán)在BC下的編譯結(jié)果如下:
從#1#8開始:
這樣,我們就大概明白和了解了編譯的基本原理了。
從上面的翻譯看來和我們前面的翻譯有點(diǎn)區(qū)別,這就是實(shí)際的使用了。
編譯原理語法分析總結(jié):
語法分析是編譯原理的核心部分。語法分析的作用是識(shí)別由詞法分析給出的單詞符號(hào)序列是否是給定文法的正確句子,目前語法分析常用的方法有自頂向下分析和自底向上分析兩大類。自頂向下分析包括確定分析和不確定分析,自底向上分析又包括算符優(yōu)先分析法和LR分析,這些分析方法各有優(yōu)缺點(diǎn)。下面分別就自頂向下語法分析方法和自底向上語法分析方法展開描述:
A. 自頂向下語法分析方法
自頂向下分析法也稱面向目標(biāo)的分析方法,也就是從文法的開始符號(hào)出發(fā)企圖推導(dǎo)出與輸入的單詞串完全相匹配的句子,若輸入串是給定文法的句子,則必能推出,反之必然出錯(cuò)。自頂向下的確定分析方法需對(duì)文法有一定的限制,但由于實(shí)現(xiàn)方法簡(jiǎn)答、直觀,便于手工構(gòu)造或自動(dòng)生成語法分析器,因而仍是目前常用的方法之一。而自頂向下的不確定分析方法是帶回溯的分析方法,這種方法實(shí)際上是一種窮舉的試探方法,因此效率低,代價(jià)高,因而極少使用。
LL(1)分析
自頂向下的確定分析方法,是從文法的開始符號(hào)出發(fā),考慮如何根據(jù)當(dāng)前的輸入符號(hào)(單詞符號(hào))唯一地確定選用哪個(gè)產(chǎn)生式替換相應(yīng)非終結(jié)符以往下推導(dǎo),或如何構(gòu)造一棵相應(yīng)的語法樹。當(dāng)我們需要選用自頂向下的確定分析技術(shù)時(shí),首先必須判別所給文法是否是LL(1)文法。因而對(duì)所給文法需計(jì)算FIRST、FOLLOW、SELECT集合,進(jìn)而判別文法是否為L(zhǎng)L(1)文法。LL(1)文法表示了自頂向下方法能夠處理的一類文法。LL(1)第一個(gè)“L”表示從左向右掃描輸入,第二個(gè)“L”表示產(chǎn)生最左推導(dǎo),而“1”則表示每一步中只需要向前看一個(gè)輸入符號(hào)來決定語法分析動(dòng)作。類似也可以有LL(k)文法,也就是需向前查看k個(gè)符號(hào)才可以確定選用哪個(gè)產(chǎn)生式。通常采用k=1,個(gè)別情況采用k=2。LL(1)文法已經(jīng)足以描述大多數(shù)程序設(shè)計(jì)語言構(gòu)造,雖然在為源語言設(shè)計(jì)適當(dāng)?shù)奈姆〞r(shí)需要多加小心。比如,左遞歸的文法和二義性的文法都不可能是LL(1)的。一個(gè)文法G是LL(1)的,當(dāng)且僅當(dāng)G的任意兩個(gè)不同的產(chǎn)生式A-》α|β滿足下面的條件:
1) 不存在終結(jié)符號(hào)a使得α和β都能夠推導(dǎo)出以a開頭的串。
2) α和β中最多只有一個(gè)可以推導(dǎo)出空串。
3) 如果βT*ε,那么α不能推導(dǎo)出任何以FOLLOW(A)中某個(gè)終結(jié)符號(hào)開頭的串。類似地,如果αT*ε,那么β不能推導(dǎo)出任何以FOLLOW(A)中某個(gè)終結(jié)符號(hào)開頭的串。
我們知道當(dāng)文法不滿足LL(1)時(shí),則不能用確定的自頂向下分析,但在這種情況下可用不確定的自頂向下分析,也就是帶回溯的自頂向下分析。引起回溯的原因是在文法中當(dāng)關(guān)于某個(gè)非終結(jié)符的產(chǎn)生式有多個(gè)候選時(shí),而面臨當(dāng)前的輸入符無法確定選用唯一的產(chǎn)生式,從而引起回溯。引起回溯的情況大致有3種:
1) 由于相同的左部的產(chǎn)生式的右部FIRST集交集不為空而引起回溯;
2) 由于相同左部非終結(jié)符的右部存在能T*ε的產(chǎn)生式,且該非終結(jié)符的FOLLOW集中含有其他產(chǎn)生式右部FIRST集的元素;
3) 由于文法含有左遞歸而引起回溯。
B. 自底向上語法分析方法
自底向上分析,也稱移近-歸約分析,粗略地說它的實(shí)現(xiàn)思想是對(duì)輸入符號(hào)串自左向右進(jìn)行掃描,并將輸入符逐個(gè)移入一個(gè)后進(jìn)先出棧中,邊移入邊分析,一旦棧頂符號(hào)串形成某個(gè)句型的句柄或可歸約串時(shí)(該句柄或可歸約串對(duì)應(yīng)某產(chǎn)生式的右部),就用該產(chǎn)生式的左部非終結(jié)符代替相應(yīng)右部的文法符號(hào)串,這稱為一步歸約。重復(fù)這一過程直到歸約到棧中只剩文法的開始符號(hào)時(shí)則為分析成功,也就確認(rèn)輸入串是文法的句子。
目前最流行的自底向上語法分析器都基于所謂的LR(k)語法分析的概念。其中,“L”表示對(duì)輸入進(jìn)行從左到右的掃描,“R”表示反向構(gòu)造出一個(gè)最右推導(dǎo)序列,而k表示在做出語法分析決定時(shí)向前看k個(gè)輸入符號(hào)。
LR語法分析技術(shù)優(yōu)點(diǎn):
1. 對(duì)于幾乎所有的程序設(shè)計(jì)語言構(gòu)造,只要能夠?qū)懗鲈摌?gòu)造的上下文無關(guān)文法,就能夠構(gòu)造出識(shí)別該構(gòu)造的LR語法分析器。確實(shí)存在非LR的上下文無關(guān)文法,但一般來說,常見的程序設(shè)計(jì)語言構(gòu)造都可以避免使用這樣的文法。
2. LR語法分析方法是已知的最通用的無回溯移入-歸約分析技術(shù),并且它的實(shí)現(xiàn)可以和其他更原始的移入-歸約方法一樣高效。
3. 一個(gè)LR語法分析器可以在對(duì)輸入進(jìn)行從左到右掃描時(shí)盡可能早地檢測(cè)到錯(cuò)誤。
4. 可以使用LR方法進(jìn)行語法分析的文法類是可以使用預(yù)測(cè)方法或LL方法進(jìn)行語法分析的文法類的真超集。一個(gè)文法是LR(k)的條件是當(dāng)我們?cè)谝粋€(gè)最右句型中看到某個(gè)產(chǎn)生式的右部時(shí),我們?cè)傧蚯翱磌個(gè)符號(hào)就可以決定是否使用這個(gè)產(chǎn)生式進(jìn)行歸約。這個(gè)要求比LL(k)文法的要求寬松很多。對(duì)于LL(k)文法,我們?cè)跊Q定是否使用某個(gè)產(chǎn)生式時(shí),只能向前看該產(chǎn)生式右部推導(dǎo)出的串的前k個(gè)符號(hào)。因此,LR文法能夠比LL文法描述更多的語言就一點(diǎn)也不奇怪了。
LR方法的主要缺點(diǎn)是為了一個(gè)典型的程序設(shè)計(jì)語言文法手工構(gòu)造LR分析器的工作量非常大,k愈大構(gòu)造愈復(fù)雜,實(shí)現(xiàn)比較困難。常見的LR方法有LR(0)、SLR(1)、LALR(1)和LR(1),其中SLR(1)和LALR(1)分別是LR(0)和LR(1)的一種改進(jìn)。下面主要介紹這四種LR分析方法:
1. LR(0)分析
LR(0)分析器是在分析過程中不需向右查看輸入符號(hào),因而它對(duì)文法的限制較大,對(duì)絕大多數(shù)高級(jí)語言的語法分析器是不能適用的,然而,它是構(gòu)造其他LR類分析器的基礎(chǔ)。LR(0)分析表構(gòu)造的思想和方法是構(gòu)造其他LR分析表的基礎(chǔ),它是LR(0)分析器的重要組成部分,它是總控程序分析動(dòng)作的依據(jù)。對(duì)于不同的文法,LR(0)分析表不同,它可以用一個(gè)二維數(shù)組表示,行標(biāo)為狀態(tài)號(hào),列標(biāo)為文法符號(hào)和“#”號(hào),分析表的內(nèi)容可由兩部分組成,一部分為動(dòng)作(ACTION)表,它表示當(dāng)前狀態(tài)下所面臨輸入符應(yīng)做的動(dòng)作是移近、歸約、接受或出錯(cuò),動(dòng)作表的行標(biāo)只包含終結(jié)符和“#”,另一部分為轉(zhuǎn)換(GOTO)表,它表示在當(dāng)前狀態(tài)下面臨文法符號(hào)時(shí)應(yīng)轉(zhuǎn)向的下一個(gè)狀態(tài),相當(dāng)于識(shí)別活前綴的有限自動(dòng)機(jī)DFA 的狀態(tài)轉(zhuǎn)換矩陣。我們知道LR(0)對(duì)文法的限制較大,它要求對(duì)一個(gè)文法的LR(0)項(xiàng)目集規(guī)范族不存在移近-歸約,或歸約-歸約沖突。所謂移近-歸約沖突也就是在一個(gè)項(xiàng)目集中移近和歸約項(xiàng)目同時(shí)存在,而歸約-歸約沖突是在一個(gè)項(xiàng)目集中歸約和歸約項(xiàng)目同時(shí)存在。
2. SLR(1)分析
由于大多數(shù)實(shí)用的程序設(shè)計(jì)語言的文法不能滿足LR(0)文法的條件,經(jīng)過改進(jìn)后得到了一種新的SLR(1)文法,其思想是基于容許LR(0)規(guī)范族中有沖突的項(xiàng)目集(狀態(tài))用向前查看一個(gè)符號(hào)的辦法來進(jìn)行處理,已解決沖突。因?yàn)橹挥袑?duì)有沖突的狀態(tài)才向前查看一個(gè)符號(hào),以確定做哪種動(dòng)作,所以稱這種分析方法為簡(jiǎn)單的LR(1)分析法,用SLR(1)表示。通常對(duì)于LR(0)規(guī)范族的一個(gè)項(xiàng)目集I可能含有多個(gè)項(xiàng)目和多個(gè)歸約項(xiàng)目,假設(shè)項(xiàng)目集I中有m個(gè)移近項(xiàng)目:A1-》α1 ?α1β1,A2-》α2 ?α2β2,… , Am-》αm ?αmβm;同時(shí)含有n個(gè)歸約項(xiàng)目為:B1-》γ1? ,B1-》γ1? , … ,Bn-》γn? 只要集合{α1 ,α2 ,… ,αm}和FOLLOW(B1),F(xiàn)OLLOW(B2),… ,F(xiàn)OLLOW(Bn)兩兩交集都為空,那么我們可以考察當(dāng)前輸入符號(hào)決定動(dòng)作,解決沖突。盡管采用SLR(1)方法能夠?qū)δ承㎜R(0)項(xiàng)目集規(guī)范族中存在動(dòng)作沖突的項(xiàng)目集,通過用向前查看一個(gè)符號(hào)的辦法來解決沖突,但是仍有很多文法構(gòu)造的LR(0)項(xiàng)目集規(guī)范族存在的動(dòng)作沖突不能用SLR(1)方法解決。當(dāng)集合{α1 ,α2 ,… ,αm}和FOLLOW(B1),F(xiàn)OLLOW(B2),… ,F(xiàn)OLLOW(Bn)之間存在交集不為空的情況,則不能根據(jù)當(dāng)前輸入符號(hào)決定動(dòng)作,存在動(dòng)作沖突。
3. LR(1)分析
可以看出SLR(1)方法雖然相對(duì)LR(0)有所改進(jìn),但仍然存在著多余歸約,也說明SLR(1)方法向前查看一個(gè)符號(hào)的方法仍不夠確切,LR(1)方法恰好是要解決SLR(1)方法在某些情況下存在的無效歸約問題。LR(1)對(duì)比SLR(1)而言,多了向前搜索符這個(gè)概念。根據(jù)項(xiàng)目集構(gòu)造原則有:若[A-》α?Bβ] ∈項(xiàng)目集I時(shí)。則[B-》?γ]也∈I(B-》γ為一產(chǎn)生式)。由此不妨考慮,把FIRST(β)作為用產(chǎn)生式B-》γ歸約的搜索符,稱為向前搜索符,作為歸約時(shí)查看的符號(hào)集合用以代替SLR(1)分析中的FOLLOW集,把此搜索符號(hào)的集合也放在相應(yīng)項(xiàng)目的后面,這種處理方法即為L(zhǎng)R(1)方法。在多數(shù)情況下,對(duì)LR(1)的歸約項(xiàng)目不存在任何無效歸約,但同一個(gè)文法的LR(1)項(xiàng)目集的個(gè)數(shù)比LR(0)項(xiàng)目集的個(gè)數(shù)多,甚至可能多好幾倍。這是由于同一個(gè)LR(0)項(xiàng)目集的搜索符集合不同,多個(gè)搜索符集合則對(duì)應(yīng)著多個(gè)LR(1)項(xiàng)目集。這可以看成是LR(1)項(xiàng)目集的構(gòu)造使某些同心集進(jìn)行了分裂,因而項(xiàng)目集的個(gè)數(shù)增多了。如果一個(gè)文法的LR(1)分析表不含多重入口時(shí),(即任何一個(gè)LR(1)項(xiàng)目集中無移近-歸約沖突或歸約-歸約沖突),則稱該文法為L(zhǎng)R(1)文法。LR(1)文法已能滿足當(dāng)前絕大多數(shù)高級(jí)語言編譯程序的需要。
4. LALR(1)分析
LR(1)分析表的構(gòu)造對(duì)搜索符的計(jì)算方法比較確切,對(duì)文法放寬了要求,也就是適應(yīng)的文法類廣,可以解決SLR(1)方法解決不了的問題,但是,由于它的構(gòu)造對(duì)某些同心集的分裂可能對(duì)狀態(tài)數(shù)目引起劇烈的增長(zhǎng),從而導(dǎo)致存儲(chǔ)容量的急劇增長(zhǎng),也使應(yīng)用受到了一定的限制,為了克服LR(1)的這種缺點(diǎn),我們可以采用對(duì)LR(1)項(xiàng)目集規(guī)范族合并同心集的方法,若合并同心集后不產(chǎn)生新的沖突,則為L(zhǎng)ALR(1)項(xiàng)目集。它的狀態(tài)個(gè)數(shù)與LR(0)、SLR(1)的相同。關(guān)于合并同心集有幾個(gè)問題需要說明:1)同心集是指心相同的項(xiàng)目集合并在一起,因此同心集合并后心仍然相同,只是超前搜索符集合為各同心集超前搜索符集合的合集;2)對(duì)于合并同心集后的項(xiàng)目集經(jīng)轉(zhuǎn)換函數(shù)所達(dá)仍為同心集;3)若文法是LR(1)文法,合并同心集后若有沖突也只可能是歸約-歸約沖突,而不可能產(chǎn)生移近-歸約沖突;4)合并同心集后對(duì)某些錯(cuò)誤發(fā)現(xiàn)的時(shí)間會(huì)產(chǎn)生推遲現(xiàn)象,但錯(cuò)誤的出現(xiàn)位置仍是準(zhǔn)確的。這意味著LALR(1)分析表比LR(1)分析表對(duì)同一輸入串的分析可能會(huì)有多余歸約。
評(píng)論
查看更多