2022年编译原理第一章练习和答案 .pdf
学而不思则惘，思而不学则殆例 1 设有文法GS: Sa| （ T）|TT,S|S （1） 试给出句子 (a,a,a)的最左推导。（2） 试给出句子 (a,a,a)的分析树（3） 试给出句子 (a,a,a)的最右推导和最右推导的逆过程( 即最左规约 ) 的每一步的句柄。【解】 (1) (a,a,a)的最左推导S=(T) =(T,S) =( T,S,S) =( S,S,S) =(a,S,S) =(a,a,S) =(a,a,a) （2）(a,a,a)的分析树S ( T ) T ，S S a T ，S a a (3) (a,a,a)最右推导最左规约每一步的句柄S=(T) 句柄为： (T) =(T,S) 句柄为： T,S =(T,a) 句柄为： a =(T,S,a) 句柄为： T,S =(T,a,a) 句柄为：第一个a =(S,a,a) 句柄为： S =(a,a,a) 句柄为：第一个a 例 2 已知文法GZ: Z 0U|1V U 1Z|1 V 0Z|0 （1） 请写出此文法描述的只含有个符号的全部句子。（2） GZ 产生的语言是什么？（3） 该文法在 Chomsky文法分类中属于几型文法？【解】 （1）0101， 0110，1010， 1001 （2）分析 GZ 所推导出的句子的特点：由Z 开始的推导不外乎图1 所示的四种情形。图 1文法 GZ可能的几种推导Z 0 1 U Z U 0 Z 1 Z 1 V 0 Z Z 1 0 V 由 Z 推导出 10 或 01 后就终止或进入递归，而Z 的每次递归将推导出相同的符号串：10 或精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 5 页学而不思则惘，思而不学则殆01。所以 GZ 产生的语言L(GZ)=x|x (10|01)+ (3) 该文法属于3 型文法。例 3 已知文法G =(A,B,C，a,b,c，P， A), P由以下产生式组成: A abc A aBbc BbbB BcCbcc bC Cb aC aaB aC aa 此文法所表示的语言是什么？【解】分析文法的规则：每使用一次BcCbcc，b、c 的个数各增加一个；每使用一次aC aaB 或 aC aa, a的个数就增加一个；产生式 Bb bB、 bCCb起连接转换作用。由于 A是开始符号，由产生式Aabc 推导得到终结符号串abc；由产生式AaBbc 推导得到 B后，每当使用产生式BbbB、BcCbcc、bC Cb、aCaaB 就会递归调用B一次，所产生的 a、 b、 c 的个数分别增加一个， 因此推导所得的终结符号串为abc、 aabbcc、 aaabbbccc 、 所以文法描述的语言为 anbncn|n0. 例 4 构造描述语言L(GS)=（n）n|n 0 的文法。【解】 (1) 找出语言的一些典型句子: n=0 n=1 ( ) n=2 () 所以 , L(GS)= 、( ) ()、()、 (2) 分析句子的特点: 只含有 ( 和),( 和 ) 的个数相同且对称, 句子中所含的符号数可无限, 句子的个数可无限。(3) 凑规则 : 由 S |() 得到 |()，由 A (S) 得到 ()，() 是在（） 的两边再加上一对（）得到，()是在 ()的两边再加上一对（）得到，所以将上述产生式合并为S(S) |。(4) 得到文法 GS: S(S) |(5) 检验 : 语言所有的句子均可由文法GS 推导出来 , 文法 GS 推导出来的所有终结符号串均为语言的句子. 例 5 构造描述语言L(GS)=am bn |nm0 的文法。【解】找出语言的一些典型句子:abb 、abbb、 aabbb、aabbbb、, 语言的句子的特点是仅含有 a、b, a在 b 的左边， b 的个数大于a 的个数， a 的个数至少是1。单独生成ck, k1 可用产生式 Cc |Cc 句子中要求b 的个数大于a 的个数，所以得到文法：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 5 页学而不思则惘，思而不学则殆GS: S Ab |Sb AaAb |ab 检验 : 语言所有的句子均可由文法GS 推导出来 , 文法 GS 推导出来的所有终结符号串均为语言 L(GS) 的句子 . 例 6 设有文法GS: SS*S|S+S|(S)|i 该文法是否为二义文法？【解】该文法是二义文法，因为该文法存在句子i*i+i,该句子有两棵不同的语法树如图2所示 . 。S S * S S S (1) + i i i S S + S S S (2) * i i i 图 2 句子 i*i+i的语法树例 7 写一个文法，使其语言是奇数集，且每个奇数不以0 开头。【解】解题思路首先分析题意，本题是希望构造一个文法，由它产生的句子是奇数，并且不以0 开头，也就是说它的每个句子都是以1、3、5、7、9 中的某个数结尾。如果数字只有一位，则1、3、5、7、9 就满足要求，如果有多位，则要求第1 位不能是0，而中间有多少位，每位是什么数字（必须是数字）则没什么要求，因此，我们可以把这个文法分3部分来完成。分别用3 个非终结符来产生句子的第1 位、中间部分和最后一位。引入几个非终结符，其中，一个用作产生句子的开头，可以是19 之间的数，不包括0，一个用来产生句子的结尾，为奇数，另一个则用来产生以非0 整数开头后面跟任意多个数字的数字串，进行分解之后， 这个文法就很好写了。解答：G(S)：SCD D CCB A BA 0 A2 468D D1 3579 例 8 写一个上下文无关文法CFG ， 使其语言是能被5整除且不以0开头的无符号整数的集合。（如 5,10,15 ， . ）【解】解答：能被 5 整除的数从形式上看，是以 0,5 结尾的数字串。 题目要求的不以0 开头， 并要注意 0 不是该语言的句子。所求文法为：G(S)：SMF 5 F5 0 M MD N DN 0 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 5 页学而不思则惘，思而不学则殆N1 2345678 9 例 9 证明下面的文法是二义的：S SS S【解】解题思路：根据文法的二义性的定义，如果要证明该文法是二义的，必须找到一个句子，使得该句子具有两个不同的最右推导或两个不同的语法树。我们首先分析这个文法，根据我们对程序语言的了解， 不难发现， 这个文法应该是用来表示if .else . 结构的 （用“i ”代表“ if ”或语句集，“e”代表“else ” ） 。因此我们就要到if .else 结构中去找二义性。我们知道，程序语言一般都规定else 部分是和它前面离它最近的没有被匹配的的if语句进行匹配。 而上面的这个文法体现不出这种限制，因此我们可以找这样一个句子，在else 前面有两个if（如句子iiiei） ，else 和不同的if进行匹配时就会产生不同的语义。解答：考虑句子 iiiei，存在如下两个最右推导：S = iSeS = iSei = iiSei = iiiei S = iS = iiSeS = iiSei = iiiei 例 10 某程序设计语言的表达式由运算符1、 2、3、标识符、（、 ）组成，其中 1和2的优先级相同， 3的优先级低于 1、2的优先级， 优先级相同的运算符从右往左计算，可以用括号改变运算的顺序，则下述四种文法中哪一个可以描述上述的表达式文法？设 E为识别符号，终结符号集=1、2、 3、 （、 ） 、I ，非终结符号集=E、T、F。a.ET|E1T|E2T TF|T3F F(E)|I b. E T|T 1E|T2E TF|F3T F(E)|I c. E T|E3T TF|T1F|T2F F(E)|I d. E T|T 3 E TF|F1T|F2T F(E)|I 【解】 对于一个包含运算符的语言，运算符的结合顺序、运算符的优先级在文法中反映为递归的方向和推导（或规约）的先后，左递归表明左边的运算先处理，对应的运算符左结合；右递归表明右边的运算先处理，对应的运算符右结合。两个运算符连续出现，后推导出（或先被规约）的，表明其运算先被处理，因此优先级高；反之，先推导出（或后被规约）的，表明其运算后被处理，因此优先级低。题意要求： 1和2的优先级相同，3的优先级低于 1、2的优先级，因此3比1、2先推导出来，即应为图3 所示的四种情形。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 5 页学而不思则惘，思而不学则殆U U 3U V V (1) 1U U 3U V V (2) 1U U 3U V V (3) 2U U 3U V V (4) 2图 3 可能的文法推导顺序因此 a 和 b 不成立。又因为优先级相同的运算符从右往左计算，应采用右递归，即应为图4 所示的情形。U U 1V W V (1) 1U U 2V W V (2 2U U 3V W V (3) 3图 4 可能的文法递归结构故 c 不成立 , 应为 d。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 5 页
