編譯原理試題及答案

1、編譯原理試題一、填空題1、匯編程序?qū)翻譯成_；編譯程序?qū)翻譯成_。2、編譯程序工作工程可以劃分為_、_、_、_和_等5個基本階段，同時還會伴有_和_。3、對編譯程序而言，輸入數(shù)據(jù)是_，輸出數(shù)據(jù)是_。4、已知文法GE：E>T|E+T|E-F，T>F|T*F|T/F，F(xiàn)>(E)|I，(“,”是間隔符號，不是文法中的符號)。該文法的開始符號（識別字符）是_，終結(jié)符號集合VT是_，非終結(jié)符號結(jié)合VN是_，句型T+T*F+i的短語有_。該文法消除直接左遞歸，改寫后的文法為E>_，T>_，F(xiàn)>_。5、Chomsky定以來寺中形式語言的文法分別為：_文法（又稱_文法）

2、、_文法（又稱_文法）、_文法（又稱_文法）、_文法（又稱_文法）。6、編譯過程中掃描器所完成的任務(wù)是從_中識別出一個個具有_。7、確定的有窮自動機是一個_，通常表示為_。8、LL(k)分析中，第一個L的含義是_，第二個L的含義是_，“k”的含義是_。9、LL(1)分析中，第一個L的含義是_，第二個L的含義是_，“1”的含義是_。10、LR(0)分析中，“L”的含義是_，“R”的含義是_，“0”的含義是_。11、SLR(1)分析中，“L”的含義是_，“R”的含義是_，“1”的含義是_。12、LR(1)分析中，“L”的含義是_，“R”的含義是_，“1”的含義是_。13、算術(shù)表達式：a*(-b+c

3、)的逆波蘭式表示為：_。14、算術(shù)表達式：ab*(c+d/e)的逆波蘭式表示為：_。15、在編譯程序中安排中間代碼生成的目的是_和_。16、語法制導(dǎo)的翻譯程序能同時進行_分析和_分析。17、根據(jù)所涉及的程序范圍，優(yōu)化可分為_、_、_三種。二、簡答題1、有人認為編譯程序的詞法分析、語法分析、語義分析和中間代碼生成、代碼優(yōu)化、目標代碼生成五個組成部分是缺一不可的，這種看法正確嗎？說明理由。2、多邊掃描的程序是高質(zhì)量的編譯程序，優(yōu)于單遍掃描的編譯程序，對嗎？為什么？3、LR分析器與優(yōu)先分析器在識別被歸約串時的主要異同時什么？三、給出生成下述語言的上下文無關(guān)的文法1n0m1m0n|n，m>=0W

4、aWr|W屬于0|1*，Wr表示W(wǎng)的逆四、給出生成下列語言的三型文法：an|n>=0anbm|n，m>0anbmck|n，m，k>=0五、構(gòu)造正規(guī)式1(0|1)*101相應(yīng)的最小DFA。六、構(gòu)造正規(guī)式b(a|b)*bab相應(yīng)的最小DFA。七、已知文法GS：S>aH；H>aMd|d；M>Ab|；A>aM|e。1、求每個非終結(jié)符號的FIRST集和FOLLOW集；2、判定該文法是否為LL(1)文法，如是，構(gòu)造LL(1)預(yù)測分析表；3、若是LL(1)文法，請給出輸入串a(chǎn)aabd的預(yù)測分析過程，并說明該輸入是GS的句子。八、已知文法GB：B>BoT|T；T

5、>TaF|F；F>nF|(B)|t|f。1、計算GB的FIRSTVT和LASTVT；2、構(gòu)造GB的算符優(yōu)先關(guān)系表并說明GB是否為算符有限文法；3、若是算符優(yōu)先文法，請給出輸入ntofat#的分析過程，并說明該輸入是GB的句子。九、文法GS：S>AB；A>aBa|；B>bAb|。1、引入產(chǎn)生式S->S，對文法進行改造為GS,計算GS的First和Follow集，由此判斷該文法是否是SLR(1)文法；2、構(gòu)造GS的項目集族和識別活前綴的DFA；3.若是SLR(1)文法，請構(gòu)造它的分析表；4.給出輸入baab#的SLR(1)分析過程。十、對下圖的流圖：1、求出流圖

6、個節(jié)點的n的必經(jīng)節(jié)點集D(n)；2、求出流圖的回邊；3、求出流圖中的循環(huán)。十一、將下面的程序段劃分為基本塊并作出其程序流圖。Read A，BF:=1C:=A*AD:=B*BIf C<D goto L1E=A*AF=F+1E:=E+fWrite EHaltL1: E:=B*BF:=F+2Write EIf E>100 goto L2HaltL2: F:=F-1Goto L1十二、有下面基本塊：S0:=2S1:=3/S0S2:=T-CS3:=T+CR:=S0/S3H:=RS4:=3/S1S5:=T+CS6:=S4/S5H:=S6*S21、應(yīng)用DAG對其進行優(yōu)化，寫出優(yōu)化后的基本塊中四元

7、式；2、假定只有R、H在基本塊出口式活躍的，寫出優(yōu)化后的四元式序列。十三、翻譯下列關(guān)于LEX一點介紹的英文。2、Lex Source.The general format of Lex source is:definitions%rules%user subroutineswhere the definitions and the user subroutines are often omitted. The second % is optional, but the first is required to mark the beginning of the rules. The absol

8、ute minimum Lex program is thus%(no definitions, no rules) which translates into a program which copies the input to the output unchanged.In the outline of Lex programs shown above, the rules represent the users control decisions; they are a table, in which the left column contains regular expressio

9、ns (see section 3) and the right column contains actions, program fragments to be executed when the expressions are recognized. Thus an individual rule might appearinteger printf("found keyword INT");to look for the string integer in the input stream and print the message found keyword INT

10、 whenever it appears. In this example the host procedural language is C and the C library function printf is used to print the string. The end of the expression is indicated by the first blank or tab character. If the action is merely a single C expression, it can just be given on the right side of

11、the line; if it is compound, or takes more than a line, it should be enclosed in braces. As a slightly more useful example, suppose it is desired to change a number of words from British to American spelling. Lex rules such ascolour printf("color");mechanise printf("mechanize");p

12、etrol printf("gas");would be a start. These rules are not quite enough, since the word petroleum would become gaseum; a way of dealing with this will be described later.十四、翻譯下列有關(guān)yacc的一些英文介紹。IntroductionYACC is short for Yet Another Compiler Compiler. A pun on the number of compiler, or par

13、ser, construction tools that were being created at the time. It is a tool that, given a BNF (Backus-Naur Form) style specification of a grammar, can generate a corresponding parser. It is worth noting that YACC will not accept every grammar presented to it. Far from it. However the class of grammars

14、 that it does accept is generally powerful enough for most programming needs.YACC was originally written by S. C. Johnson on a UNIX platform. It is closely tied in with Lex. A lexical analyser generating tool. Since then there have been many flavours of YACC implemented. Perhaps the most notable bei

15、ng BISON and BYACC.YACC generates what are termed LR parsers. This means that they scan the input from left to right, the L bit, and produce a rightmost derivation from the bottom up, the R bit. LR parsers are also called bottom-up parsers. They are somewhat different to LL parsers. Similar to LR pa

16、rsers these also scan the input from left to right, but this time construct a leftmost derivation instead. LL parsers are also called top down parsers. They have the distinct advantage that they can generally be implemented by hand. There are a number of techniques for doing this including predictiv

17、e parsing and recursive descent parsing. There are now also a number of tools which can construct LL parsers automatically. Having said all this, it is generally a time consuming task to code a parser by hand, and an LR parser construction technique is inherently more powerful than an LL one.For bot

18、h types of parser, either LR or LL, there is generally an extra piece of information which specifies how many lookahead tokens the parser uses to decide what action to perform. For instance an LR(1) parser uses one token of lookahead. This an important point because YACC generates a parser which use

19、s one token of lookahead as well. That is the parser must decide, given the symbols that it has already seen, and the current lookahead token what it needs to do next.一、1.匯編語言的程序，機器語言的程序；高級語言的程序，匯編語言或機器語言的程序。2.源程序，目標程序。3.E，+，-，*，/，i，(，)，E，T，F(xiàn)，短語：T+T*F+i，T+T*F，T，T*F，i4.從左到右的掃描，分析過程采用最左推導(dǎo)，需要向右查看一個符號便可決定如何推導(dǎo)。5.從左到右的掃描，分析過程采用最右推導(dǎo)的逆過程-最左規(guī)約，向后查看0個符號決定分析動作。6.ab!c+*7.局部優(yōu)化，循環(huán)優(yōu)化，全局優(yōu)化二、錯。在這5個部分中，詞法分析，語法分析，語義分析和目標代碼生成是必須的，代碼優(yōu)化是為了提高目標代碼的質(zhì)量而引入的，不是必須的，沒有代碼優(yōu)化編譯程序