二、概念题
1、设有文法：P→P+Q|Q
Q→Q*R|R
R→(P)|i
（1）证明Q*R+Q+Q是它的一个句型。（3分)
（2）给出Q*R+Q+Q的所有短语，直接短语和句柄。(4分) （3）给出句子ｉ+ｉ*ｉ的最右推导。(4分)
（4）给出句子ｉ+ｉ*ｉ的最左推导。(4分)
2、设有文法：E→E+T|T T→T*F|F F→(E)|i （1）证明E+T*F是它的一个句型。（3分)
⇒+⇒+*
答案：E E T E T F
（2）给出E+T*F的所有短语，直接短语和句柄。(4分) 短语: E+T*F, T*F,
直接短语: T*F
句柄: T*F
（3）给出句子ｉ+ｉ*ｉ的最右推导。(4分)
3、写出表达式a+b*(c-d)对应的逆波兰式和三元式序列。答案：逆波兰式：(abcd-*+)
三元式序列:
OP ARG1 ARG2
(1) - c d
(2) * b (1)
(3) + a (2)
三、词法分析题
给出下面语言的相应文法
L1={a n b n a m b m|n,m≥0}
答案：S→AB|A|B|∑
A→aAb|ab
B→aBb|ab
给出下面语言的相应文法
L2={a n b n c i|n≥1,i≥0}
答案：S→AB|B
A→a|aA
B→bBc|bc
给出下面语言的相应文法
L3={a n b n c m| m,n≥1，n为奇数，m为偶数}。
答案：文法G(S):S→AC
A→aaAbb/ab
C→ccCcc/cc
四、词法分析题
1、构造下面正规式相应的DFA
((0|1)*|(11)*)*
（要求：先将正规式转化为NFA，再将NFA确定化，最小化）2、构造下面正规式相应的DFA
1(0|1)*101
答案：
I I0 I1
{X} Ф{A,B,C}
{A,B,C} { B,C} { B,C,D}
{B,C} { B,C} { B,C,D}
{B,C,D} { B,C,E} { B,C,D}
{B,C,E} { B,C} {B,C,D,y}
{B,C,D,y} {B,C,E} { B,C,D}
3、构造一个DFA，它接受 ={a，b}上所有包含ab的字符串。（要求：先将正规式转化为NFA，再将NFA确定化，最小化）答案：(一)相应的正规式为(a|b)*ab(a|b)*
(二) ①与此正规式对应的NFA为
②状态转换矩阵为：
③ 最小化：
{0，1，2} {3，4，5} {0， 2}，1， {3，4，5}
0 ，终态集为{3} ，状态集为{0,1,3} ， 输入字母表是{a,b} 状态转换图如上。 4、构造与正规式 b(a|b)*ba 等价的DFA
五、语法分析题 1、对下面的文法G: Expr →- Expr
Expr →(Expr)|Var ExprTail ExprTail →- Expr|ε Var →id VarTail VarTail →(Expr) |ε
b
a
a
0 1
b
3
b
a
（1）构造LL(1)分析表。（12分）
答案：
（1）FIRST(Expr)={_ , ( , id } FIRST(ExprTail)={_ , ε } FIRST(Var)={id} FIRST(VarTail)={ ( , ε}
FOLLOW(Expr)={# , ) } FOLLOW(ExprTail) ={# , ) }
FOLLOW(Var) ={_ , # , ) } FOLLOW(VarTail) ={_ , # , ) }
（2）给出对句子id—id((id))的分析过程。（8分）
步骤符号栈输入串所用产生式
0 ＃Expr id_ _id((id))＃
1 # ExprTail Var id_ _id((id))＃Expr→Var ExprTail
2 # ExprTail VarTail id id_ _id((id))＃Var→id VarTail
3 # ExprTail VarTail _ _id((id))＃
4 # ExprTail _ _id((id))＃VarTail→ε
5 # Expr_ _ _id((id))＃ ExprTail→_ Expr
6 # Expr _id((id))＃
7 # Expr_ _id((id))＃Expr→_Expr
8 # Expr id((id))＃
9 # ExprTail Var id((id))＃Expr→Var ExprTail
10 # ExprTail VarTail id id((id))＃Var→id VarTail
11 # ExprTail VarTail ((id))＃
12 # ExprTail )Expr( ((id))＃VarTail→(Expr)
13 # ExprTail )Expr (id))＃
14 # ExprTail ) )Expr( (id))＃Expr→(Expr)
15 # ExprTail ) )Expr id))＃
16# ExprTail ) ) ExprTail Var id))＃Exp→Var ExprTail
17 # ExprTail ) )
ExprTail VarTail id id))＃Var→id VarTail 18 # ExprTail ) )
ExprTail VarTail ))＃
19 # ExprTail ) )
ExprTail ))＃VarTail→ε
20 # ExprTail ) ) ))＃ExprTail→ε
21 # ExprTail ) )＃
22 # ExprTail # ExprTail→ε
23 # # 分析成功
2、对下面的文法G:
E→TE’
