编译原理试题及答案(共8页)

1、精选优质文档-倾情为你奉上编译原理试题一、填空题1、汇编程序将_翻译成_；编译程序将_翻译成_。2、编译程序工作工程可以划分为_、_、_、_和_等5个基本阶段，同时还会伴有_和_。3、对编译程序而言，输入数据是_，输出数据是_。4、已知文法GE：E>T|E+T|E-F，T>F|T*F|T/F，F>(E)|I，(“,”是间隔符号，不是文法中的符号)。该文法的开始符号（识别字符）是_，终结符号集合VT是_，非终结符号结合VN是_，句型T+T*F+i的短语有_。该文法消除直接左递归，改写后的文法为E>_，T>_，F>_。5、Chomsky定以来寺中形式语言的文法分

2、别为：_文法（又称_文法）、_文法（又称_文法）、_文法（又称_文法）、_文法（又称_文法）。6、编译过程中扫描器所完成的任务是从_中识别出一个个具有_。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、

3、算术表达式：a*(-b+c)的逆波兰式表示为：_。14、算术表达式：ab*(c+d/e)的逆波兰式表示为：_。15、在编译程序中安排中间代码生成的目的是_和_。16、语法制导的翻译程序能同时进行_分析和_分析。17、根据所涉及的程序范围，优化可分为_、_、_三种。二、简答题1、有人认为编译程序的词法分析、语法分析、语义分析和中间代码生成、代码优化、目标代码生成五个组成部分是缺一不可的，这种看法正确吗？说明理由。2、多边扫描的程序是高质量的编译程序，优于单遍扫描的编译程序，对吗？为什么？3、LR分析器与优先分析器在识别被归约串时的主要异同时什么？三、给出生成下述语言的上下文无关的文法1n0m1m

4、0n|n，m>=0WaWr|W属于0|1*，Wr表示W的逆四、给出生成下列语言的三型文法：an|n>=0anbm|n，m>0anbmck|n，m，k>=0五、构造正规式1(0|1)*101相应的最小DFA。六、构造正规式b(a|b)*bab相应的最小DFA。七、已知文法GS：S>aH；H>aMd|d；M>Ab|；A>aM|e。1、求每个非终结符号的FIRST集和FOLLOW集；2、判定该文法是否为LL(1)文法，如是，构造LL(1)预测分析表；3、若是LL(1)文法，请给出输入串aaabd的预测分析过程，并说明该输入是GS的句子。八、已知文法GB

5、：B>BoT|T；T>TaF|F；F>nF|(B)|t|f。1、计算GB的FIRSTVT和LASTVT；2、构造GB的算符优先关系表并说明GB是否为算符有限文法；3、若是算符优先文法，请给出输入ntofat#的分析过程，并说明该输入是GB的句子。九、文法GS：S>AB；A>aBa|；B>bAb|。1、引入产生式S->S，对文法进行改造为GS,计算GS的First和Follow集，由此判断该文法是否是SLR(1)文法；2、构造GS的项目集族和识别活前缀的DFA；3.若是SLR(1)文法，请构造它的分析表；4.给出输入baab#的SLR(1)分析过程。十、

6、对下图的流图：1、求出流图个节点的n的必经节点集D(n)；2、求出流图的回边；3、求出流图中的循环。十一、将下面的程序段划分为基本块并作出其程序流图。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、应用DAG对其进行优化

7、，写出优化后的基本块中四元式；2、假定只有R、H在基本块出口式活跃的，写出优化后的四元式序列。十三、翻译下列关于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 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.十四、翻译下列有关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.汇编语言的程序，机器语言的程序；高级语言的程序，汇编语言或机器语言的程序。2.源程序，目标程序。3.E，+，-，*，/，i，(，)，E，T，F，短语：T+T*F+i，T+T*F，T，T*F，i4.从左到右的扫描，分析过程采用最左推导，需要向右查看一个符号便可决定如何推导。5.从左到右的扫描，分析过程采用最右推导的逆过程-最左规约，向后查看0个符号决定分析动作。6.ab!c+*7.局部优化，循环优化，全局优化二、错。在这5个部分中，词法分析，语法分析，语义分析和目标代码生成是必须的，代码优化是为了提高目标代码的质量而引入的，不是必须的，没有代码优化编译程序同样生成目标