編譯原理填空簡答整理

1、填空一、 素短語：含有終結(jié)符的短語，如果它不存在也具有這種性質(zhì)的真子串，則該短語為素短語。二、 二義性：文法G的一個句子如果能找到兩種不同的規(guī)范推導(dǎo)或兩棵不同的分析樹，則稱這個句子是二義性的，一個文法包含二義性的句子，則這個文法是二義性的，否則該文法是無二義性的。三、 程序流圖的構(gòu)造：程序流圖是程序結(jié)構(gòu)的圖形表示，我們把有唯一首節(jié)點n0的有向圖G成為控制流程圖，對一個程序流圖來說，節(jié)點代表計算，有向邊代表控制流，而首節(jié)點是程序起始位置所在的節(jié)點（基本塊）。四、 循環(huán)：循環(huán)是程序流圖中有唯一入口結(jié)點的強(qiáng)連通的子圖。循環(huán)要求強(qiáng)連通是很自然的，要求入口結(jié)點唯一是由于循環(huán)優(yōu)化中需要將循環(huán)不變運算提到循

2、環(huán)之外（代碼外提）入口前的一個確定地點，這就要求入口結(jié)點是唯一的。五、 必經(jīng)結(jié)點集：從流圖的首結(jié)點出發(fā)到達(dá)結(jié)點n的任一通路都必須經(jīng)過結(jié)點d，則稱d是n的必經(jīng)結(jié)點，記為d DOM n。六、 如果將DOM看成結(jié)點集N上的一種二元關(guān)系，那么它具有以下性質(zhì)：（1）自反性（2）反對稱性（3）傳遞性。七、 可歸約流圖：一個流圖刪去了回邊后的子圖是個無環(huán)路的有向圖，則稱這個流圖為可歸約的流圖。八、 循環(huán)優(yōu)化的例子：P161。九、 在基本塊范圍內(nèi)依次將三地址代碼序列變換稱目標(biāo)代碼，為使這種變換更有效，必須考慮到在基本塊范圍內(nèi)如何充分利用寄存器的問題。選擇標(biāo)準(zhǔn)是占用寄存器的變量不再被引用，或者引用點為最遠(yuǎn)的，這

3、由待用信息來表示。十、 并行編譯系統(tǒng)就是能夠處理并行程序設(shè)計語言，能夠?qū)崿F(xiàn)串行程序并行化，具有并行優(yōu)化能力的編譯系統(tǒng)。十一、 并行編譯技術(shù)中兩個最重要的內(nèi)容便是串行程序的向量化和并行化。十二、 向量計算機(jī)：向量計算機(jī)是具有向量處理能力的計算機(jī)，它是在標(biāo)量處理機(jī)的基礎(chǔ)上增加了向量處理部分而構(gòu)成的。向量處理部分通常含有若干向量寄存器、若干向量流水功能部件，以及一個控制向量操作長度的寄存器。十三、 并行編譯針對向量計算機(jī)的一個重要功能是串行程序向量化。顯然，程序中的向量成分越多，向量機(jī)的運行效率越高。十四、 共享存儲器多處理機(jī)在更大的范圍內(nèi)提供了并行處理的能力，向量機(jī)只能并行處理向量操作，而多處理機(jī)

4、可以并行執(zhí)行多個循環(huán)迭代、語句塊、子程序段。十五、 分布存儲器大規(guī)模并行計算機(jī)：分布存儲器大規(guī)模并行計算機(jī)是由成百、上千乃至上萬個結(jié)點構(gòu)成的并行機(jī)，每個結(jié)點有自己的處理機(jī)和存儲器，結(jié)點之間以互聯(lián)網(wǎng)絡(luò)相連。十六、 并行編譯系統(tǒng)的結(jié)構(gòu)：并行編譯系統(tǒng)通常包括程序分析、程序優(yōu)化、和并行代碼生成三個部分。簡答一、 編譯程序總框圖：P4。二、 簡述文法的定義：文法G是一個四元組，G=（VT，VN，S，P），其中：VT為終結(jié)符號集，這是個非空有限集。VN為非終結(jié)符號集，它也是個非空有限集。S為一文法的開始符，是一特殊的非終結(jié)符，SVN。P是產(chǎn)生式的非空有限集，其中每個產(chǎn)生式（或稱規(guī)則）是一序偶（，），通常寫

5、成： 讀作是或定義為。為產(chǎn)生式左部，為產(chǎn)生式右部。三、 簡述單詞符號的種類：單詞符號是程序語言最基本的語法符號，通常有五種。（1）基本字，有的稱為關(guān)鍵字或保留字，如if，while，for，do，goto等。（2）標(biāo)識符，用戶用來命名程序中出現(xiàn)的變量、數(shù)組、函數(shù)、過程、標(biāo)號等，通常是一個字母開頭的字母數(shù)字串，如length、nextch等。 （3）常數(shù)，包括各種類型的常數(shù)，如整型、實型、字符型等。 （4）運算符，如+、-、*、/等。 （5）界符，如；：、等。四、 簡述單詞編碼形成和特點：識別出來的單詞符號應(yīng)采用某種中間表示，以便為編譯的后續(xù)階段引用，其原則在于便以區(qū)別、便于識別，表示方法可多種

6、多樣，以有利于編譯處理為準(zhǔn)，通常單詞符號可以用一個二元組表示：（單詞類別，單詞符號的屬性值），第一元用以區(qū)分單詞符號所屬的類，以整數(shù)編碼；第二元用以區(qū)分在該類中哪一個單詞符號，即單詞符號的值的編碼，隨類別不同而不同五、 簡述正規(guī)式與正規(guī)文法的關(guān)系：正規(guī)式與正規(guī)文法都是用來描述程序語言的詞法結(jié)構(gòu)，它們有著相同的表達(dá)能力。對任一正規(guī)文法，都可找到一個正規(guī)式，使正規(guī)式表示的正規(guī)集恰為正規(guī)文法產(chǎn)生的語言，反之亦然。正規(guī)式簡潔，正規(guī)文法易識別，根據(jù)需要，可在兩者之間進(jìn)行轉(zhuǎn)換。六、 簡述遞歸下降分析方法的特點：遞歸下降分析方法是一種自頂向下的分析方法，文法的每個非終結(jié)符，對應(yīng)于一個遞歸過程。分析就是從方法

7、開始符出發(fā)執(zhí)行一組遞歸過程，向下推導(dǎo)，直到推導(dǎo)出句子。或者說從根結(jié)點出發(fā)，自上而下為輸入串尋找一個最左匹配序列，建立一棵語法分析樹。七、 簡述LR分析器特點：LR分析法是目前最廣泛的無回溯的“移動-歸約”方法，用上下文無關(guān)文法描述的程序語言，一般均可用LR分析方法，不只是因為LR分析方法對文法限制最少，而且效率同樣很高，并且對發(fā)生的錯誤能準(zhǔn)確定位。LR分析法也是一種表驅(qū)動分析方法，有一個分析棧、一個控制程序（或稱為驅(qū)動程序）和一個分析表。八、 簡述堆分配的特點：作為堆的存儲空間可以由固定長度的存儲塊組成，也可以由可變長度的存儲塊組成。在堆中可隨機(jī)申請一個或幾個存儲塊，活動結(jié)束時可隨即釋放。在這些存儲塊中有些正在使用由使用塊記錄指出各使用塊的開始位置及塊的大小等有用信息。有些則空閑，稱為自由塊。所有的自由塊均被連接起來。由指針free指向其起始塊每個自由塊都有一個指針指向下一個自由塊。當(dāng)有一個使用塊被釋放時，該塊連接到free塊中，并從使用塊中撤銷該塊的及錄項。九、 簡述符號表的特點：在程序中，用戶用標(biāo)識符定義了不少名字來代表不同的數(shù)據(jù)對象，編譯程序?qū)⑦@些名字保存在符號表中。符號表除了記錄名字本身外，還記錄了與名字關(guān)聯(lián)的各