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