编译原理试题及答案

编译原理试题

一、填空题 1、汇编程序将________翻译成________；编译程序将________翻译成________。 2、编译程序工作工程可以划分为______、______、______、______和______等5个基本阶段，同时还会伴有______和______。

3、对编译程序而言，输入数据是______，输出数据是______。

4、已知文法G[E]：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定以来寺中形式语言的文法分别为：________文法（又称________文法）、________文法（又称________文法）、________文法（又称________文法）、________文法（又称________文法）。 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、算术表达式：a*(-b+c)的逆波兰式表示为：________。

14、算术表达式：a＋b*(c+d/e)的逆波兰式表示为：____________。

15、在编译程序中安排中间代码生成的目的是__________和___________。 16、语法制导的翻译程序能同时进行________分析和________分析。

17、根据所涉及的程序范围，优化可分为________、________、________三种。 二、简答题

1、有人认为编译程序的词法分析、语法分析、语义分析和中间代码生成、代码优化、目标代码生成五个组成部分是缺一不可的，这种看法正确吗？说明理由。 2、多边扫描的程序是高质量的编译程序，优于单遍扫描的编译程序，对吗？为什么？

3、LR分析器与优先分析器在识别被归约串时的主要异同时什么？ 三、给出生成下述语言的上下文无关的文法 {1n0m1m0n|n，m>=0}

{WaWr|W属于{0|1}*，Wr表示W的逆} 四、给出生成下列语言的三型文法： {an|n>=0}

{anbm|n，m>0}

{anbmck|n，m，k>=0}

五、构造正规式1(0|1)*101相应的最小DFA。 六、构造正规式b(a|b)*bab相应的最小DFA。

七、已知文法G[S]：S－>aH；H－>aMd|d；M－>Ab|ε；A－>aM|e。 1、求每个非终结符号的FIRST集和FOLLOW集；

2、判定该文法是否为LL(1)文法，如是，构造LL(1)预测分析表； 3、若是LL(1)文法，请给出输入串aaabd＃的预测分析过程，并说明该输入是G[S]的句子。

八、已知文法G[B]：B－>BoT|T；T－>TaF|F；F－>nF|(B)|t|f。 1、计算G[B]的FIRSTVT和LASTVT；

2、构造G[B]的算符优先关系表并说明G[B]是否为算符有限文法；

3、若是算符优先文法，请给出输入ntofat#的分析过程，并说明该输入是G[B]的句子。

九、文法G[S]：S－>AB；A－>aBa|ε；B－>bAb|ε。

1、引入产生式S’->S，对文法进行改造为G[S’],计算G[S’]的First和Follow集，由此判断该文法是否是SLR(1)文法；

2、构造G[S’]的项目集族和识别活前缀的DFA； 3.若是SLR(1)文法，请构造它的分析表； 4.给出输入baab#的SLR(1)分析过程。 十、对下图的流图：

1、求出流图个节点的n的必经节点集D(n)； 2、求出流图的回边； 3、求出流图中的循环。

十一、将下面的程序段划分为基本块并作出其程序流图。 Read A，B F:=1 C:=A*A D:=B*B

If C

L1: E:=B*B

F:=F+2 Write E

If E>100 goto L2

Halt

L2: F:=F-1

Goto L1

十二、有下面基本块： S0:=2 S1:=3/S0 S2:=T-C S3:=T+C R:=S0/S3 H:=R

S4:=3/S1 S5:=T+C S6:=S4/S5 H:=S6*S2

1、应用DAG对其进行优化，写出优化后的基本块中四元式；

2、假定只有R、H在基本块出口式活跃的，写出优化后的四元式序列。 十三、翻译下列关于LEX一点介绍的英文。 2、Lex Source.

The general format of Lex source is:

{definitions}

%% {rules} %%

{user subroutines}

where 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 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 user’s control decisions; they are a table, in which the left column contains regular 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 appear

integer printf(\

to look for the string integer in the input stream and print the message ‘‘found 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 right 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 as

colour printf(\mechanise printf(\

petrol printf(\

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的一些英文介绍。 Introduction

YACC 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 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 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 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. Similar 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 including 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 LL 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 parser 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，i 4.从左到右的扫描，分析过程采用最左推导，需要向右查看一个符号便可决定如何推导。

5.从左到右的扫描，分析过程采用最右推导的逆过程-最左规约，向后查看0个符号决定分析动作。 6.ab!c+*

7.局部优化，循环优化，全局优化

二、错。在这5个部分中，词法分析，语法分析，语义分析和目标代码生成是必须的，代码优化是为了提高目标代码的质量而引入的，不是必须的，没有代码优化编译程序同样生成目标代码。

三．产生式的集合P：S→0S0|aSa|a。

四、1.S→aS|ε。2.S→aS|aA|ab，A→bA|ε。

五、解：步骤上先NFA，确定化，最小化。对于本题确定化后即最小了。

NFA0X12345Y1124Yε2325 01ABBYBDFAXABCYACAC

六、解：

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如下，项目集为每个节点内的项目。

项目集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} 回边：7→2；

循环：｛2，3，4，5，6，7｝

八、1基本块的DAG图如下。优化后四元式序列为：

S0:=2 S4:=2 S1:=1.5 S2:=T-C S3=T+C S5:=S3 R=2/S3 S6:=R H:=S6*S2

2. 优化后的四元式序列为：

S2:=T-C S3=T+C R=2/S3 H:=R*S2

九、略。能翻译点大意就得分。

本文来源：https://www.bwwdw.com/article/b1v7.html