各位同学：

    前一段时间外出了，同学周四发短信说周6下午你们参加思科培训，和考试冲突了，很遗憾，我知道的太晚了，我通知的时候没有一个同学说起这件事，等到安排好了，且已经准备考试了，才说起，不好呀。

     下面是一些复习题，作为学完该课程总结回顾之用。下午考试，考完后，我将在这里公布答案。因为关注本blog的同学不多，baidu的blog不再同步了。

一、    填空题

1.  汇编程序将           翻译成                ；编译程序将           翻译成                。

2. 编译程序工作工程可以划分为            、             、                、        和                   等5个基本阶段，同时还会伴有               和           。

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

4. 已知文法G[E]: E—>T|E+T|E-F,  T－>F|T*F|T/F,,F—>(E)|I (“,”是间隔符号，不是文法中的符号)。该文法的开始符号（识别字符）是      ，终结符号集合V_T是         ，非终结符号结合V_N是            ，句型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分析器与优先分析器在识别被归约串时的主要异同时什么？

 三、给出生成下述语言的上下文无关的文法

{1ⁿ0^m1^m0ⁿ|n,m>=0}

{WaW^r|W属于{0|1}^*,W^r表示W的逆}

四、给出生成下列语言的三型文法：

{aⁿ|n>=0}

{aⁿb^m|n,m>0}

{aⁿb^mc^k|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<D goto L1

E=A*A

F=F+1

E:=E+f

Write E

Halt

L1:          E:=B*B

              F:=F+2

              Write E

              If E>100 goto L2

Halt

L2:          F:=F-1

              Goto L1

十二、有下面基本块：

S₀:=2

S₁:=3/S₀

S₂:=T-C

S₃:=T+C

R:=S₀/S₃

H:=R

S₄:=3/S₁

S₅:=T+C

S₆:=S₄/S₅

H:=S₆*S₂

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("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 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("color");

mechanise   printf("mechanize");

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

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.