1、给出下面语言的相应文法。L1a
b
ci
≥1i≥0答案：S→ABBA→aaAB→bBcbc
2．给出下面语言的相应文法
L1a
b
cmdmm
≥1，
为奇数，m为偶数。
答案：文法GSS→AC
A→aaAbbab
C→ccCcccc3、构造一个DFA，它接受a，b上所有包含ab的字符串。（要求：先将正规式转化为NFA，再将NFA确定化，最小化）一相应的正规式为ababab二①与此正规式对应的NFA为
答案；在自己写的纸上
4、对下面的文法GE→TE’E’→EεT→FT’T’→TεF→PF’F’→F’εP→Eab∧
（1）证明这个文法是LL1的。考虑下列产生式E’EεT’TεF’F’εPE∧ab
FIRSTE∩FIRSTε∩εφFIRSTE∩FOLLOWE∩φ
fFIRSTT∩FIRSTεab∩εφFIRSTT∩FOLLOWTab∩φFIRSTF∩FIRSTε∩εφFIRSTF∩FOLLOWF∩abφFIRSTE∩FIRSTa∩FIRSTb∩FIRSTφ所以该文法式LL1文法计算这个文法的每个非终结符的FIRST和FOLLOW。（8分）
答案：FIRSTEab
FIRSTEε
FIRSTTab
FIRSTTabε
FIRSTFab
FIRSTFε
FIRSTPab
FOLLOWE
FOLLOWE
FOLLOWT
FOLLOWT
FOLLOWFab
FOLLOWFab
FOLLOWPab
（3）构造它的预测分析表。（6分）
答案；在手机上
写出表达式abcd对应的逆波兰式和三元式序列。
答案：逆波兰式：abcd
三元式序列
OPARG1ARG2
1
c
d
2
b
1
f3
a
2
给出下面语言的相应文法
L1a
b
ambm
m≥0
给出下面语言的相应文法
答案：S→ABAB∑
A→aAbab
B→aBbab
L2a
b
ci
≥1i≥0
给出下面语言的相应文法
答案：S→ABB
A→aaA
B→bBcbc
17、对下面的文法G
SSaTaTaTTaTa1消除该文法的左递归和提取左公因子；2构造各非终结符的FIRST和FOLLOW集合；3构造该文法的LL1分析表，并判断该文法是否是LL1的。
f18、文法GS及其LR分析表如下，请给出串baba的分析过程。
1S→DbB
2D→d3D→ε
4B→a5B→Bba
6B→ε
LR分析表
b0r312s43r24r65r46s778r5
ACTION
D
a

s3
acc
S5r6r4r1
S8r5
GOTO
S
B
D
1
2
6
f答案：步骤状态符号输入串
00baba
102Dbaba
2024Dbaba
30245Dbaba
40246DbBba
502467DbBba
6024678DbBba
70246DbB

8
01Sacc
七、证明题1、证明下面文法是LL1的但不是SLR1的。
S→AaAbBbBa
A→εB→ε
首先该文法无左递归存在没有公共左因子。
其次对于S→AaAbBbBaFIRSTAaAbaFIRSTBbBabFIRSTAaAb∩FIRSTBbBaΦ
所以该文法是LL1文法。
2证明该文法不是SLRr