内容发布更新时间 : 2024/12/25 17:55:07星期一 下面是文章的全部内容请认真阅读。

如对您有帮助，欢迎下载支持，谢谢！

编译原理典型案例

1. 对于文法G[S] S →(L) S→aS S→a L →L,S L→S

(1) 画出句型 (S,(a)) 的语法树；

(2) 写出上述句型的所有短语、直接短语、句柄和素短语。 解答

这类题目重点考查语法树、推导、短语、直接短语、句柄和素短语等基本概念。在句型中寻找短语、直接短语、句柄的方法：

(1) 画出句型对应的语法树。句型 (S,(a)) 的语法树如下图所示

S ( L ) L , S S ( L ) 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

1

如对您有帮助，欢迎下载支持，谢谢！

2. 写一个上下文无关文法，使其语言能被5整除且不以0开头的无符号整数集合（如{5，10，15}） 解答

能被5整除的数从形式上看，是以0，5结尾的数字串。题目要求不以0开头，注意0不是该语言的句子。句子的结构分为三种：

5 一位数 B A 两位数 B C … C A 多位数

其中，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→0 | B

3. 写一个文法G, 使其语言为 不以0开头的偶数集。 解答

不以0开头的偶数集数字的结构分为三种：一位数、两位数和多位数。

2

如对您有帮助，欢迎下载支持，谢谢！

A 一位数 C B 两位数 C D … D B 多位数

其中，A代表可以出现在个位上的数字，可以是2，4，6，8，但不能是0；

B代表可以出现在开始位上的数字，除了0以外，其他数字都可以； C代表可以出现在中间位上的数字。0-9所有数字都可以。 于是，A→2 | 4 | 6 | 8 B→0 | A

C→1 | 3 | 5 | 7 | 9 | A

D→0 | C

写文法时，先描述一位数结构，于是有产生式S →A。对于两位数和多位数，都是以C开头和以B结尾，于是有产生式S→CE。用非终结符E推导出两位数和多位数中除个位数字以外的数字。对与多位数，由于中间位可以是许多位，必须使用递归技术来描述其结构。于是有产生式： E→CE E→B

因此，所求文法为G(S)：

S→A | CE E→CE | B

A→2 | 4 | 6 | 8 B→0 | A

C→1 | 3 | 5 | 7 | 9 | A D→0 | C

4. 考虑下面的程序： …

procedure P(x, y, z);

begin y:=y+1; z:=z+x end; begin a:=2; b:=3;

3