编译原理典型例题

《编译原理典型例题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、编译原理典型案例1.对于文法G[S]S→(L)S→aSS→aL→L,SL→S(1)画出句型(S,(a))的语法树；(2)写出上述句型的所有短语、直接短语、句柄和素短语。解答这类题目重点考查语法树、推导、短语、直接短语、句柄和素短语等基本概念。在句型中寻找短语、直接短语、句柄的方法：(1)画出句型对应的语法树。句型(S,(a))的语法树如下图所示S(L)S(L)L,SSa(2)在该语法树中寻找短语、直接短语、句柄。首先我们看短语的定义：令G是一个文法，S是文法的开始符，假设α,β,δ是文法G的句型，如果有S*ÞαAδ且A+Þβ则称β是句型αβδ相对于非终结符A的短语

2、。如果有AÞβ，则称β是句型αβδ相对于规则A→β的直接短语。一个句型的最左直接短语称为该句型的句柄。根据短语的定义可知，以非终结符A为根的子树的叶结点从左到右排列就是相对于非终结符A的短语；如果子树只有两代，则短语就是直接短语；最左边的两代子树的所有叶结点从左到右排列，就是该句型的句柄。素短语是一个短语，它至少包含一个终结符，且除自身外不再包含其他素短语。处于句型最左边的素短语为最左素短语。从语法树中我们可以找到：短语：a，S，(a)，S,(a)，(S,(a))直接短语：a，S句柄：S素短语：a-16-1.写一个上下文无关文法，使其语言能被5整除且不以0开头的无

3、符号整数集合（如{5，10，15}）解答能被5整除的数从形式上看，是以0，5结尾的数字串。题目要求不以0开头，注意0不是该语言的句子。句子的结构分为三种：5BACB…CA一位数两位数多位数其中，A代表可以出现在个位上的数字，只能是0或5；B代表可以出现在开始位上的数字，除了0以外，其他数字都可以；C代表可以出现在中间位上的数字。0-9所有数字都可以。于是，A→0

4、5B→1

5、2

6、3

7、4

8、5

9、6

10、7

11、8

12、9C→0

13、B写文法时，先描述一位数结构，于是有产生式S→5。对于两位数和多位数，都是以B开头和以A结尾，于是有产生式S→DA。用非终结符D推导出两位数和多位数中除个位

14、数字以外的数字。对与多位数，由于中间位可以是许多位，必须使用递归技术来描述其结构。于是有产生式：D→DCD→B因此，所求文法为G[S]：S→5S→DAD→DCD→BA→0

15、5B→1

16、2

17、3

18、4

19、5

20、6

21、7

22、8

23、9C→0

24、B2.写一个文法G,使其语言为不以0开头的偶数集。解答不以0开头的偶数集数字的结构分为三种：一位数、两位数和多位数。-16-ACBDC…DB一位数两位数多位数其中，A代表可以出现在个位上的数字，可以是2，4，6，8，但不能是0；B代表可以出现在开始位上的数字，除了0以外，其他数字都可以；C代表可以出现在中间位上的数字。0-9所有数字都可以。于是，A

25、→2

26、4

27、6

28、8B→0

29、AC→1

30、3

31、5

32、7

33、9

34、AD→0

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

36、CEE→CE

37、BA→2

38、4

39、6

40、8B→0

41、AC→1

42、3

43、5

44、7

45、9

46、AD→0

47、C4.考虑下面的程序：    … procedureP(x,y,z);beginy:=y+1;z:=z+xend;begina:=2

48、;b:=3;P(a+b,a,a);printa-16-end.试问，若参数传递的方式分别采用传值、传地址、得结果和传名时，程序执行后输出a的值是什么?解答所谓传值是调用段把实在参数的值计算出来，被调用段把这些值抄进自己的形式参数中，像使用局部名一样使用这些形式单元。对形式参数的任何运算不影响实参的值。上面过程P调用的的参数传递过程如下图所示。过程调用前过程调用后a+b=5a=2x=5y=2b=3z=3但过程P无法改变实参a的值。因此，程序执行后输出a的值是2。所谓传地址是把实在参数的地址传递给相应的形式参数。在过程段中每个形式参数都有一个相应的单元，称为形式单元。

49、形式单元将用来存放相应实在参数的地址。过程体对形式参数的任何引用或赋值都被处理成对形式单元的间接访问。过程调用前过程调用后a+b=5a=2xyb=3z过程调用后，形参x的形式单元指向存a+b值的临时变量的地址，形参y的形式单元指向变量a的地址，形参z的形式单元指向变量b的地址。形参通过指针可以间接访问实参。执行y:=y+1;后，实在参数的变化：-16-a+b=5a=3xyb=3z执行z:=z+x;后，实参的变化：a+b=5a=8xyb=3z因此，程序执行后输出a的值是8。所谓得结果是每个形式参数对应两个单元，第一个单元存放实参的地址，第二个单元存放实参的值。在过程

50、体中对形参