題目: DO-WHILE循環(huán)語句的翻譯程序設(shè)計（LR(1)方法、輸出四元式）
1 課設(shè)任務(wù)概述
初始條件：
? 理論：完成編譯原理，數(shù)據(jù)結(jié)構(gòu)、高級編程語言、匯編語言等相關(guān)課程的學(xué)習(xí)，基于計算機專業(yè)知識進行課程設(shè)計。
? 實踐：計算機實驗室提供計算機及軟件環(huán)境。如果自己有計算機及環(huán)境也可以在其上進行設(shè)計任務(wù)。
要求完成的主要任務(wù): （包括課程設(shè)計工作量及其技術(shù)要求，以及報告書撰寫等具體要求）
（1） 寫出符合給定的語法分析方法的文法及屬性文法。
（2） 完成題目要求的中間代碼四元式的描述。
（3） 寫出給定的語法分析方法的思想，完成語法分析和語義分析程序設(shè)計。
（4） 實現(xiàn)程序，設(shè)計若干用例測試程序。
（5） 設(shè)計報告格式按附件要求書寫。
1.1 設(shè)計目的
? 本次課設(shè)任務(wù)為do-while循環(huán)語句的翻譯程序設(shè)計，通過設(shè)計、編制、調(diào)試一個詞法分析和語法、語義分析一體的程序，實現(xiàn)對文本文件提供的源程序進行詞法分析，并將得到的單詞流結(jié)果作為語法分析、語義檢查的對象，其中要求使用LR1分析方法進行語法分析和語義的翻譯工作，最終生成四元式形式的中間代碼。最終進一步掌握相關(guān)的語義分析和語法制導(dǎo)的翻譯方法，以及增進對整體編譯過程的理解和體會。
1.2 設(shè)計內(nèi)容及要求
對選定的語法成分（DO-WHILE）：
? l 按選定的題目寫出符合自身分析方法要求的文法和屬性文法描述。
? l 按選定的題目給出分析方法（LR(1)）的思想及分析表設(shè)計。
? l 給出選定的語法成分的中間代碼序列（四元式）的結(jié)構(gòu)設(shè)計。
? l 完成相應(yīng)的詞法分析、語法分析和語義分析程序設(shè)計。
編制好翻譯程序后，設(shè)計若干用例，上機測試并通過所設(shè)計的分析程序。
2 編譯程序分析
2.1 詞法、語法分析方法描述
2.1.1 詞法分析方法描述：
? 本次實驗詞法分析部分將選擇**C++**語言的源程序作為詞法分析對象，同時選取C++語言中的界符、運算符、關(guān)鍵字中的部分集合，并根據(jù)C++的詞法規(guī)則，以文本文件形式輸入源程序，并對源程序從左到右進行掃描，對組成源程序的字符串拼接成為單詞，并最終轉(zhuǎn)換成單詞屬性字，以單詞二元式的單詞流形式作為LR1語法分析過程的輸入。
2.1.2 語法分析方法描述：
? 本次實驗選取LR(1)作為語法分析、語義翻譯的分析方法，是一種移進-規(guī)約的自底向上的分析過程，當(dāng)分析的棧頂符號形成句柄或可規(guī)約串時就采取規(guī)約動作。LR(1)分析方法是一種能根據(jù)當(dāng)前分析棧中的符號串（通常以狀態(tài)表示）和向右順序查看輸入串的1個符號就可以唯一確定分析器的動作是規(guī)約還是移進和區(qū)分所用來規(guī)約的產(chǎn)生式，因而也就能唯一地確定句柄。
一個LR分析器由三個部分組成：
1）總控程序：對所有的LR分析器，總控程序相同
2）分析表或者分析函數(shù)：不同的文法分析表不同，同一個文法采用的LR分析器不同，分析表也不同，分析表又可分為動作（ACTION）表和狀態(tài)轉(zhuǎn)換（GOTO）表，均可用二維數(shù)組表示。
3）分析棧，包括符號棧和相應(yīng)的狀態(tài)棧。
? 分析器的動作由棧頂狀態(tài)和當(dāng)前輸入符號來決定。
? 針對使用LR(0)分析時可能存在的動作沖突問題以及SLR(1)方法中在某些情況下存在的無效規(guī)約問題，在LR(1)分析方法中都有較好的解決。其通過向前查看一個符號的辦法來解決沖突，將規(guī)約時查看的符號集合變更為FIRST(β)，即向前搜索符集來確保規(guī)約的有效性，最終LR(1)的規(guī)約項目不會存在任何無效規(guī)約，雖然會使某些同心集產(chǎn)生分裂，帶來項目集過多的問題，但其能滿足大多數(shù)高級語言編譯程序的需要，分析能力強。
2.2 文法及屬性文法描述
2.2.1 DO-WHILE文法設(shè)計
本次課設(shè)所設(shè)計的文法產(chǎn)生式如下：
1）A -> do{B}while{C}；
2）C -> E ROP E
3）B -> S;B | S; | A
4）S -> i=E
5）E -> -E | F | E+F | E-F | G
6）F -> F*G | F/G
7）G -> i | n | (E)
8）ROP -> > | < | == | >= | <=
其中4~7號產(chǎn)生式集合中的產(chǎn)生式為所設(shè)計的簡單賦值語句產(chǎn)生式集，在此作為DO-WHILE循環(huán)體中的內(nèi)容；在此設(shè)計的文法考慮了do-while語句的循環(huán)嵌套以及循環(huán)體內(nèi)的多語句運行；
? 符號集如下：
? 終結(jié)符：A（do-while語句）、B（循環(huán)體）、C（條件表達(dá)式）、S（賦值語句）、E（表達(dá)式）、F（項）、G（因子）、ROP（比較運算符）
? 終結(jié)符：do 、{ 、} 、while 、 ； 、 = 、 + 、- 、* 、/ 、（ 、 ） 、> 、< 、== 、>= 、<= 、i（變量標(biāo)識符）、n（常量）
2.2.2 屬性文法描述
設(shè)計上述文法對應(yīng)的屬性文法如下：(起始地址作為do的屬性)
A -> do{B}while{C}； { if C.flag goto do.add else next }
C -> E1 ROP E2 { C.flag := E1.val ROP.op E2.val }
B -> S;B { }
B -> S; { }
B -> A { }
S -> i=E { i.val := E.val }
E -> -E1 { E.val := E1.val * (-1) }
E -> F { E.val := F.val }
E -> E1+F { E.val := E1.val + F.val }
E -> E1-F { E.val := E1.val - F.val }
F -> G { F.val := G.val }
F -> F1*G { F.val := F1.val * G.val }
F -> F1/G { F.val := F1.val / G.val }
G -> i { G.val := i.val }
G -> n { G.val := n.val }
G -> (E) { G.val := E.val }
ROP -> > { ROP.op := > }
ROP -> < { ROP.op := < }
ROP -> == { ROP.op := == }
ROP -> >= { ROP.op := >= }
ROP -> <= { ROP.op := <= }
2.3 分析表定義
? LR(1)項目可以看作兩部分，與LR(0)相同的“心”和向前搜索符集，而LR(1)分析表的構(gòu)造和LR(0)分析表的構(gòu)造在形式上基本相同，只是規(guī)約項目的規(guī)約動作取決于該規(guī)約項目的向前搜索符集，即只有當(dāng)前面臨的輸入符屬于向前搜索符的集合，才做規(guī)約動作，其他情況均出錯。
? 在本次課程設(shè)計中LR(1)項目集的構(gòu)造和LR(1)分析表的生成由實現(xiàn)算法根據(jù)輸入的產(chǎn)生式自動生成，將在后續(xù)介紹。
3 編譯程序設(shè)計
3.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計（描述及數(shù)據(jù)結(jié)構(gòu)）
3.1.1 詞法分析相關(guān)數(shù)據(jù)結(jié)構(gòu)
? 1.單詞二元式結(jié)構(gòu)設(shè)計：
? 其中單詞類別sym屬性與詞法分析類中所存儲的C++關(guān)鍵字表中的下標(biāo)對應(yīng)。
// 單詞類
class word {
public:
int sym{}; // 通過其傳遞單詞類別 e.g. "ident"
string token; // 單詞的值
};
// 單詞類別 區(qū)分：界符、運算符、關(guān)鍵字、常量、標(biāo)識符
enum class type {
del, op, res, con, iden, err
};
? 2.語言的單詞集合存儲及分析結(jié)果：
// C++關(guān)鍵字表(部分)
string CppTable[75];
// 存儲詞法分析結(jié)果
vector<word> lexicalTable;
3.1.1 語法、語義分析相關(guān)數(shù)據(jù)結(jié)構(gòu)
? 1.文法存儲結(jié)構(gòu)設(shè)計：
? ① 產(chǎn)生式：
? 單個產(chǎn)生式分為左右部按照如下數(shù)據(jù)結(jié)構(gòu)存儲，文法的所有產(chǎn)生式選用對應(yīng)結(jié)構(gòu)體的vector容器存儲，即
vector<production> productionTable;
typedef struct production {
string left; // 左部(一個非終結(jié)符)
vector<string> right; // 右部(多個Vn/Vt)
}production;
? ②符號集及對應(yīng)first集：
? 為便于后續(xù)LR(1)項目集的構(gòu)建和語法語義分析的進行，識別產(chǎn)生式后將其中的終結(jié)符和非終結(jié)符分別用set集合進行存儲，例如：set Vn，LR(1)項目集構(gòu)建中形成向前搜索符集所需要用到的每個符號的first集則使用map建立從字符到first集的映射關(guān)系，便于后續(xù)直接使用，例如：
map<string, set<string>> firstMap；
以上均存儲于定義的Grammar文法類中，作為屬性存儲。
- LR(1)項目結(jié)構(gòu)體及分析表
? 在完成文法的相關(guān)準(zhǔn)備后還不能直接用LR(1)分析方法進行語法語義分析，在使用LR(1)前要構(gòu)造LR(1)的分析器，除總控程序之外需要進行LR(1)項目集的構(gòu)造從而生成LR(1)分析表，并在最后使用狀態(tài)棧、符號棧以及語義計算所需要的語義棧。
? ① LR1項目結(jié)構(gòu)體：
? 類似文法產(chǎn)生式，定義項目左部和右部，同時為標(biāo)明項目中的活前綴位置（.的位置），在此定義pointPosition指向“.”之后的下標(biāo)位置（右部中），而項目類型type則定義為聲明的枚舉類型以區(qū)分移進項目、規(guī)約項目、待約項目以及接受項目；最后的字符串容器則用于存儲當(dāng)前項目的向前搜索符號集。項目集則使用vector數(shù)組進行存儲（類似二維數(shù)組），如：
vector<term> termSet[maxNum];
typedef struct term{
termType type; // 項目類型
string leftPart; // 項目左部
vector<string> rightPart; // 項目右部
int pointPosition{ -1 }; // 前綴 . 之后的位置（項目右部中）
vector<string> searchForwardSymSet; // 向前搜索符集
}term;
? ② LR1分析表結(jié)構(gòu)設(shè)計：
? 對于動作表因需要區(qū)分規(guī)約動作（r）、移進動作（S）以及接受動作（acc），在此定義結(jié)構(gòu)體action以區(qū)分，而對應(yīng)的actionTable則使用對應(yīng)的結(jié)構(gòu)體二維數(shù)組進行存儲，行號與構(gòu)造的項目狀態(tài)集進行映射，列名與文法中的終結(jié)符進行映射；關(guān)于gotoTable則直接使用整數(shù)的二維數(shù)組進行存儲，列名與非終結(jié)符進行映射。
// action結(jié)構(gòu)體 用于actionTable
typedef struct action {
termType type{ termType::UR }; // 移進S、規(guī)約R、接收acc
int num{ -1 }; // 編號 S：狀態(tài)轉(zhuǎn)跳 R：用 num 號產(chǎn)生式規(guī)約
}action;
action actionTable[maxNum][maxNum]; // action表 行 Vt 列 status
int gotoTable[maxNum][maxNum]; // goto表 行 Vn 列 status
? ③ 語法語義分析中所需要的三個棧：
? 由于語義棧需要和符號棧進行關(guān)聯(lián)，且在進行語義計算時需要記錄符號（終結(jié)符、非終結(jié)符）所關(guān)聯(lián)的屬性值，因此考慮符號棧的類型為自定義的symItem,其中記錄文法符號名、符號對應(yīng)的屬性值（在簡單賦值文法中僅需要記錄變量及常量的值）、以及在語義計算時存到符號表中對應(yīng)的位置。
typedef struct symItem{
string symName; // 符號名
string symValue{ "0" }; // 字符串形式 符號的值
int position{ -1 }; // 該符號在符號表中的位置 默認(rèn) -1
}symItem;
stack<int> statusStack; // 狀態(tài)棧
stack<symItem> opStack; // 符號棧
stack<string> semanticStack; // 語義棧
? 3.四元式及符號表結(jié)構(gòu)設(shè)計
? 除了以上語法語義分析所需要的數(shù)據(jù)結(jié)構(gòu)外，在對符號棧中內(nèi)容用產(chǎn)生式進行規(guī)約時需要順帶進行產(chǎn)生式對應(yīng)的語義動作，因此在此將每個語義動作模塊化成一個方法函數(shù)，例如在用產(chǎn)生式E->E+F規(guī)約時，首先對操作符棧和狀態(tài)站出棧三次，獲取其中需要的兩個符號（E、F），并將產(chǎn)生式左部push到符號棧中，并依據(jù)gotoTable更新狀態(tài)棧（push），之后執(zhí)行語義動作新建一個變量置入符號表并在產(chǎn)生四元式序列的同時進行E的綜合屬性計算，以此完成語法和語義分析工作。
符號表數(shù)據(jù)結(jié)構(gòu)：
vector<symItem> symbolTable;
四元式數(shù)據(jù)結(jié)構(gòu)：
typedef struct quaternion{
string op; // 操作符
symItem arg1; // 源操作數(shù)1
symItem arg2; // 源操作數(shù)2
symItem result; // 目的操作數(shù)
}quaternion;
臨時變量生成定義方法函數(shù) newTemp();
四元式生成定義方法函數(shù) GEN(op,arg1Index,arg2Index,resIndex); （Index為變量在符號表中的索引）
3.2 系統(tǒng)結(jié)構(gòu)設(shè)計
除了此前介紹所使用的數(shù)據(jù)結(jié)構(gòu)與設(shè)計思路之外為滿足模塊化設(shè)計要求，本次do-while循環(huán)語句的翻譯程序的系統(tǒng)結(jié)構(gòu)設(shè)計有如下功能結(jié)構(gòu)圖：
? 圖1 do-while翻譯程序系統(tǒng)結(jié)構(gòu)圖
3.3 詳細(xì)算法描述
3.3.1 詞法分析模塊
? 在此主要介紹詞法分析主控程序部分，首先將源程序讀入的數(shù)據(jù)變?yōu)樽址问降膇nputStr，然后通過lexicalAnalysis方法對inputStr逐個字符的分析，若讀入為有效字符（非空格等），則按照讀入字符的類型（字母、數(shù)字、特殊符號等）進行各自的處理判斷處理，依次分析后續(xù)字符直到判別為完整的單詞，將單詞的二元式結(jié)果存入lexicalTable中，將輸入指針后移當(dāng)前單詞的長度，持續(xù)分析，直到輸入流分析完畢，最后的詞法分析結(jié)果（單詞流）都會存入lexicalTable中。
? 如下為將關(guān)鍵字和標(biāo)識符判斷細(xì)化后的詞法分析流程圖：
? 圖2 詞法分析流程圖
3.3.2 語法分析模塊
? 語法分析模塊初始化時會讀取文法類Grammar.class中的產(chǎn)生式文法，LR(1)分析表的生成會同步根據(jù)產(chǎn)生式和符號集各個非終結(jié)符對應(yīng)的First集合按照LR(1)項目集構(gòu)造方法構(gòu)造項目集，在語法分析的總控程序中執(zhí)行對單詞流的分析，即按照分析表執(zhí)行移入、規(guī)約、報錯，規(guī)約時按照規(guī)約的產(chǎn)生式編號調(diào)用對應(yīng)封裝好的語義動作函數(shù)（隨分析過程調(diào)用語義計算模塊進行語義計算）即可。
? 圖3 求LR1項目集的閉包算法（closure）流程圖
? 圖4 求轉(zhuǎn)移后的項目集（goto）流程圖
? 圖5 分析表和項目集的同步構(gòu)造流程圖
? 圖6語法分析總控程序流程圖
? 在此說明產(chǎn)生式對應(yīng)封裝的語義動作函數(shù)，例如執(zhí)行如下產(chǎn)生式對應(yīng)的函數(shù)：
A -> do{B}while{C}； { if C.flag goto do.add else next }
? 會對符號棧opStack和狀態(tài)棧statusStack出棧9次（產(chǎn)生式右部的符號數(shù)），記錄其中do、B、C位置處的符號，然后將產(chǎn)生式左部的非終結(jié)符A推入到符號棧opStack，并讀取gotoTable當(dāng)前statusTack棧頂狀態(tài)下規(guī)約到A的狀態(tài)推入到statusStack當(dāng)中，隨后對語義棧執(zhí)行出棧操作并獲取do、B、C位置的屬性值（do.add在入棧時記錄為do-while語句的四元式入口地址序號），并生成一個條件轉(zhuǎn)跳語句的四元式并推入到四元式序列中。
GEN(j_true,C,_,do.add)——表示若C的值為true則轉(zhuǎn)跳至do的地址位置，否則順序執(zhí)行即可。
4 編譯程序?qū)崿F(xiàn)和測試
4.1 編程語言及開發(fā)環(huán)境
PC機：Windows 10 簡體中文專業(yè)版
CPU AMD Ryzen 7 4800H/16G內(nèi)存/1024G硬盤、分辨率 1920x1080 顯示器。
程序語言：C++
集成開發(fā)環(huán)境：VisualStudio 2019
4.2 運行結(jié)果分析
4.2.1 測試用例
4.2.2 運行結(jié)果
? 圖7 LR(1)項目集（部分）
? 圖8 生成的LR(1)分析表（前16個狀態(tài)左半部分，控制臺輸出有換行）
? 圖9 生成的LR(1)分析表（前16個狀態(tài)右半部分）
? 圖10 詞法分析結(jié)果
? 圖11 語法分析結(jié)果
4.2.3 運行結(jié)果分析
? 根據(jù)運行結(jié)果可以看到LR(1)項目集和分析表構(gòu)造無誤（共生成118個LR(1)項目集），同時詞法分析可以正確的輸出單詞二元式序列，所生成的中間代碼中四元式編號0-4為外層do-while的循環(huán)體；5-6為內(nèi)層do-while的循環(huán)體；7-8為內(nèi)層do-while的循環(huán)條件判斷，將“a<=10“的邏輯值（true or false）賦給臨時變量T5，然后判斷T5是否為true，若為true則轉(zhuǎn)跳至對應(yīng)循環(huán)體的起始四元式編號地址，即5號;9-10為外層do-while的循環(huán)條件判斷，轉(zhuǎn)跳地址為0，最終結(jié)果無誤。
5 實踐總結(jié)
? 在本次課程設(shè)計中進行了do-while循環(huán)語句的翻譯程序設(shè)計，由于課設(shè)題目較早的通知，在之前課內(nèi)實驗中就嘗試進行了LR(1)分析方法中有關(guān)項目集和分析表的自動構(gòu)造，雖然在當(dāng)時花費了大量的時間和精力，但相對的在課設(shè)過程中只需要設(shè)計do-while的文法和屬性文法并對相應(yīng)語義動作加以實現(xiàn)即可，對于相關(guān)項目集和分析表自動構(gòu)建的考量和編碼實現(xiàn)也是在本次課設(shè)中感覺自己做的比較好的一個方面。而在對語法分析器的更改中也是對于LR分析器在不同文法中使用的異同有了一定的體會，詞法分析、語法分析、語義分析以及中間代碼生成一系列流程的編碼實現(xiàn)也是讓自己能對程序編譯過程中的前端處理有了更深的理解。也希望在未來的學(xué)習(xí)和實踐中也能維持對高標(biāo)準(zhǔn)的熱情，兩者相輔相成，讓自己更上一層樓。
6 參考文獻(xiàn)
[1] 王生原、董淵、張素琴、呂映芝.編譯原理 (第3版) [M].北京:清華大學(xué)出版社，2015.
[2] 劉剛、趙鵬翀. 編譯原理實驗教程 [M].北京:清華大學(xué)出版社，2017.
相關(guān)代碼已上傳至遠(yuǎn)程倉庫：文章來源：http://www.zghlxwxcb.cn/news/detail-777822.html
編譯原理: 詞法分析+語法分析 DO-WHILE循環(huán)語句的翻譯程序設(shè)計（LR(1)方法、輸出四元式） (gitee.com)文章來源地址http://www.zghlxwxcb.cn/news/detail-777822.html
到了這里，關(guān)于[編譯原理]DO-WHILE循環(huán)語句的翻譯程序設(shè)計（LR(1)方法、輸出四元式）C++實現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
