1、【精品文檔】如有侵權(quán)，請聯(lián)系網(wǎng)站刪除，僅供學習與交流編譯原理實驗指導.精品文檔.編譯原理實驗指導書主編：徐靜 李娜 信息與電氣工程學院2010年3月概 述一、本課程實驗的目的和任務 編譯原理是一門實踐性很強的課程，只有通過實踐，才能真正掌握。實際的編譯程序是十分復雜的，有時由多達十幾萬條指令組成。為此，編譯原理的實踐教學，采用簡化編譯過程的辦法，選擇最關(guān)鍵的3個環(huán)節(jié)詞法分析、語法分析（包括語義處理、產(chǎn)生無優(yōu)化的目標指令）、連接調(diào)試，進行編程和調(diào)試訓練。每個環(huán)節(jié)作為一個實踐課題。先分別編程調(diào)試，再連接在一起總調(diào)。 二、實驗方法 任何一個實用的高級語言，其語法都比較復雜，如選其作為源語言，很難實踐

2、全過程。故本實驗將定義一個簡化的語言 C語言的一個子集作為源語言，設計調(diào)試出它的編譯程序。前后貫穿這一條主線進行實踐。每次都可利用課余時間編程，利用上機時間進行輸入和調(diào)試。 三、實驗報告的規(guī)范和要求 每個實驗完成后寫出實驗報告。實驗報告的內(nèi)容包括如下內(nèi)容：一、 實驗目的二、 程序設計時采用的算法和方法三、 輸入的源程序四、 詞法分析程序清單和輸出結(jié)果。 五、 心得體會實驗一 詞法分析一、實驗目的： （1）通過設計編制調(diào)試一個具體的詞法分析程序，理解詞法分析在編譯程序中的作用。（2）加深對有窮自動機模型的理解。（3）掌握詞法分析程序的實現(xiàn)方法和技術(shù)。（4）用C語言對一個簡單語言的子集編制一個一遍

3、掃描的程序，以加深對編譯原理的理解，掌握編譯程序的實現(xiàn)方法和技術(shù)。編制一個讀單詞過程，從輸入的源程序中，識別出各個具有獨立意義的單詞，即基本保留字、標識符、常數(shù)、運算符、分隔符五大類。并依次輸出各個單詞的內(nèi)部編碼及單詞符號自身值。（遇到錯誤時可顯示“Error”，然后跳過錯誤部分繼續(xù)顯示） 。二、實驗預習提示 1. 詞法分析器的功能和輸出格式詞法分析器的功能是輸入源程序，輸出單詞符號。詞法分析器的單詞符號常常表示成以下的二元式（單詞種別碼，單詞符號的屬性值）。本實驗中，采用的是一類符號一種別碼的方式。2. 單詞的BNF表示<標識符> <字母><字母數(shù)字串>&

4、lt;字母數(shù)字串><字母><字母數(shù)字串>|<數(shù)字> <字母數(shù)字串>|<下劃線><字母數(shù)字串>|<無符號整數(shù)> <數(shù)字> <數(shù)字串><數(shù)字串> <數(shù)字><數(shù)字串> |<加法運算符> +<減法運算符> -<大于關(guān)系運算符> ><大于等于關(guān)系運算符> >=3. “超前搜索”方法詞法分析時，常常會用到超前搜索方法。如當前待分析字符串為“a>+”,當前字符為“ >”，此時，分析器到底是

5、將其分析為大于關(guān)系運算符還是大于等于關(guān)系運算符呢？顯然，只有知道下一個字符是什么才能下結(jié)論。于是分析器讀入下一個字符“+”，這時可知應將“ >”解釋為大于運算符。但此時，超前讀了一個字符“+”，所以要回退一個字符，詞法分析器才能正常運行。在分析標識符，無符號整數(shù)等時也有類似情況。4. 模塊結(jié)構(gòu)YNYN調(diào)用返回輸出緩沖區(qū)中是否還有字符取單詞掃描一個字符結(jié)束主函數(shù)main（）輸入文件名判斷能否打開文件緩沖區(qū)掃描一個字符三、實驗過程和指導： （一）準備： 1.閱讀課本有關(guān)章節(jié)，明確語言的語法，寫出基本保留字、標識符、常數(shù)、運算符、分隔符和程序例。2.初步編制好程序。3.準備多組測試數(shù)據(jù)。（二）

6、上課上機： 將源代碼拷貝到機上調(diào)試，發(fā)現(xiàn)錯誤，再修改完善。第二次上機調(diào)試通過。（三）程序要求：程序輸入/輸出示例：如源程序為C語言。輸入如下一段：main( )                                    

7、0;                                    int a,b;a = 10; b = a + 20;要求輸出如下圖。（2，”main”）（5，”（“）（5，”）“）（5，”“）（1，”int”）（2，”a”）（5，”,”

8、）（2，”b”）（5，”;”）（2，”a”）（4，”=”）（3，”10”）（5，”;”）（2，”b”）（4，”=”）（2，”a”）（4，”+”）（3，”20”）（5，”;”）（5，”“）要求：1. 識別保留字：if、int、for、while、do、return、break、continue；單詞種別碼為1。2. 其他的都識別為標識符；單詞種別碼為2。3. 常數(shù)為無符號整型數(shù)；單詞種別碼為3。4. 運算符包括：+、-、*、/、=、<、=、<=、!= ；單詞種別碼為4。5. 分隔符包括：,、;、(、)； 單詞種別碼為5。以上為參考，具體可自行增刪。（四）程序思路（僅供參考）：這里以開

9、始定義的C語言子集的源程序作為詞法分析程序的輸入數(shù)據(jù)。在詞法分析中，自文件頭開始掃描源程序字符，一旦發(fā)現(xiàn)符合“單詞”定義的源程序字符串時，將它翻譯成固定長度的單詞內(nèi)部表示，并查填適當?shù)男畔⒈?。?jīng)過詞法分析后，源程序字符串（源程序的外部表示）被翻譯成具有等長信息的單詞串（源程序的內(nèi)部表示），并產(chǎn)生兩個表格：常數(shù)表和標識符表，它們分別包含了源程序中的所有常數(shù)和所有標識符。0. 定義部分：定義常量、變量、數(shù)據(jù)結(jié)構(gòu)。1. 初始化：從文件將源程序全部輸入到字符緩沖區(qū)中。2. 取單詞前：去掉多余空白。3. 取單詞后：去掉多余空白。4. 取單詞：讀出單詞的每一個字符，組成單詞，分析類型。（關(guān)鍵是如何判斷取單

10、詞結(jié)束？取到的單詞是什么類型的單詞？）5. 顯示結(jié)果。（五）練習該實驗的目的和思路：程序開始變得復雜起來，可能是大家目前編過的程序中最復雜的，但相對于以后的程序來說還是簡單的。因此要認真把握這個過渡期的練習。本實驗和以后的實驗相關(guān)。通過練習，掌握對字符進行靈活處理的方法。（六）為了能設計好程序，注意以下事情：1. 模塊設計：將程序分成合理的多個模塊（函數(shù)），每個模塊做具體的同一事情。2. 寫出（畫出）設計方案：模塊關(guān)系簡圖、流程圖、全局變量、函數(shù)接口等。3. 編程時注意編程風格：空行的使用、注釋的使用、縮進的使用等。 （七）程序框架：#include<stdio.h>#includ

11、e<string.h>char program80,token8; /*數(shù)組program存放的為源程序所有字符，數(shù)組token為存放的單詞自身字符串*/char ch;int syn,p,m,n,row; /*syn為單詞種別碼*/long int num; /*sum為整型常數(shù)*/char *key 8= "if","int","for","while","do","return","break","continue"

12、/*保留字*/void main( ) p=0; row=1; printf("n please input string:n"); do /*從文件將源程序全部輸入到字符緩沖區(qū)中*/  ch=getchar();  programp+=ch; while(ch!='#');  p=0; do  scaner( );  switch(syn)   case 3: printf("n(%d, %d)",syn,n

13、um);break;   case -1: printf("nFOUND ERROR IN ROW %d",row);break;   case -2: row=row+;break;   default: printf("n(%d, %s)",syn,token);break;  while(syn!=0); getch( );scaner( )  for(n=0;n<8;n+) tokenn=NULL;  m=0;  ch=progra

14、mp+;  while(ch=' ')   ch=programp+; /*分類判斷1.識別標識符（包括保留字）。建議：關(guān)鍵字作為特殊標識符處理，把它們預先安排在一張表格中（保留字表），當掃描程序識別標識符時，查關(guān)鍵字，否則為一般標識符。注意：識別保留字：if、int、for、while、do、return、break、continue；單詞種別碼為1。其他的都識別為標識符；單詞種別碼為2。2.識別常數(shù)。注意：常數(shù)的有效范圍，如果產(chǎn)生溢出則設置syn的值，與主函數(shù)的代碼呼應。case 3: printf("n(%d, %d)",

15、syn,num);break;case -1: printf("nFOUND ERROR IN ROW %d",row);break;常數(shù)為無符號整型數(shù)；單詞種別碼為3。3.識別運算符。注意：區(qū)分兩個運算符<和<=。 （switch語句）運算符包括：+、-、*、/、=、<、=、<=、!= 單詞種別碼為4。4.識別界符。分隔符包括：,、;、(、) 單詞種別碼為5。 （switch語句）實驗二 遞歸下降分析法一、實驗目的：   根據(jù)某一文法編制調(diào)試遞歸下降分析程序，以便對任意輸入的符號串進行分析。本次實驗的目的主要是加深對遞歸下降分析法的理解。

16、二、實驗預習提示 1遞歸下降分析法的功能詞法分析器的功能是利用函數(shù)之間的遞歸調(diào)用模擬語法樹自上而下的構(gòu)造過程。2遞歸下降分析法的前提改造文法：消除二義性、消除左遞歸、提取左因子，判斷是否為LL（1）文法。3遞歸下降分析法實驗設計思想及算法為G的每個非終結(jié)符號U構(gòu)造一個遞歸過程，不妨命名為U。U的產(chǎn)生式的右邊指出這個過程的代碼結(jié)構(gòu)：(1) 若是終結(jié)符號，則和向前看符號對照，若匹配則向前進一個符號；否則出錯。(2) 若是非終結(jié)符號，則調(diào)用與此非終結(jié)符對應的過程。當A的右部有多個產(chǎn)生式時，可用選擇結(jié)構(gòu)實現(xiàn)。具體為： 對于每個非終結(jié)符號U u1|u2|un處理的方法如下：U( )ch=當前符號；if(

17、ch可能是u1字的開頭) 處理u1的程序部分；else if(ch可能是u2字的開頭) 處理u2的程序部分；else error()； 對于每個右部ux1x2xn的處理架構(gòu)如下：處理x1的程序；處理x2的程序；處理xn的程序； 如果右部為空，則不處理。 對于右部中的每個符號xi。A 如果xi為終結(jié)符號：if(xi= = 當前的符號) NextChar()； Return； else出錯處理B如果xi為非終結(jié)符號，直接調(diào)用相應的過程xi( )。說明： NextChar為前進一個字符函數(shù)。三、實驗過程和指導： （一）準備： 1.閱讀課本有關(guān)章節(jié)，2.考慮好設計方案；3.設計出模塊結(jié)構(gòu)、測試數(shù)據(jù)，初

18、步編制好程序。（二）上課上機： 將源代碼拷貝到機上調(diào)試，發(fā)現(xiàn)錯誤，再修改完善。第二次上機調(diào)試通過。（三）程序要求：程序輸入/輸出示例： 對下列文法，用遞歸下降分析法對任意輸入的符號串進行分析： （1）ETG（2）G+TG|TG（3）G（4）TFS（5）S*FS|/FS（6）S（7）F(E)（8）Fi輸出的格式如下：(1) 遞歸下降分析程序，編制人：姓名，學號，班級(2) 輸入一以#結(jié)束的符號串(包括+*/（）i#)：在此位置輸入符號串例如：i+i*i# (3) 輸出結(jié)果：i+i*i#為合法符號串 備注：輸入一符號串如i+i*#,要求輸出為“非法的符號串”。注意：1.表達式中允許使用運

19、算符（+-*/）、分割符（括號）、字符I，結(jié)束符#； 2.如果遇到錯誤的表達式，應輸出錯誤提示信息（該信息越詳細越好）；3.對學有余力的同學，可以詳細的輸出推導的過程，即詳細列出每一步使用的產(chǎn)生式。（四）程序思路（僅供參考）：0. 定義部分：定義常量、變量、數(shù)據(jù)結(jié)構(gòu)。1. 初始化：從文件將輸入符號串輸入到字符緩沖區(qū)中。2. 利用遞歸下降分析法分析，對每個非終結(jié)符編寫函數(shù)，在主函數(shù)中調(diào)用文法開始符號的函數(shù)。（五）練習該實驗的目的和思路： 程序開始變得復雜起來，需要利用到程序設計語言的知識和大量編程技巧，遞歸下降分析法是一種較實用的分析法，通過這個練習可大大提高軟件開發(fā)能力。通過練習，掌握函數(shù)間相

20、互調(diào)用的方法。（六）為了能設計好程序，注意以下事情：1. 模塊設計：將程序分成合理的多個模塊（函數(shù)），每個模塊做具體的同一事情。2. 寫出（畫出）設計方案：模塊關(guān)系簡圖、流程圖、全局變量、函數(shù)接口等。3. 編程時注意編程風格：空行的使用、注釋的使用、縮進的使用等。實驗三 LL(1)分析法一、實驗目的：      根據(jù)某一文法編制調(diào)試LL（1）分析程序，以便對任意輸入的符號串進行分析。本次實驗的目的主要是加深對預測分析LL（1）分析法的理解。二、實驗預習提示 1、LL（1）分析法的功能LL（1）分析法的功能是利用LL（1）控制程序根據(jù)顯示棧棧頂內(nèi)容、向前看

21、符號以及LL（1）分析表，對輸入符號串自上而下的分析過程。2、LL（1）分析法的前提改造文法：消除二義性、消除左遞歸、提取左因子，判斷是否為LL（1）文法，3、LL（1）分析法實驗設計思想及算法三、實驗過程和指導： （一）準備： 1. 閱讀課本有關(guān)章節(jié)。2. 考慮好設計方案。3. 設計出模塊結(jié)構(gòu)、測試數(shù)據(jù)，初步編制好程序。（二）上課上機： 將源代碼拷貝到機上調(diào)試，發(fā)現(xiàn)錯誤，再修改完善。第二次上機調(diào)試通過。（三）程序要求：程序輸入/輸出示例： 對下列文法，用LL（1）分析法對任意輸入的符號串進行分析： （1）ETG（2）G+TG|TG（3）G（4）TFS（5）S*FS|/FS（6）S（7）F(E

22、)（8）Fi輸出的格式如下：(1) LL（1）分析程序，編制人：姓名，學號，班級(2) 輸入一以#結(jié)束的符號串(包括+*/（）i#)：在此位置輸入符號串 (3) 輸出過程如下：  步驟分析棧剩余輸入串所用產(chǎn)生式1Ei+i*i#ETG  (4) 輸入符號串為非法符號串（或者為合法符號串）。 備注：(1) 在“所用產(chǎn)生式”一列中如果對應有推導則寫出所用產(chǎn)生式；如果為匹配終結(jié)符則寫明匹配的終結(jié)符；如分析異常出錯則寫為“分析出錯”；若成功結(jié)束則寫為“分析成功”。(2) 在此位置輸入符號串為用戶自行輸入的符號串。(3) 上述描述的輸出過程只是其中一部分的。  注意

23、：1. 表達式中允許使用運算符（+-*/）、分割符（括號）、字符i，結(jié)束符#； 2. 如果遇到錯誤的表達式，應輸出錯誤提示信息（該信息越詳細越好）；3. 對學有余力的同學，測試用的表達式事先放在文本文件中，一行存放一個表達式，同時以分號分割。同時將預期的輸出結(jié)果寫在另一個文本文件中，以便和輸出進行對照；（四）程序思路（僅供參考）：模塊結(jié)構(gòu)：（1）定義部分：定義常量、變量、數(shù)據(jù)結(jié)構(gòu)。（2）初始化：設立LL(1)分析表、初始化變量空間（包括堆棧、結(jié)構(gòu)體、數(shù)組、臨時變量等）；（3）控制部分：從鍵盤輸入一個表達式符號串；（4）利用LL(1)分析算法進行表達式處理：根據(jù)LL(1)分析表對表達式符號串進行

24、堆棧（或其他）操作，輸出分析結(jié)果，如果遇到錯誤則顯示錯誤信息。（五）練習該實驗的目的和思路： 程序相當復雜，需要利用到大量的編譯原理，也用到了大量編程技巧和數(shù)據(jù)結(jié)構(gòu)，通過這個練習可大大提高軟件開發(fā)能力。（六）為了能設計好程序，注意以下事情：1.模塊設計：將程序分成合理的多個模塊（函數(shù)），每個模塊做具體的同一事情。2.寫出（畫出）設計方案：模塊關(guān)系簡圖、流程圖、全局變量、函數(shù)接口等。3.編程時注意編程風格：空行的使用、注釋的使用、縮進的使用等。實驗四 逆波蘭式的產(chǎn)生與計算一、實驗目的：   將非后綴式用來表示的算術(shù)表達式轉(zhuǎn)換為用逆波蘭式來表示的算術(shù)表達式，并計算用逆波蘭式來表示的算術(shù)表

25、達式的值。二、實驗預習提示 1逆波蘭式定義將運算對象寫在前面，而把運算符號寫在后面。用這種表示法表示的表達式也稱做后綴式。逆波蘭式的特點在于運算對象順序不變，運算符號位置反映運算順序。采用逆波蘭式可以很好的表示簡單算術(shù)表達式，其優(yōu)點在于易于計算機處理表達式。2產(chǎn)生逆波蘭式的前提中綴算術(shù)表達式3逆波蘭式生成的實驗設計思想及算法sym=當前輸入符號否是是是處理將棧頂運算符彈出，且輸出輸入一個中綴式表示的簡單運算表達式#入棧2sym是數(shù)字嗎？棧頂運算符優(yōu)先級低于sym嗎？棧頂運算符與sym優(yōu)先級相等嗎？棧頂運算符優(yōu)先級高于sym嗎？對數(shù)字進行處理，形成一個數(shù)字串將向前看符號入棧棧頂是(且sym為)嗎

26、？程序結(jié)束棧頂運算符出棧是否否否否是(1) 首先構(gòu)造一個運算符棧，此運算符在棧內(nèi)遵循越往棧頂優(yōu)先級越高的原則。(2) 讀入一個用中綴表示的簡單算術(shù)表達式，為方便起見,設該簡單算術(shù)表達式的右端多加上了優(yōu)先級最低的特殊符號“#”。(3) 從左至右掃描該算術(shù)表達式，從第一個字符開始判斷，如果該字符是數(shù)字，則分析到該數(shù)字串的結(jié)束并將該數(shù)字串直接輸出。(4) 如果不是數(shù)字，該字符則是運算符，此時需比較優(yōu)先關(guān)系。做法如下：將該字符與運算符棧頂?shù)倪\算符的優(yōu)先關(guān)系相比較。如果，該字符優(yōu)先關(guān)系高于此運算符棧頂?shù)倪\算符，則將該運算符入棧。倘若不是的話，則將此運算符棧頂?shù)倪\算符從棧中彈出，將該字符入棧。(5) 重復

27、上述操作(1)-(2)直至掃描完整個簡單算術(shù)表達式，確定所有字符都得到正確處理，我們便可以將中綴式表示的簡單算術(shù)表達式轉(zhuǎn)化為逆波蘭表示的簡單算術(shù)表達式。4逆波蘭式計算的實驗設計思想及算法讀入一個逆波蘭算術(shù)表達式Sym=當前輸入符號Sym是運算符嗎？Sym=#將該字符入棧根據(jù)運算符的特點從棧頂部取出若干個運算符對象進行該運算將運算結(jié)果入棧程序結(jié)束否否是是(1) 構(gòu)造一個棧，存放運算對象。(2) 讀入一個用逆波蘭式表示的簡單算術(shù)表達式。(3) 自左至右掃描該簡單算術(shù)表達式并判斷該字符，如果該字符是運算對象，則將該字符入棧。若是運算符，如果此運算符是二目運算符，則將對棧頂部的兩個運算對象進行該運算，

28、將運算結(jié)果入棧，并且將執(zhí)行該運算的兩個運算對象從棧頂彈出。如果該字符是一目運算符，則對棧頂部的元素實施該運算，將該棧頂部的元素彈出，將運算結(jié)果入棧。(4) 重復上述操作直至掃描完整個簡單算術(shù)表達式的逆波蘭式，確定所有字符都得到正確處理，我們便可以求出該簡單算術(shù)表達式的值。三、實驗過程和指導： （一）準備： 1.閱讀課本有關(guān)章節(jié)。2.考慮好設計方案。3.設計出模塊結(jié)構(gòu)、測試數(shù)據(jù)，初步編制好程序。（二）上課上機： 將源代碼拷貝到機上調(diào)試，發(fā)現(xiàn)錯誤，再修改完善。第二次上機調(diào)試通過。（三）程序要求：程序輸入/輸出示例： 輸出的格式如下：(1) 逆波蘭式的生成及計算程序，編制人：姓名，學號，班級(2)

29、輸入一以#結(jié)束的中綴表達式(包括+*/（）數(shù)字#)：在此位置輸入符號串如(28+68)*2# (3) 逆波蘭式為：28&68+2* (4) 逆波蘭式28&68+2*計算結(jié)果為192備注：(1) 在生成的逆波蘭式中如果兩個數(shù)相連則用&分隔，如28和68，中間用&分隔；(2) 在此位置輸入符號串為用戶自行輸入的符號串。 注意：1. 表達式中允許使用運算符（+-*/）、分割符（括號）、數(shù)字，結(jié)束符#； 2. 如果遇到錯誤的表達式，應輸出錯誤提示信息（該信息越詳細越好）；3. 對學有余力的同學，測試用的表達式事先放在文本文件中，一行存放一個表達式，同時以分號分

30、割。同時將預期的輸出結(jié)果寫在另一個文本文件中，以便和輸出進行對照；（四）程序思路（僅供參考）：模塊結(jié)構(gòu)：（1）定義部分：定義常量、變量、數(shù)據(jù)結(jié)構(gòu)。（2）初始化：設立算符優(yōu)先分析表、初始化變量空間（包括堆棧、結(jié)構(gòu)體、數(shù)組、臨時變量等）；（3）控制部分：從鍵盤輸入一個表達式符號串；（4）利用算符優(yōu)先分析算法進行表達式處理：根據(jù)算符優(yōu)先分析表對表達式符號串進行堆棧（或其他）操作，輸出分析結(jié)果，如果遇到錯誤則顯示錯誤信息。（5）對生成的逆波蘭式進行計算。（五）練習該實驗的目的和思路： 程序較復雜，需要利用到程序設計語言的知識和大量編程技巧，逆波蘭式的生成是算符優(yōu)先分析法的應用，是一種較實用的分析法，通

31、過這個練習可大大提高軟件開發(fā)能力。（六）為了能設計好程序，注意以下事情：1.模塊設計：將程序分成合理的多個模塊（函數(shù)），每個模塊做具體的同一事情。2.寫出（畫出）設計方案：模塊關(guān)系簡圖、流程圖、全局變量、函數(shù)接口等。3.編程時注意編程風格：空行的使用、注釋的使用、縮進的使用等。實驗五 LR(1)分析法一、實驗目的：     構(gòu)造LR(1)分析程序，利用它進行語法分析，判斷給出的符號串是否為該文法識別的句子，了解LR（K）分析方法是嚴格的從左向右掃描，和自底向上的語法分析方法。二、實驗預習提示： 1使用LR(1)的優(yōu)點：(1) LR分析器能夠構(gòu)造來識別所有能用上下文

32、無關(guān)文法寫的程序設計語言的結(jié)構(gòu)。(2) LR分析方法是已知的最一般的無回溯移進-歸約方法，它能夠和其他移進-歸約方法一樣有效地實現(xiàn)。(3) LR方法能分析的文法類是預測分析法能分析的文法類的真超集。(4) LR分析器能及時察覺語法錯誤，快到自左向右掃描輸入的最大可能。為了使一個文法是LR的，只要保證當句柄出現(xiàn)在棧頂時，自左向右掃描的移進-歸約分析器能夠及時識別它便足夠了。當句柄出現(xiàn)在棧頂時，LR分析器必須要掃描整個棧就可以知道這一點，棧頂?shù)臓顟B(tài)符號包含了所需要的一切信息。如果僅知道棧內(nèi)的文法符號就能確定棧頂是什么句柄。LR分析表的轉(zhuǎn)移函數(shù)本質(zhì)上就是這樣的有限自動機。不過，這個有限自動機不需要根

33、據(jù)每步動作讀棧，因為，如果這個識別句柄的有限自動機自底向上讀棧中的文法符號的話，它達到的狀態(tài)正是這時棧頂?shù)臓顟B(tài)符號所表示的狀態(tài)，所以，LR分析器可以從棧頂?shù)臓顟B(tài)確定它需要從棧中了解的一切。2LR分析器由三個部分組成：(1) 總控程序，也可以稱為驅(qū)動程序。對所有的LR分析器總控程序都是相同的。(2) 分析表或分析函數(shù)，不同的文法分析表將不同，同一個文法采用的LR分析器不同時，分析表將不同，分析表又可以分為動作表（ACTION）和狀態(tài)轉(zhuǎn)換（GOTO）表兩個部分，它們都可用二維數(shù)組表示。(3) 分析棧，包括文法符號棧和相應的狀態(tài)棧，它們均是先進后出棧。分析器的動作就是由棧頂狀態(tài)和當前輸入符號所決定。

34、LR分析器結(jié)構(gòu)：輸入串XXX#總控程序輸出Xn.X1n1.1ACTION表GOTO表其中:SP為棧指針，Si為狀態(tài)棧，Xi為文法符號棧。狀態(tài)轉(zhuǎn)換表用GOTOi，X=j表示，規(guī)定當棧頂狀態(tài)為i，遇到當前文法符號為X時應轉(zhuǎn)向狀態(tài)j，X為終結(jié)符或非終結(jié)符。ACTIONi，a規(guī)定了棧頂狀態(tài)為i時遇到輸入符號a應執(zhí)行。動作有四種可能：(1) 移進：actioni，a= Sj：狀態(tài)j移入到狀態(tài)棧，把a移入到文法符號棧，其中i,j表示狀態(tài)號。(2) 歸約：actioni，a=rk：當在棧頂形成句柄時，則歸約為相應的非終結(jié)符A，即文法中有A-B的產(chǎn)生式，若B的長度為R(即|B|=R)，則從狀態(tài)棧和文法符號棧中自頂向下去掉R個符號，即棧指針SP減去R，并把A移入文法符號棧內(nèi)，j=GOTOi,A移進狀態(tài)棧，其中i為修改指針后的棧頂狀態(tài)。(3) 接受acc：當歸約到文法符號棧中只剩文法的開始符號S時，并且輸入符號串已結(jié)束即當前輸入符是'#'，則為分析成功。(4) 報錯：當遇到狀態(tài)棧頂為某一狀態(tài)下出現(xiàn)不該遇到的文法符號時，則報錯，說明輸入端不是該文