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

1、如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!1.把匯編語(yǔ)言程序翻譯成機(jī)器可執(zhí)行的目標(biāo)程序的工作是由 B 完成的。 A、編譯器 C、解釋器 D、預(yù)處理器2.編譯程序生成的目標(biāo)程序 B 是機(jī)器語(yǔ)言的程序。 A、一定 B、不一定 3.下面關(guān)于解釋程序的描述正確的是 B 。 解釋程序的特點(diǎn)是處理程序時(shí)不產(chǎn)生目標(biāo)代碼。 解釋程序適用于COBOL和FORTRAN語(yǔ)言。 解釋程序是為打開(kāi)編譯程序技術(shù)得僵局而開(kāi)發(fā)的。A、 B、 C、 D、4.設(shè)有文法GI：II1I0IaIcabc下列符號(hào)串中是該文法的句子有 B 。 ab0 a0c01 aaa bc10可選項(xiàng)有： A、 B、 C、 D、5.一個(gè)上下文無(wú)關(guān)文法消除

2、了左遞歸，提取了左公共因子后是滿足LL（1）文法的 A 。 A、 必要條件 B、充分必要條件1.一個(gè)語(yǔ)言的文法是 B 。A、唯一的B、不唯一的C、個(gè)數(shù)有限的2. 設(shè)有文法GS:S:=S*S|S+S|(S)|a該文法 B 二義性文法A 是 B 不是 C無(wú)法判斷。 3.給定文法AbAcc，下面的符號(hào)串中，為該文法句子的是 A 。A、cc B、bcbc C、bccbcc D、bbbcc4.編譯過(guò)程中，語(yǔ)法分析器的任務(wù)是 B 。分析單詞是怎樣構(gòu)成的分析單詞串是如何構(gòu)成語(yǔ)句和說(shuō)明的分析語(yǔ)句和說(shuō)明是如何構(gòu)成程序的分析程序的結(jié)構(gòu)A、 B、 C、 D、 5.一個(gè)句型中的最左 B 成為該句型的句柄。 A、短語(yǔ)

3、B、簡(jiǎn)單短語(yǔ) C、素短語(yǔ) D、終結(jié)符號(hào)1. 面向機(jī)器語(yǔ)言指的是_C_。 A、用于解決機(jī)器硬件設(shè)計(jì)問(wèn)題的語(yǔ)言 B、特定計(jì)算機(jī)系統(tǒng)所固有的語(yǔ)言 C、各種計(jì)算機(jī)系統(tǒng)都通用的語(yǔ)言 D、只能在一臺(tái)計(jì)算機(jī)上使用的語(yǔ)言2.如果文法G是無(wú)二義的，則下面 D 成立。A、文法中的句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)；B、文法中某個(gè)句子有兩個(gè)不同的最左推導(dǎo)；C、文法中某個(gè)句子有兩個(gè)不同的最右推導(dǎo)；D、文法中任一句子，它的最左或最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹(shù)相同。 3.運(yùn)行階段的存儲(chǔ)組織與管理的目的是_C_。 提高編譯程序的運(yùn)行速度。 提高目標(biāo)程序的運(yùn)行速度。 為運(yùn)行階段的存儲(chǔ)分配做準(zhǔn)備。 A、 B、 C、 D、4. 設(shè)有文法GI:I-I

4、1|I0|Ia|Ic|a|b|c下列符號(hào)串中是該文法的句子的是_C_1 ab0 2 a0c01 3 aaa 4 bc10可選項(xiàng)有 A 1 B234 C 34 D12341 / 45如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!5.下面說(shuō)法正確的是 A 。 A、一個(gè)SLR（1）文法一定也是LALR（1）文法 B、一個(gè)LR（1）文法一定也是LALR（1）文法1.動(dòng)態(tài)存儲(chǔ)分配時(shí)，可以采用的分配方法有_ C _。 以過(guò)程為單位的棧式動(dòng)態(tài)存儲(chǔ)分配 堆式存儲(chǔ)分配 最佳分配方法 A、 B、 C、 D、2.面向機(jī)器語(yǔ)言的特點(diǎn)是_ D _。 A、程序的執(zhí)行效率低，編制效率低，可讀性差 B、程序的執(zhí)行效率高，編制效率

5、高，可讀性強(qiáng) C、程序的執(zhí)行效率低，編制效率高，可讀性強(qiáng) D、程序的執(zhí)行效率高，編制效率低，可讀性差3. 下面關(guān)于解釋程序的描述正確的是 B 。 解釋程序的特點(diǎn)是處理程序時(shí)不產(chǎn)生目標(biāo)代碼。 解釋程序適用于COBOL和FORTRAN語(yǔ)言。 解釋程序是為打開(kāi)編譯程序技術(shù)得僵局而開(kāi)發(fā)的。A、 B、 C、 D、 4. 編譯過(guò)程中，語(yǔ)法分析器的任務(wù)是 B 。分析單詞是怎樣構(gòu)成的分析單詞串是如何構(gòu)成語(yǔ)句和說(shuō)明的分析語(yǔ)句和說(shuō)明是如何構(gòu)成程序的分析程序的結(jié)構(gòu)A、 B、 C、 D、 5. 一個(gè)句型中的最左 B 成為該句型的句柄。 A、短語(yǔ) B、簡(jiǎn)單短語(yǔ) C、素短語(yǔ) D、終結(jié)符號(hào)1. 編譯程序眾的語(yǔ)法分析器接受以

6、 C 為單位的輸入，并產(chǎn)生有關(guān)信息工以后各階段適用。 A、表達(dá)式 B、 產(chǎn)生式 C、單詞 D、語(yǔ)句2. 經(jīng)過(guò)編譯所得到的目標(biāo)程序是 D 。 A、 四元式序列 B、 二元式序列 C、 間接三元式序列 D、 機(jī)器語(yǔ)言程序或匯編語(yǔ)言程序 3. 編譯程序是將高級(jí)語(yǔ)言程序翻譯成 B 。 A、機(jī)器語(yǔ)言程序 B、匯編語(yǔ)言程序或機(jī)器語(yǔ)言程序 C、匯編語(yǔ)言程序或高級(jí)語(yǔ)言程序 D、機(jī)器語(yǔ)言程序或高級(jí)語(yǔ)言程序4. 設(shè)有文法GI：II1I0IaIcabc下列符號(hào)串中是該文法的句子有 B 。 ab0 a0c01 aaa bc10可選項(xiàng)有： A、 B、 C、 D、 5. 巴科斯-諾爾范式（BNF）是一種廣泛采用的 C 的

7、工具。A、描述規(guī)則 B、描述語(yǔ)言 C、 描述文法 D、 描述句子1. 編譯程序眾的語(yǔ)法分析器接受以 C 為單位的輸入，并產(chǎn)生有關(guān)信息工以后各階段適用。 A、表達(dá)式 B、 產(chǎn)生式 C、單詞 D、語(yǔ)句2. 如果文法G是無(wú)二義的，則下面 D 成立。A、文法中的句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)；B、文法中某個(gè)句子有兩個(gè)不同的最左推導(dǎo)；C、文法中某個(gè)句子有兩個(gè)不同的最右推導(dǎo)；2 / 45如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!D、文法中任一句子，它的最左或最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹(shù)相同。 3. 編譯過(guò)程中，語(yǔ)法分析器的任務(wù)是 B 。(1) 分析單詞是怎樣構(gòu)成的（2）分析單詞串是如何構(gòu)成語(yǔ)句和說(shuō)明的（3）分析語(yǔ)句和說(shuō)

8、明是如何構(gòu)成程序的（4）分析程序的結(jié)構(gòu)A、（2）（3） B、（2）（3）（4） C、(1)（2）（3） D、(1)（2）（3）（4）4. 動(dòng)態(tài)存儲(chǔ)分配時(shí)，可以采用的分配方法有 C 。 以過(guò)程為單位的棧式動(dòng)態(tài)存儲(chǔ)分配。 堆式存儲(chǔ)分配。 最佳分派方法 A、 B、 C、 D、 5. 一個(gè)編譯程序中，不僅包含詞法分析，語(yǔ)法分析，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等五個(gè)部分，還應(yīng)包含 C 。 A、模擬執(zhí)行器 B、解釋器 C、表格處理和出錯(cuò)處理 D、符號(hào)執(zhí)行器1.一個(gè)LR（1）文法合并同心集后若不是LALR（1）文法 B 。 A、則可能存在移進(jìn)/歸約沖突 B、則可能存在歸約/歸約沖突 C、則可能存在移進(jìn)

9、/歸約沖突和歸約/歸約沖突2.LL(k)文法 B 二義性的。 A、都是B、都不是C、不一定3. 與PASCAL語(yǔ)言存儲(chǔ)分配方式相識(shí)的語(yǔ)言是 A 。 A、C語(yǔ)言 B、BASIC語(yǔ)言 C、FORTRAN-77 D、C+語(yǔ)言4. B 這樣一些語(yǔ)言，它們能夠被確定的有窮自動(dòng)機(jī)識(shí)別，但不能用正規(guī)表達(dá)式表示。A、存在B、不存在 C、無(wú)法判定5. 編譯程序在其工作過(guò)程中使用最多的數(shù)據(jù)結(jié)構(gòu)是 D 。 A、線性表 B、鏈表 C、表 D、符號(hào)表1. 程序語(yǔ)言的語(yǔ)言處理程序是一種 A 。 A、系統(tǒng)軟件 B、應(yīng)用軟件 C、實(shí)時(shí)軟件 D、分布式系統(tǒng)2. 一個(gè)正規(guī)語(yǔ)言只能對(duì)應(yīng) B 。 A、 一個(gè)正規(guī)文法 B、一個(gè)最小有限

10、狀態(tài)自動(dòng)機(jī)3. 下列關(guān)于標(biāo)識(shí)符和名字的敘述中，正確的為 D 。 A、標(biāo)識(shí)符有一定的含義 B、名字是一個(gè)沒(méi)有意義的字符序列 C、名字有確切的屬性 D、都不對(duì)4.文法GA：A AaB BAb Ba是 B 。 A、正規(guī)文法 B、二型文法5. 返填技術(shù)指的是 A 。 A、生成跳轉(zhuǎn)、調(diào)用等指令時(shí)，不能獲得轉(zhuǎn)向地址，需要等到獲得該轉(zhuǎn)向地址后再回來(lái)填寫(xiě)。 4 / 45如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!B、符號(hào)表中過(guò)程或函數(shù)標(biāo)識(shí)符的地址部分要填上入口地址，在掃描到過(guò)程或函數(shù)標(biāo)識(shí)符的說(shuō)明時(shí)這些地址是無(wú)法知道的，只有等到開(kāi)始生成過(guò)程或函數(shù)的指令部分時(shí)才能填入。 C、A和B D、都不確切1. 一般程序設(shè)計(jì)語(yǔ)

11、言的定義都涉及 B 三個(gè)方面。語(yǔ)法 語(yǔ)義 語(yǔ)用 程序基本符號(hào)的確定A、 B、 C、 D、 2. 下面說(shuō)法正確的是 B 。 A、一個(gè)正規(guī)式只能對(duì)應(yīng)一個(gè)確定的有限狀態(tài)自動(dòng)機(jī)； B、一個(gè)正規(guī)語(yǔ)言可能對(duì)應(yīng)多個(gè)正規(guī)文法；3. 程序基本塊是指 D 。 A、一個(gè)子程序 B、一個(gè)僅有一個(gè)入口和一個(gè)出口的語(yǔ)句 C、一個(gè)沒(méi)有嵌套的程序段 D、一組順序執(zhí)行的程序段，僅有一個(gè)入口和一個(gè)出口。4. 詞法分析的常用方法有 A 。 A、有窮自動(dòng)機(jī)理論 B、圖靈機(jī) C、圖論 D、無(wú)窮自動(dòng)機(jī)理論5. 編譯方法中自頂向下的語(yǔ)法分析算法有 D 。簡(jiǎn)單優(yōu)先分析方法算符優(yōu)先分析方法 遞歸子程序法 LL(K)分析法 SLR分析法 LR(

12、K)方法LALR(K)方法 預(yù)測(cè)分析方法A、 B、 C、 D、 E、二、填空題 （15分）1. 編譯程序必須完成的工作有 A 。詞法分析 語(yǔ)法分析 語(yǔ)義分析 代碼生成 中間代碼生成 代碼優(yōu)化A、 B、 C、 D、 E、2. 語(yǔ)法分析的常用方法有 D 。 A、自頂向下匹配 B、自底向上歸約 C、回溯法 D、自頂向下匹配和自底向上歸約3. 在編譯程序采用的優(yōu)化方法中， C 是在循環(huán)語(yǔ)句范圍內(nèi)進(jìn)行的。（1）合并已知常量（2）刪除多余運(yùn)算（3）刪除歸納變量（4）強(qiáng)度削弱（5）代碼外提 A、（1）（4） B、（1）（5） C、（1）（4）（5） D、（3）（4）（5）4. 過(guò)程調(diào)用時(shí)，參數(shù)的傳遞方法通常

13、有 D 。（1）傳值（2）傳地址（3）傳結(jié)果（4）傳名 A、（1）（2） B、（1）（2）（3） C、（1）（2）（4） D、（1）（2）（3）（4）5. 編譯方法中自底向上的語(yǔ)法分析算法有 C 。簡(jiǎn)單優(yōu)先分析方法算符優(yōu)先分析方法 遞歸子程序法 LL(K)分析法 SLR分析法 LR(K)方法 LALR(K)方法 預(yù)測(cè)分析方法A、 B、 C、 D、 E、1. 文法G所描述的語(yǔ)言是 D 集合。A、 文法G的字匯表V中所有符號(hào)組成的符號(hào)串B、 文法G的字匯表V的閉包V*中的所有符號(hào)串C、 由文法的識(shí)別符號(hào)推出的所有符號(hào)串D、 由文法的識(shí)別符號(hào)推出的所有終結(jié)符號(hào)串2. 下面說(shuō)法正確的是 B 。 A、一

14、個(gè)正規(guī)式只能對(duì)應(yīng)一個(gè)確定的有限狀態(tài)自動(dòng)機(jī)； B、一個(gè)正規(guī)語(yǔ)言可能對(duì)應(yīng)多個(gè)正規(guī)文法；3. 代碼生成應(yīng)著重考慮的問(wèn)題是 B 。4 / 45如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載! 每一個(gè)語(yǔ)法成分的語(yǔ)義目標(biāo)程序運(yùn)行所占用的空間目標(biāo)程序的運(yùn)行速度目標(biāo)代碼中需要那些信息，怎樣截取這些信息A、 B、 C、 D、 4.編譯程序在優(yōu)化時(shí)， B 用到源程序中的注釋。A、可能要 B、不可能5. 下面說(shuō)法正確的是 A 。 A、 一個(gè)正規(guī)文法也一定是二型文法B、一個(gè)二型文法也一定能有一個(gè)等價(jià)的正規(guī)文法1. 文法的二義性和語(yǔ)言的二義性是兩個(gè) A 的概念。 A、不同 B、相同 C、不一定2. 下面說(shuō)法正確的是 B 。

15、A、一個(gè)正規(guī)式只能對(duì)應(yīng)一個(gè)確定的有限狀態(tài)自動(dòng)機(jī)； B、一個(gè)正規(guī)語(yǔ)言可能對(duì)應(yīng)多個(gè)正規(guī)文法；3. LR語(yǔ)法分析棧中存放的狀態(tài)是識(shí)別的 B DFA狀態(tài)。A、前綴 B、可歸前綴 C、項(xiàng)目 D、句柄4. 正規(guī)文法 A 二義性的。A、可以是B、一定不是C、一定是5. 高級(jí)語(yǔ)言編譯程序常用的語(yǔ)法分析方法中，遞歸下降分析法屬于 B 分析方法。 A、 自左向右 B、自頂向下 C、自底向上 D、自右向左1. 一個(gè)語(yǔ)言的文法是 B 。A、唯一的B、不唯一的C、個(gè)數(shù)有限的2. 代碼生成應(yīng)著重考慮的問(wèn)題是 D 。 每一個(gè)語(yǔ)法成分的語(yǔ)義目標(biāo)程序運(yùn)行所站用的空間目標(biāo)程序的運(yùn)行速度目標(biāo)代碼中需要那些信息，這樣截取這些信息。

16、A、 B、 C、 D、3. 運(yùn)行階段的存儲(chǔ)組織與管理的目的是 C 。 提高編譯程序的運(yùn)行速度。 提高目標(biāo)程序的運(yùn)行速度。 為運(yùn)行階段的存儲(chǔ)分配做準(zhǔn)備。 A、 B、 C、 D、 4. 編譯過(guò)程中，比較常見(jiàn)的中間語(yǔ)言有 D 。 波蘭表示逆波蘭表示三元式四元式樹(shù)形表示 A、B、C、 D、5. 過(guò)程信息表中至少應(yīng)該包括有 D 。 過(guò)程名過(guò)程的靜態(tài)層次過(guò)程的入口地址過(guò)程首部在源程序中的行號(hào)有關(guān)過(guò)程的參數(shù)信息。 A、 B、 C、 D、二、填空題 （15分）1.如果在一個(gè)文法中存在某個(gè)句子，它有二個(gè)以上的最左（最右）推導(dǎo)，也就是說(shuō)，若該句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù) ，則這個(gè)文法是二義性文法。 2. 假設(shè)G是一個(gè)

17、文法，S是文法的開(kāi)始符號(hào)，如果S * x，則稱x是 句型 。（2分）3.LR(K)分析法中， L的含義是自左向右進(jìn)行分析，R含義是采用最右推導(dǎo)的逆過(guò)程最左歸約，“K”的含義是至多向前查看K個(gè)輸入符號(hào)。4.自頂向下語(yǔ)法分析方法會(huì)遇到的主要問(wèn)題有 左遞歸 和 回溯 。5.編譯過(guò)程中，常見(jiàn)的中間語(yǔ)言形式有三元式、 逆波蘭式 和四元式。5 / 45如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!6.在編譯程序中安排中間代碼生成的目的是便于代碼優(yōu)化和便于目標(biāo)程序的移植。1.程序的翻譯方式有兩種，分別是_編譯方式_和_解釋方式_。 2.字的前綴是指該字的 任意首部 。（2分）3.LR(1)分析法中，L的含義是自

18、左向右進(jìn)行分析，R含義是采用最右推導(dǎo)的逆過(guò)程-最左歸約，“1”的含義是向貌似句柄的符號(hào)串后查看一個(gè)輸入符號(hào)。4.編譯過(guò)程中，常見(jiàn)的中間語(yǔ)言形式有 三元式 、逆波蘭式和四元式 。5.程序的可再入性指的是：當(dāng)程序在執(zhí)行時(shí)，可以_隨時(shí)中斷_它的執(zhí)行，也可隨時(shí)_執(zhí)行進(jìn)程_恢復(fù)其原來(lái)的_執(zhí)行進(jìn)程_；而且可以在_中斷時(shí)間里_，又從該程序的_頭上 開(kāi)始一個(gè)新的執(zhí)行過(guò)程。1.編譯程序與具體的機(jī)器 無(wú)關(guān) ，與具體的語(yǔ)言 有關(guān) 。2.SLR(1)分析法中，L的含義是 自左向右進(jìn)行分析 ，R含義是 采用最右推導(dǎo)的逆過(guò)程 ，S含義是 簡(jiǎn)單的 ，“1”的含義是 向貌似句柄的符號(hào)串的查看一個(gè)輸入符號(hào) 。4.確定的有窮自動(dòng)

19、機(jī)是一個(gè) 五元組 ，通常表示為 M（Q，t,q0,F） 。5.在大部分現(xiàn)有編譯中采用的方案主要有兩種： 動(dòng)態(tài) 分配方案和_靜態(tài)_分配方案。6.假定G是一個(gè)文法，S是它的 開(kāi)始符號(hào) ，如果S * ，則稱_是一個(gè)句型，僅含終結(jié)符號(hào)的句型是一個(gè) 句子 。文法G所產(chǎn)生的 句子的全體是一個(gè) 語(yǔ)言 ，將它記為L(zhǎng)(G)。1. 如果在一個(gè)文法中存在某個(gè)句子，它有 二個(gè)以上 得最左（最右）推導(dǎo)，也就是說(shuō)，若該句子對(duì)應(yīng)兩棵不同的 語(yǔ)法樹(shù) ，則這個(gè)文法是 二義性 文法。 2. 對(duì)編譯程序而言，輸入數(shù)據(jù)是源程序，輸出結(jié)果是 目標(biāo)程序 。3. LR(1)分析法中，L的含義是 自左向右進(jìn)行分析 ，R含義是采用最右推導(dǎo)的逆

20、過(guò)程最左歸約，“1”的含義是 至多向前查看一個(gè)輸入符號(hào)。4. 語(yǔ)法分析是依據(jù)語(yǔ)言的語(yǔ)法 規(guī)則進(jìn)行的，中間代碼產(chǎn)生是依據(jù)語(yǔ)言的語(yǔ)義 規(guī)則進(jìn)行的。5. 編譯過(guò)程中，常見(jiàn)的中間語(yǔ)言形式有 三元式 、逆波蘭式和 四元式 。6. 編譯過(guò)程中掃描器所完成的任務(wù)是從 源程序 中識(shí)別出一個(gè)一個(gè)具有獨(dú)立 語(yǔ)法意義的單詞 。1. 如果在一個(gè)文法中存在某個(gè)句子，它有 二個(gè)以上 得最左（最右）推導(dǎo)，也就是說(shuō)，若該句子對(duì)應(yīng)兩棵不同的 語(yǔ)法樹(shù) ，則這個(gè)文法是 二義性 文法。 2. 編譯方式與解釋方式的根本區(qū)別在于 是否生成目標(biāo)代碼 。（2分）3. LL(1)分析法中，第一個(gè)L的含義是 從左往右 ，第二個(gè)L含義是 每次進(jìn)行

21、最左推導(dǎo)，“1”的含義是 向輸入串中查看一個(gè)輸入符號(hào) 。4. 自頂向下語(yǔ)法分析方法會(huì)遇到的主要問(wèn)題有左遞歸和回溯。5. 符號(hào)表的數(shù)據(jù)結(jié)構(gòu)可以是 線性符號(hào)表、 樹(shù)結(jié)構(gòu) 、 散列表。6. 一個(gè)字集是正規(guī)的，當(dāng)且僅當(dāng)它可由 DFA（NFA） 所識(shí)別。1. 假定G是一個(gè)文法，S是它的 開(kāi)始符號(hào) ，如果S * ，則稱 是一個(gè)句型，僅含終結(jié)符號(hào)的句型是一個(gè) 句子 。文法G所產(chǎn)生的 句子 的全體是一個(gè) 語(yǔ)言 ，將它記為L(zhǎng)(G)。 2. 喬姆斯基定義的四種形式語(yǔ)言文法分別為： 0型 文法（又稱 短語(yǔ)結(jié)構(gòu) 文法）、 1型 文法（又稱 上下文有關(guān)文法）、 2型 文法（又稱 上下文無(wú)關(guān) 文法）、 3型 文法（又稱

22、正則文法）。3. 自頂向下 語(yǔ)法分析方法的基本思想是：從 識(shí)別符號(hào) 出發(fā)，利用文法的規(guī)則不斷建立 直接推導(dǎo)推導(dǎo)，試圖構(gòu)造一個(gè)推導(dǎo)序列，最終由它推導(dǎo)出與輸入符號(hào)串 相同的符號(hào)串。1.編譯程序的工作過(guò)程一般可以劃分為_(kāi)詞法分析_、_語(yǔ)法分析_、_語(yǔ)義分析、_中間代碼生成、_代碼優(yōu)化_等幾個(gè)基本階段，同時(shí)還會(huì)伴有 表格處理 和 出錯(cuò)處理 。 6 / 45如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!2.文法G產(chǎn)生的 所有句子 的全體是該文法描述的語(yǔ)言。3.來(lái)自中間代碼的代碼生成涉及了兩個(gè)標(biāo)準(zhǔn)技術(shù)：宏擴(kuò)展和靜態(tài)模擬。_宏擴(kuò)展_涉及到用一系列等效 的目標(biāo)代碼指令代替每一種中間代碼指令。4.為文法的每一個(gè)規(guī)則

23、配備的計(jì)算屬性的計(jì)算規(guī)則，稱為 語(yǔ)義規(guī)則。1.中間代碼有逆波蘭式 、 三元式樣 、 四元式、 樹(shù)形表示 等形式，生成中間代碼主要是為了使 代碼優(yōu)化及目標(biāo)程序便于移植 。（6分）。 2. 文法G產(chǎn)生的 句子 的全體是該文法描述的語(yǔ)言（2分）。3. 在一個(gè)基本塊內(nèi)，可實(shí)行3種優(yōu)化方法，即合并已知量、刪除無(wú)用賦值 、刪除多余運(yùn)算。4. 確定的有窮自動(dòng)機(jī)是一個(gè)五元組 ，通常表示為 M（Q，t,q0,F） 。5. 活前綴是指規(guī)范句型的一個(gè)前綴，這種前綴不含句柄之后的任何符號(hào)。1. 編譯程序的工作過(guò)程一般可以劃分為詞法分析_、_語(yǔ)法分析_、_語(yǔ)義分析、_中間代碼生成、_代碼優(yōu)化_等幾個(gè)基本階段，同時(shí)還會(huì)伴

24、有表格處理 和 出錯(cuò)處理（6分）。 2. 在目標(biāo)代碼生成階段，符號(hào)表是 地址分配 的依據(jù)。（2分）。3. 符號(hào)表的數(shù)據(jù)結(jié)構(gòu)可以是無(wú)序符號(hào)表、有序符號(hào)表 、棧式符號(hào)表 。4. 詞法分析階段的錯(cuò)誤主要是 單詞拼寫(xiě)錯(cuò)誤 ，可通過(guò)最小距離匹配的辦法糾正錯(cuò)誤。5. 在大部分現(xiàn)有編譯中采用的方案主要有兩種： 動(dòng)態(tài) 分配方案和 靜態(tài) 分配方案。1. 編譯程序工作過(guò)程中，第一段輸入是 源程序 ，最后階段的輸出為 目標(biāo) 程序。2.若二個(gè)正規(guī)式所表示的正規(guī)集相同，則認(rèn)為二者是等價(jià)的（2分）。 3. 符號(hào)表中名字的有關(guān)信息在 詞法分析 和 語(yǔ)法語(yǔ)義分析 過(guò)程中陸續(xù)填入。4. 自頂向下 語(yǔ)法分析方法的基本思想是：從

25、識(shí)別符號(hào) 出發(fā)，利用文法的規(guī)則不斷建立 直接 推導(dǎo)，試圖構(gòu)造一個(gè)推導(dǎo)序列，最終由它推導(dǎo)出與輸入符號(hào)串 的符號(hào)串。5. 堆式動(dòng)態(tài)分配策略允許用戶動(dòng)態(tài)的 申請(qǐng) 和 釋放 存儲(chǔ)空間存儲(chǔ)。6. 語(yǔ)法樹(shù)代表推導(dǎo)過(guò)程，分析樹(shù)代表歸約過(guò)程。7.在優(yōu)化中，可把循環(huán)中的不變運(yùn)算提到循環(huán)外面去，這種方法稱為 代碼外提。1 最左推導(dǎo)是指每次都對(duì)句型中的 最左 非終結(jié)符進(jìn)行擴(kuò)展。2. 確定有限自動(dòng)機(jī)DFA是 NFA 的一個(gè)特例。（2分）。3. 自頂向下語(yǔ)法分析方法的基本思想是：從 識(shí)別符號(hào)出發(fā)，利用文法的規(guī)則不斷建立 直接推導(dǎo)，試圖構(gòu)造一個(gè)推導(dǎo)序列，最終由它推導(dǎo)出與輸入符號(hào)串 的符號(hào)串。4. 確定的有窮自動(dòng)機(jī)是一個(gè)

26、五元組 ，通常表示為 M（Q，t,q0,F） 。5. 一個(gè)字集是正規(guī)的，當(dāng)且僅當(dāng)它可由 DFA（NFA） 所識(shí)別。6.文法中的終結(jié)符和非終結(jié)符的交集是空集 。詞法分析器交給語(yǔ)法分析器的文法符號(hào)一定是終結(jié)符 ，它一定只出現(xiàn)在產(chǎn)生式的右 部。7 目標(biāo)程序運(yùn)行的動(dòng)態(tài)分配策略中，含有棧式 和 堆式分配策略。1.自底向上語(yǔ)法分析方法的基本思想是：從待輸入的符號(hào)串開(kāi)始，利用文法的規(guī)則步步向上進(jìn)行 歸約 ，試圖 歸約 到文法的 識(shí)別符號(hào) 。2. 若源程序使用高級(jí)語(yǔ)言編寫(xiě)的，目標(biāo)程序是 機(jī)器語(yǔ)言程序 ，則其翻譯程序稱為編譯程序（2分）。 2. 編譯程序是指將 源程序 程序翻譯成 目標(biāo) 程序的程序。3. 自頂向

27、下 語(yǔ)法分析方法的基本思想是：從 識(shí)別符號(hào) 出發(fā)，利用文法的規(guī)則不斷建立直接推導(dǎo)推導(dǎo)，試圖構(gòu)造一個(gè)推導(dǎo)序列，最終由它推導(dǎo)出與輸入符號(hào)串 的符號(hào)串。4. 編譯過(guò)程通?？煞譃?個(gè)階段，分別是 詞法分析 、語(yǔ)法分析、 語(yǔ)義分析 、代碼優(yōu)化和目標(biāo)代碼生成。5. 優(yōu)化就是對(duì)程序進(jìn)行各種等價(jià)變換，使之能生成更有效的目標(biāo)代碼。1. 自下而上分析法采用 移進(jìn) 、歸約、錯(cuò)誤處理、 接受 等四種操作。 2. 采用 自上而下 語(yǔ)法分析時(shí)，必須消除文法的左遞歸（2分）。3. 已知文法GE：ETE+TE-TTFT*FT/FF(E)i該文法的開(kāi)始符號(hào)是 E ，終結(jié)符號(hào)集合VT是 +、-、*、/、(、)、i ，非終結(jié)符號(hào)集

28、合V8 / 45如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!N是 E、T、F。4. 掃描器 的任務(wù)是從左到右一個(gè)一個(gè)地對(duì)源程序進(jìn)行掃描，產(chǎn)生一個(gè)一個(gè)的 具有獨(dú)立語(yǔ)法意義的單詞 。5. 優(yōu)化就是對(duì)程序進(jìn)行各種 等價(jià) 變換，使之能生成更有效的 目標(biāo)代碼 。6. A稱為歸約 項(xiàng)目；對(duì)文法開(kāi)始符S為接受項(xiàng)目；若a為終結(jié)符，則稱Aa為 移進(jìn) 項(xiàng)目；若B為非終結(jié)符，則稱Aa為待約 項(xiàng)目。三、簡(jiǎn)答題。（30分） 1.什么是算符優(yōu)先文法？給出一個(gè)非教材上提供的算符優(yōu)先文法的例子，并給出算符優(yōu)先表？（6分）設(shè)文法G，如果它的產(chǎn)生式右部不包含相鄰非終結(jié)符號(hào)，則稱文法G為算符文法，如果算符文法的終結(jié)符號(hào)集中任意兩個(gè)符

29、號(hào)之間至多存在一種優(yōu)先關(guān)系，則稱該算符文法為算符優(yōu)先文法。例如：E-E+T|TT-T*F|FF-(E)|i+*()i+(=i2.設(shè)有文法GS：Sa|(T)TT,S|S請(qǐng)給出句子(a,(a,a)的最左和最右推導(dǎo)，給出該句子的短語(yǔ)和句柄。（7分）最左推導(dǎo)：S=(T) =(T,S) =(a,S)=(a,(T,S) =(a,(S,S)=(a,(a,S)=(a,(a,a)最右推導(dǎo)：S=(T)=(T,S)=(T,(T)=(T,(T,S) =(T,(T,a)=(T,(S,a)=(T,(a,a) =(S,(a,a)=(a,(a,a)3. 編譯程序的實(shí)現(xiàn)應(yīng)考慮的問(wèn)題有那些？（4分）編譯程序的實(shí)現(xiàn) 應(yīng)考慮：開(kāi)發(fā)周

30、期、目標(biāo)程序的效率、可移植性、可調(diào)試性、可維護(hù)性、可擴(kuò)充性等。4.什么是二義性文法？請(qǐng)用例說(shuō)明文法GE：Ei|(E)|EAE A+|-|*|/是二義性文法。（6分）一個(gè)文法如果它的一個(gè)句子有兩棵或兩棵以上的語(yǔ)法樹(shù)，則稱該句子具有二義性，如果一個(gè)文法含有二義性的句子，則該文法是二義性文法。如句子：i+i+i5.在編譯過(guò)程中為什么要建立符號(hào)表？簡(jiǎn)述符號(hào)表的組織，即它一般分成幾部分，含有那些域？（6分）8 / 45如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!在編譯過(guò)程中，始終涉及到對(duì)一些語(yǔ)法符號(hào)的處理，需要用到這些語(yǔ)法符號(hào)的相關(guān)屬性。為了在需要的時(shí)候能找到這些語(yǔ)法成分及其相關(guān)屬性，必須使用一些表格保存

31、這些語(yǔ)法成分及其屬性，這些表格就是符號(hào)表。符號(hào)表應(yīng)包括語(yǔ)法符號(hào)的名字和相關(guān)屬性，不同語(yǔ)法符號(hào)在符號(hào)表中存放的信息不同。符號(hào)表的條目一般由兩部分組成，即名字欄和信息欄。符號(hào)表域包括標(biāo)識(shí)符名、其他信息、地址等。對(duì)名字欄，為節(jié)省空間，可另外設(shè)立一個(gè)存放標(biāo)識(shí)符的字符數(shù)組。對(duì)信息欄中的類型等信息可以用數(shù)值或向量來(lái)表示，以節(jié)省空間1. .設(shè)有文法GE： ET|ET TF|T * F F(E)|i 請(qǐng)給出句型(T * Fi)的最右推導(dǎo)及畫(huà)出語(yǔ)法樹(shù)。（5分）最右推導(dǎo)： ETF(E) (ET) (EF) (Ei)(Ti) (T*Fi)ETF( E ) E + T F i T T * F 2.對(duì)于上題，消除左遞歸

32、和回溯，給出遞歸下降算法。（6分）3.對(duì)于第1小題，給出句型(T * Fi)的短語(yǔ)、簡(jiǎn)單短語(yǔ)及句柄。（5分）短語(yǔ)：(T*Fi)，T*Fi，T*F，i素短語(yǔ)：T*F,i4. 適合采用靜態(tài)存儲(chǔ)分配的程序設(shè)計(jì)語(yǔ)言應(yīng)有哪些限制？（6分）數(shù)據(jù)實(shí)體所需空間在編譯時(shí)能確定運(yùn)行時(shí)每個(gè)數(shù)據(jù)對(duì)象只能有一個(gè)實(shí)例數(shù)組的上下界是常量過(guò)程調(diào)用不允許遞歸不能動(dòng)態(tài)建立數(shù)據(jù)實(shí)體5.分離連表法是如何解決沖突的？如雜湊表的尺寸是5，有4個(gè)變量，x，y，temp，z，其中y和temp的雜湊值相等，請(qǐng)給出分離鏈接的雜湊表。（8）1.設(shè)有文法GS：SaAcB|BdAAaB|cBbScA|b請(qǐng)給出句子acabcbbdcc的最左推導(dǎo)及語(yǔ)法樹(shù)

33、。（6分）s-aAcB-aAaBcB-aCaBcB-acabcB-acabcbScA-acabcbBCCA-acabcbbdcc 2.判斷上題是否是算符優(yōu)先文法？如是，請(qǐng)給出算符優(yōu)先關(guān)系表。（7分）9 / 45如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!是算符優(yōu)先關(guān)系。因?yàn)楫a(chǎn)生式右部不包含相鄰非終結(jié)符號(hào)firstvt(s)=a,b,d lastvt(s)=a,b,c,dfirstvt(s)=a,c lastvt(s)=a,b,cfirstvt(s)=b lastvt(s)=a,b,cabcdab=cd3.對(duì)于第1小題給定的文法，句型aAaBScAcB的短語(yǔ)、簡(jiǎn)單短語(yǔ)及句柄是什么？（6分）S a

34、A C B A a B b s c A短語(yǔ)：bScA AabScA aAabScAcB簡(jiǎn)單短語(yǔ)：bScA句柄：bScA4.什么是二義性文法？請(qǐng)用例說(shuō)明文法GE：Ei | (E) | EAE A + | - | * | /是二義性文法。（6分）一個(gè)文法如果它的一個(gè)句子有兩棵或兩棵以上的語(yǔ)法樹(shù)，則稱此句子具有二義性，如果一個(gè)文法含有二義性的句子，則稱此文法具有二義性。例： i+i+i5.符號(hào)表的作用是什么？一般有哪幾種結(jié)構(gòu)？（5分）在編譯過(guò)程中，始終涉及對(duì)一些語(yǔ)法符號(hào)的處理。要用到這些符號(hào)的相關(guān)屬性。符號(hào)表的作用就是保存這些成份及其相關(guān)屬性，以便在用時(shí)能找到。無(wú)序符號(hào)表有序符號(hào)表?xiàng)７?hào)表1、簡(jiǎn)述自

35、頂向下分析法。從識(shí)別符號(hào)出發(fā)，不斷建立直接推導(dǎo)，試圖構(gòu)造一個(gè)推導(dǎo)序列，最終由它推導(dǎo)出與輸入符號(hào)串相同的符號(hào)串。從語(yǔ)法樹(shù)的角度看，自頂向下分析過(guò)程是以識(shí)別符號(hào)為根結(jié)點(diǎn)，試圖向下構(gòu)造一棵語(yǔ)法樹(shù)，使其末端結(jié)點(diǎn)符號(hào)串正好與輸入符號(hào)串相同。2、設(shè)有文法GA的產(chǎn)生式集為: ABaC|CbB BAc|c CBb|b 試消除GA的左遞歸。 提示：不妨以A、B、C排序.先將A代入B中，然后消除B中左遞歸；再將A、B代入C中。再消除C中左遞歸。 最后結(jié)果為:GA: ABaC|CbB BCbBcB|cB BaCcB| CcBbC|bC CbBcBbC|3、寫(xiě)出表達(dá)式a+b*(c-d)+e/(c-d)*n的三元式序列

36、或P代碼表示。(1)（_,c,d） (2) (*,b,(1) (3) (+,a,(2) (4) (_,c,d)(5) (/,e,(4) (6) (*,n,(5) (7)(+,(3),(6)4、什么樣的文法是算符優(yōu)先文法，請(qǐng)舉個(gè)算符優(yōu)先文法的例子。設(shè)文法G，如果它的產(chǎn)生式右部不包含相鄰非終結(jié)符號(hào)，則稱文法G為算符文法，如果算符文法的終結(jié)符號(hào)集中任意兩個(gè)符號(hào)之間至多存在一種優(yōu)先關(guān)系，則稱該算符文法為算符優(yōu)先文法。例如：E-E+T|TT-T*F|F F-(E)|i+*()i+(=10 / 45如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!i5、解釋什么是歸約？我們稱直接歸約出A，僅當(dāng)A 是一個(gè)產(chǎn)生式，

37、且、(VNVT)*。歸約過(guò)程就是從輸入串開(kāi)始，反復(fù)用產(chǎn)生式右部的符號(hào)替換成產(chǎn)生式左部符號(hào)，直至文法開(kāi)始符。1、DFA和NFA有何區(qū)別？DFA和NFA的區(qū)別表現(xiàn)在三個(gè)方面。一是NFA可有若干個(gè)開(kāi)始狀態(tài)，而DFA僅有一個(gè)。二是DFA的映像M是從K到K，而的映象M是從K到K的子集，即映像M將產(chǎn)生一個(gè)狀態(tài)集合（可能為空集），而不單個(gè)狀態(tài)。三是NFA在沒(méi)有掃描輸入符號(hào)的情況下，也可以進(jìn)行空移。2、已知文法G為：S aAcB|BdA AaB|cB bScA|b寫(xiě)出句子acabcbbdcc得最左推導(dǎo)及語(yǔ)法樹(shù)s-aAcB-aAaBcB-aCaBcB-acabcB-acabcbScA-acabcbBCCA-ac

38、abcbbdcc Sa A c B A a B b S c A C b B d b3、寫(xiě)出表達(dá)式A=（x+y）*（c+d）+（x+y+c）的四元式序列或P代碼表示。11 / 45如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!(1)（+,x,y）(2) (+,c,d)(3) (*,(1),(2)(4) (+,x,y)(5) (+,(4),c)(6) (+,(3),(5)1、語(yǔ)法分析的主要（功能）任務(wù)是什么？有哪二種分析分方法？語(yǔ)法分析的主要任務(wù)是對(duì)詞法分析的輸出結(jié)果-單詞序列進(jìn)行分析，識(shí)別合法的 語(yǔ)法單位。若給定的輸入符號(hào)是該文法所產(chǎn)生的語(yǔ)言中的句子，就給出它的語(yǔ)法樹(shù)，否則就報(bào)告出錯(cuò)信息。自上而下語(yǔ)

39、法分析和自下而上語(yǔ)法分析。2、令文法G為Sa|(T)TT,S|S（1）給出(a,(a,a)的最右推導(dǎo)和最左推導(dǎo)。（2）畫(huà)出語(yǔ)法分析樹(shù)最左推導(dǎo)：S=(T) =(T,S) =(a,S)=(a,(T,S) =(a,(S,S)=(a,(a,S)=(a,(a,a)最右推導(dǎo)：S=(T)=(T,S)=(T,(T)=(T,(T,S) =(T,(T,a)=(T,(S,a)=(T,(a,a) =(S,(a,a)=(a,(a,a)3、寫(xiě)出表達(dá)式A=（a+b）+（c+d）*（x+y+c）的三元式序列或P代碼表示。15 / 41如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!(1)（+,a,b）(2) (+,c,d)15 /

40、 41如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!(3) (+,x,y)(4) (+,(3),c)(5) (*,(2),(4)(6) (+,(1),(5)14 / 45如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!4、什么是二義性文法？請(qǐng)舉例說(shuō)明。一個(gè)文法如果它的一個(gè)句子有兩棵或兩棵以上的語(yǔ)法樹(shù)，則稱此句子具有二義性，如果一個(gè)文法含有二義性的句子，則稱此文法具有二義性。例： Ei | (E) | EAE A + | - | * | /i+i+iEEE A EE A EEA E t I i t E A Ei t i i t i5、在一個(gè)基本塊內(nèi)通?？蓪?shí)現(xiàn)哪些優(yōu)化？合并已知量 刪除公共子表達(dá)式 刪除無(wú)用

41、代碼 復(fù)寫(xiě)傳播15 / 41如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!4、什么是語(yǔ)法樹(shù)?滿足下面4個(gè)條件的樹(shù)稱之為文法GS的一棵語(yǔ)法樹(shù)。每一終結(jié)均有一標(biāo)記，此標(biāo)記為VNVT中的一個(gè)符號(hào)；樹(shù)的根結(jié)點(diǎn)以文法GS的開(kāi)始符S標(biāo)記；若一結(jié)點(diǎn)至少有一個(gè)直接后繼，則此結(jié)點(diǎn)上的標(biāo)記為VN中的一個(gè)符號(hào)；若一個(gè)以A為標(biāo)記的結(jié)點(diǎn)有K個(gè)直接后繼，且按從左至右的順序，這些結(jié)點(diǎn)的標(biāo)記分別為X1,X2,Xk，則AX1,X2,Xk， 必然是G的一個(gè)產(chǎn)生式。5、在編譯過(guò)程中為什么要建立符號(hào)表，簡(jiǎn)述符號(hào)表的組織，即它一般分成幾部分，含有那些域？在編譯過(guò)程中，始終涉及到對(duì)一些語(yǔ)法符號(hào)的處理，需要用到這些語(yǔ)法符號(hào)的相關(guān)屬性。為了在需

42、要的時(shí)候能找到這些語(yǔ)法成分及其相關(guān)屬性，必須使用一些表格保存這些語(yǔ)法成分及其屬性，這些表格就是符號(hào)表。符號(hào)表應(yīng)包括語(yǔ)法符號(hào)的名字和相關(guān)屬性，不同語(yǔ)法符號(hào)在符號(hào)表中存放的信息不同。符號(hào)表的條目一般由兩部分組成，即名字欄和信息欄。符號(hào)表域包括標(biāo)識(shí)符名、其他信息、地址等。對(duì)名字欄，為節(jié)省空間，可另外設(shè)立一個(gè)存放標(biāo)識(shí)符的字符數(shù)組。對(duì)信息欄中的類型等信息可以用數(shù)值或向量來(lái)表示，以節(jié)省空間1. 對(duì)如下文法：GS：SabS|aaB|adBbbB|b分別給出句子abaabbb和ad的句柄（6分）句子abaabbb的句柄是b；句子ad的句柄是ad2. 什么是可規(guī)約活前綴？舉一例說(shuō)明。（6分）若活前綴是含句柄的活

43、前綴，即有 = ,且是句柄，則活前綴為可歸約活前綴。例S a|bCdC e則be為一個(gè)可歸約活前綴3.寫(xiě)出表達(dá)式(ab*c)/(ab)d的逆波蘭表示及三元式序列或P代碼。（6分）16 / 45如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!(1)（*,b,c）(2) (+,a,(1)(3) (+,a,b)(4) (/,(2),(3)(5) (-,(4),d)15 / 41如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!4.詞法分析和語(yǔ)法分析都是對(duì)字符串進(jìn)行識(shí)別，二者有何區(qū)別？（4分）在詞法分析和語(yǔ)法分析中，都是對(duì)輸入符號(hào)串進(jìn)行識(shí)別。但詞法分析的輸入符號(hào)串是一個(gè)單詞，而語(yǔ)法分析的輸入符號(hào)串是一個(gè)句子或者說(shuō)是

44、一個(gè)程序。為了討論方便，我們都是用小寫(xiě)字母來(lái)表示終結(jié)符號(hào)，但一定要明白在詞法分析中小寫(xiě)字母表示組成單詞的字符，而在語(yǔ)法分析中小寫(xiě)字母表示組成程序的的一個(gè)單詞，識(shí)別方式來(lái)說(shuō)，詞法分析和語(yǔ)法分析都是對(duì)輸入符號(hào)串結(jié)構(gòu)的識(shí)別，但由于單詞和程序的結(jié)構(gòu)有所區(qū)別，所以具體的識(shí)別方式不一樣。5.已知文法GS為：Sa|(T) TT,S|S判斷該文法是否是算符優(yōu)先文法？如是，請(qǐng)給出算符優(yōu)先關(guān)系表。（8分）(1) FIRSTVT和LASTVT FIRSTVT LASTVT S a、（ a、） T ，、a、（ ，、a、) (2) 算符優(yōu)先關(guān)系 a ( ) , # a ( ) , # 1、計(jì)算機(jī)執(zhí)行用高級(jí)語(yǔ)言編寫(xiě)的程序

45、有那些途徑？它們之間的主要區(qū)別是什么？計(jì)算機(jī)執(zhí)行用于高級(jí)語(yǔ)言編寫(xiě)的程序主要有兩種途徑：解釋和編譯。在解釋方式下，翻譯程序并不對(duì)高級(jí)語(yǔ)言進(jìn)行徹底的翻譯，而是讀入一條語(yǔ)句，就解釋其含義并執(zhí)行，然后再讀入下一條語(yǔ)句，再執(zhí)行。在編譯方式下，翻譯程序先對(duì)高級(jí)語(yǔ)言進(jìn)行徹底的翻譯并生成目標(biāo)代碼，然后再對(duì)目標(biāo)代碼進(jìn)行優(yōu)化，即對(duì)源程序的處理是先翻譯后執(zhí)行。從速度上看，編譯方式下，源程序的執(zhí)行比解釋方式下快，但在解釋方式下，有利于程序的調(diào)試。2、編譯程序的實(shí)現(xiàn)途徑有那些？ 編譯程序的實(shí)現(xiàn)途徑可有：- 手工構(gòu)造：用機(jī)器語(yǔ)言、匯編語(yǔ)言或高級(jí)程序設(shè)計(jì)語(yǔ)言書(shū)寫(xiě)。- 自動(dòng)構(gòu)造工具：Lex,Yacc。 Lex ,Yacc分別

46、是詞法和語(yǔ)法分析器的生成器。 - 移植方式：目標(biāo)程序用中間語(yǔ)言 - 自展方式：用T型圖表示 3、文法GE為： EE+T|T TT*F|F F(E)|i 試給出句型(E+F)*i的短語(yǔ)，簡(jiǎn)單(直接)短語(yǔ),句柄和最左素短語(yǔ)。短語(yǔ)有: (E+F)*i ，(E+F) ，E+F ，F(xiàn) ，i 簡(jiǎn)單(直接)短語(yǔ)有: F ，i 句柄是: F 最左素短語(yǔ)是: E+F4、有人認(rèn)為：“1型文法對(duì)規(guī)則的限制比2型文法對(duì)規(guī)則的限制要多一些”，這種說(shuō)法對(duì)嗎？文法是嚴(yán)格按照規(guī)則的形式來(lái)分類的1型文法的規(guī)則是：xUy-xuy uVn uV+ x,yV*18 / 45如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!要求將U替換為u時(shí)

47、，U的前后一定要有x和y。而2型文法的規(guī)則形式為U-u uVn uV*沒(méi)有什么要求，似乎1型的規(guī)則限制要多一些。但仔細(xì)看看1型規(guī)則中的條件x和y時(shí)，就不難發(fā)現(xiàn)當(dāng)x和y為空時(shí)，正好是2型文法。從0型文法到3型文法，是依次增加對(duì)文法的限制，所以描述的語(yǔ)言集合越來(lái)越小。5、簡(jiǎn)述自底向上分析法?；舅枷胧牵簭拇斎氲姆?hào)串開(kāi)始，利用文法的規(guī)則步步向上歸約，試圖歸約到文法的識(shí)別符號(hào)。從語(yǔ)法樹(shù)的角度看，自底向上分析的過(guò)程是以輸入符號(hào)串作為末端結(jié)點(diǎn)符號(hào)串，向著根結(jié)點(diǎn)方向往上構(gòu)造語(yǔ)法樹(shù)，使識(shí)別符號(hào)正好是該語(yǔ)法樹(shù)的根結(jié)點(diǎn)。如果最終根結(jié)點(diǎn)是識(shí)別符號(hào)，則輸入符號(hào)串被識(shí)別是相應(yīng)語(yǔ)言的一個(gè)句子；否則不是。 自底向上分析過(guò)程實(shí)際上是一個(gè)不斷進(jìn)行直接歸約的過(guò)程。1、什么是規(guī)范推導(dǎo)？每個(gè)句型都有規(guī)范推導(dǎo)嗎？規(guī)范推導(dǎo)就是最右推導(dǎo)每一個(gè)句子都有一個(gè)規(guī)范推導(dǎo)，而每一個(gè)句型則不一定都有規(guī)范推導(dǎo)，比如說(shuō)采用非規(guī)范推導(dǎo)得到的句型。2、已知文法GE: EET+|T TTF* | F FF | a 試證：FF*是文法的句型，指出該句型的短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄。該句型對(duì)應(yīng)的語(yǔ)法樹(shù)如下：該句型相對(duì)于E的短語(yǔ)有FF*；相對(duì)于T的短語(yǔ)有FF*,F;相對(duì)