編譯原理復習題2017含試卷

1、1?編譯原理復習題編譯原理復習題一簡答題：一簡答題：1)1)什么是句子？什么是句子？什么是語言什么是語言解答：句子——設G是一個給定的文法，S是文法的開始符號，如果Sx（其中x∈VT），則稱x是文法的一個句子。語言——語言是句子的集合。或——設G[S]是給定文法，則由文法G所定義的語言L(G)可描述為：L(G)＝x│Sxx∈VT。2)2)DFADFA與NFANFA有何區(qū)別有何區(qū)別解答:DFA與NFA的區(qū)別表現(xiàn)為兩個方面:一是NFA可以有

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

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

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

5、V為屬性的有窮集；E為一組語義規(guī)則。9）語法制導翻譯）語法制導翻譯3答：一個編譯程序對符號表的總體組織可有三種選擇：第一種：把屬性種類完全相同的那些符號組織在一起，構造出表項是分別為等長的多個符號表。這樣組織的最大優(yōu)點是每個符號表的屬性個數(shù)和結構完全相同。則表項是等長的，并且表項中的每個屬性欄都是有效的，對于單個符號表示來說，這樣使得管理方便一致，空間效率高。但這樣組織的主要缺點是一個編譯程序將同時管理若干個符號表，增加了總體管理的工作

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

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

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