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