大學(xué)期間的筆記補(bǔ)全铅歼。編譯原理內(nèi)容太多分幾次公壤。
課本《編譯原理》第三版，陳火旺等編著谭贪。
筆記總目錄：
一境钟、引論
二、高級語言及其語法描述
三俭识、詞法分析
四慨削、語法分析——自上而下分析
五、語法分析——自下而上分析
六套媚、屬性文法和語法制導(dǎo)翻譯
七缚态、語義分析和中間代碼生成
八、優(yōu)化
九堤瘤、目標(biāo)代碼生成
編譯原理結(jié)束玫芦！
六、屬性文法和語法制導(dǎo)翻譯
6.1 屬性文法
在上下文無關(guān)文法的基礎(chǔ)上本辐，在描述語義動作時桥帆，為每個文法符號（終結(jié)符和非終結(jié)符）配備若干相關(guān)的“值”，如“類型”慎皱，“地址”等老虫，稱為屬性。
對文法的每個產(chǎn)生式配備一組屬性計算規(guī)則稱為語義規(guī)則茫多。
每個文法符號聯(lián)系于一組屬性祈匙，且對每個產(chǎn)生式都給出其語義規(guī)則的文法稱為屬性文法。
6.1.1 屬性和語義規(guī)則
-
屬性的特征
- 代表與文法符號相關(guān)信息天揖，如類型夺欲、值、代碼序列今膊、符號表內(nèi)容等些阅；
- 可以進(jìn)行計算和傳遞；
-
屬性的分類
- 綜合屬性
-
繼承屬性
繼承屬性
對于一些產(chǎn)生式中的屬性而言斑唬，
任意一個產(chǎn)生式左邊的非終結(jié)符帶有的屬性是：
- 綜合屬性：產(chǎn)生式右邊包含語法生成樹子節(jié)點(diǎn)的屬性扑眉，
- 繼承屬性：產(chǎn)生式右邊僅僅由語法生成樹兄弟節(jié)點(diǎn)或父節(jié)點(diǎn)屬性構(gòu)成。
若所有產(chǎn)生式（不再有還未寫出的產(chǎn)生式）赖钞，屬性僅在產(chǎn)生式右邊的非終結(jié)符出現(xiàn)，則是繼承屬性聘裁。
-
注意：
終結(jié)符只有綜合屬性雪营，由詞法分析器提供。
非終結(jié)符既可有綜合屬性也可有繼承屬性衡便，文法開始符號的所有繼承屬性作為屬性計算前的初始值献起。
-
對出現(xiàn)在產(chǎn)生式右邊的繼承屬性和出現(xiàn)在產(chǎn)生式左邊的綜合屬性都必須提供一個計算規(guī)則洋访。屬性計算規(guī)則中只能使用相應(yīng)產(chǎn)生式中的文法符號的屬性；
出現(xiàn)在產(chǎn)生式左邊的繼承屬性和出現(xiàn)在產(chǎn)生式右邊的綜合屬性不由所給的產(chǎn)生式的屬性計算規(guī)則進(jìn)行計算谴餐，它們由其它產(chǎn)生式的屬性規(guī)則計算或者由屬性計算器的參數(shù)提供姻政。
這也是為什么之前說的時候前提是 “對于一個產(chǎn)生式中的屬性而言“。
-
S-屬性文法
僅僅使用綜合屬性的屬性文法岂嗓。
- 在語法樹中汁展，一個結(jié)點(diǎn)的綜合屬性的值由其子結(jié)點(diǎn)的屬性值確定。
- 使用自底向上的方法在每一個結(jié)點(diǎn)處使用語義規(guī)則計算綜合屬性的值厌殉。
S-屬性文法非常適合配合LR分析法進(jìn)行計算食绿。
-
L-屬性文法
如果每個產(chǎn)生式
的每條語義規(guī)則計算的屬性
的綜合屬性；或者是
的繼承屬性公罕，但它僅依賴：
- 該產(chǎn)生式中
的屬性器紧；
-
S-屬性文法屬于L-屬性文法。
左遞歸文法不可用LR(1)分析法楼眷。
- 該產(chǎn)生式中
6.2 語法制導(dǎo)翻譯
直觀上說就是為每個產(chǎn)生式配上一個翻譯子程序（稱語義動作或語義子程序）铲汪，并且在語法分析的同時執(zhí)行它。
語義動作一方面規(guī)定了產(chǎn)生式產(chǎn)生的符號串的意義罐柳，另一方面又按照這種意義規(guī)定了生成中間代碼應(yīng)做的基本動作掌腰。
定義：在語法分析過程中，當(dāng)一個產(chǎn)生式獲得匹配（自上而下分析）或用于歸約（自下而上分析）時硝清，此產(chǎn)生式對應(yīng)的語義子程序進(jìn)入工作辅斟，完成既定翻譯任務(wù)，產(chǎn)生中間代碼芦拿。
-
作用
如果語義動作不是簡單的計值程序士飒，而是某種中間代碼的產(chǎn)生程序，那么隨著語法分析的進(jìn)展蔗崎，這種代碼也逐步生成酵幕。
-
語法制導(dǎo)翻譯的作用
- 產(chǎn)生中間代碼
- 產(chǎn)生目標(biāo)指令
- 對輸入串進(jìn)行解釋執(zhí)行
七、語義分析和中間代碼產(chǎn)生
7.1 中間語言
中間語言（復(fù)雜性界于源語言和目標(biāo)語言之間）的好處：
- 便于進(jìn)行與機(jī)器無關(guān)的代碼優(yōu)化工作
- 易于移植
- 使編譯程序的結(jié)構(gòu)在邏輯上更為簡單明確
7.1.1 常用中間語言
-
后綴式缓苛，逆波蘭表示
- 表達(dá)式：-(a+b)*(c+d)-(a+b+c)
- 后綴式：ab+-cd+*ab+c+-
-
圖表示
- DAG
- 抽象語法樹
-
三地址代碼
- 三元式
- 四元式
- 間接三元式
7.1.2 三地址代碼
-
四元式
一個帶有四個域的記錄結(jié)構(gòu)芳撒，這四個域分別稱為op, arg1, arg2及result。
例子：計算a:=b*(-c)+b*(-c)：
計算過程- 四元式之間的聯(lián)系通過臨時變量實(shí)現(xiàn)未桥。
- 單目運(yùn)算只用arg1域笔刹，轉(zhuǎn)移語句將目標(biāo)標(biāo)號放入result域。
- arg1,arg2,result通常為指針冬耿，指向有關(guān)名字的符號表入口舌菜，且臨時變量填入符號表。
7.2 說明語句
7.3 賦值語句的翻譯
7.4 布爾表達(dá)式的翻譯
-
布爾表達(dá)式：用布爾運(yùn)算符把布爾量亦镶、關(guān)系表達(dá)式聯(lián)結(jié)起來的式子日月。
- 布爾運(yùn)算符：and, or, not 袱瓮；
- 關(guān)系運(yùn)算符 ＜,≤,＝, ≠，＞ ,≥
-
布爾表達(dá)式的兩個基本作用:
- 用于邏輯演算,計算邏輯值;
- 用于控制語句的條件式.
-
產(chǎn)生布爾表達(dá)式的文法:
- E→E or E | E andE | ?E | (E) | id rop id | id
- 運(yùn)算符優(yōu)先級：布爾運(yùn)算由高到低：not > and > or爱咬，同級左結(jié)合關(guān)系運(yùn)算符同級尺借，且高于布爾運(yùn)算符
-
兩種計算方法：
-
計算邏輯值
- 如同計算算術(shù)表達(dá)式一樣,一步步算
- 采用優(yōu)化措施（短路計算）
-
作為條件控制：
條件語句
if E then S1 else S2。賦予E兩種出口：一真一假精拟。
6-3.pngif語句（條件語句）的四元式怎么寫燎斩？和
：因為在歸約B的時候并不知道
以及他們的入口地址，跳轉(zhuǎn)位置不明確串前，所以必須要把跳轉(zhuǎn)信息記錄下來等待之后補(bǔ)充具體跳轉(zhuǎn)的地址瘫里。故將跳轉(zhuǎn)信息存入
。
-
兩遍掃描
- 為給定的輸入串構(gòu)造一棵語法樹荡碾；
- 對語法樹進(jìn)行深度優(yōu)先遍歷谨读，進(jìn)行語義規(guī)則中規(guī)定的翻譯。
-
如何一遍掃描坛吁？
四元式merge時改變的第四位的數(shù)值不是表示跳轉(zhuǎn)劳殖，而是表示（暫時的）鏈接，便于之后找到了跳轉(zhuǎn)地址全部遍歷重寫拨脉。
四元式序列求解過程
思路總結(jié)_1
思路總結(jié)_2
思路總結(jié)_3
-
7.5 控制語句的翻譯
控制語句在歸約的時候：
- if-then-else：只有N的時候會產(chǎn)生jump中間語句哆姻，其他操作都只是改變跳轉(zhuǎn)地址
- while-do：只需要在最后生成新的jump中間語句，其他操作都只是改變跳轉(zhuǎn)地址
If語句的翻譯
- N的作用：為了在if-then-else歸約時不需要在兩種結(jié)果之間加上強(qiáng)制跳出的中間代碼玫膀。
while語句的翻譯
- 不需要N矛缨，因為跳轉(zhuǎn)語句插入在末尾，不需要復(fù)雜的操作帖旨。
- while-do語句在歸約為
時要產(chǎn)生一條中間代碼箕昭，用戶在do的內(nèi)容執(zhí)行完之后跳回while的開始重新循環(huán)
- while-do語句歸約后false的出口地址寫成
。
- 只要是
goto語句
-
goto L1 有兩種情況：
- 先定義L1落竹，再出現(xiàn)goto L1
- 先出現(xiàn)goto L1（L1地址未知），再出現(xiàn)L1
-
解決：符號表
當(dāng)出現(xiàn)情況1货抄，掃描到L1時先將L1的信息填入符號表述召，定義否為“是”，地址為L1的起始地址
當(dāng)出現(xiàn)情況2蟹地，每當(dāng)掃描到goto卻沒有L1积暖，先將L1插入，定義否為“否”怪与，地址為goto語句的next信息夺刑；直到掃描到L1，將定義否改為“是”琼梆，為地址中g(shù)oto語句的next信息賦值性誉，再將地址改為L1的起始地址。
名字 類型 定義否 地址 L1 標(biāo)號 是/否 L1起始地址 / 傳遞的goto語句的next
case語句
- 翻譯法1：L1-if-goto-L2-if-goto-......
- 翻譯法2：L1-L2-......-if-goto-if-goto-......
7.6 過程調(diào)用的處理
- 過程調(diào)用文法：
- S -> call id (Elist) ：for隊列queue中的每一項p茎杂，有emit('param' p)错览；循環(huán)之后emit('call' id.place)
- Elist -> Elist, E ：將E.place加入到queue的隊尾
- Elist -> E ：初始化queue僅包含E.place
八、優(yōu)化
優(yōu)化：對程序進(jìn)行等價變換煌往，使得從優(yōu)化后的程序出發(fā)倾哺，能生成更有效的目標(biāo)代碼。
8.1 概述
- 優(yōu)化原則：
- 等價原則：優(yōu)化前后不改變程序運(yùn)行結(jié)果
- 有效原則：使優(yōu)化后產(chǎn)生的目標(biāo)代碼運(yùn)行時間較短刽脖，占用儲存空間較小
- 合算原則：較低的代價取得較好的效果
- 三個不同級別
- 局部
- 循環(huán)
- 全局
- 優(yōu)化的種類
- 刪除多余運(yùn)算（刪除公用子表達(dá)式）
- 復(fù)寫傳播
- 刪除無用賦值
- 代碼外提（循環(huán)等）
- 強(qiáng)度消弱（如：冪運(yùn)算->乘法運(yùn)算羞海，乘除->加減）
- 變換循環(huán)控制條件
- 合并已知量（包括一些簡單的預(yù)計算）
8.2 局部優(yōu)化
-
基本塊：
指程序中一順序語句執(zhí)行序列，其中只有一個入口（第一條語句）和一個出口（最后一條（goto）語句）
一條三地址語句x:=y+z曲管，則稱x定值并引用y和z却邓。
活躍：某個變量是活躍的，意味著這個變量在之后的程序（此基本塊或其他基本塊）中被引用院水。
-
劃分基本塊：
-
求出入口語句
第一個語句
能由條件轉(zhuǎn)移/無條件轉(zhuǎn)移語句轉(zhuǎn)移到的語句
-
緊跟在條件轉(zhuǎn)移語句后面的語句
無條件轉(zhuǎn)移后面的語句不作為入口語句原因：下一句除非有別的語句跳轉(zhuǎn)（在跳轉(zhuǎn)邏輯被作為入口）腊徙，否則永遠(yuǎn)都無法被訪問到，不需要作為入口語句檬某。
-
確定基本塊
- | 入口語句 -> |下一個入口語句
- | 入口語句 -> 轉(zhuǎn)移語句 |
- | 入口語句 -> 停語句 |
未被納入某一基本塊的語句從程序中刪除
-
-
-
基本塊中的優(yōu)化措施
- 刪除公共子表達(dá)式
- 刪除無用賦值
- 合并已知量
- 臨時變量改名
- 交換語句的位置
- 代數(shù)變換
-
基本塊的DAG表示
基本塊的DAG是一種帶有下述標(biāo)記或附加信息的DAG
葉節(jié)點(diǎn)以一標(biāo)識符或常數(shù)作為標(biāo)記撬腾，表示該點(diǎn)代表該變量或常數(shù)的值
內(nèi)部節(jié)點(diǎn)以一運(yùn)算符作為標(biāo)記，表示該節(jié)點(diǎn)應(yīng)用該運(yùn)算符對其后繼節(jié)點(diǎn)的值進(jìn)行運(yùn)算
-
任意節(jié)點(diǎn)可能附加一個或多個標(biāo)識符恢恼，表示這些變量具有該節(jié)點(diǎn)所代表的值
構(gòu)建DAG_1構(gòu)建DAG_2構(gòu)建DAG_3
8.3 循環(huán)優(yōu)化
九民傻、目標(biāo)代碼生成
9.1 基本問題
代碼生成是把語法分析或優(yōu)化后的中間代碼變換成目標(biāo)代碼。
著重考慮的問題：
- 目標(biāo)代碼長度
- 充分利用寄存器场斑，減少訪問貯存器的次數(shù)
- 充分利用指令系統(tǒng)的特點(diǎn)
代碼生成器的輸入：源程序中間代碼漓踢，符號表的信息
代碼生成器的輸出：目標(biāo)代碼（3種形式：立即執(zhí)行的機(jī)器語言代碼、待裝配的機(jī)器語言模塊和簸、匯編語言代碼）
考慮方法：
- 指令選擇
- 寄存器分配
- 計算順序選擇
9.2 目標(biāo)機(jī)器模型
9.3 一個簡單的代碼生成器
-
計算信息
計算信息_1計算信息_2計算信息_3 -
分配寄存器
盡量延遲 STORE 的時間彭雾。
寄存器分配
