卜第3章文法和语言的形式定义·” 3。语法树与短语 语法树子树的末端结点从左到右排列所组成的符号串即是语法树所描述句型（相对于 子树的根)的短语，简单子树（只有父子两代)的末端结点符号串即是语法树所描述句型 的直接短语或简单短语，最左简单子树的末端结点符号串即是语法树所描述句型的句柄 4.文法的二义性 如果文法G中的某一个句子存在两棵（包括两棵）以上的不同的语法树，则称该句子 是二义性的。如果一个文法含有二义性的句子，则称该文法是二义性的。 处理文法的二义性通常有两种方法： (1)在语义上加些限制。 (2)重新构造一个等价的无二义性的文法。 3.1.6文法的实用限制和文法变换 在实际应用中，通常对文法有下面的实用限制。 (1)文法中不含有形如U→U的有害规则，若有，则删去。 (2)文法中不包含多余规则，若有，则酬去。 下面两种情形的规则为多余规则： ①某条规则U→u中的左部符号U(U不是识别符号)，不在所属文法的任何其他规则 右部出现，即从开始符号出发的所有推导始终不会用到此规则。 ②使用规则U→u后推不出终结符号串。 经过处理，不包含多余规则的文法称为压缩过了的文法 (3)关于文法左递归的限制. 在有些分析方法（如自上而下语法分析）中，要求文法不含有左递归(U→U…或 U声U…),若有，需消除。消除直接左递归的方法有 ·采用扩充BNF范式 例如U一Uxy,可改写为U-y{x)。 引进新的非终结符号，将左递归改写为右递归 一般地，没有文法规则 U→UxUx…Uxmlyily2y。 其中y=l,2,…,n)均不以符号U为首，那么增加一新的非终结符号U',便可将 上述规则变换为不再含有直接左递归的等价形式，即 U→yU"y2U4y.U" U'◆x,UIx,UI…x.U'l 消除间接左递归的方法在“自上而下分析方法”中介绍 (4)文法中不含空规则U→e。 有的分析算法（如算符优先分析法）要求文法中没有空产生式U→，若有，则要消除， 明狼
编译原理习题与解析（第2版）一二® 3.2基本题 3.2.1填空题 1,(湖北省高等教育白学考试)假设G是一个文法，S是文法的开始符号，如果$当x, 则称x是该文法的一个 答案：句型 2.(国防科技大学1984)文法G产牛的 的全体是该文法描述的语言 答案：句子 3.文法G S-AB A-aAle B→Bclbe 描述的语言L(G[S 答案：{a"bc"n20,m21} 4.(北京科技大学1985)给定如下子语言框架PASCS: <程序>→Program<程序名>：<分程序>. <分程序>→<分程序体水说明><分程序体 <说明>→Integer<标识符表>Real←标识符表>Boolcan<标识符表> Procedure<-过程标识符>；<分程序>k说明>；<说明> <分程序体→Begin<语句>End <语句>→<标识符≥水特殊字符>水语句><语句 <程序名>→<标识符> <过程标识符 <标识符 <标识符表>+<标识符>K标识符>，<标识符表> <标识符>→<字母>水标识符><字母>水标识符><数字 <特殊字符>·多 <字母>→AB…-… <数字>→0…9 该子语言文法的识别符号为(1)一，终结符集为(2)，非终结符集为(3)一。 答案：(1)程序> (2) (Program,:,.,Integer,Real,Boolean.Procedure. Begin,End,SA,B,…,Z.a,h,…,z,0,l.…,9y (3) {长程序>，<分程序>，<说明>，<分程序体>，<语句>，程序名>， <过程标识符>，<标识符表>，<标识符>，<特殊字符>，<宁母>， 数字>} 分析： 这是用BNF表示的文法，用<>括住的是一个语法成分。 20Page
p 第3廉文法和语言的形式定义·” 该文法中所有产生式的形式都满足2型文法对规则的形式要求，所以这是一个2型文法。 所有产生式的左部符（如<程序>，<分程序>，…，<数字>等）构成文法的非终结符号集， 而其他符号构成终结符号集。Program,Real等也是终结符号，它们是系统定义的保留半。 5. (华中科技大学1991)己知文法GE]: E-TIE+TIE-T T→FT*FT F-(E)i 该文法的开始符号（识别符号）是(1)一，终结符号集合V是(2) ，非终结 符号集合VN是(3)句型T+T*F+i的短语有(4)。用扩充的BNF改写该文法以消 除直接左递归，改写后的文法为： E+(5),T+(6),F+(7) 答案：(1)E(2)+,*,)i(3){ET,F (4)T+T*F+i,T+T*F,第一个T,T*F和i (5)T{+H)T}(6){W)F}(7)(E) 分析(2)、(3)空： 该文法中所有产生式的形式都满足2型文法对规则的形式要求，所以这是一个2型文法 所有产生式的左部符号（如E,T,F等）构成文法的非终结符号集，而除开“一”、“” 等元符号的其他符号构成终结符号集。 6.(华北电力学院北京研究生部1985)一个文法GZ若存在推导序列z±Z…,则 称G[Z是(1)文法，这类文法所产生的句子有(2)个。 答案：(1)递归(2)无数 7.已知文法G[z: Z→U0V1 U+Z11 V+Z00 请写出由此文法描述的只含有4个符号的全部句子：(1)一 该文法是Chomsky.(2)_型文法。 答案：(1)0101,1010,1001,0110 (2)3 分析： (1)句子就是从文法的开始符号推导出的终结符号串，因此只需要从该文法的开始符 号Z推导出长度为4的终结符号串即可。 (2)该文法中所有产生式的形式都满足3型文法对规则的形式要求，所以这是一个3 型文法。 8.(中国科技大学1999)乔姆斯基定义的4种形式语言文法分别为：(1)文法（又 称(2)文法)、(3) 文法（又称(4）文法)、(5)文法（又称 (6)文法)、(7)文法（又称(8）文法)。 答案：(1)0型(2)短语结构(3)1型(4)上下文有关 (5)2型·(6)上下文无关(7)3型(8)正则/正规
编译原理习题与解析（第2版）一— 3.2.2单项选择题 1.文法G所描述的语言是 订洗项有， a.文法G的字汇表V中所有符号组成的符号串的集合 h.文法G的字汇表V的闭包V中的所有符号串的集合 c.由文法的识别符号推出的所有符号串的集合 d由文法的识别符号推出的所有终结符号串的集合 答案：d 2.(清华大学1984)巴科斯-诺尔范式（即BNF)是一种广泛采用的 的工具。 可选项有： a.描述规则b.描述语言 c.描述文法d.描述句了 答宝.c 3.(武汉大学1991)一个语言的文法是 可选项有： a.惟一的b.不惟一的c.个数有限的 答案：b 分析： 如果不同的文法推导出的终结符号串的集合是相同的，则它们是等价文法。一个文法 的等价文法的个数是无限的，所以一个语言的文法是不惟一的。 4.(湖北省高等教有自学考试)设有文法G[S]({S,B),{b},{S→bbB,B→bS),S),该 文法所描述的语言是 可选项有： a.L(G[S])=(b'i20) b.L(G[SJ)=(bi0} c.L(GSb2i≥0 d.L(G[S])={ 答案：c 分析： 语言就是从文法的开始符号推导出的终结符号串的集合。 从该文法的开始符号$推导出奇数个b,并且句了中b的个数至少为1 所以选c。 5.(云南大学1985)己知语言L={abb21},则下述文法中 可以产生语 言L。 可选项有： a.Z-→aZblaAbb b.A-aAb 22Pa8
、第3章文法和语言的形式定义·"。 A-aAblb A-b c.Z--AbB d.Z-aAb A-aAla A→aAblb B→bBb 答案：d 分析： 由于句子中a和b的个数关系是a比b少l,且a和b以最左的一个b为中心对称出现，因此， 在构造文法的规则时，注意让a和b对称生成。 a.如果选“Z→b”推导得到句子“b”,此时句子中符号“a”的长度n=0.不满足语 言的要求」 b.如果选“A→b”推导得到句子“b”,此时句子中符号“a”的长度nO,不满足语 言的要求。 c.从Z推导出的符号串是ab”,并且不能保证m、n相等或n-m+1。 d.从Z正好推导出语言L={abbn>l3。 所以选d 6.(湖北省高等教有白学考试)描述语言L={ab2心1}的文法为。 可选项有： A.Z→ABb b.Z-ABb A→aAla A→Aala B→bBb B-aBblb c.Z-Ab d Z-aAb A-aAba A-AblaAbl8 答案：d 分析： a.不能保证推导出的符号串ab"中n心m一定成立。 b.递归规则“A→Aa”的应用可能使符号串ab中m>n,不满足语言的要求。 c.除了m=m=1外，其他句子中均是m>m,不满足语言的要求。 d.从z正好推导出语言L={a"b”2m21} 所以选d。 7.(上海交通大学1996)生成非0开头的正偶数集的文法是 可选项有： a.Z-ABC b.Z-ABC C→02144618 C→01244618 B→3ABOle B→BAB0I0 A→123…19 A→123…9 c.Z-ABC21468 d.Z-ABC2468 C→024618 C→024618