編譯原理基礎(chǔ)

第一章引論主要內(nèi)容：編譯原理的基本概念、定義、編譯原理的應(yīng)用發(fā)展和現(xiàn)狀。重點：編譯程序工作的基本構(gòu)成及各階段的基本任務(wù)，具體要求：理解什么是編譯程序，了解各編譯程序的基本構(gòu)成及各階段的基本任務(wù)，編譯程序總框，了解編譯程序生成過程和構(gòu)造工具。一、名詞解釋1、編譯程序：能夠把用各種高級語言書寫的源程序翻譯成某種等價的目標程序的翻譯程序。2、遍：指編譯程序?qū)υ闯绦蚧蛑虚g代碼程序從頭到尾掃描一次。3、靜態(tài)分配：在編譯時就能夠安排好目標程序運行時的全部數(shù)據(jù)空間。二、問答題1、簡述編譯程序的結(jié)構(gòu)？答：編譯程序包括詞法分析、語法分析、中間代碼生成、優(yōu)化，目標代碼產(chǎn)生五個階段，上述各階段中還要進行表格處理和出錯處理的工作。2、編譯程序可分成哪幾個階段？它們之間的關(guān)系如何？答：編譯程序可分為五個階段：詞法分析、語法分析、中間代碼生成、優(yōu)化、目標代碼生成。上述五個階段之間每個階段輸出為作下一階段的輸入，第一階段的輸入是源程序，最后階段的輸出是目標代碼程序。注意：編譯過程中，階段的劃分和遍的劃分不一定相同第二章高級程序語言概述主要內(nèi)容：程序語言定義、初等數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)、表達式、語句、高級語言的一般特征及程序語言的語法描述。重點：程序語言定義具體要求：理解程序語言的詞法、語法和語義等概念；熟悉高級程序語言的一般結(jié)構(gòu)和主要共同特征。一、填空題1、程序語言是由（語法）和（語義）兩方面定義的。2、一個名字的屬性包括（類型）和（作用域）3、目標代碼一般有三種形式：能夠立即執(zhí)行的機器語言代碼，（待裝配的機器語言模塊）和（匯編語言代碼）4、語義：定義一個程序的意義的（一組規(guī)則）5、2型文法又稱為（上下文無關(guān)文法），3型文法又為（正規(guī)文法）二、是非題1、雖然名字都是用標識符表示的，但名字和標識符有著本質(zhì)的區(qū)別（對）2、各種名字都是用標識符表示的，所以名字和標識沒有本質(zhì)的區(qū)別（錯）3、數(shù)組元素的地址計算與數(shù)組的存儲方式?jīng)]有關(guān)系（錯）4、語法是指程序的含義（錯）5、因名字都是用標識符表示的，故名字與標識符沒有區(qū)別（錯）第三章詞法分析主要內(nèi)容：詞法分析器的任務(wù)、詞法分析器的設(shè)計、正規(guī)表達式與有限自動機、詞法分析器的自動生成。重點：詞法分析器的任務(wù)，詞法分析器設(shè)計，正規(guī)表達式與有限自動機，詞法分析器自動生成，狀態(tài)轉(zhuǎn)換圖具體要求：理解詞法分析器的功能及輸出形式；熟練掌握詞法詞法分析器的設(shè)計的原理，掌握運用狀態(tài)轉(zhuǎn)換圖進行詞法分析器設(shè)計。一、是非題1、一個狀態(tài)轉(zhuǎn)換圖可以用于識別一定的字符串。（對）二、填空題1、詞法分析器的任務(wù)是從（源程序）中識別出一個個（單詞符號）。2、詞法分析器的任務(wù)是（輸入）源程序、（輸出）單詞符號。3、執(zhí)行詞法分析的程序稱為（詞法分析器）或（掃描器）。4、詞法分析器所輸出的單詞符號常常表示成如下二元關(guān)系：（單詞種別，單詞自身值）。5、一張轉(zhuǎn)換圖只包含有限個狀態(tài)，其中有一個被認為是（初態(tài)），而且實際上至少要有一個（終態(tài)）。6、程序語言的單詞符號包括：（標識符）、（運算符）、（常數(shù)）、（基本字）、界符等。7、一張轉(zhuǎn)換圖只包含有限個狀態(tài)，其中有一個被認為是（初）態(tài)，而且是實際上至少要有一個（終）態(tài)。名詞解釋1、詞法分析器：是一種程序，它能將字符串形式的源程序改造成單詞符號串形式的中間程序。2、超前搜索：在詞法分析過程中，有時為了確定詞性，需要超前掃描若干個字符，這個動作為超前搜索。四、簡答題1、何謂狀態(tài)轉(zhuǎn)換圖？作用是什么？答：狀態(tài)轉(zhuǎn)換圖是一張有限方向圖，其中結(jié)點代表狀態(tài)，狀態(tài)之間用箭弧連接，箭弧上的標記代表在射出結(jié)點狀態(tài)下可能出現(xiàn)的輸入字符或字符類，狀態(tài)中有一個初態(tài)，至少有一個終態(tài)。第四章語法分析--自上而下分析主要內(nèi)容：上下文無關(guān)文法，語法分析器的功能、自上而下分析所面臨的問題、LL（1）分析法、遞歸下降分析的構(gòu)造過程、預測分析程序等內(nèi)容。重 點：上下文無關(guān)文法，遞歸下降子程序預測分析表構(gòu)造，LL（1）方法。具體要求：正確理解上下文無關(guān)方法基本概念，包括：文法的定義、縮寫、句型、句子、語言、語法樹、二義性等；正確理解自上而下分析的基本思想；熟練掌握遞歸下降分析基本方法；消除左遞歸、消除回溯，構(gòu)造遞歸下降子程序；掌握預測分析程序的基本原理的預測分析構(gòu)造；理解LL（1）方法的定義，LL（1）文法的條件及其判別，計算first集和follow集。一、 是非題：1、 使用自上而下分析法，首先必須消去文法的左遞歸。（對）2、 文法是描述語言語義的形式規(guī)則。（錯）3、 一個文法是二義的，則這個文法的每個句子都對應(yīng)兩棵不同的語法樹。（錯）4、 一個上下文無關(guān)文法的產(chǎn)生式的左部符號可以是非終結(jié)符也可以是終結(jié)符。（錯）5、 遞歸下降分析法是一種自下而上的分析法。（錯）6、 一個上下文無關(guān)文法的開始符號是一個特殊的非終結(jié)符。（對）7、 一個句型的推導可表示在一棵語法樹。（對）8、 一個文法G,若它的分析表M不含多重定義入口，則G是LL（1）文法。（對）9、 文法的二義性與語言的二義性是兩個相同的概念。（錯）10、 對于任何一個含有左遞歸的文法必存在一個等價的不含左遞歸的文法。（對）11、 一個文法的句子也一定是該文法的句型。（對）12、 如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則該文法是二義的。（對）13、 一個上下文無關(guān)文法的開始符號可以是終結(jié)符和非終結(jié)符。（錯）14、 已經(jīng)證明文法的二義性是可判定的。（錯）二、 填空題*1、假定G是一個文法，S是它的開始符號，如果Sna，則稱a是一個（句型），僅包含終結(jié)符號的句型是一個（句子）。2、 常用的語法分析方法有（自下而上分析法）或（算符優(yōu)先分析法），（自上而下分析法）或（遞歸下降法）等。3、 一個上下文無關(guān)文法包括四個組成部分是（一組終結(jié)符號，一組非終結(jié)符號，一個開始符號，一組產(chǎn)生式）。4、 一個文法G,若它的分析表M不含多重定義入口則（G是LL（1）文法）。5、 每個文法G的程序語言都包含（語法）和（語義）兩方面定義的。6、 一個文法，如果存在非終結(jié)符P，P—Pa，則稱這個文法含有（左遞歸）。7、 一般程序語言的語法單位有：（表達式）、（語句）、（過程）、（程序）等等。8、 所謂最右推導是指：（任何一步a=〉B都是對a中最右非終結(jié)符號進行替換的）。9、 語法分析的任務(wù)是（分析一個文法的句子結(jié)構(gòu)）。10、 假定S是文法G的開始符號，對于G的任何非終結(jié)符A,定義集合*FOLLOW（A）=（｛a|Sn...Aa,8丘片｝）。11、預測分析程序是使用一張（分析表）和一個（符號棧）進行聯(lián)合控制的。12、如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則稱這個文法是（二義的）。13、文法G所產(chǎn)生的句子的全體是（語言），將它記為L（G）。14、文法是描述語言的（語法結(jié)構(gòu)）的形式規(guī)則。15、產(chǎn)生式的用于定義（語法范疇）的一種書寫規(guī)則。16、 所謂最左推導是指（任何一步a=〉B都是對a中的最左非終結(jié)符進行替換的）。17、 語法分析的方法大致可分為兩類，一類是（自上而下）分析法，另一類是（自下而上的）分析法。18、 如果a=>a二〉…二〉a,則我們稱這個序列是（從a到a的一個推導）。12n1n19、 語法規(guī)則是（語法單位）形成規(guī)則，詞法規(guī)則的（單詞符號）形成規(guī)則。20、 最右推導亦為（規(guī)范推導），由此推得的句型稱為（規(guī)范）句型。三、名詞解釋：1、 文法：描述語言的的語法結(jié)構(gòu)的形式規(guī)則。2、 句型：設(shè)G是一個文法，S是它的開始符號，若S=>a，貝臨稱為一個句型。3、 二義性文法：若文法存在某個句子對應(yīng)兩棵不同的語法樹（或兩種不同的推導）。4、 最左推導：推導的任何一步a=〉B都是對a中最左非終結(jié)符進行替換。5、 語法分析：按文法的產(chǎn)生式識別輸入的符號串是否為一個句子的分析過程。6、 規(guī)范推導：最右推導稱為規(guī)范推導。7、 語法：是一組規(guī)則，用它可以形成和產(chǎn)生一個合式的程式。8、 產(chǎn)生式：是定義語法范疇一種書寫規(guī)則，其形式是A~a，其中：A是非終結(jié)符，a是終結(jié)符或非終結(jié)符組成的串。9、 規(guī)范句型：由規(guī)范推導所得的句型。10、 語法樹：用一張圖表示一個句型的推導的表示方法。第五章語法分析—自下而上分析主要內(nèi)容：上下文無關(guān)文法，自下而上分析的基本問題、算符優(yōu)先分析、LR分析法。重點：上下文無關(guān)文法，算符優(yōu)先分析基本方法、算符優(yōu)先表和歸約。具體要求：正確理解上下文無關(guān)方法基本概念，正確理解自下而上分析的基本思想；以及歸約、短語、句柄、分析樹等概念；掌握自下而上語法分析（算符優(yōu)先分析法），算符優(yōu)先分析基本方法、算符優(yōu)先表和算符優(yōu)先函數(shù)構(gòu)造技術(shù)，LR分析器，LR（O）項目集族和LR（O）分析表的構(gòu)造，SLR分析表的構(gòu)造，規(guī)范LR分析表的構(gòu)造，出錯處理概述，詞法分析階段的錯誤診察，語法分析（自下而上）階段的錯誤診察。一、判斷題1、 最左歸約是最右推導的逆過程。（TURE）2、 一個優(yōu)先表一定存在相應(yīng)的優(yōu)先函數(shù)。（FALSE）3、 算符優(yōu)先分析法是一種自上而下的分析法。（FALSE）4、 優(yōu)先關(guān)系表所對應(yīng)的優(yōu)先函數(shù)，如果存在，則一定唯一。（FALSE）5、 一個句型的直接短語是唯一的。（FALSE）二、填空題1、如果一個文法的任何產(chǎn)生式的右部都不含有兩個相繼（并列）的非終結(jié)符，則這種文法稱為（算符）文法。2、一個句型的最左直接短語稱為該句型的（句柄）。三、名詞解釋1、句柄：一個句型的最左直接短語稱為句型的句柄。2、 對于文法G和每個非終結(jié)符P,定義集合FIRSTVT（P）=（｛a|P=〉a…或P=〉Qa…，a^V而QUV｝）TN3、 短語：令G是一個文法，S是文法的開始符號，假定ap6是文法G的一個句型。如果*有：SnaA8，且A=0,則稱p是句型ap6相對非終結(jié)符A的短語。4、 素短語：素短語是指這樣一個短語，它至少含有一個終結(jié)符，并且除它自身之外不再含任何更小的素短語。5、 算符優(yōu)先文法：如果一個算符文法G中任何終結(jié)符對，（a,b）至多只滿足下述三關(guān)系之一：a?b,a<?b,a?號則稱G是一個算符優(yōu)先文法。6、 語法樹：用一張圖表示一個句型的推導之表示方法。第七章語法制導翻譯和中間代碼生成主要內(nèi)容：語法制導翻譯概述，各種常見的中間語言形式，中間語言，說明語句，賦值語句的翻譯，布爾表達式的翻譯，控制語句到四元式的翻譯，自上而下分析制導翻譯概述。重點：語法制導翻譯基本思想，三種中間語言，四元式，逆波蘭表示，算術(shù)表達式，算術(shù)表達式的翻譯，布爾表達式的翻譯，控制語句的翻譯。具體要求：正確理解語法制導翻譯基本原理；熟悉常見的幾種中間語言。四元式、三元式，逆波蘭表示；掌握各種語句到四元式的翻譯方法，包括：簡單算術(shù)表達式，布爾表達式，控制語句，數(shù)組引用，過程調(diào)用等。一、 是非題1、數(shù)組元素的地址計算和數(shù)組的存貯方式無關(guān)。 （錯）2、逆波蘭式表示的表達式亦稱后綴式。 （對）二、 填空1、 表達式a+b*（d-c）的逆波蘭表示為（abdc-*+）。2、 語法分析是根據(jù)語言的（語法規(guī)則）進行的，中間代碼產(chǎn)生是根據(jù)語言的（語義規(guī)則）進行的。3、 表達式a-（b+c）/d的逆波蘭表示為（abc+d/-）。4、 逆波蘭式abc*d+/所表示的表達式為（a/（b*c+d））。5、 逆波蘭式ab+cd+*所表示的表達式為（（a+b）*（c-d））。6、表達式（a+b）/（c+d）的逆波蘭表示為（ab+cd+/）。7、 表達式a/（b*c+d）的逆波蘭表式為（abc*d+/）。8、 表達式a*（b+c）/（d-e）的逆波蘭表示為（abc+*de-/）。9、 表達式a+b*（d-c）的逆波蘭表示為（abdc-*+）10、 逆波蘭式abc+d/-所表示的表達式為（a-（b+c）/d）。11、 常見的中間語言有（三元式，四元式，逆波蘭式，樹形表示）等等12、 表達式（a-b*c）/d的逆波蘭表示為（abc*-d/）。三、名詞解釋：1、 逆波蘭表示：逆波蘭表示法是一種表示表達式的方式，這種表示法是：把運算量（操作數(shù)）寫在前面，把算符寫在后面（后綴）。2、 后綴式：是一種把運算量寫在前面，把算符號寫在后面的表示式的方法。3、 語言的語義：它是一組規(guī)則，用它可以定義一個程序的意義。4、 語義：定義一個程序的意義的一組規(guī)則。5、 語法制導翻譯：在語法分析過程中，隨著分析的步步進展，根據(jù)每個產(chǎn)生式所對應(yīng)的語義對程序進行翻譯的辦法。第八章符號表主要內(nèi)容：符號表的組織和使用，整理與查找，名字的作用范圍，符號表的內(nèi)容。重點：符號表的作用與內(nèi)容。具體要求：理解符號表的作用及符號表的組織和使用方法，作用域信息的保存，整理與查找，了解名字的作用范圍，符號表的內(nèi)容等。一、填空1、 編譯過程中，常見的構(gòu)造和查填符號表的方法有（線性查找），（對折查找與二叉樹）各（雜湊技術(shù)）。2、 一張符號表的每一項包含兩大欄，即（名字欄）和（信息欄）。3、 符號表的信息欄中登記了每個名字的有關(guān)性質(zhì)，如（類型，種屬，所占單元大小，相對地址）等。4、 符號表的整理和查找技術(shù)通常有（線性查找二叉樹雜湊技術(shù)）等等。二、論述題1、 符號表有哪幾種整理與查找方法？它們的效率及構(gòu)造難易程度如何？答：符號表的整理與查找方法有三種：線性查找、二叉樹和雜湊技術(shù)。線性查找最簡單，但效率低；二叉樹的查找效率高一些，然而實現(xiàn)上較困難一點；雜湊技術(shù)效率高，可實現(xiàn)上比較復雜，而且要消耗一些額外的存儲空間。2、 對符號表的操作包括哪些方面？答：對給定名字，確定此名是否在表中，填入新名，對給定名字，訪問它的有關(guān)信息，對給定名字，填寫或更新它的某些信息；刪除一個或一組無用的項。第九章運行對存儲空間組織一、是非題1、棧式存貯分配適合于解決過程和函數(shù)的遞歸調(diào)用。（對）2、靜態(tài)存貯分配策略適用于fortran類語言。（對）3、每個過程的display表的體積在編譯時就可確定。（對）4、每個過程的活動記錄的體積在編譯時可靜態(tài)確定。（對）二、填空1、 對于數(shù)據(jù)空間的存貯分配，fortran采用（靜態(tài)存貯分配）策略，pascal采用（動態(tài)存貯分配）策略。2、 常用的兩種動態(tài)存儲分配辦法是（棧式）動態(tài)分配和（堆式）動太分配。3、 對不同的語言，采取的存儲分配策略也可能不同；如：（fortran）語言采用靜態(tài)分配策略。（pascal）語言采用動態(tài)分配策略。4、 如果在編繹時能夠確定一個程序在運行時所需的全部數(shù)據(jù)空間的大小，則可采用（靜態(tài)）存儲分配策略，如果在編繹時不能確定程序在運行時所需數(shù)據(jù)空間的大小，則必須采用（動態(tài)）存儲分配策略。5、 數(shù)據(jù)存貯空間的分配策略一般分為（靜態(tài)分配）和（動態(tài)分配）兩大類。6、 存儲分配策略分為（靜態(tài)）分配策略和（動態(tài)）分配策略兩種。三、名詞解釋1、 動態(tài)存貯分配：程序運行時動態(tài)地確定所需數(shù)據(jù)空間的大小。2、 靜態(tài)存貯分配：編繹時完全確定目標程序運行時的全部數(shù)據(jù)空間。3、 活動記錄：一個過程在運行時所需數(shù)據(jù)空間中，編譯時可確定體積的部分稱該過程的活動記錄。4、 Display表：過程的嵌套層次顯示表，記錄該過程的各外層過程最新活動記錄的起始地址。四、論述題1、簡要描述嵌套過程語言的活動記錄所包含的項目，一個過程的活動記錄:2、簡述嵌套過和語言在存貯分配時為何要引進display表。答：程序運行時，一個過程Q可能引用它的外層過程P的最新活動記錄中的某些數(shù)據(jù)，故Q運行時必須知道它的所有外層過程的最新活動記錄的地址，因此，必須設(shè)法跟蹤每個外層過程的最新活動記錄的位置，層次顯示表（display表）就是用于登記每個外層的最新活動記錄位置的表。3、 一個過程的活動記錄一般包括哪些項目？答：應(yīng)包含下面三方面內(nèi)容：（1）連接數(shù)據(jù)。（2）形式單元。（3）局部變量和臨時單元4、 在進行地址分配時，是不是一定要對每個臨時變量分配一個不同的存貯單元？臨時變量地址分配的一般原則是什么？答：不是。如果兩個臨時變量的作用域不相交，則它們可分配在同一單元中。5、 試問：對pascal語言采用何種存貯分配策略？為什么？答：動態(tài)分配策略。因為pascal是嵌套過程語言，允許過程遞歸和允許自由申請與退還數(shù)據(jù)空間。6、 一個fortran程序段局部數(shù)據(jù)區(qū)一般包含哪些內(nèi)容？答：臨時變量，數(shù)組，簡單變量，形式單元，寄存器保護區(qū)，返回地址。第十章優(yōu)化主要內(nèi)容：優(yōu)化概述，局部優(yōu)化，基本塊的DAG表示及其應(yīng)用?？刂屏鞣治龊脱h(huán)查找算法，到達定值與引用定值鏈，循環(huán)優(yōu)化。重 點：局部優(yōu)化，DAG的構(gòu)造和應(yīng)用，控制流分析和循環(huán)査找算法，到達定值與引用定值鏈，循環(huán)優(yōu)化。具體要求：正確理解代碼優(yōu)化的定義以及各種可能的優(yōu)化的概念，掌握用DAG表示進行局部優(yōu)化的方法。掌握對各類優(yōu)化的理解，包括常量合并、公共子表達式刪除、復寫傳播、死代碼刪除、循環(huán)優(yōu)化（代碼外提、歸納變量刪除、強度削弱）等。掌握建立程序流圖的算法和流圖中自然循環(huán)的識別算法。一、 是非題1、 一個基本塊的進口和出口可以不唯一。（錯）TOC\o"1-5"\