1、- 1 -二、概念题1、设有文法：PP+Q|QQQ*R|RR(P)|i（1）证明 Q*R+Q+Q 是它的一个句型。 （3 分)（2）给出 Q*R+Q+Q 的所有短语，直接短语和句柄。(4 分)（3）给出句子+*的最右推导。(4 分)（4）给出句子+*的最左推导。(4 分)2、设有文法：EE+T|T TT*F|F F(E)|i（1）证明 E+T*F 是它的一个句型。 （3 分)答案： ETF*（2）给出 E+T*F 的所有短语，直接短语和句柄。(4 分)短语: E+T*F, T*F,直接短语: T*F句柄: T*F（3）给出句子+*的最右推导。(4 分)3、写出表达式 a+b*(c-d)对应的逆
2、波兰式和三元式序列。答案：逆波兰式：(abcd-*+) - 2 -三元式序列:OP ARG1 ARG2(1) - c d(2) * b (1)(3) + a (2) 三、词法分析题给出下面语言的相应文法L1=anbnambm|n,m0答案： SAB|A|B|A aAb|ab B aBb|ab给出下面语言的相应文法L2=anbnci|n1,i0答案： S AB|B A a|aA B bBc|bc给出下面语言的相应文法L3=anbncm| m,n1，n 为奇数，m 为偶数。答案：文法 G(S):SAC AaaAbb/ab CccCcc/cc四、词法分析题- 3 -1、构造下面正规式相应的 DFA(
3、0|1)*|(11)*)*（要求：先将正规式转化为 NFA，再将 NFA 确定化，最小化）2、构造下面正规式相应的 DFA1(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,D3、构造一个 DFA，它接受 =a，b上所有包含 ab 的字符串。（要求：先将正规式转化为 NFA，再将 NFA 确定化，最小化）答案：(一)相应的正规式为(a|b)*ab(a|b)*(二) 与此正规式对应的 NFA 为状态转换矩阵为：- 4 - 最
4、小化：0，1，2 3，4，50， 2，1， 3，4，5所以此等价的 DFA 为：开始状态为 0 ，终态集为3 ，状态集为0,1,3 ，输入字母表是a,b 状态转换图如上。4、构造与正规式 b(a|b)*ba 等价的 DFA五、语法分析题1、对下面的文法 G:Expr- ExprExpr(Expr)|Var ExprTailExprTail- Expr|Varid VarTail VarTail(Expr) |baa0 1b3ba- 5 -（1） 构造 LL(1)分析表。 （12 分）答案：（1）FIRST(Expr)=_ , ( , id FIRST(ExprTail)=_ , FIRST(V
5、ar)=id FIRST(VarTail)= ( , FOLLOW(Expr)=# , ) FOLLOW(ExprTail) =# , ) FOLLOW(Var) =_ , # , ) FOLLOW(VarTail) =_ , # , ) （2） 给出对句子 idid(id)的分析过程。 （8 分）步骤 符号栈 输入串 所用产生式0 Expr id_ _id(id)1 # ExprTail Var id_ _id(id) ExprVar ExprTail2 # ExprTail VarTail id id_ _id(id) Varid VarTail3 # ExprTail VarTail _
6、 _id(id)4 # ExprTail _ _id(id) VarTail5 # Expr_ _ _id(id) ExprTail_ Expr6 # Expr _id(id)7 # Expr_ _id(id) Expr_Expr8 # Expr id(id)- 6 -9 # ExprTail Var id(id) ExprVar ExprTail10 # ExprTail VarTail id id(id) Varid VarTail11 # ExprTail VarTail (id) 12 # ExprTail )Expr( (id) VarTail(Expr)13 # ExprTail
7、)Expr (id)14 # ExprTail ) )Expr( (id) Expr(Expr)15 # ExprTail ) )Expr id)16 # ExprTail ) ) ExprTail Var id)ExpVar ExprTail17 # ExprTail ) )ExprTail VarTail id id) Varid VarTail18 # ExprTail ) )ExprTail VarTail )19 # ExprTail ) )ExprTail ) VarTail20 # ExprTail ) ) ) ExprTail21 # ExprTail ) )22 # Expr
8、Tail # ExprTail23 # # 分析成功2、对下面的文法 G:ETE- 7 -E+E|TFTTT|FPFF *F |P(E)|a|b|（1） 计算这个文法的每个非终结符的 FIRST 和 FOLLOW。 （8 分）答案：FIRST(E)=(,a,b,FIRST(E)=+,FIRST(T)=(,a,b,FIRST(T)=(,a,b,FIRST(F)=(,a,b,FIRST(F)=*,FIRST(P)=(,a,b,FOLLOW(E)=#,)FOLLOW(E)=#,)FOLLOW(T)=+,),#FOLLOW(T)=+,),#FOLLOW(F)=(,a,b,+,),#FOLLOW(F)=
9、(,a,b,+,),#FOLLOW(P)=*,(,a,b,+,),#- 8 -（2） 证明这个文法是 LL(1)的。 （6 分）答案：考虑下列产生式:ETFPab|*|()FIRST(+E)FIRST()=+=FIRST(+E)FOLLOW(E)=+#,)=FIRST(T)FIRST()=(,a,b,=FIRST(T)FOLLOW(T)=(,a,b,+,),#=FIRST(*F)FIRST()=*=FIRST(*F)FOLLOW(F)=*(,a,b,+,),#=FIRST(E)FIRST(a) FIRST(b) FIRST()=所以,该文法式 LL(1)文法.（3） 构造它的预测分析表。 （6
10、 分）3、已知文法 GS 为： S-a|(T)T-T,S|S - 9 -消除文法 GS中的左递归，得文法 GS。 文法 GS是否为 LL(1)的？若是，给出它的预测分析表。4、对下面的文法 G:S S a T | a T | a TT a T | a(1) 消除该文法的左递归和提取左公因子；(2) 构造各非终结符的 FIRST 和 FOLLOW 集合；(3) 构造该文法的 LL(1)分析表，并判断该文法是否是 LL(1)的。答案：5、文法 G(S)及其 LR 分析表如下，请给出串 baba#的分析过程。- 10 -(1) S DbB (2) D d (3) D (4) B a (5) B Bba (6) B LR 分析表ACTION GOTOb D a # S B D0 r3 s3 1 21 acc2 s43 r24 r6 S5 r6 65 r4 r46 s7 r17 S88 r5 r5答案：步骤 状态 符号 输入串0 0 # baba#1 02 #D baba#2 024 #Db aba#3 0245 #Dba ba#4 0246 #DbB ba#5 02467 #DbBb a#6 024678 #DbBba #7 0246 #DbB #8 01 #S # acc
