一．令文法为
E?T|E?T|E?TT?F|T*F|T/F F?(E)|i（1） 给出i+i*i、i*(i+i)的最左推导和最右推导； （2） 给出i+i+i、i+i*i、i-i-i的语法树。 最左推导:
E?E?T?T?T?F?T?i?T?i?T*F?i?F*F?i?i*F?i?i*iE?T?T*F?F*F?i*F?i*(E)?i*(E?T)?i*(T?T)?i*(F?T)?i*(i?T)?i*(i?F)?i*(i?i)最右推导:
E?E?T?E?T*F?E?T*i?E?F*i?E?i*i?T?i*i?F?i*i?i?i*iE?T?F*T?F*F?F*(E)?F*(E?T)?F*(E?F)?F*(E?i)?F*(T?i)?F*(F?i)?F*(i?i)?i*(i?i)语法树：
EETEE
E+E+TE-TE+TFTT*F-TFTFiFFiTFiFiiiFiiii+i+ii-i-ii+i*ii+i+i i+i*i i-i-i
考虑文法G(E):
E→E+T | T T→T*F | F F→(E) | i
（1）给出句型E+F*F的语法树；
（2）给出以上句型的的短语、直接短语、句柄。 E =>E+T=>E+T*F=>E+F*F
E E + T T * F 由上图知：
F 短语：F,F*F,E+F*F 直接短语：F 句柄：F
二．构造下列正规式相应的NFA。 1求1(0|1)*00的状态最少的DFA。 解： 1)得到NFA
1 0 0 1 1 2 0 Y X
2） NFA转换成DFA 状态转换矩阵为： I {X} {1} {1,2} {1,2,Y} 重新命名后为：
I0 --- {1,2} {1,2,Y} {1,2,Y} I1 {1} {1} {1} {1}
表格 1
S 0 1 2 3 3)DFA的化简
0 -- 2 3 3 1 1 1 1 1 例如：将下图最小化。
b b a 2 3 0
a b a a b b a 4 5 1 a a 最小化：
b b a 1 2 0
a b
五．令文法G1为：
E->E+T|T T->T*F|F F->(E)|i
证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。 解：E?E?T?E?T*F 短语: E+T*F, T*F, 直接短语: T*F 句柄: T*F
E->E+T|T T->T*F|F F->(E)|i
句型（E+T）*i+F指出这个句型的所有短语、直接短语和句柄、素短语、最左素短语 短语：E+T (E+T) i (E+T)*i (E+T)*i+F F 直接短语:E+T i F 素短语: i E+T 最左素短语: E+T 1、 名词解释：
句柄：一个句型的最左直接短语称为这个句型的句柄。
最左素短语：包括至少一个终结符号，且除自身之外不包含其它素短语的短语称作素短
语。 某句型最左边的那个素短语，称为最左素短语。
六．给出下面表达式的逆波兰表示（后缀式）
七．将表达式-(a+b)*(c+d)-(a+b+c)分别表示成三元式、间接三元式和四元式序列。 三元式序列: (1) +, a, b (2) @, (1), - (3) +, c, d (4) *, (2), (3) (5) +, a, b (6) +, (5), c (7) -, (4), (6) 间接三元式序列: 三元式表： (1) +, a, b (2) @, (1), - (3) +, c, d (4) *, (2), (3) (5) +, (1), c (6) -, (4), (5) 间接码表： (1) (2) (3) (4) (1) (5) (6)
四元式序列:
(1) +, a, b, T1 (2) @, T1, -, T2 (3) +, c, d, T3 (4) *, T2, T3, T4 (5) +, a, b, T5 (6) +, T5, c, T6 (7) -, T4, T6, T7 八．按照表7.3产生三地址代码的属性文法，自下而上把赋值句A:=B*(-C+D)翻译成四元式。 步骤 输入串 栈 PLACE 四元式 (1) A:=B*(-C+D)
(2) :=B*(-C+D) i A (3) B*(-C+D) i:= A- (4) *(-C+D) i:=i A-B
(5) *(-C+D) i:=E A-B (6) *(-C+D) i:=E A-B (7) (-C+D) i:=E* A-B-
(8) (9) (10) (11) (12) (13) (14) (15) (16) (17) (18) (19)
-C+D) i:=E*( C+D) i:=E*(- +D) i:=E*(-i +D) +D) D) )
i:=E*(-E i:=E*(E i:=E*(E+
A-B-- A-B--- A-B---C A-B---C A-B--T A-B--T-
1111(@,C,-, T)
1 i:=E*(E+i A-B--T-D
i:=E*(E+E A-B--T-D (+,T,D,T) i:=E(E i:=E*(E) i:=E+E i:=E
A-B--T A-B--T- A-B-T A-T
32) )
1222(*,B,T,T) (:=,T,-,A)
3
23(20) A 产生的四元式： (@,C,-, T) (+,T,D,T)
12(*,B,T,T)
1(:=,T,-,A)
3备注:本类题目不需要写出详细过程，只要会用抽象语法树写出四元式即可。 九．试把以下程序划分为基本块并作出其程序流图。 1、划分基本块的算法：
（1）先求出四元式程序中各个基本块的入口： ①程序的第一条语句；
⑵能由条件转移语句或无条件转移语句转移到的语句； ③紧跟在条件转移语句后面的语句。
（2）对以上求出的每一入口语句，构造其所属的基本块。它是由该入口语句到另一入口语句，或到一转移语句，或到一停语句之间的语句序列组成的。
（3）凡未被纳入某一基本块中的语句，都是程序中控制流程无法到达的语句，从而也是不会被执行到的语句，可把它们从程序中删除。 Read C A:=0 B:=1 L1: A:=A+B
If B≥C goto L2 B:=B+1 Goto L1 L2: write A
halt
23
复习题（软件）
