答：DAG：优化后的代码1． t1＝3*A2． t2＝2*C3． t3＝t1＋t24． t4＝t3＋55．M＝t3－16．N＝t4－M3、设有布尔表达式文法G【B】： B→B or T | TT→T and F | FF→not F | （B）| true | false 给出句子（ true or false）and not false的推导和语法树。
解：B T T and F F and F（B）and F （B or T）and F（T or T）and F （F or T）and F （true or T）and F（true or F）and F （true or false ）and F（true or false ）and not F （ true or false）and not false答：逆波兰式： x a b * c d e f * g / ＋* h * ＋＝答：分析表（每个2分，共10分）Pbegind ；X endX d ；XX sYY ；sYYe四元式：答：因为FOLLOW(B)=FIRST(c)∪FOLLOW(S)={c,#}分析表8、对于下述文法G【A】： A→cAb | cAd | ε1.构造识别其规范句型所有活前缀的DFA；2.说明该文法是何种LR文法，并给出其相应的LR分析表。
G’[A’]：(0) A’→A (1) A→cAb (2) A→cAd (3)A→εDFA因为上述DFA的I0、I2状态集中有移进-归约冲突，所以该文法不是LR(0)文法。
对于I0、I2中：归约项目A→•移进项目A→•cAb和A→•cAd 而：{ c} ∩FOLLOW(A)= {c} ∩{ b，d，＃} ＝Φ所以可用SLR(1)方法解决I0、I2的冲突。
所以该文法是SLR(1)文法。
分析表（6分,每行1分）9、将语句if x > y then x:=10 else x:= x + y 翻译为相应四元式。
第7 题证明下述文法G[〈表达式〉]是二义的。
〈表达式〉∷=a|(〈表达式〉)|〈表达式〉〈运算符〉〈表达式〉〈运算符〉∷=+|-|*|/答案：可为句子a+a*a 构造两个不同的最右推导:最右推导1 〈表达式〉=>〈表达式〉〈运算符〉〈表达式〉=>〈表达式〉〈运算符〉a=>〈表达式〉* a=>〈表达式〉〈运算符〉〈表达式〉* a=>〈表达式〉〈运算符〉a * a=>〈表达式〉+ a * a=>a + a * a最右推导2 〈表达式〉=>〈表达式〉〈运算符〉〈表达式〉=>〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式〉=>〈表达式〉〈运算符〉〈表达式〉〈运算符〉a=>〈表达式〉〈运算符〉〈表达式〉* a=>〈表达式〉〈运算符〉a * a=>〈表达式〉+ a * a=>a + a * a第8 题文法G[S]为：S→Ac|aB A→ab B→bc该文法是否为二义的？为什么？答案：对于串abc(1)S=>Ac=>abc (2)S=>aB=>abc即存在两不同的最右推导。
所以，该文法是二义的。
或者：对输入字符串abc，能构造两棵不同的语法树，所以它是二义的。
第9 题考虑下面上下文无关文法：S→SS*|SS+|a(1)表明通过此文法如何生成串aa+a*，并为该串构造语法树。
(2)G[S]的语言是什么？答案：(1)此文法生成串aa+a*的最右推导如下S=>SS*=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*(2)该文法生成的语言是：*和+的后缀表达式，即逆波兰式。
第10 题文法S→S(S)S|ε(1) 生成的语言是什么？(2) 该文法是二义的吗？说明理由。
答案：（１）嵌套的括号（２）是二义的，因为对于（）（）可以构造两棵不同的语法树。
第11 题令文法G[E]为：E→T|E+T|E-T T→F|T*F|T/F F→(E)|i证明E+T*F 是它的一个句型，指出这个句型的所有短语、直接短语和句柄。
