《编译原理：第二章作业》由会员分享，可在线阅读，更多相关《编译原理：第二章作业（7页珍藏版）》请在装配图网上搜索。
1、第二章第二章 文法和语言文法和语言11.一个上下文无关文法生成句子一个上下文无关文法生成句子abbaa的推导树如下：的推导树如下：（1）给出该句子相应的最左推导，最右推导。）给出该句子相应的最左推导，最右推导。SABSaS B BA ab ba最左推导：最左推导：S=ABS=aBS=aSBBS=aBBS=abBS=abbS=abbAa=abbaa最右推导：最右推导：S=ABS=ABAa=ABaa=ASBBaa=ASBbaa=ASbbaa=Abbaa=abbaa(2)给出该文法的产生式集合给出该文法的产生式集合P可能有哪些元素？可能有哪些元素？SABSaS B BA ab baS-ABS|AaA
2、-aB-SBB|b(3)找出该句子的所有短语，简单短语，句柄找出该句子的所有短语，简单短语，句柄由语法树求短语、直接短语、句柄由语法树求短语、直接短语、句柄语法树子树的叶节点从左到右构成的符号串（相对语法树子树的叶节点从左到右构成的符号串（相对于子树的根）即是此语法树所描述的句型的短语；于子树的根）即是此语法树所描述的句型的短语；简单子树（只有父子两代）的叶节点从左到右构成简单子树（只有父子两代）的叶节点从左到右构成的符号串即是直接短语；的符号串即是直接短语；最左简单子树的叶节点构成的符号串即是句柄。最左简单子树的叶节点构成的符号串即是句柄。短语有：短语有：a1,b1,b2,a2,b1b2,a
3、2a3,a1b1b2a2a3简单短语有：简单短语有：a1,b1,b2,a2句柄是：句柄是：a1SABSa1S B BA a3b1b2a2短语的三个条件：短语的三个条件：是文法的一个句型；是文法的一个句型；S=*A;A=+是句型是句型相对于非终结符相对于非终结符A的的短语短语a1b1b2a2a315.分以下两种情形，各写一个文法，使其语分以下两种情形，各写一个文法，使其语言是十进制非负偶数的集合：言是十进制非负偶数的集合：（1）允许）允许0打头；打头；S-Even|Num EvenNum-Digit|Num Digit Digit-0|1|2|3|4|5|6|7|8|9Even-0|2|4|6|815.分以下两种情形，各写一个文法，使其语分以下两种情形，各写一个文法，使其语言是十进制非负偶数的集合：言是十进制非负偶数的集合：（2）不允许）不允许0打头。打头。S-Even|Num EvenNum-Nonzero|Num DigitNonzero-1|2|3|4|5|6|7|8|9Digit-0|1|2|3|4|5|6|7|8|9Even-0|2|4|6|8
编译原理：第二章作业
