哈工大編譯原理習題及答案

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

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

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

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

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

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

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

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)生式。試證明：一個文法是無二義性的，當且僅當此文法的每一句型至多只有一個句柄和一個句柄產(chǎn)生式。213化簡下列各個文法。(1)S→aABSS→bCACd