【編譯原理】部分題目+知識點

引論

計算機語言分類

1. 機器語言與匯編語言
   更接近計算機硬體指令系統的作業
2. 高級語言
   更接近求解問題的表示方法
3. 命令語言
   控制系統的作業——以功能封裝為特征

翻譯程式解釋程式編譯程式區別

翻譯程式是將某一種語言描述的程式（源程式）翻譯成等價的另一種語言描述的程式描述的程式（目標程式）
解釋程式是邊解釋邊執行的，不產生目標程式，速度要慢，
編譯程式則是將高級語言程式翻譯成匯編/機器語言程式，計算機直接執行翻譯后的程式，速度要快，

編譯系統的總體結構

詞法分析器-> 語法分析器->語意分析和中間代碼生成器->代碼優化->目標代碼生成器
全程序均有表格管理和出錯處理，

詞法分析的功能是什么？

詞法分析由詞法分析器完成，它從左到右掃描源程式——發現一個字串，則將該字串轉化成單詞（token）串；同時查詞法錯誤，進行識別符號登記——符號表管理，期間需要刪去空格字符和注解等
輸入：字串
輸出：token（種別碼，屬性值）序列

語法分析的功能是什么？

實作組詞成句，識別詞組成的各類語法成分，指出語法錯誤，制導翻譯，
輸入：token序列
輸出：語法成分

語意分析的功能是什么？

分析由語法分析器識別出的語法單位的語意
獲取識別符號的屬性：型別、作用域等，
語意檢查：運算的合法性、取值范圍等，
子程式的靜態系結：代碼的相對地址
變數的靜態系結：資料的相對地址

中間代碼的特點？

簡單規范、與機器無關、易于優化與轉換

代碼優化

對中間代碼的優化處理：對代碼進行等價變換以求提高效率——提高運行速度和節省存盤空間（機器有關和機器無關，詳見計算機體系結構），

目標代碼生成

將中間代碼轉換成目標機上的機器指令代碼或匯編代碼

表格管理是什么

管理各種符號表（常數、標號、變數、程序、結構……），查、填（登記、查找）源程式中出現的符號和編譯程式生成的符號，為編譯的各個階段提供資訊，

錯誤處理包含哪些內容

進行各種錯誤的檢查、報告、糾正，以及相應的續編譯處理（如：錯誤的定位與區域化）
詞法：識別符號命名是否符合規范等等
語法：陳述句結構、運算式結構是否符合
語意：型別是否匹配

簡單介紹編譯的前端和后端

**前端：**與源語言有關、與目標機無關的部分詞法分析、語法分析、語意分析與中間代碼生成、與機器無關的代碼優化，
**后端：**與目標機有關的部分、與機器有關的代碼優化、目標代碼生成，

編譯程式生成可以采用哪些技術

1. 編譯程式的自展技術
2. 利用編譯程式自動生成器

詞法分析

單詞符號有哪些分類

1. 關鍵字
2. 識別符號
3. 常數
4. 運算子
5. 界限符 , ; ( ) : =等

已經可以得知單詞在機內表示的方式為一個二元式（單詞種別碼，單詞自身值），那種別碼和自身值確定規規則是什么樣的？

種別碼
關鍵字：一種一碼
識別符號：一種碼
常數：一型別一碼
界限符：一符一碼
單詞值
并不是所有的單詞都有，關鍵字、界限符、運算子就沒有自身值，常數和識別符號的自身值為本身或者符號表入口地址，

詞法分析的程序中，會碰到各種問題，有什么問題以及解決方法是什么？

1. 詞法分析的程序中會有雙字符運算子，像是>=,<=,==等，如果僅僅掃描一個字符的時候掃描到>的時候并不能直接判斷其為>運算子，需要結合后面一個字符來看，因此需要用到超前掃描下一個字符來判斷，解決該問題，
2. 預處理問題，掃描程序中，剔除源程式里面的無用符號、空格、換行、注釋等，
3. 源程式難免發生錯誤，首先需要進行一個定位，進行行列計數，再來可以采用恐慌模式，忽略或者替換插入字符繼續進行分析等等，

編譯程序中，會維持一張符號表，符號表在編譯程序中的作用是什么？

它用于存盤程式編譯或運行程序中所使用的變數（識別符號）和常量（數字常數、字符常數）等資訊，
在詞法分析階段：該階段主要建立符號表，將不重復的識別符號，數字常數和字符常數的性質填入符號表中，并且將變數（常數）在符號表中的入口地址寫到自身的token字中，
在語法分析階段：主要使用符號表，在分析程序中，需要用到某個識別符號（或常數）時，就從符號表的指定入口查找出改符號，
在語意分析及中間代碼生成階段：主要是查填符號表，在生成四元式時，通常不是使用變數的名字而是使用它們在符號表的入口地址，另外，在翻譯說明陳述句時，要向符號表中填入變數的型別資訊，
資料存盤分配：將變數（或常數）所使用的資料區映像地址寫入符號表中的地址（ADDR）欄，若資料區是動態資料，則在符號表中存盤程序層號和位移量等資訊，待運行時再計算具體地址，
代碼優化階段：使用符號表，一方面遇到變數時，要到符號表中查找它的具體資訊，另一方面，在優化程序中，也有可能使用符號表，
目標代碼生成階段：查找符號表，為最終生成目標代碼提供必要的資訊，

符號表內容有什么

符號表中包括名字（NAME）、型別（TYPE）、種屬（KIND）、數值（VAL）、作用域和地址（ADDR）等欄，還帶有一個字串表，

語法分析

自頂向下分析面臨的問題有什么？

1. 存在回溯
   文法中每個非終結符的產生式右部稱為該符號的候選式，如果有多個候選式左端第一個符號相同，則語法分析程式無法根據當前輸入符號選擇產生式，只能試探，可以通過提取左公因子改寫文法來解決，
2. 左遞回問題
   無法根據左遞回文法進行自頂向下的分析，不過可以消除左遞回，
3. 二義性
   可以通過重寫文法來消除二義性，引入新的語法變數，
4. CFG的使用限制
   沒有一種方法能夠有效地分析所有背景關系無關文法，存在無法處理的CFG，且每種方法都有適用范圍，

消除左遞回例題

1. 直接左遞回
   E -> E+T | T
   T -> T*F | F
   F -> (E) | id
   消除后
   E -> T E’
   E’ -> +T E’| ε
   T -> F T’
   T’ -> *F T’ | ε
   F -> (E) | id
2. 間接左遞回
   S→Ac|c
   A→Bb|b
   B→Sa|a
   將B的定義代入A的產生式
   A -> Sab|ab|b
   將A的定義代入S中
   S -> Sabc | abc| bc | c
   消除直接左遞回：
   S -> abcS’ | bcS’ | cS’
   S’ -> abcS’|ε
   洗掉多余的產生式A ->Sab|ab|b和B->Sa|a
   結果為 S-> abcS’|bcS’|cS’，S’->abcS’|ε，

自頂向下的分析方法的基本思想和程序

基本思想：
尋找輸入符號串的最左推導
試圖根據當前輸入單詞判斷使用哪個產生式
基本程序：
從根開始，按與最左推導相對應的順序，構造輸入符號串分析樹，

候選式無回溯的條件

設A→α1|α2|…|αn是所有的A產生式
如果各個αi能推匯出的首終結符各不相同，則可以構造無回溯的分析，自頂向下希望文法滿足無回溯，

LL(1)分析法

分析表構造

1. 對于每一個產生式執行(2)和(3);
2. 對于FIRST(α)中的每一終結符a，將A -> α填入M[A,a];
3. 如果ε屬于FIRST(α)，則對FOLLOW(A)中每一個終結符b，將A-> α填入M[A,b]，同時，若$在Follow(A)中，則將A->α，填入M[A,$];
4. 將所有無定義的M[A,a]標上錯誤標志，

題目 構造給定文法的預測分析表

S -> AB
A -> Ba | ε
B -> Db | D
D -> d | ε
求出first和follow
first(D) = {d,ε}
first(B) = {b,d,ε}
first(A) = {a,b,d,ε}
first(S) = {a,b,d,ε}
follow(S) = {$}
follow(B) = {a,$}
follow(D) = {a,b,$}
follow(A) = {d,b,$}

由此可見，這個表格是用沖突的，這個文法其實并不是LL(1)文法，

考題-文法計算題

去年文法計算題

判斷是否為LL(1)文法，分三步走：

1. 有左遞回不是LL(1)文法(無法對左遞回的文法進行自頂向下的分析)
2. 若A -> α 1 ∣ . . . ∣ α i ∣ . . . ∣ α n \alpha_1|...|\alpha_i|...|\alpha_n α1?∣...∣αi?∣...∣αn?,則First( α i \alpha_i αi?) ∩First( α j \alpha_j αj?)=? ( i!=j )
3. 若 α i \alpha_i αi?-*->ε(i只能有一個)，則對First( α j \alpha_j αj?) ∩Follow(A)=?(i!=j)

該文法為LL(1)文法，

1. 首先，文法無左遞回
2. 求First集和Follow集合
   First(S) = {long int}, First(A) = {long int}, First(B) = {id}, First(C ) = {, ε}
   Follow(S) = {$}, Follow(A) = {id}, Follow(B)={$}, Follow(C ) = {$}
   產生式左部為S: ε不包含于First(S)，且產生式只有一個，無二義性，
   產生式左部為A: ε不包含于First(A), First(int)∩First(long) = ?，無二義性，
   產生式左部為B: ε不包含于First(B), 且產生式只有一個無二義性，
   產生式左部為C: ε包含于First(C ),但First(,idC) ∩ Follow(C ) = ?，并且First(,idC )∩First(ε )=?，
   所以該文法為LL（1）文法，
   LL分析表如下：

如果再加一個讓分析 int a,b 分析程序中中分析堆疊中元素變化如下，
首先堆疊中元素為：$ S next:int,按照分析表彈出S移入AB
堆疊中元素為：$ B A next:int，按照分析表彈出A移入int
堆疊中元素為：$ B int next:int，此時堆疊頂元素 = int,彈堆疊移入下一個符號.
堆疊中元素為：$ B next:id，按照分析表彈出B，移入idC
堆疊中元素為：$ C id next:id，堆疊頂元素 = id，彈堆疊移入下一個符號.
堆疊中元素為：$ C next:,，按照分析表彈出C，移入,idC
堆疊中元素為：$ C id , next:,，堆疊頂元素=,，彈堆疊移入下一個符號
堆疊中元素為：$ C id next:id，堆疊頂元素=id，彈堆疊移入下一個符號
堆疊中元素為：$ C next:$，按照分析表彈出C,移入ε，相當于沒移入，
堆疊中元素為：$ next:$，堆疊頂元素=$，分析成功結束，
所以推導程序如下
S -> AB -> int B -> int id C -> int id , id C -> int id,id

介紹自底向上的語法分析技術

從輸入串出發，反復利用產生式進行歸約，如果最后能得到文法的開始符號，則輸入串是句子，否則輸入串有語法錯誤，核心是尋找句柄，

最左推導和最右推導

最左推導：每次推導都施加在句型的最左邊的語法變數上，
最右推導：每次推導都施加在句型的最右邊的語法變數上，

介紹一下句柄

最右句型（規范規約）中某個產生式體匹配的子串，它的歸約代表了該最右句型的最右推導的最后一步；正式定義：如果S=>*αAw =>*αβw；那么緊跟α之后的A→β是最右句型αβw的一個句柄；
在一個最右句型中，句柄右邊只有終結符號
如果文法是無二義性的，那么每個句型都有且只有一個句柄，

移入-規約分析法確定句柄的方法

1. 優先法
2. 狀態法

LR

LR語法分析器的格局

LR語法分析器的格局包含堆疊中內容和余下的輸入

專案集 I 的相容及LR(0)判定

如果 I 中至少含兩個歸約專案，則稱 I 有歸約—歸約沖突
如果 I 中既含歸約專案，又含移入專案，則稱 I 有移入—歸約沖突
若既沒有歸約-歸約沖突也沒有移入規約沖突，則稱它為相容的，為LR(0)文法，

SLR的不足

SLR只孤立地考察輸入符號是否屬于歸約專案A→α.相關聯的集合FOLLOW（A），而沒有考察符號串α所在規范句型的“背景關系”，

考題-文法計算題

第四個文法計算題
參考博客傳送門



該題目程式gitee地址：https://gitee.com/loxs/compileEXE.git

語法制導翻譯

語法制導

背景關系無關文法和屬性的結合
屬性與文法符號相關聯，動作和產生式相關聯，
根據需要將文法符號和某些屬性相關聯，并通過語意規則來描述如何計算屬性的值，

語法制導翻譯

在產生式體中加入語意動作，并在合適的實際執行這些動作，

繼承屬性和綜合屬性

綜合屬性：分析樹節點N上的非終結符號A的屬性值由N的產生式所關聯的語意規則來定義，這個產生式的頭一定是A，
必然通過N的子節點或者N本省來定義，
繼承屬性：分析樹節點N屬性值由N的父節點所關聯的語意規則來定義，這個產生式的體中必定包含B，
依賴于N的父節點，N本身，N的兄弟節點的屬性值，

S屬性的SDD

每個屬性都是綜合屬性
都是根據子構造的屬性來計算整個構造的屬性
在依賴圖中總是以子節點的屬性值來計算父節點的屬性值，可以和自頂向下、自底向上的語法分析程序一起計算，
自底向上：在構造分析樹的子節點同時計算相關的屬性，
自頂向下：在遞回子程式法中，在程序A()的最后計算A的屬性，

L屬性的SDD

每個屬性要么是綜合屬性，要么是繼承屬性且產生式A -> X1X2…Xn中計算Xi.a的規則只能使用
A的繼承屬性
Xi左邊的文法符號Xj的繼承屬性或綜合屬性
Xn自身的繼承屬性和綜合屬性，且這些屬性依賴關系不形成環

具有受控副作用的語意規則

有副作用原因：屬性文法沒有副作用，但是會增加描述的復雜度，
比如語法分析的時如果沒有副作用，符號表就必須作為屬性傳遞，可以把符號表作為全域變數，然后通過副作用函式來添加新識別符號，
受控的副作用：一般屬性值計算（基于屬性值或常量進行的）之外的功能，不會對屬性求值造成約束，即可以按照任何拓撲結構求值，不會影響最終的結果，添加了部分簡單約束，

語法制導的翻譯方案

是在產生式體中嵌入程式片段的背景關系無關文法

后綴翻譯方案

文法可以自底向上分析且SDD是S屬性的，
可以構造SDT，且所有動作都放在產生式的最后；分析程序中按照這個產生式規約時執行這個動作，計算得到的屬性值都放在堆疊中，
所有動作都在產生式最右端的SDT稱為后綴翻譯方案，

產生式內部帶有語意動作的SDT

一個動作左部的所有符號（所有符號）處理完成后，就立即執行這個動作，
B -> X{a}Y
自底向上分析時，a在X出現在堆疊頂時執行，
自頂向下分析時，在試圖展開Y或者在輸入中檢測到Y時執行，
后綴SDT以及實作L屬性的SDT可以在分析時完成，

L屬性的自底向上實作

首先構造出L屬性SDD的SDT，即在非中介符號前計算其繼承屬性
若產生式A->α {a} β，則對每個語意動作a，引入標記非終結符號M，且M->ε，
定義M->ε{a’}，其中a’的構造方法如下：
將a中需要A或者其他屬性作為M的繼承屬性進行拷貝，
按照a中的規則計算各個屬性，作為M的綜合屬性，
例子：A->{B.i = f(A.i);}BC
引入標記非終結符號M后
A->MBC
M->ε {M.i = A.i;M.s = f(M.i);}
A.i為A的繼承屬性，a的繼承屬性分析堆疊BC下方，

考題-文法翻譯題

三地址代碼（偷個懶按照從1開始做了）

1:if x<3 goto 3
2:goto 11
3:if y<2 goto 5
4:goto 15
5:if c<1 goto 7
6:goto 15
7:t1=x-1
8:y=t1
9:goto 3
10:goto 15
11:if x>1 goto 13
12:goto 15
13:t2=x-2
14:x=t2
15:

(2) 11
(3) 4 6 10 12
該題目程式gitee地址：https://gitee.com/loxs/compileEXE2.git

運行時刻環境

概述

運行時刻環境
確定訪問變數時使用的機制
程序之間的連接
引數傳遞
和作業系統、輸入輸出設備相關的其他介面

編譯程式除了要關心目標代碼生成的問題之外，還必須考慮程式運行時使用的資料區域管理的問題，

為什么要使用資料區

程式運行時各種資料都必須放在記憶體里，便于訪問和使用，
另外涉及資料區的管理：
記憶體永遠不能滿足要求
必須找到存盤的資料
按照程式單位分配和管理資料區

資料區存盤內容

變數和常數：用戶自己定義
臨時單元：源程式沒有，編譯程式在生成中間代碼時建立和使用
形式單元：存放程序或函式間傳遞的引數
回傳地址：回傳主調程式的入口
保護區：保護主調程式暫存器內容，恢復現場
資料訪問控制資訊
存盤管理：堆疊分配、堆管理、垃圾回收

存盤

目標程式代碼放在代碼區
靜態區、堆區、堆疊區分別放不同型別生命期的資料值，即資料區，

靜態和動態存盤分配

靜態分配

編譯器在編譯時刻就可以做出存盤分配決定，不需要運行時刻的情景，
要求：
不存在可變長的陣列，可變長的字串、指標，
不存在函式的遞回與嵌套，
全域變數

會在符號表中按照物件屬性順序分配資料區，從而建立一個資料映像，運行時按照此映像分配實際的記憶體資料區，

動態分配

堆疊式存盤

在程序的呼叫/回傳同步進行分配和回收，值的生命期和程序生命期相同，
有可變陣列，有程序和函式的遞回嵌套，
活動樹
程序呼叫在時間上總是嵌套的：后呼叫的先回傳
因此可以用堆疊式分配來處理程序活動所需的記憶體空間，
程式運行的所有程序可以用 一個樹來表示，

1. 每個節點對應一個程序活動
2. 根節點對應main函式的活動
3. 程序p的某次程序活動對應的子節點對于此次活動呼叫的各個程序活動，

程序呼叫和回傳由控制堆疊進行管理
每個活躍的活動對于堆疊中的一個活動記錄
活動記錄按斬訓動的開始時間，從堆疊底到堆疊頂排列，

運行堆疊：把控制堆疊中的資訊拓廣到包括程序活動所需的所有區域資訊

堆疊中的變長資料:如果資料物件的生命期局限于程序活動的生命期，就可以分配在運行時刻堆疊中，
top指向實際堆疊頂
top_sp用于尋找頂層記錄的定長欄位

訪問鏈
被用于訪問非區域的資料
如果程序p在宣告時嵌套在程序q的宣告中，那么p的活動記錄中訪問鏈指向最上層的q的活動記錄
從堆疊頂活動記錄開始，訪問鏈形成了一個鏈路嵌套深度逐一遞減，

如果深度為np的程序p訪問變數x，而變數x在深度為nq的程序中宣告，那么
從當前活動記錄出發，沿訪問鏈前進np-nq次找到的活動記錄中的x就是要找的變數位置，

x相對于活動記錄的偏移量和np-nq在編譯時刻已知

顯示表
背景：用訪問鏈訪問資料時，如果嵌套深度大，則訪問效率差，
使用陣列d為每個嵌套深度保留一個指標，指標d[i]指向最高的深度為i的活動記錄，
如果程式p中訪問深度為i的程序q的變數x，那么d[i]直接指向相應的q的活動記錄，
維護：

1. 呼叫程序p時，在p的活動記錄中保留d[np]的值，并將d[np]設定為當前活動記錄，
2. 從p回傳時，恢復d[np]的值

考題

堆存盤

在編譯是無法確定資料區的大小，在程序的入口處也確定不了資料區的大小，因此無法使用靜態或堆疊式分配方法，
條件：有static型別，指標型別和表單等變數，
存盤分配器
為每個記憶體請求分配一段連續的適當大小的堆空間，首先從空閑的堆空間分配；如果不行則從作業系統中獲取記憶體、增加堆空間，
回收：把回收的空間回傳空閑空間緩沖池，以滿足其他的分配，
評價特性：空間效率（需要的堆空間最小，減小碎片）程式效率（充分使用記憶體系統的層次，提高效率）、低開銷（使分配/識訓記憶體的操作盡可能高效）
堆空間的分配及管理
固定長分塊法：將堆空間分成帶下相同的塊，使用鏈表連接各個單元；適用于型別單一或長度一致的資料型別，
可變長分塊法：將堆空間分成長度不同的塊，
外部碎片和內部碎片問題
堆空間不可以隨便釋放，釋放方法：參照計數法、無用單元收集，

代碼生成

主要問題

正確性
易于實作、測驗和維護
輸入IR的選擇
四元式、三元式、位元組代碼、堆疊機代碼、后綴表示、抽象語法樹、DAG圖
輸出
RISC、CISC
可重定向代碼、匯編語言

目標機模型

使用三地址機器的模型
指令

1. 加載 2. 保存 3. 計算 4. 無條件跳轉 5. 條件跳轉

尋址模式
和匯編中的差不多

目標代碼中的地址

如何將IR中的名字轉換成目標代碼中的地址？
不同區域中的名字采用不同尋址方式，

活動記錄靜態分配

每個程序靜態分配一個資料區域，開始位置用staticArea表示

• call callee的實作
• callee 中的return

活動記錄堆疊式分配

暫存器SP指向堆疊頂
第一個程序（main）初始化堆疊區
程序呼叫指令序列
ADD SP,SP,#caller.recordSize //增加堆疊指標
ST 0(SP),#here + 16// 保護回傳地址
BR callee.codeArea// 轉移到被呼叫者
回傳指令序列
BR *0(SP)// 被呼叫者執行，回傳呼叫者
SUP SP,SP,#caller.recordSize//呼叫者減低堆疊指標

基本塊和流圖

中間代碼的流圖表示法

中間代碼劃分成基本塊，控制流只能第一個指令進入，除了基本塊最后一個ie指令，控制流不會跳轉停機
流圖的節點是基本塊，流圖的邊指明了哪些基本塊可以跟在一個基本塊之后運行，

流圖可以作為優化的基礎

它指出了基本塊之間的控制流
可以根據流圖了解到一個值是否會被使用等資訊

劃分基本塊

確定首指令（基本塊的第一個指令）滿足下列三條之一即可：
中間代碼的第一個三地址指令
任意一個條件或無條件轉移指令的目標指令
緊跟在一個條件/無條件轉移指令之后的指令
確定基本塊
每個首指令對應于一個基本塊：從首指令（包含）開始到下一個首指令（不含）

一個簡單的代碼生成器

重要子函式：getReg(I)
為三地址指令I選擇暫存器；
根據暫存器描述符和地址描述符、以及資料流資訊來分配最佳的暫存器；
得到的機器指令的質量依賴于getReg函式選取暫存器的演算法
代碼生成時必須更新暫存器描述符和地址描述符，

彩蛋

試驗的翻譯方案：選用不同的M可能會避免一些潛在的沖突，但是，也有一些另外的作用，if和if else得選一樣的M，
全域變數

static int instr=0;  // 指令序號從0開始
int offset; // 偏移量 - 宣告陳述句對于
queue<Gen> gens;//指令緩沖佇列 便于回填

宣告陳述句

P -> M1 D S{}
D -> L id ; N1 D{}
L -> int
{
    L.type=1;
    L.width=4;
}
L -> float
{
    L.type=2;
    L.width=8;
}
M1 -> ε
{
    offset = 0;
}
N1 -> ε
{
    table.put(id.lexeme,L.Type,L.width);
    offset = offset+L.width;
}

賦值和運算陳述句

/*
	mergeType 型別轉換&&型別檢查 funType(int,float)=float 這種的
	checkType 檢查型別是否匹配
	呼叫一次gen，instr++,并且每個指令都有自己的instr編號便于回填
*/
S -> id = E ;
{
    checkType(id.Type,E.type);
    gens.push(gen(table[id.lexeme]=E.addr));
}
E -> E1 + T
{
    E.addr = newTemp();
    E.type=mergeType(E1.type,T.type);
    gens.push(gen(E.addr=E1.addr+T.addr));
}
E -> E1 - T
{
    E.addr = newTemp();
    E.type=mergeType(E1.type,T.type);
    gens.push(gen(E.addr=E1.addr-T.addr));
}
E -> T
{
    E.addr=T.addr;
    E.type=T.type;
}
T -> F
{
    T.addr=F.addr;
    T.type=F.type;
}
T -> T1 * F
{
    T.addr = newTemp();
    T.type=mergeType(T1.type,F.type);
    gens.push(gen(T.addr=T1.addr*F.addr));
}
T -> T1 / F
{
    T.addr = newTemp(); 
    T.type=mergeType(T1.type,F.type);
    gens.push(gen(T.addr=T1.addr/F.addr));
}
F -> ( E )
{
    F.addr=E.addr;
    F.type=E.type;
}
F -> id
{
    F.addr=table[id.lexeme];
    F.type=id.type;
}
F -> digits
{
    F.addr=table[digits.lexeme];
    F.type=digits.type;
}

布爾運算式

C -> E1 > E2
{
    C.trueList=makelist(instr);
    C.falseList=makelist(instr+1);
    gens.push(gen(if E1>E2 goto _));
    gens.push(gen(goto _));
}
C -> E1 < E2
{
    C.trueList=makelist(instr);
    C.falseList=makelist(instr+1);
    gens.push(gen(if E1<E2 goto _));
    gens.push(gen(goto _));
}
C -> E1 == E2
{
    C.trueList=makelist(instr);
    C.falseList=makelist(instr+1);
    gens.push(gen(if E1==E2 goto _));
    gens.push(gen(goto _));
}
C -> C1 || M7 C2
{
    backpatch(C.falselist,M1.instr);
    C.truelist=merge(C1.truelist,C2.truelist);
    C.falselist=C2.falselist;
}
C -> C1 && M7 C2
{
    backpatch(C.truelist,M1.instr);
    C.truelist=C2.truelist;
    C.falselist=merge(C1.falselist,C2.falselist);
}
C -> ( C1 )
{
    C.falselist=C.falselist;
    C.truelist=C.truelist;
}
C -> true
{
    C.truelist=makelist(instr);
    gens.push(gen(goto _));
}
C -> false
{
    C.falselist=makelist(instr);
    gens.push(gen(goto _));
}
C -> ! C1
{
    C.falselist=C.truelist;
    C.truelist=C.falselist;
}
M7 -> ε
{
    M1.instr=instr;
}

控制陳述句

S -> if ( C ) M2 S1
{
    backpatch(C.truelist,M1.instr);
    S.nextlist=merge(C.falselist,S1.nextlist);'
}
S -> if ( C ) M2 S1 N2 else M4 S2
{
    backpatch(C.truelist,M1.instr);
    backpatch(C.falselist,M2.instr);
    S.nextlist=merge(S2.nextlist,merge(N2.nextlist,S1.nextlist));
 }
S -> while M5 ( C ) M6 S1
{
    backpatch(S1.nextlist,M1.instr);
    backpatch(C.truelist,M2.instr);
    S.nextlist=C.falselist;gens.push(gen(goto M1.instr));
}
S -> S1 M7 S2
{
    S.nextlist=S2.nextlist;
    backpatch(S1.nextlist,M1.instr);
}
M1_7 -> ε
{
    M1.instr=instr;
}
N2 -> ε
{
    N2.nextlist=makelist(instr);
    gens.push(gen(goto _));
}

參考博客：https://blog.csdn.net/qq_39384184/article/details/86037568