表达式〉a〈表达式〉〈运算符〉aa〈表达式〉aaaaa最右推导2〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈运算符〉a〈表达式〉〈运算符〉〈表达式〉a〈表达式〉〈运算符〉aa
f清华大学第二版编译原理答案
〈表达式〉aaaaa第8题文法GS为：S→AcaBA→abB→bc该文法是否为二义的？为什么？答案：对于串abc1SAcabc2SaBabc即存在两不同的最右推导。所以，该文法是二义的。或者：对输入字符串abc，能构造两棵不同的语法树，所以它是二义的。SaBbcSAcab第9题考虑下面上下文无关文法：S→SSSSa1表明通过此文法如何生成串aaa，并为该串构造语法树。SSSSSaaa2GS的语言是什么？答案：1此文法生成串aaa的最右推导如下SSSSSSaSSaSaaaaa2该文法生成的语言是：和的后缀表达式，即逆波兰式。第10题文法S→SSSε1生成的语言是什么？2该文法是二义的吗？说明理由。答案：（１）嵌套的括号（２）是二义的，因为对于（）（）可以构造两棵不同的语法树。第11题令文法GE为：E→TETETT→FTFTF
f清华大学第二版编译原理答案
F→Ei证明ETF是它的一个句型，指出这个句型的所有短语、直接短语和句柄。答案：此句型对应语法树如右，故为此文法一个句型。或者：因为存在推导序列EETETF，所以ETF句型此句型相对于E的短语有ETF；相对于T的短语有TF直接短语为：TF句柄为：TF第13题一个上下文无关文法生成句子abbaa的推导树如下：1给出串abbaa最左推导、最右推导。2该文法的产生式集合P可能有哪些元素？3找出该句子的所有短语、直接短语、句柄。BaSABSaSBAεbba答案：1串abbaa最左推导SABSaBSaSBBSaBBSabBSabbSabbAaabbaa最右推导：SABSABAaABaaASBBaaASBbaaASbbaaAbbaaabbaa2产生式有：S→ABSAaεA→aB→SBBb可能元素有：εaaababbaaaaabbaa……3该句子的短语有：a是相对A的短语ε是相对S的短语b是相对B的短语εbb是相对B的短语aa是相对S的短语aεbbaa是相对S的短语直接短语有：aεb句柄是：a《编译原理》课后习题答案第四章第1题构造下列正规式相应的DFA（１）101101（２）１101010101）0
f清华大学第二版编译原理答案
（３）aababab（４）babbbab答案：1先构造NFA：用子集法将NFA确定化01XAAAABABACABACAABYABYACAB除X，A外，重新命名其他状态，令Ar