編譯原理期末總結復習
篇一：
一、簡(jiǎn)答題
1.什么是編譯程序？
答：編譯程序是一種將高級語(yǔ)言程序(源程序)翻譯成低級語(yǔ)言(目標程序)的程序 。
將高級程序設計語(yǔ)言程序翻譯成邏輯上等價(jià)的低級語(yǔ)言(匯編語(yǔ)言,機器語(yǔ)言)程序的翻譯程序。
2.請寫(xiě)出文法的形式定義？
答：一個(gè)文法G抽象地表示為四元組 G=（Vn,Vt,P,S）
– 其中Vn表示非終結符號
– Vt表示終結符號，Vn∪Vt=Ｖ(字母表)，Vn∩Vt=φ
– S是開(kāi)始符號，
– P是產(chǎn)生式，形如：α→β(α∈V+且至少含有一個(gè)非終結符號，β∈V*)
3.語(yǔ)法分析階段的功能是什么？
答：在詞法分析的基礎上，根據語(yǔ)言的語(yǔ)法規則，將單詞符號串分解成各類(lèi)語(yǔ)法短語(yǔ)(例：
程序、語(yǔ)句、表達式)。確定整個(gè)輸入串是否構成語(yǔ)法上正確的程序。
4.局部?jì)?yōu)化有哪些常用的技術(shù)？
答：優(yōu)化技術(shù)1—刪除公共子表達式
優(yōu)化技術(shù)2—復寫(xiě)傳播
優(yōu)化技術(shù)3—刪除無(wú)用代碼
優(yōu)化技術(shù)4—對程序進(jìn)行代數恒等變換（降低運算強度）
優(yōu)化技術(shù)5—代碼外提
優(yōu)化技術(shù)6—強度削弱
優(yōu)化技術(shù)7—刪除歸納變量
優(yōu)化技術(shù)簡(jiǎn)介——對程序進(jìn)行代數恒等變換（代數簡(jiǎn)化）
優(yōu)化技術(shù)簡(jiǎn)介——對程序進(jìn)行代數恒等變換（合并已知量）
5．編譯過(guò)程分哪幾個(gè)階段？
答：邏輯上分五個(gè)階段：詞法分析、語(yǔ)法分析、語(yǔ)義分析與中間代碼生成、代碼優(yōu)化、目
標代碼生成。每個(gè)階段把源程序從一種表示變換成另一種表示。
6. 什么是文法？
答：文法是描述語(yǔ)言的語(yǔ)法結構的形式規則。是一種工具，它可用于嚴格定義句子的結構；
用有窮的規則刻劃無(wú)窮的集合；文法是被用來(lái)精確而無(wú)歧義地描述語(yǔ)言的句子的構成方式；文法描述語(yǔ)言的時(shí)候不考慮語(yǔ)言的含義。
7. 語(yǔ)義分析階段的功能是什么？
答：對語(yǔ)法分析所識別出的各類(lèi)語(yǔ)法范疇分析其含義，進(jìn)行初步的翻譯(翻譯成中間代碼)；
并對靜態(tài)語(yǔ)義進(jìn)行審查。
8.代碼優(yōu)化須遵循哪些原則？
答：等價(jià)原則：不改變運行結果
有效原則：優(yōu)化后時(shí)間更短，占用空間更少
合算原則：應用較低的代價(jià)取得較好的優(yōu)化效果
9.詞法分析階段的功能是什么？
答：
逐個(gè)讀入源程序字符并按照構詞規則切分成一系列單詞
任務(wù)：讀入源程序，輸出單詞符號
— 濾掉空格，跳過(guò)注釋、換行符
— 追蹤換行標志，指出源程序出錯的行列位置
— 宏展開(kāi)，……
10.什么是符號表？
答：符號表在編譯程序工作的過(guò)程中需要不斷收集、記錄和使用源程序中一些語(yǔ)法符號
的類(lèi)型和特征等相關(guān)信息。這些信息一般以表格形式存儲于系統中。如常數表、變量名表、數組名表、過(guò)程名表、標號表等等，統稱(chēng)為符號表。對于符號表組織、構造和管理方法的好壞會(huì )直接影響編譯系統的運行效率。
11.什么是屬性文法？
答：是在上下文無(wú)關(guān)文法的基礎上，為每個(gè)文法符號(含終結符和非終結符)配備若干個(gè)屬
性值，對文法的每個(gè)產(chǎn)生式都配備了一組屬性計算規則(稱(chēng)為語(yǔ)義規則)。在語(yǔ)法分析過(guò)程中，完成語(yǔ)義規則所描述的動(dòng)作，從而實(shí)現語(yǔ)義處理。
12.什么是基本塊
答：是指程序中一順序執行的語(yǔ)句序列，其中只有一個(gè)入口語(yǔ)句和一個(gè)出口語(yǔ)句，入口
是其第一個(gè)語(yǔ)句，出口是其最后一個(gè)語(yǔ)句。
13.代碼優(yōu)化階段的功能是什么？
答：對已產(chǎn)生的中間代碼進(jìn)行加工變換，使生成的目標代碼更為高效(時(shí)間和空間)。
14.文法分哪幾類(lèi)？
答：文法有四種:設有G=(Vn,Vt,P,S),不同類(lèi)型的文法只是對產(chǎn)生式的要求不同：
�。靶臀姆�(短文文法)： G的每個(gè)產(chǎn)生式αβ滿(mǎn)足：α∈V+且α中至少含有一個(gè)非終結符,β∈V*
�。毙臀姆�(上下文有關(guān)文法)：如果G的每個(gè)產(chǎn)生式αβ均滿(mǎn)足|β|>=|α|,僅當Ｓε除外，但S不得出現在任何產(chǎn)生式的右部
�。残臀姆�(上下文無(wú)關(guān)文法)：G的每個(gè)產(chǎn)生式為Aβ, A是一非終結符，β∈V*
�。承臀姆�(正規文法)：G的每個(gè)產(chǎn)生式的形式都是：AαB或Aα，其中A,B是非終結符，α是終結符串。(右線(xiàn)性文法)。
15.循環(huán)優(yōu)化常用的技術(shù)有哪些？
答：代碼外提；強度削弱；刪除歸納變量。
16.什么是算符優(yōu)先文法？
答：算符文法G的任何終結符a,b之間要么沒(méi)有優(yōu)先關(guān)系，若有優(yōu)先關(guān)系,
至多有
中的一種成立,則G為一算符優(yōu)先文法。
二、計算題
�。ㄒ唬┩茖�、最左推導、最右推導和語(yǔ)法樹(shù),復習表達式文法及相關(guān)例題。
1. 表達式的推導
例： G = ({E}, {i, +, *, (, ) } , P , E)
P： E E+E | E*E | (E) | i
答：表達式(i)和(i+i)*i的推導：
E (E) (i)
E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i
E E*E E*i (E)* i (E + E)*i (E+ i)*i (i + i)*i
(i+i)*i的最左推導過(guò)程：
E E*E (E)*E (E + E)*E (i + E)*E (i + i)*E (i + i)*i
(i+i)*i的最右推導過(guò)程：
E E*E E*i (E + E)*i (E+ i)*i (i + i)*i
2．語(yǔ)法樹(shù)
例：對文法G = ({E}, {i, +, *, (, ) } , P , E)
P： E E + E | E * E | ( E ) | i
答： 句子(i+i)*i 的語(yǔ)法樹(shù)：
例： G = ({E}, {i, +, *, (, ) } , P , E)
P： E E + E | E * E | ( E ) | i
答：句子 ( i * i + i)的語(yǔ)法樹(shù)：
(1) E (E) (E + E) (E * E + E) (i * E + E) (i *i + i)
�。ǘ┙o定語(yǔ)言求文法
�。ㄈ┠娌ㄌm式
篇二：
翻譯程序:把一種語(yǔ)言程序轉換成另一種語(yǔ)言程序，且在功能上是相同的這樣的程序。 編譯程序：把高級語(yǔ)言轉換成低級語(yǔ)言，且在功能上是相同的這樣的程序。
解釋程序：邊解釋邊執行源程序的程序。區別：編譯程序有中間代碼，而解釋程序沒(méi)有。 編譯過(guò)程的五個(gè)階段：
1、 詞法分析 任務(wù)：對構成源程序的字符串進(jìn)行掃描和分解，識別出一個(gè)個(gè)單詞。
2、 語(yǔ)法分析 任務(wù)：在詞法分析的基礎上，根據語(yǔ)言規則，把單詞符號串分解成各類(lèi)語(yǔ)法
單位。
3、 語(yǔ)義分析和中間代碼產(chǎn)生 任務(wù)：對語(yǔ)法分析所識別出的各類(lèi)語(yǔ)法范疇，分析其含義，
并進(jìn)行初步翻譯。
4、 優(yōu)化 任務(wù)：對前段產(chǎn)生的中間代碼進(jìn)行加工變換，以期在最后階段能產(chǎn)生出更為高效
的目標代碼。
5、 目標代碼生成 任務(wù)：把中間代碼變換成特定機器上的低級語(yǔ)言代碼。
編譯程序的七個(gè)部分詞法分析器，語(yǔ)法分析器、語(yǔ)義分析與中間代碼產(chǎn)生器、優(yōu)化器、目標代碼生成器、表格管理和出錯處理。
編譯程序生成的五個(gè)辦法：機器語(yǔ)言、高級語(yǔ)言、移植、自編譯方式和使用工具自動(dòng)生成。 詞法規則：指單詞符號的形成規則。（也就是正規式）
語(yǔ)法規則：規定了如何從單詞符號形成更大的結構。就是語(yǔ)法單位的形成規則。 空字：不包含任何符號的序列。
閉包：中所有的符號組成的集合。
上下文無(wú)關(guān)文法是指：所定義的語(yǔ)法范疇是完全獨立于這種范疇可能出現的環(huán)境的文法。 上下文無(wú)關(guān)文法的四個(gè)組成部分：一組終結符號、一組非終結符號、一個(gè)開(kāi)始符號和一組產(chǎn)生式。
終結符號也就是不可再分的基本符號。
非終結符號是用來(lái)代表語(yǔ)法范疇，表示一定符號串的集合。
開(kāi)始符號是語(yǔ)言中我們最感興趣的語(yǔ)法范疇。
產(chǎn)生式是定義語(yǔ)法范疇的書(shū)寫(xiě)規則。
句子：文法中從開(kāi)始符號推導的終結符號串。
句型：從開(kāi)始符號推導的符號串。
語(yǔ)言：文法中所有句子的集合。
程序語(yǔ)言的單詞符號分為五種：關(guān)鍵字、標識符、常數、運算符和界符。
二元式表示：（種類(lèi)，屬性）
正規式的`運算符有三種：或，連接和閉包。優(yōu)先順序是：閉包，連接，或。
DFA怎么識別字：若存在一條從初態(tài)結點(diǎn)到某一終態(tài)結點(diǎn)的通路，且這條通路上所有弧的標記符連接成的字是a，則稱(chēng)a可為DFA所識別。
DFA怎么識別空字：若DFA的初態(tài)結點(diǎn)同時(shí)又是終態(tài)結點(diǎn)，則空字可為DFA所識別。 NFA怎么識別字：若存在一條從某一初態(tài)結點(diǎn)到終態(tài)結點(diǎn)的通路，且這條通路上所有弧的標記字依序連接成的字等于a，則稱(chēng)a可為NFA識別。
NFA怎么識別空字：若M的某些結點(diǎn)即是初態(tài)又是終態(tài)結點(diǎn)，或者存在一條從某個(gè)初態(tài)結點(diǎn)到某個(gè)終態(tài)結點(diǎn)的空通路，那么，空字可為M所識別。
語(yǔ)言的語(yǔ)法結構是用上下文無(wú)關(guān)文法描述的。
語(yǔ)法分析分為兩類(lèi)：自上而下分析法，自下而上分析法。
自上而下分析法面臨的問(wèn)題：1.文法的左遞歸問(wèn)題。2.回溯3.成功可能是暫時(shí)的，產(chǎn)生虛假匹配。4.難于知道輸入串中出錯的確切位置。5.效率低，代價(jià)高。
為什么消除左遞歸？因為含有左遞歸的文法將自上而下分析的過(guò)程陷入無(wú)限循環(huán)。 為什么消除回溯？因為回溯統一做一大堆無(wú)效的工作。
自下而上分析法：從輸入串開(kāi)始，逐步進(jìn)行歸約，知道歸約到文法的開(kāi)始符號。 短語(yǔ)：符號串推導過(guò)程中某非終結符推導的部分。
直接短語(yǔ)：符號串推導過(guò)程中某非終結符一步推導的部分。
句柄：一個(gè)句型的最左直接短語(yǔ)。
最左歸約是最有推導的逆過(guò)程。
中間語(yǔ)言形式：后綴式，三元式，四元式，間接三元式。
中間語(yǔ)言的好處：1.便于進(jìn)行與機器無(wú)關(guān)的代碼優(yōu)化工作。2.使編譯程序改變目標機更容易。
3.使編譯程序的結構在邏輯上更為簡(jiǎn)單，以中間語(yǔ)言為界面，編譯前端和后端的借口更清晰。
篇三：
(1)程序設計語(yǔ)言
機器語(yǔ)言: 由0、1代碼構成，不需翻譯就可直接執行其程序。
匯編語(yǔ)言: 機器指令助記符（偽代碼）形式，匯編后才可執行其程序。
高級程序設計語(yǔ)言: 類(lèi)自然語(yǔ)言和數學(xué)公式形式
(2) 基本術(shù)語(yǔ)
源程序(Source Program)：用源語(yǔ)言寫(xiě)的程序。源語(yǔ)言可以是匯編語(yǔ)言，也可以是高級程
序設計語(yǔ)言。
目標程序(Target Program) ：也稱(chēng)為“結果程序”，是源程序經(jīng)翻譯程序加工以后所生成
的程序。目標程序可以用機器語(yǔ)言表示，也可以用匯編語(yǔ)言或其它中間語(yǔ)言表示。
翻譯程序(Translating Program)：是指把一個(gè)源程序翻譯成邏輯上等價(jià)的目標程序的程序。
源程序為其輸入，目標程序為其輸出。
匯編程序(Assembler)：是指把一個(gè)匯編語(yǔ)言寫(xiě)的源程序轉換成等價(jià)的機器語(yǔ)言表示的目
標程序的翻譯程序。
編譯程序(Compiler)：若源程序是用高級程序設計語(yǔ)言所寫(xiě)，經(jīng)翻譯程序加工生成目標程
序，則該翻譯程序就稱(chēng)為“編譯程序”，也可稱(chēng)為編譯器。
解釋程序：是高級語(yǔ)言翻譯程序的一種，他將源語(yǔ)言書(shū)寫(xiě)的源程序作為輸入，解釋一句
后就提交計算機執行一句，并不形成目標程序，就像外語(yǔ)翻譯中的“口譯”一樣，不產(chǎn)生全文的翻譯文本。
運行系統(Running System)：目標程序執行時(shí)，需要有一些子程序（如一些連接裝配程序
及一些連接庫等）配合進(jìn)行工作，由這些子程序組成的一個(gè)子程序庫稱(chēng)為運行系統。 編譯系統(Compiling System)：編譯程序和運行系統合稱(chēng)編譯系統。
(3) 程序的翻譯
除機器語(yǔ)言程序外，用其它語(yǔ)言書(shū)寫(xiě)的程序都必須經(jīng)過(guò)翻譯才能被計算機識別。這一過(guò)
程由翻譯程序來(lái)完成。
編譯方式是一種分階段進(jìn)行的方式，包括翻譯和運行兩部分。
前一階段：翻譯
后一階段：運行，由運行系統配合完成。
(4) 過(guò)程
1、詞法分析階段
這個(gè)階段的任務(wù)是從左到右一個(gè)字符一個(gè)字符地讀入源程序，對構成源程序的字符流進(jìn)行掃描和分解，從而識別出一個(gè)個(gè)單詞（也稱(chēng)單詞符號或符號TOKEN）。
某源程序片斷如下：
begin var sum, first, count: real; sum:=first+count*10 end.
保留字 begin var real end
標識符 sumfirstcountsumfirstcount
界符 .
逗號，逗號,冒號：分號；加號+乘號*賦值號 ：=整數10 10
2、語(yǔ)法分析階段
是編譯過(guò)程的第二個(gè)階段。語(yǔ)法分析的任務(wù)是在詞法分析的基礎上將單詞序列分解成各類(lèi)語(yǔ)法短語(yǔ)，如“程序”，“語(yǔ)句”，“表達式”等等。一般這種語(yǔ)法短語(yǔ)，也稱(chēng)語(yǔ)法單位，或語(yǔ)法成分，或語(yǔ)法范疇。
語(yǔ)法分析所依據的是語(yǔ)言的語(yǔ)法規則，即描述程序結構的規則。通過(guò)語(yǔ)法分析確定整個(gè)輸入串是否構成一個(gè)語(yǔ)法上正確的程序。
3、語(yǔ)義分析階段
依據語(yǔ)言的語(yǔ)義規則，對語(yǔ)法分析得到的語(yǔ)法結構分析其含義以及應進(jìn)行的運算，審查源程序中有無(wú)語(yǔ)義錯誤，為代碼生成階段收集類(lèi)型信息。
4、中間代碼生成
在進(jìn)行了上述的語(yǔ)法分析和語(yǔ)義分析階段的工作之后，有的編譯程序將源程序轉變成一種內部表示形式，這種內部表示形式叫做中間代碼。
所謂“中間代碼”是一種結構簡(jiǎn)單，含義明確的記號系統，這種記號系統可以設計為多種多樣的形式。
重要的設計原則：一是容易生成；二是容易將它翻譯成目標代碼。
5、代碼優(yōu)化
任務(wù)：對前階段產(chǎn)生的中間代碼系列進(jìn)行變換或改造。目的是使生成的目標代碼更高效，即省時(shí)間省空間。例如上例四個(gè)四元式可優(yōu)化為下面兩個(gè)四元式。
6、目標代碼生成
任務(wù)：將中間代碼變換成特定機器上的絕對指令代碼或可重定位的指令代碼或匯編指令代碼。它的工作與硬件系統結構和指令含義有關(guān)。
7、表格管理
編譯過(guò)程中源程序的各種信息被保留在種種不同的表格里，編譯各階段的工作都涉及到構造、查找或更新有關(guān)的表格，因此需要有表格管理的工作；
8、出錯處理
如果編譯過(guò)程中發(fā)現源程序有錯誤，編譯程度應報告錯誤的性質(zhì)和錯誤發(fā)生的地點(diǎn)，并且將錯誤所造成的影響限制在盡可能小的范圍內，使得源程序的其余部分能繼續被編譯下去，有些編譯程序還能自動(dòng)校正錯誤，這些工作稱(chēng)之為出錯處理。
(5) 前端與后端
參考上面的圖，目的是為了在多種源語(yǔ)言和多種目標語(yǔ)言的開(kāi)發(fā)過(guò)程中，可以靈活搭配組合，消除重復開(kāi)發(fā)的工作量，提高編譯系統的開(kāi)發(fā)效率。
(6) 遍
所謂遍，是對源程序或源程序的中間形式從頭到尾掃視并完成規定任務(wù)的過(guò)程。
每一遍掃視可完成一個(gè)階段或多個(gè)階段的功能。
一遍的編譯程序：以語(yǔ)法分析程序為核心 。
多遍掃描的優(yōu)點(diǎn)：
可以減少內存容量的需求，分遍后，以遍為單位分別調用編譯的各個(gè)程序，各遍程序可以相互覆蓋。
可使各遍的編譯程序相互獨立，結構清晰。
能夠進(jìn)行充分優(yōu)化，產(chǎn)生高質(zhì)量的目標程序。
可將編譯程序分為前端和后端，有利于編譯程序的移植。
多遍掃描的缺點(diǎn)
每遍都要讀符號、送符號，增加了許多重復性的工作，降低編譯效率。
(7) 程序設計語(yǔ)言范型（從支持的計算模式）
1. 強制(命令)式語(yǔ)言:是面向動(dòng)作的，即一個(gè)計算過(guò)程看做是一系列動(dòng)作，其動(dòng)作是命令驅動(dòng)，以語(yǔ)言形式表示。
也稱(chēng)過(guò)程式語(yǔ)言，如C,FORTRAN等;
2. 函數式語(yǔ)言：注重程序表示的功能
也稱(chēng)應用式語(yǔ)言，如ML和LISP等；
3. 基于規則的語(yǔ)言：檢查一定的使能條件，滿(mǎn)足時(shí)執行動(dòng)作
也稱(chēng)邏輯程序設計語(yǔ)言，如PROLOG。
4. 面向對象語(yǔ)言：提供抽象數據類(lèi)型，支持封裝性、繼承性和多態(tài)性。
如C++和Java等。
(1) 符號和符號串
1、 字母表：元素的有窮非空集合。
2、 符號串：由字母表中的符號組成的任何有窮序列。
3、 符號串的頭尾，固有頭和固有尾：如果z=xy是一符號串，那么x是z的頭，y是z
的尾，如果x是非空的，那么y是固有尾；同樣如果y非空，那么x是固有頭。 如:設z=abc，那么z的頭是，a, ab, abc, 除abc外，其它都是固有頭；z的尾是, c, bc, abc, z的固有尾是, c, bc。
4、 符號串的運算
�。�1）符號串的連接：設x和y是符號串，x和y的連接xy是把y的符號寫(xiě)在x的符號后得的符號串。
如：x=ST, y=abu, 則xy=STabu顯然有x=x=x。
�。�2）符號串的方冪：設x是符號串，把x自身連接n次得x的幾次方冪xn。
如：設x=ab則x0=x1=abx2=ababx3=ababab
�。�3）符號串集合的乘積：設A和B為符號串集合，則A和B的乘積定義為AB={xy|xA且yB}
如：a={a, b}, B={00, 11} 則AB={a00, a11, b00, b11} 顯然：{}A=A{}=A
�。�4）符號串集合的方冪：設A為符號串集，則A的n次方冪An定義為:An=AA……A=AAn-1=An-1A
�。�5）符號串集合的正閉包A+：A+=A1 U A2 U … U An U …
�。�6）符號串集合的閉包A*：A*=A0 U A+ = {} U A+
如：設有正字母表={0，1} 則*=0 U 1 U 2 U … U n U …={, 0, 1, 00,01, 10, 11, 000, 001,……}
(2) 文法
文法G定義為四元組（VN ，VT，P，S）其中:
�。�1）VN 為非終結符號集
非終結符號表示一個(gè)語(yǔ)言短語(yǔ)（或語(yǔ)法成分、語(yǔ)法單位）。 如 程序、語(yǔ)句、表達式等。一般用大寫(xiě)字母或用〈 〉括起表示非終結符號。
�。�2）VT 為終結符號集
終結符號：組成語(yǔ)言的基本符號。是文法中不屬于非終結符號集合的符號。一般用小寫(xiě)字母或不帶〈 〉的符號表示。如程序設計語(yǔ)言的單詞符號。
設V=VN U VT，稱(chēng)V為文法G的字母表。
�。�3）P 為產(chǎn)生式（也稱(chēng)規則）的集合。
產(chǎn)生式的形式：→或∷=，其中∈V+，∈V*
�。�4）S 稱(chēng)作識別符號或開(kāi)始符號，是一個(gè)非終結符號。
一般表示此文法定義的最大語(yǔ)法短語(yǔ)，至少要在一條產(chǎn)生式 中作為左部出現。 句型、句子的定義
設G[S]是一文法，如果符號串x是從識別符號推導出來(lái)的，即有S*x， 則稱(chēng)x是文法G[S]的句型。
若x僅由終結符號組成，即S*x, xV T ，則稱(chēng)x為G[S]的句子。
句型：在一棵樹(shù)生長(cháng)過(guò)程的任何時(shí)刻，所有那些端末結點(diǎn)自左至右的排列，就是一個(gè)句型。
語(yǔ)言的定義：文法G產(chǎn)生的語(yǔ)言記為L(cháng)（G），它是文法G產(chǎn)生的全部句子的集合。 文法等價(jià)定義：若L（G1）=L（G2）則稱(chēng)文法G1和G2是等價(jià)的。
(3) 文法的類(lèi)型 N.Chomsky
0型文法：定義0型語(yǔ)言，對應Turing機；
1型文法：定義1型語(yǔ)言，對應線(xiàn)性限界自動(dòng)機；箭頭后面的要比前面的長(cháng)或相等 2型文法：定義2型語(yǔ)言，對應非確定下推自動(dòng)機；箭頭前面的是非終結符，后面是串 3型文法：定義3型語(yǔ)言，對應有限自動(dòng)機。非終結符可以推出一個(gè)終結符或一個(gè)終結符和一個(gè)非終結符
最右推導也稱(chēng)為規范推導，所得句型稱(chēng)為規范句型。
如果一個(gè)文法存在某個(gè)句型對應兩棵不同的語(yǔ)法樹(shù)，則說(shuō)這個(gè)文法是二義的�；蛘哒f(shuō)，若一個(gè)文法中存在某個(gè)句型，它有兩個(gè)不同的最左（最右）推導，則這個(gè)文法是二義的。
上下文無(wú)關(guān)文法是否具有二義性是不可判定的。
但有些特殊的2型文法[例如LL（1）、LR（0）、LR（1）等文法]是無(wú)二義性的。 一個(gè)文法兼有左遞歸和右遞歸是導致二義性的常見(jiàn)原因。
排除文法二義性通常有兩種方法:
�。�1）在語(yǔ)義上加些限制
�。�2）重新構造一個(gè)無(wú)二義性的文法
(4) 句型的分析
句型的分析：就是識別一個(gè)符號串是否為某文法的句型。是某個(gè)推導的構造過(guò)程。 分析方法分兩大類(lèi)：自上而下分析法和自下而上分析法推導與歸約，最右推導是規范推導，逆過(guò)程為規范規約
若S*A+（由A+得）則稱(chēng)是句型相對于非終結符A的短語(yǔ)。
若S*A(由A→得)則稱(chēng)是句型相對于A(yíng)→的直接短語(yǔ)（也稱(chēng)簡(jiǎn)單短語(yǔ)）。 一個(gè)句型的最左直接短語(yǔ)稱(chēng)為該句型的句柄。
一棵子樹(shù)（至少要有父子兩代）的所有端末結點(diǎn)自左至右排列起來(lái)形成相對于子樹(shù)根的短語(yǔ)。若子樹(shù)只有父子兩代，則得到直接短語(yǔ)。
(5) 有關(guān)文法
�。�1）有害規則 文法中含形如U→U的產(chǎn)生式。
它對描述語(yǔ)言沒(méi)有必要，且會(huì )引起文法的二義性。
�。�2）多余規則 文法中任何一個(gè)句子的推導都用不到的規則。
�。�3）無(wú)用規則 文法中含形如U→V的產(chǎn)生式，即單產(chǎn)生式。
為保證文法G的任一非終結符A在句子推導中出現，必須滿(mǎn)足如下兩個(gè)條件：
�。�1）A必須在某句型中出現，A。
�。�2） 必須能夠從A推導出終結符號串t。
有關(guān)文法的化簡(jiǎn)和改造，包括以下幾項工作：
�。ǎ保o(wú)用符號和無(wú)用產(chǎn)生式的刪除。
�。ǎ玻� －產(chǎn)生式的消除。
�。ǎ常﹩萎a(chǎn)生式的消除。
�。ǎ矗┳筮f歸的消除。
(1) 詞法分析輸出
單詞符號（TOKEN) 是一個(gè)程序設計語(yǔ)言的基本語(yǔ)法符號。程序設計語(yǔ)言的單詞符號一般可分成下列5種：
1．基本字，也稱(chēng)關(guān)鍵字，如PASCAL語(yǔ)言中的begin，end，if，while和var等。
2．標識符，用來(lái)表示各種名字，如常量名、變量名和過(guò)程名等。
3．常數，各種類(lèi)型的常數，如25，3.1415，TRUE和"ABC"等。
4．運算符，如+，*，<= 等。
5．界符，如逗點(diǎn)，分號，括號等。
詞法分析程序所輸出的單詞符號常常采用下二元式表示：（單詞種別，單詞自身的值） 可用整數碼或助記符等表示。
(2) 單詞的描述工具
程序設計語(yǔ)言中的單詞(TOKEN)是基本語(yǔ)法符號。單詞符號的語(yǔ)法可以用有效的工具加以描述。
正規式和它所表示的正規集的遞歸定義如下。設字母表為∑，輔助字母表∑ ={ |, ·, *, (, ) }
定義（正規式和它所表示的正規集）：
設字母表為Σ，輔助字母表Σ`={Φ，ε，|，·，*，(， }。
�、� ε和Φ都是Σ上的正規式，它們所表示的正規集分別為{ε}和{ }；
�、� 任何a∈Σ，a是Σ上的一個(gè)正規式，它所表示的正規集為{a}；
�、� 假定e1和e2都是Σ上的正規式，它們所表示的正規集分別為L(cháng)(e1)和L(e2)，那么，(e1), e1|e2, e1·e2, e1*也都是正規式,它們所表示的正規集分別為L(cháng)(e1), L(e1)∪L(e2), L(e1)L(e2)和(L(e1))*。
�、� 僅由有限次使用上述三步驟而定義的表達式才是Σ上的正規式，僅由這些正規式所表示的字集才是Σ上的正規集。
(3) 有窮自動(dòng)機
有窮自動(dòng)機（也稱(chēng)有限自動(dòng)機）作為一種識別裝置，它能準確地識別正規集，即識別正規文法所定義的語(yǔ)言和正規式所表示的集合，引入有窮自動(dòng)機這個(gè)理論，正是為詞法分析程
【編譯原理期末總結復習】相關(guān)文章：
編譯原理小論文03-30
編譯原理知識點(diǎn)總結03-30
編譯原理實(shí)驗課程教學(xué)設計的改進(jìn)論文06-12
編譯原理課程設計心得體會(huì )01-12
會(huì )計學(xué)原理復習總結08-05
物理期末復習總結03-05