編譯原理試題及答案(共8頁(yè))

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

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

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

4、0n|n，m>=0WaWr|W屬于0|1*，Wr表示W(wǎng)的逆四、給出生成下列語(yǔ)言的三型文法：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、求每個(gè)非終結(jié)符號(hào)的FIRST集和FOLLOW集；2、判定該文法是否為L(zhǎng)L(1)文法，如是，構(gòu)造LL(1)預(yù)測(cè)分析表；3、若是LL(1)文法，請(qǐng)給出輸入串a(chǎn)aabd的預(yù)測(cè)分析過程，并說明該輸入是GS的句子。八、已知文法GB

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

6、對(duì)下圖的流圖：1、求出流圖個(gè)節(jié)點(diǎn)的n的必經(jīng)節(jié)點(diǎn)集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對(duì)其進(jìn)行優(yōu)化

7、，寫出優(yōu)化后的基本塊中四元式；2、假定只有R、H在基本塊出口式活躍的，寫出優(yōu)化后的四元式序列。十三、翻譯下列關(guān)于LEX一點(diǎn)介紹的英文。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 rul

8、es. The absolute 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 regu

9、lar expressions (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 foun

10、d keyword INT 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 r

11、ight side of 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("mecha

12、nize");petrol 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 com

13、piler, or parser, 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 clas

14、s of grammars 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 mos

15、t notable being 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. Sim

16、ilar to LR parsers 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 includ

17、ing predictive 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 L

18、L one.For both 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 par

19、ser which uses 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.匯編語(yǔ)言的程序，機(jī)器語(yǔ)言的程序；高級(jí)語(yǔ)言的程序，匯編語(yǔ)言或機(jī)器語(yǔ)言的程序。2.源程序，目標(biāo)程序。3.E，+，-，*，/，i，(，)，E，T，F(xiàn)，短語(yǔ)：T+T*F+i，T+T*F，T，T*F，i4.從左到右的掃描，分析過程采用最左推導(dǎo)，需要向右查看一個(gè)符號(hào)便可決定如何推導(dǎo)。5.從左到右的掃描，分析過程采用最右推導(dǎo)的逆過程-最左規(guī)約，向后查看0個(gè)符號(hào)決定分析動(dòng)作。6.ab!c+*7.局部?jī)?yōu)化，循環(huán)優(yōu)化，全局優(yōu)化二、錯(cuò)。在這5個(gè)部分中，詞法分析，語(yǔ)法分析，語(yǔ)義分析和目標(biāo)代碼生成是必須的，代碼優(yōu)化是為了提高目標(biāo)代碼的質(zhì)量而引入的，不是必須的，沒有代碼優(yōu)化編譯程序同樣生成目標(biāo)