- 1 - 编译原理典型案例 1. 对于文法G[S] S →(L) S→aS S→a L →L,S L→S (1) 画出句型 (S,(a)) 的语法树； (2) 写出上述句型的所有短语、直接短语、句柄和素短语。 解答 这类题目重点考查语法树、推导、短语、直接短语、句柄和素短语等基本概念。在句型中寻找短语、直接短语、句柄的方法： (1) 画出句型对应的语法树。句型 (S,(a)) 的语法树如下图所示 (2) 在该语法树中寻找短语、直接短语、句柄。首先我们看短语的定义：令G 是一个文法，S 是文法的开始符，假设α,β,δ是文法G 的句型，如果有 S*αAδ 且 A +β 则称β是句型αβδ相对于非终结符A 的短语。如果有 Aβ，则称β是句型αβ δ相对于规则 A→β的直接短语。一个句型的最左直接短语称为该句型的句柄。根据短语的定义可知，以非终结符A 为根的子树的叶结点从左到右排列就是相对于非终结符A 的短语；如果子树只有两代，则短语就是直接短语；最左边的两代子树的所有叶结点从左到右排列，就是该句型的句柄。素短语是一个短语，它至少包含一个终结符，且除自身外不再包含其他素短语。处于句型最左边的素短语为最左素短语。 从语法树中我们可以找到： 短语：a，S，(a)， S, (a)， (S, (a)) 直接短语：a，S 句柄：S 素短语：a S ( L ) S ( L ) L , S S a - 2 - 2. 写一个上下文无关文法，使其语言能被5 整除且不以0 开头的无符号整数集合（如{5，10，15} ） 解答 能被5 整除的数从形式上看，是以0，5 结尾的数字串。题目要求不以0 开头，注意0不是该语言的句子。句子的结构分为三种： 其中，A 代表可以出现在个位上的数字，只能是0 或5； B 代表可以出现在开始位上的数字，除了0 以外，其他数字都可以； C 代表可以出现在中间位上的数字。0-9 所有数字都可以。 于是，A→ 0 | 5 B→ 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 C→ 0 | B 写文法时，先描述一位数结构，于是有产生式S → 5。对于两位数和多位数，都是以B开头和以A 结尾，于是有产生式S→ DA。用非终结符D 推导出两位数和多位数中除个位数字以外的数字。对与多位数，由于中间位可以是许多位，必须使用递归技术来描述其结构。于是有产生式： D→ DC D→ B 因此，所求文法为G[S]： S → 5 S→ DA D→ DC D→ B A→ 0 | 5 B→ 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 C...
