编译原理习题1

1．编译过程一般分为               、               、中间代码生成、               

和目标代码生成五个阶段。

2．语法分析最常用的两类方法是                和                 分析法。

3．确定的有穷自动机是一个        ，通常表示为                           。

4．所谓最右推导是指                                                   。

5．语法分析器的任务是                                                 。

6．如果一个文法的任何产生式的右部都不含有    的非终结符，则这种文法称为      文法。

7．进行确定的自上而下语法分析要求语言的文法是无               和               的。

8．LR分析法是一种                                     的语法分析方法。

9．根据优化对象所涉及的程序范围，代码优化分为              、              和             等。

10．常用的优化技术包括：              、               、强度削弱、复写传播、            等。

二、        是非题（下列各题，你认为正确的，请在题后的括号内打“ √”，错的打“×”。每题2分，共20分）

1．正规文法产生的语言都可以用上下文无关文法来描述。   ……………………   (       )

2．仅考虑一个基本块，不能确定一个赋值是否真是无用的。……………………… （ 　　　）

3．如果一个文法是递归的，则其产生的语言的句子是无穷个。  ………………… （ 　　　）

4．四元式之间的联系是通过符号表实现的。………………………………………… （ 　　　）

5．文法的二义性和语言的二义性是两个不同的概念。   ……………………… … （ 　  　）

6．一个LL( l)文法一定是无二义的。…………………………………………… …  (        )

7．在规范规约中用最左素短语来刻划可归约串。…………………  ……………   (       )

8．目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 ……………   (       )

9．编译程序是对汇编程序的翻译。            …………………………………… （ 　　　）

10．逆波兰法表示的表达式亦称前缀式。  ……………………………………………  (       )

三、        简答题（每题5分，共15分）

1、简述栈式存储管理策略；   2、何谓DAG；   3、何谓文法的二义性；

四、        给出下述文法对应的正规式   （7分）

 S→ 0A| 1B

A→1S | 1

B→0S | 0

五、           已知文法G(E)：

E→T | E+T | E-T

T→F | T*F | T/F

F→(E) | i

证明E+T*F是该文法的一个句型，并指出该句型的所有短语、直接短语和句柄。（8分）

六、        设有文法G[S]：

S→ aBc|bAB

A→ aAb|b

B→ b|ε

构造其LL(1)分析表，并分析符号串baabbb是否是该文法的句子.   (10分)

七、        设有文法G[E]:

E→ (E) | ε

试判断该文法是否为SLR(1)文法，若不是，请说明理由；若是请构造SLR(1)分析表。(10 分)

八、        假设可用寄存器为R0和R1，试写出下列四元式序列对应的目标代码。（10分）

T1=B-C

T2=A*T1

   T3=D+1

   T4=E-F

   T5=T3*T4

           参

  一、填空题(1X20=20分)

1．            词法分析、语法分析、代码优化

2．            自上而下、自下而上

3．            五元组、DFA=(K , ∑, M, S, Z)

4．            任何一步都是对中最右非终结符进行替换

5．            分析一个文法的句子结构

6．            相邻、算符

7．            左递归、公共左因子

8．            自下而上

9．            局部优化、循环优化、局部优化

10．       删除公共子表达式、代码外提、变换循环控制条件、合并已知量、删除无用赋值（任选3个）

   二、是非题（2X10=20分）

 1、×    2、√   3、√   4、×   5、√   6、√   7、 ×   8、√   9、×   10、×

 三、简答题（见书中相应部分）（5X3=15 分）

 四、解：首先得正规式方程组：

                S=0A+1B

                A=1S+1

                B=0S+0

       求解该方程组得：

S=(01|10)(01|10)*     （8分）

五、解     （2分）

          是文法G[S]的句型。

          短语：E+T*F,  T*F  （2分）

          直接短语：T*F      （2分）

          句柄：T*F          （2分）

六、解：

、因为FOLLOW(B)=FIRST(c)∪FOLLOW(S)={c,#}(2分), 所以构造文法G[S]的LL（1）分析表（5）如下：

七     (2 分)

      所以该文法为SLR(1)文法。其分析表如下：(8分)

            LD  R0,B

            SUB R0,C

            LD  R1,A

            MUL R1,R0

            LD  R0,D

            ADD R0,1

            ST  R1,M

            LD  R1,E

            SUB R0,F

            MUL R0,R1

           LD  R1,M

           DIV R1,R0

           ST  R1,W