第3童文法和语言的形式定义·” 答案：a 分析： 正规文法只是从产生式的形式上加以限制，并没有从产生式的选用上给出要求。 正规文法也可能是二义性的。例如文法GS]: G[S]:S-Sal Aal a A-a 该文法的句子aa就存在两个不同的最左推导： S→Sa→aa S→Aa→aa 20.(上海交通大学1995)下列文法 二义文法： E→EiTT T→T+FiFF F→E*I( 可选项有： a.是b.不是c.无法判定 答累：a 分析： 该文法的句子“((*”存在两棵不同的语法树，如图3.4所示 图3,4句子”((”的两棵不同的语法树 21.(国防科技大学1984)文法的二义性和语言的二义性是两个 的概念。 可选项有：
编译原理习题与解析（第2版）一 a.不同 b.相同 c.无法判断 答案：a 分析： 文法的二义性和语言的二义性是不同的概念： 如果文法的一个句子有两棵（或两棵以上）不同的语法树，则称该句子是二义性的： 含有二义性句子的文法是二义性文法：如果个语言没有无二义性的文法，则称该语言是 二义性的。 22.(湖北省高等教育自学考试)设有文法G[S]: S→S*SS+S(Sla 该文法 二义性文法。 可选项有： a.是b.不是c.无法判断 答案：a 分析： 该文法存在句子 a*a十a 该句子存在两棵不同的语法树，如图3.5所示 图3.5句子a*a+的语法树 3.3习题解析 3.3.1文法、语言的形式定义 1,“符号就是字符”，对吗？ 解答：不对。 符号是字母表中的元素，不能把符号理解成字符。如4个保留字的字母表 (BEGIN,END,FOR.WHILE) 此时，BEGN、END、FOR、WHLE分别都是一个符号，因为它们是字母表中的元素 2.“文法中，产生式规则的左部就是非终结符号”，对吗？ 30 Page
、第3章文法和语言的形式定义" 解答：不对。并非所有在规则左部出现的内容都是非终结符号。对于2型、3型文法而 言，非终结符号是指规则左部出现的符号，对于其他类型的文法而言，则是非终结符号集 中的元素。例如规则 xUy→uvw 不能理解成xUy是非终结符号，或x、U、y都是非终结符号。非终结符号一般代表程序 的语法成分，如“<威值语句>”，它是程序的个语法成分，这个符号一 <威值语句> 本身不会在程序中出现：而终结符号则是会在程序中出现的，如-个具体的赋值语句 “i=X+1”中的符号“=”、“+”等。 3.设有G[S]: S◆A A→BIFA THEN A ELSE A B→CB+C+C C→DIC*DI*D D-x/(A)-D (1)试问其中哪些是终结符号，哪些是非终结符号？ (2)对于下列符号串： ②IFX+x THEN x*x ELSE-X 3 IF-x THEN x ELSE IF x THEN x+x ELSE x 试分别构造其推导的语法树，并指出句柄。 (3)求出每一个非终结符号的头符号集合HEAD(U) 解答：(1)非终结符号集V=S,A,B,C,D) 终结符号集V={IF,THEN,ELSE,+,-,*,（,),x} (2)所给句型的语法树如图3.6所示。 句型(x*-x)的句柄为第一个x 向型F x+x THEN x*x ELSE-X的句柄为第一个X 句型IF-X THEN x ELSE IF x THEN x+x ELSE x的句柄为第一个x (3)HEAD(S)=(A,B.C,D.x,IF,+,-,*,( HEAD(A)={B,C,D,x,IF,+,-,*,(} HEAD(B)={B,C,D,x,+,,*,(} HEAD(C)=(C,D,*x,(,- HEAD(D)={x,-,(
编译原理习题与解析（第2版）一二 X+ X THEN x*xLSE-X的语法树 ①(x-x)的语法树 THEN ELSE ③IF -X THEN x ELSE IFx THENx+x ELSE x的语法树 图3.6句型的语法树 4 Page
第3章文法和语言的形式宠义·”。 4.现有文法GS]: S→aAb A→BCAB B→ide 试问下列符号串： (1)aidtcBcAb (2)aidtceb (3)ab (4)abidt (5)aidtcidtcidtb (6)aidtBb 是否为该文法的句型或句子？ 解答：句子是仅由终结符号组成的句型，所以，一个符号串不是句型，则一定不是句 子。而如果某一符号申不是句子，它还可能是句型，关键在于它能否出识别符号推出。 由于： (I)S-aAb=aBcAb-→aidtcAb→aidtcBcAb (2)S>aAb-aBcAb=>aidtcAb-aidtcBcAb=aidtcecAb=aidtccAb aidtccBb-aidtcceb=aidtccb (3)S→aAb→aBb→asb=ab (4)因S是开始符号，而对S,只有一个规则右部aAb,其尾符号是b,不会是t,所以 不可能推出abidt。 (5)S→aAb→aBcAb-→aidtcAb-→aidtcBcAb--→aidtcidteAb →aidtcidtcBb-→aidtcidtcidtb (6)由s无法推出aidtBb 所以，(1)、(2)、(3)、(5)是句型，(2)、(3)、(5)是句子，(4)、 (6)既不是句子也不是句型。 3.3.2短语、直接短语（简单短语）、句柄 1.(湖北省高等教育自学考试)设有文法GS: s→aje(T) T→T,S1s 请给出句子(a,(a,a)的最左、最右推导并指出其最右推导的逆过程（即最左归约）每一 步的句柄。 解答：最左推导为： S(T)→T,S)→(S,S)=a,S)a,(T)=→a,T,S》 →(a,(S,S)→(a,(a,S)→(a(a,a) 最右推导为：最左归约的句柄 S=(T) 句柄为 (T) →(T,S) 句柄为 T.S →(T,(T) 句柄为 (T) →(T,T,S》 句柄为 T,S →(T,T,a》 句柄为 →T.S,a) 句柄为