《编译原理》期中课堂试卷
班级 姓名
一、:请写出由下列文法所确定的语言. 1. G1: S→10S01 S→aA A→bA A→a
2. G2: S→aSS S→a 1、
解：
S?10S01?1010S0101?(10)nS(01)n?(10)naA(01)n?(10)nabA(01)nmn?(10)nabmA(01)n?(10)nabma(01)n所以语言{(10)nabma(01)n} n>=0,m>=0
S?aaa2、
解：
S?aaSSS?aaaaa
S?aaSSaSS?aaaaaaaS?a2n?1*所以语言{ a2n?1} n>=0
二、证明文法G1和G2等价 G1：S→0S1，S→01
G2：A→0R，A→01，R→A1
n?1n?1nn证明：S?0S1?00S11?0S1?01
n?1n?1A?0R?0A1?00R1?00A11?0n?1A1n?1?0n1n
因为两个文法的语言相同，所以文法G1，G2等价 三、令文法G为
E→T|E+T|E-T T→F|T*F|T/F F→（E）|i
1. 给出句子i+i*i的最左推导和i*(i+i)的最右推导，并给出相应的语法树 2. 试证明符号串T*F+i是G的一个句型(要求画出语法树). 3. 写出T*F+i句型的所有短语,直接短句和句柄.
解：
1.E?E?T?T?T?F?T?i?T?i?T*F?i?F*F?i?i*F?i?i*i
E?T?T*F?T*(E)?T*(E?T)?T*(E?F)
?T*(E?i)?T*(T?i)?T*(F?i)?T*(i?i)?F*(i?i)?i*(i?i)2、证明：E?E?T?T?T?T*F?T?T*F?F?T*F?i E E + T T F T * F i
3、短语：T*F+i,T*F,i, 直接短语：T*F,i 句柄：T*F
四、构造以下正规式相应的NFA，再确定化
*
10（1|0）11
0
1 0 1
AB C x
1
0 T0:{X} ? T1:{A} {B}:T2 1 D 1 {A} :T1 ? T2:{B} {B}:T2 {B,C}:T3 T3:{B,C} {B},T2 {B,C,D}:T4 T4:{B,C,D} {B}:T2 {B,C,D}:T4 0 1 1 0 1 1 T0 T1 T2 T3 T4 0 0 五、判断下列文法是否为LL（1）文法，如果不是则把其转化为LL（1）文法（15分） G：S→A|B A→aA|a B→bB|b 解：因为
Select(A?aSelect(A?aA)?Select(A?a)?{a}
Select(B?bB)?Select(B?b)?{b}所以此文法不是LL（1）文法 产生式A，B有左公因子 提取左公因子得：
A?a(A|?)?A?aA'B?b(B|?)?B?bB'A'?AB'?BA'??
B'??A'?AA'??
S?AS?BA?aA'故文法为
B?bB'B'?BB'??判断此文法是否为LL（1）文法
select(S?A)?select(S?B)?first(A)?first(B)??select(A'?A)?select(A'??)?first(A)?follow(A')?{a}?follow(S)?? select(B'?B)?select(B'??)?first(B)?follow(B')?{b}?follow(S)??因为它们的SELECT集交集为空，所以转化后的文法为LL（1）文法
编译原理课堂考试试卷
