编译原理——编译程序构造实践教程 教学课件 作者 张幸儿 戴新宇 201编译程序构造与实践教程第二章.ppt

《编译原理——编译程序构造实践教程 教学课件 作者 张幸儿 戴新宇 201编译程序构造与实践教程第二章.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第2章编译程序构造的基础知识两个基本问题:一是如何生成正确的程序，二是如何自动检查是正确的程序。围绕这两个问题，提出相关概念。本章讨论问题：文法和语言的概念和定义文法和语言的分类句型分析语法分析树的计算机生成简略回顾•对程序的理解程序是计算机执行的一系列指令；程序是计算任务的处理对象和处理规则的描述。•对程序设计语言的理解程序设计语言是程序的书写规范；程序设计语言的要素：一组记号(符号)和一组规则。程序设计语言程序是：程序设计语言之符号集合上的、按一定规则组成的符号串。新概念•语言是一切句子的集合；程序设计语言是一切程序的集合；把程序看做程

2、序设计语言的句子。•程序是(程序设计）语言的句子•如何系统地构造程序？或者，一般地，如何为一个(程序设计)语言生成句子？2.1符号串与符号串集合语言实际上是一个符号串集合；句子是一个语言之字母表上按一定规则构造的符号串。1.字母表:有穷非空的符号集合。例∑={a,b,c}B={0,1}C语言字母表={字母，数字，界限符}不同的语言有不同的字母表。字母表上的元素（即符号）组成符号串。2.符号串:由字母表上的符号所组成的有穷序列。⑴　字母表B={0，1}上的符号串：0,1,00,01,10,11,000,001,010,011,100,101,

3、110,111,0000,0001,0010,0100,1000,0011,…,ε（空串）字母表A={a,b,c}上的符号串：a,b,c,aa,ab,ac,ba,bb,bc,ca,cb,cc,aaa,aab,aac,baa,abcab,…,ε注意：顺序是重要的,ab≠baC语言字母表上的符号串？长度：

4、aabcaca

5、=7

6、ε

7、=0⑵子符号串若u=xvy，其中

8、v

9、≠0（

10、u

11、>=

12、v

13、），则v是u中的子符号串。例a+(b-c)/d中的子符号串:符号串的头与尾abc的头：a,ab,abc,Ɛabc的尾：c,bc,abc,Ɛx=t…(关注符号

14、串x之头t)x=…t(关注符号串x之尾t)x=…t…(关注t出现在符号串x中)⑶对符号串的运算联结（或并置）：x=aby=baxy=abbayx=baab对任何符号串x，有x=x=x。方幂：xn=xx…x(x自身联结n次)xn=xn-1x=xxn-1x0=Ɛx3=(ab)3=ababab

15、xy

16、=

17、x

18、+

19、y

20、

21、xn

22、=n

23、x

24、

25、x0

26、=0特例：若x字母表，则

27、xn

28、=n,因为

29、x

30、=1。3.符号串集合⑴概念一切元素都是某字母表上的符号串的集合。⑵表示法枚举法{1，11，111，1111}省略法{1，11，111，1111，┅}描述

31、法{1i

32、i≥1}或{x

33、x全由1组成,

34、x

35、≥1}一般，描述法形式：{x

36、x满足的条件}j注意：一定不能涉及含义,如{x

37、x=∑10i,j≥0}。i=0⑶对符号串集合的运算乘积：AB={xy

38、x∈A且y∈B}{1,0}{a,b,c}=?对任何符号串x有x=x=x，因此，{}A=A{}=A，但ØA=AØ=Ø。方幂：An=AA…A(n个A乘积）An=An-1A=AAn-1特例，字母表A的方幂，x∈An,

39、x

40、=n{1,0}3=?{1,0}n=?4.字母表的闭包与正闭包闭包A*=A0∪A1∪┅∪An∪┅{0，1，2}*正闭包A+=A1∪

41、┅∪An∪┅{0，1，2}+x∈A+,则

42、x

43、≥1x∈A*,则

44、x

45、≥0任何一个语言是其字母表之正闭包的真子集。如何找出此真子集？或说，如何找出其句子？2.2文法与语言文法规定语言中句子的构造规则。从文法生成的一切句子构成语言。2.2.1文法及其应用1.重写规则定义：U::=u规则表示法：通常的E::=E+TE::=T或E::=E+T

46、T术语：非终结符号，非终结符号集VN终结符号，终结符号集VT（VN∩VT=ØV=VN∪VT）单规则U::=V其中U,VVN,规则U::=ε2.文法文法G[Z]是非空有穷的重写规则集合，其中Z是识别符号（或

47、称开始符号），G是文法名。例G1[E]：E::=E+TE::=TT::=T*FT::=FF:=(E)F::=iG2[E]：E::=E+T

48、TT::=T*F

49、FF::=(E)F::=i文法的四要素：VN，VT，P，Z3.应用文法生成句子G[<变量说明>]:1.<变量说明>::=<类型符><变量名>2.<类型符>::=int6.<变量名>::=b3.<类型符>::=float7.<变量名>::=c4.<类型符>::=char8.<变量名>::=d5.<变量名>::=a例试以文法G[<变量说明>]为例，考察如何应用文法来生成句子。替换为<变量说明

50、>=><类型符><变量名>(规则1)=>int<变量名>(规则2)=>inta(规则5)替换为<变量说明>=><类型符><变量名>(规则1)=>float<变量名>(规则3)