二、概念题1、设有文法:P→P+Q|QQ→Q*R|RR→(P)|i(1)证明Q*R+Q+Q是它的一个句型。
(3分)(2)给出Q*R+Q+Q的所有短语,直接短语和句柄。
(4分) (3)给出句子i+i*i的最右推导。
(4分)(4)给出句子i+i*i的最左推导。
(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)给出句子i+i*i的最右推导。
(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|abB→aBb|ab给出下面语言的相应文法L2={a n b n c i|n≥1,i≥0}答案:S→AB|BA→a|aAB→bBc|bc给出下面语言的相应文法L3={a n b n c m| m,n≥1,n为奇数,m为偶数}。
答案:文法G(S):S→ACA→aaAbb/abC→ccCcc/cc四、词法分析题1、构造下面正规式相应的DFA((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,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 →- ExprExpr →(Expr)|Var ExprTail ExprTail →- Expr|ε Var →id VarTail VarTail →(Expr) |εbaa0 1b3ba(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 ExprTail2 # ExprTail VarTail id id_ _id((id))#Var→id VarTail3 # ExprTail VarTail _ _id((id))#4 # ExprTail _ _id((id))#VarTail→ε5 # Expr_ _ _id((id))# ExprTail→_ Expr6 # Expr _id((id))#7 # Expr_ _id((id))#Expr→_Expr8 # Expr id((id))#9 # ExprTail Var id((id))#Expr→Var ExprTail10 # ExprTail VarTail id id((id))#Var→id VarTail11 # 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 ExprTail17 # 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’E’→+E|εT→FT’T’→T|εF→PF’F’→*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')={(,a,b,^,+,),#}FOLLOW(P)={*,(,a,b,^,+,),#}(2) 证明这个文法是LL(1)的。
(6分) 答案:考虑下列产生式:'→+'→'→'→E E T T F F P E a b ||*|()|^||εεε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分)3、已知文法G[S] 为: S->a|(T) T->T,S|S①消除文法G[S]中的左递归,得文法G´[S]。
②文法G´[S]是否为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#的分析过程。
(1) S → DbB(2) D → d(3) D → ε(4) B → a(5) B → Bba(6) B → ε LR分析表答案:步骤状态符号输入串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六、语法分析题 考虑文法:S →AS|b A →SA|a(1) 列出这个文法的所有LR(0) 项目。
(5分) 答案0.'→⋅S S 1.'→⋅S S 2.S AS →⋅ 3.S A S →⋅ 4.S AS →⋅ 5.S b →⋅ 6.S b →⋅ 7.A SA →⋅ 8.A S A →⋅ 9.A SA →⋅ 10.A a →⋅ 11.A a →⋅(2)给出识别文法所有活前缀的DFA 。
(5分) (3)求所有非终结符的FOLLOW 集。
(5分)(4)文法是SLR 文法吗?若是,构造出它的SLR 分析表,否则说明理由。
(5分) 不是SLR 文法状态3,6,7有移进归约冲突 状态3:FOLLOW(S’)={#}不包含a,b状态6:FOLLOW(S)={#,a,b}包含a,b,;移进归约冲突无法消解 状态7:FOLLOW(A)={a,b}包含a,b ;移进归约冲突消解 所以不是SLR 文法。
七、证明题1、证明下面文法是LL(1)的但不是SLR(1)的。
S→AaAb|BbBaA→εB→ε首先该文法无左递归存在,没有公共左因子。
其次:对于S→AaAb|BbBa FIRST(AaAb)={a} FIRST(BbBa)={b}FIRST(AaAb)∩FIRST(BbBa)=Φ所以该文法是LL(1)文法。
(2)证明该文法不是SLR的。
文法的LR(0)项目集规范族为:I0={S’→.S S→.AaAb S→.BbBa A→. B→.}I1={ S’→ S. }I2={ S→A.aAb }I3={ S→B.bBa }I4={ S→Aa.Ab A→. }I5={ S→Bb.Ba B→. }I6={ S→AaA.b }I7={ S→BbB.a }I8={ S→AaAb. }I9={ S→BbBa. }考察I0:FOLLOW(A)={a,b} FOLLOW(B)={a,b} FOLLOW(A)∩FOLLOW(B)= {a,b}产生规约-规约冲突。
所以该文法不是SLR(1)文法。
2、证明下面文法是SLR(1)但不是LR(0)的。
S→AA→Ab|bBaB→aAc|a|aAb解:文法G[S]:0:S→A1:A→Ab2:A→bBa3:B→aAc4:B→a5:B→aAb构造LR(0)项目集规范族:状态5存在“归约-移进”冲突,状态9存在“归约-归约”冲突,因此该文法不是LR(0)文法。