哈工大編譯原理習(xí)題及答案

1、1.1何謂源程序、目標(biāo)程序、翻譯程序、編譯程序和解釋程序它們之間可能有何種關(guān)系1.2一個(gè)典型的編譯系統(tǒng)通常由哪些部分組成各部分的主要功能是什么1.3選擇一種你所熟悉的程序設(shè)計(jì)語言，試列出此語言中的全部關(guān)鍵字，并通過上機(jī)使用該語言以判明這些關(guān)鍵字是否為保留字。1.4選取一種你所熟悉的語言，試對(duì)它進(jìn)行分析，以找出此語言中的括號(hào)、關(guān)鍵字END以及逗號(hào)有多少種不同的用途。1.5試用你常用的一種高級(jí)語言編寫一短小的程序，上機(jī)進(jìn)行編譯和運(yùn)行，記錄下

2、操作步驟和輸出信息，如果可能，請(qǐng)卸出中間代碼和目標(biāo)代碼。第一章習(xí)題解答1.解：源程序是指以某種程序設(shè)計(jì)語言所編寫的程序。目標(biāo)程序是指編譯程序（或解釋程序）將源程序處理加工而得的另一種語言（目標(biāo)語言）的程序。翻譯程序是將某種語言翻譯成另一種語言的程序的統(tǒng)稱。編譯程序與解釋程序均為翻譯程序，但二者工作方法不同。解釋程序的特點(diǎn)是并不先將高級(jí)語言程序全部翻譯成機(jī)器代碼，而是每讀入一條高級(jí)語言程序語句，就用解釋程序?qū)⑵浞g成一段機(jī)器指令并執(zhí)行之，

3、然后再讀入下一條語句繼續(xù)進(jìn)行解釋、執(zhí)行，如此反復(fù)。即邊解釋邊執(zhí)行，翻譯所得的指令序列并不保存。編譯程序的特點(diǎn)是先將高級(jí)語言程序翻譯成機(jī)器語言程序，將其保存到指定的空間中，在用戶需要時(shí)再執(zhí)行之。即先翻譯、后執(zhí)行。2.解：一般說來，編譯程序主要由詞法分析程序、語法分析程序、語義分析程序、中間代碼生成程序、代碼優(yōu)化程序、目標(biāo)代碼生成程序、信息表管理程序、錯(cuò)誤檢查處理程序組成。3.解：C語言的關(guān)鍵字有：autobreakcaseconstcon

4、tinuedefaultdodoubleelseenumexternfloatfgotoifintlongregisterreturnshtsignedsizeofstaticstructswitchtypedefunionunsignedvoidvolatilewhile。上述關(guān)鍵字在C語言中均為保留字。4.解：C語言中括號(hào)有三種：，[]，（）。其中，用于語句括號(hào)；[]用于數(shù)組；（）用于函數(shù)（定義與調(diào)用）及表達(dá)式運(yùn)算（改變運(yùn)算順序）。

5、C語言中無END關(guān)鍵字。逗號(hào)在C語言中被視為分隔符和運(yùn)算符，作為優(yōu)先級(jí)最低的運(yùn)算符，運(yùn)算結(jié)果為逗號(hào)表達(dá)式最右側(cè)子表達(dá)式的值（如：(abcd)的值為d）。5.略第二章前后文無關(guān)文法和語言21設(shè)有字母表A1=ab…z，A2=01…9，試回答下列問題：(1)字母表A1上長度為2的符號(hào)串有多少個(gè)(2)集合A1A2含有多少個(gè)元素(3)列出集合A1(A1∪A2)中的全部長度不大于3的符號(hào)串。22試分別構(gòu)造產(chǎn)生下列語言的文法。27設(shè)已給文法G［S］：

6、S→aAcBS→BdSB→AB→cABA→BaBA→aBcA→aB→b試檢驗(yàn)下列符號(hào)串中哪些是G［S］中的句子，給出這些句子的最左推導(dǎo)、最右推導(dǎo)和相應(yīng)的語法樹。(1)aacb(2)aabacbadcd(3)aacbccb(4)aacabcbcccaacdca(5)aacabcbcccaacbca28設(shè)G=(VNVTPS)為CFG，α1α2…αn為V上的符號(hào)串，試證明：若α1α2…αnβ則存在V上的符號(hào)串β1β2，…βn，使β=β1β2

7、…βn，且有aiβi(i=12…n)29設(shè)G=(VNVTPS)為CFG，α和β都是V上的符號(hào)串，且αβ，試證明：當(dāng)α的首符號(hào)為終結(jié)符號(hào)時(shí)，β的首符號(hào)也必為終結(jié)符號(hào)；當(dāng)β的首符號(hào)為非終結(jié)符號(hào)時(shí)，則α的首符號(hào)也必為非終結(jié)符號(hào)。210試證明：文法S→ABS→DCA→aAA→aB→bBcB→bcC→cCC→cD→aDbD→ab為二義性文法。211對(duì)于下列的文法和相應(yīng)的句子，試指出這些句子的全部短語；分別給出句子的最右推導(dǎo)，并指出各步直接推導(dǎo)

8、所得句型的句柄。(1)S→ABS→cA→bAA→aB→aSbB→cbbaacb(2)S→(AS)S→(b)A→(SaA)A→(a)(((b)a(a))(b))(3)E→ETE→TT→TFT→FF→FP↑F→PP→EP→iiiii↑212在自底向上的分析中，用來歸約句型句柄的產(chǎn)生式稱為句柄產(chǎn)生式。試證明：一個(gè)文法是無二義性的，當(dāng)且僅當(dāng)此文法的每一句型至多只有一個(gè)句柄和一個(gè)句柄產(chǎn)生式。213化簡下列各個(gè)文法。(1)S→aABSS→bCACd