編譯原理復(fù)習(xí)

《編譯原理復(fù)習(xí)》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、編譯原理復(fù)習(xí)一、基本概念（填空15分，選擇10分，簡(jiǎn)答：15分）1、編譯程序按掃描源程序的遍數(shù)分類(lèi)可以分為哪兩類(lèi)？一遍掃描、多遍掃描2、高級(jí)語(yǔ)言的單詞分類(lèi)有哪些？基本字、運(yùn)算符、標(biāo)識(shí)符、常數(shù)、界符3、二義性文法，二義性語(yǔ)言的定義？二義性文法：文法G對(duì)某句型存在至少兩種不同的語(yǔ)法樹(shù)。二義性語(yǔ)言：某語(yǔ)言對(duì)應(yīng)的任意一種文法都是二義性文法4、DFA的定義及組成：確定的有窮自動(dòng)機(jī)；?M=(K,∑,f,?S,Z)?K是一個(gè)有窮集，它的每個(gè)元素稱(chēng)為一個(gè)狀態(tài)；?∑是一個(gè)有窮字母表，它的每個(gè)元素稱(chēng)為一個(gè)輸入符號(hào)，所以也稱(chēng)∑為輸入符號(hào)表；?F是轉(zhuǎn)換函數(shù)，是K×∑→K上的映像?S∈K，是唯一的一個(gè)初態(tài)?Z???

2、??K，是一個(gè)終極態(tài)，終態(tài)也稱(chēng)為接收狀態(tài)或結(jié)束狀態(tài)5、最左推導(dǎo)、規(guī)范推導(dǎo)的定義：最左推導(dǎo)：若x和y是符號(hào)串α中有兩個(gè)以上的非終結(jié)符號(hào)時(shí)，對(duì)推導(dǎo)的每一步堅(jiān)持把α中的最左非終結(jié)符號(hào)進(jìn)行替換，稱(chēng)為最左推導(dǎo)。規(guī)范推導(dǎo)：通常，我們把能由最左(右)推導(dǎo)推出的句型稱(chēng)為左(右)句型。另外，也常把最右推導(dǎo)稱(chēng)為規(guī)范推導(dǎo)，而把右句型稱(chēng)為規(guī)范句型。6、確定的自頂向下分析方法通常有哪兩種？采用確定的自頂向下分析的前提條件是什么？遞歸子程序法、預(yù)測(cè)分析法對(duì)每一個(gè)非終結(jié)符A的兩個(gè)不同產(chǎn)生式，A→α，B→β，滿(mǎn)足SELECT（A→α）∩SELECT（B→β）=?，其中αβ不同時(shí)能→ε7、詞法分析的常用方法有哪兩種？自頂向

3、下；自底向上。8、簡(jiǎn)單優(yōu)先分析法、算符優(yōu)先分析法屬于、LR(0)分析法分別屬于何種歸約？規(guī)范規(guī)約、非規(guī)范規(guī)約、規(guī)范規(guī)約9、高級(jí)程序設(shè)計(jì)語(yǔ)言的翻譯方式主要有哪兩種，二者的根本區(qū)別在于哪里？方式：編譯程序、解釋程序???區(qū)別：生不生成目標(biāo)代碼10、詞法分析程序和語(yǔ)法分析程序的任務(wù)分別是什么？詞法分析是編譯的第一階段，它的主要任務(wù)是按語(yǔ)言的詞法規(guī)則，從左至右逐個(gè)字符地對(duì)源程序進(jìn)行掃描，從源程序中識(shí)別出每個(gè)單詞，并把每個(gè)單詞轉(zhuǎn)換成它們的內(nèi)部表示，即所謂的token，同時(shí)進(jìn)行詞法檢查。語(yǔ)法分析的任務(wù)是在詞法分析的基礎(chǔ)上將單詞序列組合成各類(lèi)語(yǔ)法短語(yǔ),如“程序”,“語(yǔ)句”,“表達(dá)式”等等。11、可歸約前

4、綴的定義規(guī)范句型中每次規(guī)范動(dòng)作前符號(hào)棧中的內(nèi)容12、有限自動(dòng)機(jī)能識(shí)別何種文法？正規(guī)文法13、在PL/0編譯過(guò)程中，詞法處理后輸出的結(jié)果是何種形式一個(gè)個(gè)的單詞符號(hào)14、編譯程序的作用及目的是什么？是何種軟件？將源程序翻譯成等價(jià)的目標(biāo)語(yǔ)言程序語(yǔ)言翻譯程序軟件15、預(yù)測(cè)分析序法：是自頂向下分析的另一種方法，一個(gè)預(yù)測(cè)分析器是由三個(gè)部分組成1、預(yù)測(cè)分析程序2、先進(jìn)后出棧3、預(yù)測(cè)分析表。簡(jiǎn)單優(yōu)先分析法：是按照文法符號(hào)的優(yōu)先關(guān)系確定句柄的。算符優(yōu)先分析法：只考慮算符之間的優(yōu)先關(guān)系。LR分析法的定義：LR分析法正是給出一種能根據(jù)當(dāng)前分析棧中的符號(hào)串和向右順序查看輸入串的K個(gè)符號(hào)就可唯一確定分析器的動(dòng)作是移

5、近還是歸約和用哪個(gè)產(chǎn)生式歸約，因而也就能唯一確定句柄。16、移入、待約、歸約、接受的定義分別為？移入：圓點(diǎn)后為終結(jié)符待約：圓點(diǎn)后為非終結(jié)符歸約：圓點(diǎn)在產(chǎn)生式右部最后接收：輸入串為該文法的句子717、巴克斯－瑙爾范式（EBNF）是一種什么工具？是表達(dá)作為描述計(jì)算機(jī)編程語(yǔ)言和形式語(yǔ)言的正規(guī)方式的上下文無(wú)關(guān)文法的元語(yǔ)法符號(hào)表示法。18、在算符優(yōu)先分析法中歸約的是什么？最左素短語(yǔ)19、PL/0編譯系統(tǒng)中詞法分析階段三個(gè)全程變量（即：SYM、ID、NUM）的作用SYM:存放每個(gè)單詞的類(lèi)別，用內(nèi)部編碼表示。ID:存放用戶(hù)所定義的標(biāo)識(shí)符的值，即標(biāo)識(shí)符的機(jī)內(nèi)表示。NUM:存放用戶(hù)定義的數(shù)20、什么是遍？一

6、種高級(jí)語(yǔ)言通過(guò)幾遍掃描能完成編譯？遍是對(duì)源程序或其等價(jià)的中間語(yǔ)言程序從頭到尾掃視并完成規(guī)定任務(wù)的過(guò)程。一個(gè)編譯過(guò)程可由一遍、兩遍或多遍完成。二、計(jì)算分析證明繪圖典型題例（60分）1、文法G[N]為：N->D

7、NDD->0

8、1

9、2

10、3

11、4

12、5

13、6

14、7

15、8

16、9G[N]的語(yǔ)言是什么？（自己練習(xí)）V+V={0,1,2,3,4,5,6,7,8,9}2、文法G[S]為：S->Ac

17、aBA->abB->bc寫(xiě)出L(G[S])的全部元素。（自己練習(xí)）L(G[S])={abc}3、寫(xiě)出表達(dá)式：a+b*(c+d/e)及-a+b*(-c+d)的逆波蘭式和四元式。前一個(gè)為：逆波蘭式：abcde/+*+逆波蘭式:a

18、@bc@d+*+四元式：（/,d,e,t1）四元式(@，a，-，T1)(+,t1,c,t2)(@，c，-，T2)(*,t2,b,t3)(+，T2，d，T3)(+,t3,a,t4))(*，b，T3，T4)(+，T1，T4，T5)4、令文法G[S]為:S->SS*S->SS+S->a(1)分析說(shuō)明aa+a*是它的一個(gè)句型；(2)指出這個(gè)句型的所有短語(yǔ)、直接短語(yǔ)和句柄。(3)該文法的語(yǔ)言是什么？解：（1）該字符串對(duì)應(yīng)的語(yǔ)法樹(shù)為