編譯原理復(fù)習(xí)題2017含試卷

1、1?編譯原理復(fù)習(xí)題編譯原理復(fù)習(xí)題一簡(jiǎn)答題：一簡(jiǎn)答題：1)1)什么是句子？什么是句子？什么是語(yǔ)言什么是語(yǔ)言解答：句子——設(shè)G是一個(gè)給定的文法，S是文法的開(kāi)始符號(hào)，如果Sx（其中x∈VT），則稱(chēng)x是文法的一個(gè)句子。語(yǔ)言——語(yǔ)言是句子的集合?；颉O(shè)G[S]是給定文法，則由文法G所定義的語(yǔ)言L(G)可描述為：L(G)＝x│Sxx∈VT。2)2)DFADFA與NFANFA有何區(qū)別有何區(qū)別解答:DFA與NFA的區(qū)別表現(xiàn)為兩個(gè)方面:一是NFA可以有

2、若干個(gè)開(kāi)始狀態(tài)，而DFA僅只有一個(gè)開(kāi)始狀態(tài)。另一方面，DFA的映象M是從K∑到K，而NFA的映象M是從K∑到K的子集，即映象M將產(chǎn)生一個(gè)狀態(tài)集合（可能為空集），而不是單個(gè)狀態(tài)。3)3)自頂向下的語(yǔ)法分析方法的基本思想是什么自頂向下的語(yǔ)法分析方法的基本思想是什么解答:從文法的開(kāi)始符號(hào)開(kāi)始，根據(jù)給定的輸入串并按照文法的產(chǎn)生式一步一步的向下進(jìn)行直接推導(dǎo)，試圖推導(dǎo)出文法的句子，使之與給定的輸入串匹配。4)4)自底向上的語(yǔ)法分析方法的基本思想是什

3、么自底向上的語(yǔ)法分析方法的基本思想是什么解答:從給定的輸入串（終結(jié)符串）開(kāi)始，根據(jù)文法的規(guī)則一步一步的向上進(jìn)行直接歸約，試圖歸約到文法的開(kāi)始符號(hào)。5)5)一個(gè)上下文無(wú)關(guān)文法一個(gè)上下文無(wú)關(guān)文法G包括哪四個(gè)組成部分？包括哪四個(gè)組成部分？解答:一組非終結(jié)符號(hào)，一組終結(jié)符號(hào)，一個(gè)開(kāi)始符號(hào)，以及一組產(chǎn)生式。6)6)在自底向上的語(yǔ)法分析方法中，分析的關(guān)鍵是什么？在自底向上的語(yǔ)法分析方法中，分析的關(guān)鍵是什么？解答:關(guān)鍵是尋找句柄。7)7)在自頂向下的

4、語(yǔ)法分析方法中，分析的關(guān)鍵是什么？在自頂向下的語(yǔ)法分析方法中，分析的關(guān)鍵是什么？解答:關(guān)鍵是選擇候選式。8）什么是屬性文法？）什么是屬性文法？答：是在上下文無(wú)關(guān)文法的基礎(chǔ)上，為每個(gè)文法符號(hào)(含終結(jié)符和非終結(jié)符)配備若干個(gè)屬性值，對(duì)文法的每個(gè)產(chǎn)生式都配備了一組屬性計(jì)算規(guī)則(稱(chēng)為語(yǔ)義規(guī)則)。在語(yǔ)法分析過(guò)程中，完成語(yǔ)義規(guī)則所描述的動(dòng)作，從而實(shí)現(xiàn)語(yǔ)義處理。一個(gè)屬性文法形式的定義為一個(gè)三元組AG，AG=（G，V，E）。其中G為一個(gè)上下文無(wú)關(guān)文法；

5、V為屬性的有窮集；E為一組語(yǔ)義規(guī)則。9）語(yǔ)法制導(dǎo)翻譯）語(yǔ)法制導(dǎo)翻譯3答：一個(gè)編譯程序?qū)Ψ?hào)表的總體組織可有三種選擇：第一種：把屬性種類(lèi)完全相同的那些符號(hào)組織在一起，構(gòu)造出表項(xiàng)是分別為等長(zhǎng)的多個(gè)符號(hào)表。這樣組織的最大優(yōu)點(diǎn)是每個(gè)符號(hào)表的屬性個(gè)數(shù)和結(jié)構(gòu)完全相同。則表項(xiàng)是等長(zhǎng)的，并且表項(xiàng)中的每個(gè)屬性欄都是有效的，對(duì)于單個(gè)符號(hào)表示來(lái)說(shuō)，這樣使得管理方便一致，空間效率高。但這樣組織的主要缺點(diǎn)是一個(gè)編譯程序?qū)⑼瑫r(shí)管理若干個(gè)符號(hào)表，增加了總體管理的工作

6、量和復(fù)雜度。而且對(duì)各類(lèi)符號(hào)共同屬性的管理必須設(shè)置重復(fù)的運(yùn)行機(jī)制。使得符號(hào)表的管理顯得臃腫。第二種：把所有語(yǔ)言中的符號(hào)都組織在一張符號(hào)表中。組成一張包括了所有屬性的龐大的符號(hào)表。這樣組織方式的最大優(yōu)點(diǎn)是總體管理非常集中單一，且不同種類(lèi)符號(hào)的共同屬性可一致地管理和處理。這樣組織所帶來(lái)的缺點(diǎn)是，由于屬性的不同，為完整表達(dá)各類(lèi)符號(hào)的全部屬性必將出現(xiàn)不等長(zhǎng)的表項(xiàng)，以及表項(xiàng)中屬性位置的交錯(cuò)重疊的復(fù)雜情況，這就極大地增加了符號(hào)表管理的復(fù)雜度。為使表項(xiàng)

7、等長(zhǎng)且實(shí)現(xiàn)屬性位置的唯一性，可以把所有符號(hào)的可能屬性作為符號(hào)表項(xiàng)屬性。這種組織方法可能有助于降低符號(hào)表管理復(fù)雜性，但對(duì)某個(gè)具體符號(hào)，可能增加了無(wú)用的屬性空間，從而增加了空間開(kāi)銷(xiāo)。第三種：折衷方式是根據(jù)符號(hào)屬性相似程度分類(lèi)組織成若干張表，每張表中記錄的符號(hào)都有比較多的相同屬性。這種折衷的組織方式在管理復(fù)雜性及時(shí)空效率方面都取得折衷的效果，并且對(duì)復(fù)雜性和效率的取舍可由設(shè)計(jì)者根據(jù)自己的經(jīng)驗(yàn)和要求及目標(biāo)系統(tǒng)的客觀環(huán)境和需求進(jìn)行選擇和調(diào)整。212

8、1）.在整個(gè)編譯期間，對(duì)于符號(hào)表的操作有哪些？在整個(gè)編譯期間，對(duì)于符號(hào)表的操作有哪些？答：在整個(gè)編譯期間，對(duì)于符號(hào)表的操作大致可歸納為五類(lèi)：對(duì)給定名字，查詢(xún)此名是否已在表中；往表中填入一個(gè)新的名字；對(duì)給定名字，訪問(wèn)它的某些信息；對(duì)給定名字，往表中填寫(xiě)或更新它的某些信息；刪除一個(gè)或一組無(wú)用的項(xiàng)。2222）.符號(hào)表的作用有哪些？符號(hào)表的作用有哪些？答：在編譯程序中符號(hào)表用來(lái)存放語(yǔ)言程序中出現(xiàn)的有關(guān)標(biāo)識(shí)符的屬性信息，這些信息集中反映了標(biāo)識(shí)符的