2、构造算符优先表。
五、计算题4
21. 已知文法G(S)为：
S → A A → Ab | bBa B → aAc | a | aAb
给出文法的项目集规范族。
22. 已知文法G（E）：
1.
2. 3. 4. 5. 6.
的LR分析表为：
E→ E+T E→ T T→ T*F T→ F F→ (E) F→ i
Acction Goto ） r2 r4 r6 $ Acc r2 r4 r6 r1 r3 r5 E 1 T 2 F 3 3 3 S 0 1 2 3 4 5 6 7 8 9 10 11 i S5 + * s7 r4 （ S4 S6 r2 r4 S5 8 2 S4 r6 r6 S5 S5 9 S4 S4 S7 r3 r5 10 S5 r1 r3 r5 S11 r1 r3 r5 第 6 页 共 26 页
请按以下格式给出“i+i*i$”的LR分析过程。
步骤 栈 输入
动作 说明 23. 已知文法G(S)：
S→(L) | a L→L,S | S
给出文法的项目集规范族。
24. 已知文法G（S ）：
S→(L) | a L→L,S | S
的项目集规范族如下：
I0： S’→?S ( S I1： S’→ S? I2： ( a a L S ( ) I4： S→ (L?) , I6： S→ (L)? I7： I5： L→ S? S→?(L) a I3： S→ a? S→(?L) L→?L,S L→?S S →L,?S S→?(L) S I8： S →L,S? 构造其的SLR分析表。 25. 已知文法G[S]：
S?SA|A A?a
1、求其识别活前缀的项目集规范族
2、构造其SLR(1)分析表。
第 7 页 共 26 页
六、计算题5
26. 已知文法G(L)为：
L→En E → E+T|T T → T*F| F F →digit
根据S属性定义，求表达式为3*5+4的带注释分析树。 27. 已知表达式S=A?B?┐C； 1、求其后缀表示
2、求其用布尔表达式的控制流翻译方法翻译的四元式。 28. 将下列程序段翻译成四元式序列并划分基本块：
A=M＋N；
B= M－N； IF A≦B C=N； ELSE C=M；
29. 翻译下列语句为逆波兰式。
if X else C=C+X; 30. 翻译下列语句为四元式。 if X else C=C+X; 七、简答题 （略）…… 第 8 页 共 26 页 答案 一、计算题1 1. 确定化: i0{0} i1{0,1} i2{1,2} i3{1} DFA M： a {0,1} {0,1} {1} / b / {1,2} {1,2} {1,2} (内容一行1.5分，图１分，共7分) 正规式:a+b(b|ab)*(有拓广1分，消0、１态2分，消２、3态3分，共6分) 2. NFA Ｍ: (有初态2分，有末态2分，有中间态2分，共6分) 确定化: i0{0} i1{0,1} i2{1,2} i3{1} a {0,1} {0,1} {1} / 第 9 页 共 26 页 b / {1,2} {1,2} {1,2} DFA M： (内容一行1.5分，图１分，共7分) 3. 1、NFA M (有初态1分，终态1分，1态、2态各1分，共4分) 2、确定化： I0{0} I1{0,1,2} NFA M： a {0,1,2 } {0,1,2} b / {0,1,2} （有框架１分，内容一行1.5分， DFA效果图2分，共6分） 3、最小化：∵ 0 1 ∴原图已最小化 （原因2分，结果１分，共3分） 4. 语言L的正规式是： (正规式5分) 第 10 页 共 26 页 a 1 1 b / 1 (a b*a | b)* 或 b*(a b*a b*)*