搜索
第2章参考答案：1：解答：略！2．解答：字母表：是元素的有穷非空集合Σ字母表：是元素的有穷非空集合Σ符号串:由字母表中的符号组成的任何有穷序列称为符号串，推导:连续使用产生式右部去替换左部某个非终结符的过程,得到的连续序列称为一个推导。句型：设Ｇ(s)是一文法，如果符号串x是从开始符号推导出来的，即有s=x,则称x是文法G(s)的一个句型。（在语法树的推导过程中的任何时刻，没有后代的端末结点自左至右排列起来就是一个句型）句子：若x仅由终结符号组成，则称x为G(S)的句子最左推导:在整个推导过程中,任何一步推导α=β都是对α中最左边的非终结符进行替换。如果一个文法存在某个句子对应两棵不同的语法树，则说这个文法是二义的语法树：推导的形式化表示，有助于理解句子语法结构的层次3．解答：略！4.解答：A：①B：③C：①D：②5.解答：用E表示表达式，T表示项，F表示因子，上述文法可以写为：E→T|E+TT→F|T*FF→(E)|i最左推导：E=E+T=E+T+T=T+T+T=F+T+T=i+T+T=i+F+T=i+i+T=i+i+F=i+i+iE=E+T=T+T=F+T=i+T=i+T*F=i+F*F=i+i*F=i+i*i最右推导：E=E+T=E+F=E+i=E+T+i=E+F+i=E+i+i=T+i+i=F+i+i=i+i+iE=E+T=E+T*F=E+T*i=E+F*i=E+i*i=T+i*i=F+i*i=i+i*ii+i+i和i+i*i的语法树如下图所示。i+i+i、i+i*i的语法树6.解答：(1)终结符号为：{or,and,not,(,),true,false}非终结符号为：{bexpr,bterm,bfactor}开始符号为：bexpr(2)句子not(trueorfalse)的语法树为：7.解答：(1)把anbnci分成anbn和ci两部分，分别由两个非终结符号生成，因此，生成此文法的产生式为：S→ABA→aAb|abB→cB|(2)令S为开始符号，产生的w中a的个数恰好比b多一个，令E为一个非终结符号，产生含相同个数的a和b的所有串，则产生式如下：S→aE|Ea|bSS|SbS|SSbE→aEbE|bEaE|(3)设文法开始符号为S，产生的w中满足|a|≤|b|≤2|a|。因此，可想到S有如下的产生式（其中B产生1到2个b）：S→aSBS|BSaSB→b|bb(4)解法一：S→〈奇数头〉〈整数〉〈奇数尾〉|〈奇数头〉〈奇数尾〉|〈奇数尾〉〈奇数尾〉→1|3|5|7|9〈奇数头〉→2|4|6|8|〈奇数尾〉〈整数〉→〈整数〉〈数字〉|〈数字〉〈数字〉→0|〈奇数头〉解法二：文法G=({S,A,B,C,D},{0,1,2,3,4,5,6,7,8,9},P,S)S→AB|BA→AC|DB→1|3|5|7|9D→2|4|6|8|BC→0|D(5)文法G=({N,S,N,M,D},{0,1,2,3,4,5,6,7,8,9},S,P)S→N0|N5N→MD|M→1|2|3|4|5|6|7|8|9D→D0|DM|(6)G[S]：S→aSa|bSb|cSc|a|b|c|8.解答：(1)句子abab有如下两个不同的最左推导：S=aSbS=abS=abaSbS=ababS=ababS=aSbS=abSaSbS=abaSbS=ababS=abab所以此文法是二义性的。(2)句子abab的两个相应的最右推导：S=aSbS=aSbaSbS=aSbaSb=aSbab=ababS=aSbS=aSb=abSaSb=abSab=abab(3)句子abab的两棵分析树：(a)(b)(4)此文法产生的语言是：在{a，b}上由相同个数的a和b组成的字符串。9，10：解答：略！