文档介绍：编译原理****题课
中国海洋大学计算机系
葛琳
green.******@
1
完整版PPT课件
期中试卷的试题1
写一个文法，使其语言是二进制偶数集，且每个偶数不以0开头。
作为该语言的串是不合适的。
该语言的串是“偶数”，而不是由“偶数个…组成的…串”
如果该题中将“二进制偶数” 改成“十进制偶数”，其他要求不变，文法应该如何写？
2
完整版PPT课件
第三章****题：例10
文法：S  (L) | a
L  L, S | S
(a) 构造(a, (a, a))的最右推导，说出每个右句型的句柄
S rm (L) rm (L, S) rm (L, (L))
rm (L, (L, S)) rm (L, (L, a)) rm (L, (S, a))
rm (L, (a, a)) rm (S, (a, a)) rm (a, (a, a))
句柄必须用下划线标出，不能只写出。
(b) 给出移进-归约分析器步骤：按照上课讲的格式写（栈，输入，动作）P126/表4-4
(c) 给出构造分析树步骤：一步一步画自下而上的分析树
3
完整版PPT课件
第三章****题：例11
为下列文法构造SLR分析表
E  E + T | T
T  T F | F
F  F* | a | b
4
完整版PPT课件
第三章****题：例11（续）
拓广文法：
(0) E  E (1) E  E + T
(2) E  T (3) T  T F
(4) T  F (5) F  F *
(6) F  a (7) F  b
5
完整版PPT课件
第三章****题：例11（续）
项目集规范族：
I0:
E ·E
E  ·E + T
E  ·T
T  ·T F
T  ·F
F  ·F*
F  ·a
F  ·b
I1: goto ( I0, E )
E  E·
E  E· + T
I2: goto ( I0, T )
E  T·
T T· F
F  ·F*
F  ·a
F  ·b
I3: goto ( I0, F)
T  F·
F F ·*
I4: goto ( I0, a)
F a·
I5: goto ( I0, b)
F b·
6
完整版PPT课件
第三章****题：例11（续）
I6 : goto ( I1, +)
EE + ·T
T ·T F
T ·F
F ·F *
F ·a
F ·b
I7 : goto ( I2, F)
T T F ·
F F · *
I8 : goto ( I7, *)
F F * ·
I9 : goto ( I6, T)
EE + T ·
T T · F
F ·F *
F ·a
F ·b
7
完整版PPT课件
第三章****题：例11（续）
DFA（略）
注意：构造SLR分析表需计算FOLLOW集合：
FOLLOW(E) = {$, +}
FOLLOW(T) = {a, b, $, +}
FOLLOW(F) = {*, a, b, $, +}
8
完整版PPT课件
第三章****题：例11（续）
状态
动作
转移
+  a b $
E T F
0
s4 s5
1 2 3
1
s6 acc
7
2
r2 s4 s5 r2
3
r4 s8 r4 r4 r4
4
r6 r6 r6 r6 r6
9
完整版PPT课件
第三章****题：例11（续）
状态
动作
转移
+  a b $
E T F
5
r7