编译原理试题及答案.doc-淘文阁

资源描述

《编译原理试题及答案.doc》由会员分享，可在线阅读，更多相关《编译原理试题及答案.doc（29页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date编译原理试题及答案编译原理试题及答案编译原理试题一、填空题1、汇编程序将_翻译成_；编译程序将_翻译成_。2、编译程序工作工程可以划分为_、_、_、_和_等5个基本阶段，同时还会伴有_和_。3、对编译程序而言，输入数据是_，输出数据是_。4、已知文法GE：ET|E+T|E-F，TF|T*F|T/F，F(E)|I，(“,”是间隔符号，不是文法中的符号)。该文法的开始符号

2、（识别字符）是_，终结符号集合VT是_，非终结符号结合VN是_，句型T+T*F+i的短语有_。该文法消除直接左递归，改写后的文法为E_，T_，F_。5、Chomsky定以来寺中形式语言的文法分别为：_文法（又称_文法）、_文法（又称_文法）、_文法（又称_文法）、_文法（又称_文法）。6、编译过程中扫描器所完成的任务是从_中识别出一个个具有_。7、确定的有穷自动机是一个_，通常表示为_。8、LL(k)分析中，第一个L的含义是_，第二个L的含义是_，“k”的含义是_。9、LL(1)分析中，第一个L的含义是_，第二个L的含义是_，“1”的含义是_。10、LR(0)分析中，“L”的含义是_，“R”的

3、含义是_，“0”的含义是_。11、SLR(1)分析中，“L”的含义是_，“R”的含义是_，“1”的含义是_。12、LR(1)分析中，“L”的含义是_，“R”的含义是_，“1”的含义是_。13、算术表达式：a*(-b+c)的逆波兰式表示为：_。14、算术表达式：ab*(c+d/e)的逆波兰式表示为：_。15、在编译程序中安排中间代码生成的目的是_和_。16、语法制导的翻译程序能同时进行_分析和_分析。17、根据所涉及的程序范围，优化可分为_、_、_三种。二、简答题1、有人认为编译程序的词法分析、语法分析、语义分析和中间代码生成、代码优化、目标代码生成五个组成部分是缺一不可的，这种看法正确吗？说明

6、法，请构造它的分析表；4.给出输入baab#的SLR(1)分析过程。十、对下图的流图：1、求出流图个节点的n的必经节点集D(n)；2、求出流图的回边；3、求出流图中的循环。十一、将下面的程序段划分为基本块并作出其程序流图。Read A，BF:=1C:=A*AD:=B*BIf C100 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对其进行优化，写出优化后的基本块中四元式；2、假定只有R、H在基本块出口式活跃的，

7、写出优化后的四元式序列。十三、翻译下列关于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 absolute minimum Lex progra

8、m 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 expressions (see section 3) and

9、 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 whenever it appears. In this exam

10、ple 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 the line; if it is compound, or ta

11、kes 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);petrol printf(gas);would be a start. These rules are not qu

12、ite 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 compiler, or parser, construction tools that were being created at the time. It is a t

13、ool 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 that it does accept is generally powerful enough for most programming

14、 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 being BISON and BYACC.YACC generates what are termed LR parsers. This mea

15、ns 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 parsers these also scan the input from left to right, but this time cons

16、truct 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 predictive parsing and recursive descent parsing. There are now also a number o

17、f 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 both types of parser, either LR or LL, there is generally an extra piece

18、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 uses one token of lookahead as well. That is the parser must decide, give

19、n 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.局部优化，循环优

20、化，全局优化二、错。在这5个部分中，词法分析，语法分析，语义分析和目标代码生成是必须的，代码优化是为了提高目标代码的质量而引入的，不是必须的，没有代码优化编译程序同样生成目标代码。三产生式的集合P：S0S0|aSa|a。四、1.SaS|。2.SaS|aA|ab，AbA|。五、解：步骤上先NFA，确定化，最小化。对于本题确定化后即最小了。六、解：1.First(S)=a，b，,First(S)=a，b，First(A)=a，First(B)=b，;Follow(S)=#，Follow(S)=#，Follow(A)=#，b，Follow(B)=a，#。2.构造活前缀的DFA如下，项目集为每个节点内

21、的项目。项目集0，2，3，5中存在移近-规约冲突。在I0和I5中，因为Follow（A）=b，#与Select（A-aBa）交集为空；I2和I3中select(B-bAb)交Select(B-)为空，这样所用的移近规约冲突解决了，因此是SLR(1)文法。3.构造分析表如下：4.对aaabd的预测分析过程如下：七、解：D(1)=1，D(2)=1，2，D(3)=1，2，3，D(4)=1，2，3，4，D(5)=1，2，3，5，D(6)=1，2，3，6，D(7)=1，2，7，D(8)=1，2，7，8回边：72；循环：2，3，4，5，6，7八、1基本块的DAG图如下。优化后四元式序列为：S0:=2S4:=2S1:=1.5S2:=T-CS3=T+CS5:=S3R=2/S3S6:=RH:=S6*S22. 优化后的四元式序列为：S2:=T-CS3=T+CR=2/S3H:=R*S2九、略。能翻译点大意就得分。-

展开阅读全文