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

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

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

3、B、簡單短語 C、素短語 D、終結(jié)符號(hào)1. 面向機(jī)器語言指的是_C_。 A、用于解決機(jī)器硬件設(shè)計(jì)問題的語言 B、特定計(jì)算機(jī)系統(tǒng)所固有的語言 C、各種計(jì)算機(jī)系統(tǒng)都通用的語言 D、只能在一臺(tái)計(jì)算機(jī)上使用的語言2.如果文法G是無二義的，則下面 D 成立。A、文法中的句子對(duì)應(yīng)兩棵不同的語法樹；B、文法中某個(gè)句子有兩個(gè)不同的最左推導(dǎo)；C、文法中某個(gè)句子有兩個(gè)不同的最右推導(dǎo)；D、文法中任一句子，它的最左或最右推導(dǎo)對(duì)應(yīng)的語法樹相同。 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.下面說法正確的是 A 。 A、一個(gè)SLR（1）文法一定也是LALR（1）文法 B、一個(gè)LR（1）文法一定也是LALR（1）文法1.動(dòng)態(tài)存儲(chǔ)分配時(shí)，可以采用的分配方法有_ C _。 以過程為單位的棧式動(dòng)態(tài)存儲(chǔ)分配 堆式存儲(chǔ)分配 最佳分配方法 A、 B、 C、 D、2.面向機(jī)器語言的特點(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語言。 解釋程序是為打開編譯程序技術(shù)得僵局而開發(fā)的。A、 B、 C、 D、 4. 編譯過程中，語法分析器的任務(wù)是 B 。分析單詞是怎樣構(gòu)成的分析單詞串是如何構(gòu)成語句和說明的分析語句和說明是如何構(gòu)成程序的分析程序的結(jié)構(gòu)A、 B、 C、 D、 5. 一個(gè)句型中的最左 B 成為該句型的句柄。 A、短語 B、簡單短語 C、素短語 D、終結(jié)符號(hào)1. 編譯程序眾的語法分析器接受以

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

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

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 。 以過程為單位的棧式動(dòng)態(tài)存儲(chǔ)分配。 堆式存儲(chǔ)分配。 最佳分派方法 A、 B、 C、 D、 5. 一個(gè)編譯程序中，不僅包含詞法分析，語法分析，中間代碼生成，代碼優(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語言存儲(chǔ)分配方式相識(shí)的語言是 A 。 A、C語言 B、BASIC語言 C、FORTRAN-77 D、C+語言4. B 這樣一些語言，它們能夠被確定的有窮自動(dòng)機(jī)識(shí)別，但不能用正規(guī)表達(dá)式表示。A、存在B、不存在 C、無法判定5. 編譯程序在其工作過程中使用最多的數(shù)據(jù)結(jié)構(gòu)是 D 。 A、線性表 B、鏈表 C、表 D、符號(hào)表1. 程序語言的語言處理程序是一種 A 。 A、系統(tǒng)軟件 B、應(yīng)用軟件 C、實(shí)時(shí)軟件 D、分布式系統(tǒng)2. 一個(gè)正規(guī)語言只能對(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è)沒有意義的字符序列 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)向地址后再回來填寫。 4 / 45如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!B、符號(hào)表中過程或函數(shù)標(biāo)識(shí)符的地址部分要填上入口地址，在掃描到過程或函數(shù)標(biāo)識(shí)符的說明時(shí)這些地址是無法知道的，只有等到開始生成過程或函數(shù)的指令部分時(shí)才能填入。 C、A和B D、都不確切1. 一般程序設(shè)計(jì)語

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

12、K)方法LALR(K)方法 預(yù)測(cè)分析方法A、 B、 C、 D、 E、二、填空題 （15分）1. 編譯程序必須完成的工作有 A 。詞法分析 語法分析 語義分析 代碼生成 中間代碼生成 代碼優(yōu)化A、 B、 C、 D、 E、2. 語法分析的常用方法有 D 。 A、自頂向下匹配 B、自底向上歸約 C、回溯法 D、自頂向下匹配和自底向上歸約3. 在編譯程序采用的優(yōu)化方法中， C 是在循環(huán)語句范圍內(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. 過程調(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. 編譯方法中自底向上的語法分析算法有 C 。簡單優(yōu)先分析方法算符優(yōu)先分析方法 遞歸子程序法 LL(K)分析法 SLR分析法 LR(K)方法 LALR(K)方法 預(yù)測(cè)分析方法A、 B、 C、 D、 E、1. 文法G所描述的語言是 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. 下面說法正確的是 B 。 A、一

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

15、A、一個(gè)正規(guī)式只能對(duì)應(yīng)一個(gè)確定的有限狀態(tài)自動(dòng)機(jī)； B、一個(gè)正規(guī)語言可能對(duì)應(yīng)多個(gè)正規(guī)文法；3. LR語法分析棧中存放的狀態(tài)是識(shí)別的 B DFA狀態(tài)。A、前綴 B、可歸前綴 C、項(xiàng)目 D、句柄4. 正規(guī)文法 A 二義性的。A、可以是B、一定不是C、一定是5. 高級(jí)語言編譯程序常用的語法分析方法中，遞歸下降分析法屬于 B 分析方法。 A、 自左向右 B、自頂向下 C、自底向上 D、自右向左1. 一個(gè)語言的文法是 B 。A、唯一的B、不唯一的C、個(gè)數(shù)有限的2. 代碼生成應(yīng)著重考慮的問題是 D 。 每一個(gè)語法成分的語義目標(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. 編譯過程中，比較常見的中間語言有 D 。 波蘭表示逆波蘭表示三元式四元式樹形表示 A、B、C、 D、5. 過程信息表中至少應(yīng)該包括有 D 。 過程名過程的靜態(tài)層次過程的入口地址過程首部在源程序中的行號(hào)有關(guān)過程的參數(shù)信息。 A、 B、 C、 D、二、填空題 （15分）1.如果在一個(gè)文法中存在某個(gè)句子，它有二個(gè)以上的最左（最右）推導(dǎo)，也就是說，若該句子對(duì)應(yīng)兩棵不同的語法樹 ，則這個(gè)文法是二義性文法。 2. 假設(shè)G是一個(gè)

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

18、左向右進(jìn)行分析，R含義是采用最右推導(dǎo)的逆過程-最左歸約，“1”的含義是向貌似句柄的符號(hào)串后查看一個(gè)輸入符號(hào)。4.編譯過程中，常見的中間語言形式有 三元式 、逆波蘭式和四元式 。5.程序的可再入性指的是：當(dāng)程序在執(zhí)行時(shí)，可以_隨時(shí)中斷_它的執(zhí)行，也可隨時(shí)_執(zhí)行進(jìn)程_恢復(fù)其原來的_執(zhí)行進(jìn)程_；而且可以在_中斷時(shí)間里_，又從該程序的_頭上 開始一個(gè)新的執(zhí)行過程。1.編譯程序與具體的機(jī)器 無關(guān) ，與具體的語言 有關(guān) 。2.SLR(1)分析法中，L的含義是 自左向右進(jìn)行分析 ，R含義是 采用最右推導(dǎo)的逆過程 ，S含義是 簡單的 ，“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是它的 開始符號(hào) ，如果S * ，則稱_是一個(gè)句型，僅含終結(jié)符號(hào)的句型是一個(gè) 句子 。文法G所產(chǎn)生的 句子的全體是一個(gè) 語言 ，將它記為L(G)。1. 如果在一個(gè)文法中存在某個(gè)句子，它有 二個(gè)以上 得最左（最右）推導(dǎo)，也就是說，若該句子對(duì)應(yīng)兩棵不同的 語法樹 ，則這個(gè)文法是 二義性 文法。 2. 對(duì)編譯程序而言，輸入數(shù)據(jù)是源程序，輸出結(jié)果是 目標(biāo)程序 。3. LR(1)分析法中，L的含義是 自左向右進(jìn)行分析 ，R含義是采用最右推導(dǎo)的逆

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

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

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

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

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

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. 語法樹代表推導(dǎo)過程，分析樹代表歸約過程。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. 自頂向下語法分析方法的基本思想是：從 識(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é)符的交集是空集 。詞法分析器交給語法分析器的文法符號(hào)一定是終結(jié)符 ，它一定只出現(xiàn)在產(chǎn)生式的右 部。7 目標(biāo)程序運(yùn)行的動(dòng)態(tài)分配策略中，含有棧式 和 堆式分配策略。1.自底向上語法分析方法的基本思想是：從待輸入的符號(hào)串開始，利用文法的規(guī)則步步向上進(jìn)行 歸約 ，試圖 歸約 到文法的 識(shí)別符號(hào) 。2. 若源程序使用高級(jí)語言編寫的，目標(biāo)程序是 機(jī)器語言程序 ，則其翻譯程序稱為編譯程序（2分）。 2. 編譯程序是指將 源程序 程序翻譯成 目標(biāo) 程序的程序。3. 自頂向

27、下 語法分析方法的基本思想是：從 識(shí)別符號(hào) 出發(fā)，利用文法的規(guī)則不斷建立直接推導(dǎo)推導(dǎo)，試圖構(gòu)造一個(gè)推導(dǎo)序列，最終由它推導(dǎo)出與輸入符號(hào)串 的符號(hào)串。4. 編譯過程通?？煞譃?個(gè)階段，分別是 詞法分析 、語法分析、 語義分析 、代碼優(yōu)化和目標(biāo)代碼生成。5. 優(yōu)化就是對(duì)程序進(jìn)行各種等價(jià)變換，使之能生成更有效的目標(biāo)代碼。1. 自下而上分析法采用 移進(jìn) 、歸約、錯(cuò)誤處理、 接受 等四種操作。 2. 采用 自上而下 語法分析時(shí)，必須消除文法的左遞歸（2分）。3. 已知文法GE：ETE+TE-TTFT*FT/FF(E)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ú)立語法意義的單詞 。5. 優(yōu)化就是對(duì)程序進(jìn)行各種 等價(jià) 變換，使之能生成更有效的 目標(biāo)代碼 。6. A稱為歸約 項(xiàng)目；對(duì)文法開始符S為接受項(xiàng)目；若a為終結(jié)符，則稱Aa為 移進(jìn) 項(xiàng)目；若B為非終結(jié)符，則稱Aa為待約 項(xiàng)目。三、簡答題。（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)，給出該句子的短語和句柄。（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)考慮的問題有那些？（4分）編譯程序的實(shí)現(xiàn) 應(yīng)考慮：開發(fā)周

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

31、這些語法成分及其屬性，這些表格就是符號(hào)表。符號(hào)表應(yīng)包括語法符號(hào)的名字和相關(guān)屬性，不同語法符號(hào)在符號(hào)表中存放的信息不同。符號(hào)表的條目一般由兩部分組成，即名字欄和信息欄。符號(hào)表域包括標(biāo)識(shí)符名、其他信息、地址等。對(duì)名字欄，為節(jié)省空間，可另外設(shè)立一個(gè)存放標(biāo)識(shí)符的字符數(shù)組。對(duì)信息欄中的類型等信息可以用數(shù)值或向量來表示，以節(jié)省空間1. .設(shè)有文法GE： ET|ET TF|T * F F(E)|i 請(qǐng)給出句型(T * Fi)的最右推導(dǎo)及畫出語法樹。（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)的短語、簡單短語及句柄。（5分）短語：(T*Fi)，T*Fi，T*F，i素短語：T*F,i4. 適合采用靜態(tài)存儲(chǔ)分配的程序設(shè)計(jì)語言應(yīng)有哪些限制？（6分）數(shù)據(jù)實(shí)體所需空間在編譯時(shí)能確定運(yùn)行時(shí)每個(gè)數(shù)據(jù)對(duì)象只能有一個(gè)實(shí)例數(shù)組的上下界是常量過程調(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)及語法樹

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的短語、簡單短語及句柄是什么？（6分）S a

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

35、頂向下分析法。從識(shí)別符號(hào)出發(fā)，不斷建立直接推導(dǎo)，試圖構(gòu)造一個(gè)推導(dǎo)序列，最終由它推導(dǎo)出與輸入符號(hào)串相同的符號(hào)串。從語法樹的角度看，自頂向下分析過程是以識(shí)別符號(hào)為根結(jié)點(diǎn)，試圖向下構(gòu)造一棵語法樹，使其末端結(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、寫出表達(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)*。歸約過程就是從輸入串開始，反復(fù)用產(chǎn)生式右部的符號(hào)替換成產(chǎn)生式左部符號(hào)，直至文法開始符。1、DFA和NFA有何區(qū)別？DFA和NFA的區(qū)別表現(xiàn)在三個(gè)方面。一是NFA可有若干個(gè)開始狀態(tài)，而DFA僅有一個(gè)。二是DFA的映像M是從K到K，而的映象M是從K到K的子集，即映像M將產(chǎn)生一個(gè)狀態(tài)集合（可能為空集），而不單個(gè)狀態(tài)。三是NFA在沒有掃描輸入符號(hào)的情況下，也可以進(jìn)行空移。2、已知文法G為：S aAcB|BdA AaB|cB bScA|b寫出句子acabcbbdcc得最左推導(dǎo)及語法樹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、寫出表達(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、語法分析的主要（功能）任務(wù)是什么？有哪二種分析分方法？語法分析的主要任務(wù)是對(duì)詞法分析的輸出結(jié)果-單詞序列進(jìn)行分析，識(shí)別合法的 語法單位。若給定的輸入符號(hào)是該文法所產(chǎn)生的語言中的句子，就給出它的語法樹，否則就報(bào)告出錯(cuò)信息。自上而下語

39、法分析和自下而上語法分析。2、令文法G為Sa|(T)TT,S|S（1）給出(a,(a,a)的最右推導(dǎo)和最左推導(dǎo)。（2）畫出語法分析樹最左推導(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、寫出表達(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)舉例說明。一個(gè)文法如果它的一個(gè)句子有兩棵或兩棵以上的語法樹，則稱此句子具有二義性，如果一個(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á)式 刪除無用

41、代碼 復(fù)寫傳播15 / 41如果您需要使用本文檔，請(qǐng)點(diǎn)擊下載按鈕下載!4、什么是語法樹?滿足下面4個(gè)條件的樹稱之為文法GS的一棵語法樹。每一終結(jié)均有一標(biāo)記，此標(biāo)記為VNVT中的一個(gè)符號(hào)；樹的根結(jié)點(diǎn)以文法GS的開始符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、在編譯過程中為什么要建立符號(hào)表，簡述符號(hào)表的組織，即它一般分成幾部分，含有那些域？在編譯過程中，始終涉及到對(duì)一些語法符號(hào)的處理，需要用到這些語法符號(hào)的相關(guān)屬性。為了在需

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

43、前綴，即有 = ,且是句柄，則活前綴為可歸約活前綴。例S a|bCdC e則be為一個(gè)可歸約活前綴3.寫出表達(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.詞法分析和語法分析都是對(duì)字符串進(jìn)行識(shí)別，二者有何區(qū)別？（4分）在詞法分析和語法分析中，都是對(duì)輸入符號(hào)串進(jìn)行識(shí)別。但詞法分析的輸入符號(hào)串是一個(gè)單詞，而語法分析的輸入符號(hào)串是一個(gè)句子或者說是

44、一個(gè)程序。為了討論方便，我們都是用小寫字母來表示終結(jié)符號(hào)，但一定要明白在詞法分析中小寫字母表示組成單詞的字符，而在語法分析中小寫字母表示組成程序的的一個(gè)單詞，識(shí)別方式來說，詞法分析和語法分析都是對(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í)語言編寫的程序

45、有那些途徑？它們之間的主要區(qū)別是什么？計(jì)算機(jī)執(zhí)行用于高級(jí)語言編寫的程序主要有兩種途徑：解釋和編譯。在解釋方式下，翻譯程序并不對(duì)高級(jí)語言進(jìn)行徹底的翻譯，而是讀入一條語句，就解釋其含義并執(zhí)行，然后再讀入下一條語句，再執(zhí)行。在編譯方式下，翻譯程序先對(duì)高級(jí)語言進(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ī)器語言、匯編語言或高級(jí)程序設(shè)計(jì)語言書寫。- 自動(dòng)構(gòu)造工具：Lex,Yacc。 Lex ,Yacc分別

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