《编译原理》复习题
51．写出C语言标识符集（字母或下划线开头的由字母、数字、下划线构成的串）的正规式。 解答：用D表示数字0-9，用L表示字母a-z|A-Z，则C语言标识符的正规式为：
（L|_）（L|D|_）*
52．有一语法制导定义如下，其中+表示符号连接运算：
S→B print B.vers B→a B.vers=a B→b B.vers=b
B→Ba B.vers=a+B.vers B→Bb B.vers=b+B.vers
若输入序列为abab，且采用自底向上的分析方法，则输出序列为（__________baba_________）。 用分析树表示求解过程。
S B B b B a B b a Print baba B.vers=baba B.vers=aba B.vers=ba B.vers=a
53．假设第一个四元式的序号是100，写出布尔表达式a
100 （j<, a, b, 106） 101 （j, _, _ , 102） 102 （jnz, c, _ ,104） 103 （j，_ ,_ ,q） 104 （j>，d, e, 106） 105 （j，_ , _ , q ） T:106 …… F:q …….
54．设有如下文法： G[E]：E→EWT|T T→T/F|F
F→（E）|a|b|c W→+|-
证明符号串a/(b-c)是句子。 解答：有推导
25
E?T?T/F?F/F?a/F?a/(E)?a/(EWT)?
a/(TWT)? a/(FWT)? a/(bWT)? a/(b-T)? a/(b-c)，即从文法开始符号E能够推导出a/(b-c)，所以a/(b-c)是文法G[E]的句子。 55．对于下列文法 G[S]： S→Sb|bA A→aA|a
（1）构造一个与G等价的LL（1）文法G′。 （2）对于文法G′,构造相应的LL（1）分析表。 解： （1）（5分）G′：S→bAS′ S′→b S′|ε
A→aA′
A′→A|ε
（2）（1分）FIRST（S）={ b } FIRST（S′）={ b，ε} FIRST（A）={a}
FIRST（A′）={a，ε} FOLLOW（S）={#} FOLLOW（S′）={#} FOLLOW（A）={b，#}
FOLLOW（A′）=（b，#）
LL（1）分析表：
a b #
S S→
bAS′
S′ S′→b S′→ε
S′
A A→
aA′
A′ A′→A A′→A′→ε
ε
56．构造下述文法的SLR（1）分析表。
G[S]：S→（A） A→ABB|B B→b 解：拓广文法：（1分） S′→S （0）
S→（A） （1） A→ABB （2）
A→B （3） B→b （4） 识别活前缀的DFA：（4分）
《编译原理》复习题
S→（L） S.num=L.num+1
(1)
0S→a S.num=0 L→L，S
(1)(1) S→.(A) L.num=