第二章文法与语言ppt课件.ppt

《第二章文法与语言ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编译原理CompilerPrinciples2013年9月闫雷鸣第二章文法与语言讨论问题：文法和语言的概念和定义文法和语言的分类文法等价变换句型分析简单回顾对程序的理解程序是计算机执行的一系列指令；程序是计算任务的处理对象和处理规则的描述。•对程序设计语言的理解程序设计语言是程序的书写规范；程序设计语言的要素：一组记号(符号)和一组规则。程序设计语言程序是程序设计语言之符号集合上的、按一定规则组成的符号串。•语言是一切句子的集合；程序设计语言是一切程序的集合；把程序看做程序设计语言的句子。•程序是(程序设计）语言的句子•如何系统地构造程序？或者，一般地，如何为一个(程序设计)语言生

2、成句子？2.1符号串与符号串集合语言实际上是一个符号串集合；文法规定语言中句子的构造规则。句子是一个语言之字母表上按一定规则构造的符号串。2.1.1字母表字母表:有穷非空的符号集合。例A={a,b,c}∑={0,1}C语言字母表={字母，数字，界限符}不同的语言有不同的字母表。字母表上的元素（即符号）组成符号串。2.1.2符号串:1.符号串及其长度符号串:由字母表上的符号所组成的有穷序列。字母表A={a,b,c}上的符号串：a,b,c,ab,ba,aaa,aab,baa,abcab,ε(空串)注意：顺序是重要的,ab≠baC语言字母表上的符号串？长度：

3、aabcaca

4、=7

5、ε

6、=

7、02.子符号串若u=xvy，其中

8、v

9、≠0（

10、u

11、>=

12、v

13、）则v是u中的子符号串。（非空符号串）例a+(b-c)/d中的子符号串3.符号串的头与尾（前缀、后缀）abc的头：a,ab,abc,Ɛx=t…abc的尾：c,bc,abc,Ɛx=…t4.对符号串的运算联结（或并置）：x=aby=baxy=abbayx=baab对任何符号串x，有x=x=x。方幂：xn=xx…x(x自身联结n次)xn=xn-1x=xxn-1x0=Ɛx3=(ab)3=ababab

14、xy

15、=

16、x

17、+

18、y

19、

20、xn

21、=n

22、x

23、

24、x0

25、=02.1.3符号串集合（语言）1.符号串集合的定义1)它是一切元素都是某字母表

26、上的符号串的集合。2)表示法枚举法{1，11，111，1111}省略法{1，11，111，1111，┅}描述法{1i

27、i≥1}或{x

28、x全由1组成,

29、x

30、≥1}注意：一定不能涉及含义,如{x

31、x=∑10i}。字母表∑上的一个语言就是∑上的一些符号串组成的集合。空集ф是一个语言，仅含一个空符号串集合{ф}也是一个语言。特别需要指出的是，Ɛ和{Ɛ}是不同的语言。2.对符号串集合的运算乘积：AB={xy

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

33、=AAn-1特例，字母表A的方幂，x∈An,

34、x

35、=n{1,0}3=?{1,0}n=?3.字母表的闭包与正闭包闭包A*=A0∪A1∪┅∪An∪┅{0，1，2}*正闭包A+=A1∪┅∪An∪┅=A*-{}{0，1，2}+x∈A+,则

36、x

37、>=1x∈A*,则

38、x

39、>=0任何一个语言是其字母表之正闭包的真子集。如何找出此真子集？或说，如何找出其句子？2.2文法与语言的形式定义2.2.1文法的形式定义1.重写规则（产生式规则）定义：有序对（U，u)或U::=uA→α（或A::=α）其中，A是一个符号，称为产生式规则的左部，而α是有穷非空符号串，称为产生式规则的右部，“→”和“::=”表示

40、“定义为”或“由……组合成的”或“生成”，其含义是左部符号用右部的符号串定义或左部符号生成右部符号串。产生式规则可合写，如：A→α和A→β可写为A→α

41、β1.重写规则（产生式规则）规则表示法：通常的E::=E+TE::=T或E::=E+T

42、T扩充的E::=T{+T}术语：非终结符号，非终结符号集VN终结符号，（不会出现在规则左部）终结符号集VT（VN∩VT=ØV=VN∪VT）单规则：右部是单个非终结符{}用于指定重复次数<标识符>::=<字母>{<字母数字>}05[]内中符号至多出现一次<整数>::=[+

43、-]<数字>{<数字>}()提公因子E::=E+T

44、E-T可改写为E::=E

45、(+

46、-)T16规则构造的例子C语言标识符的规则：<标识符>::=<字母下划线><标识符>::=<标识符><字母下划线><标识符>::=<标识符><数字><字母下划线>::=A

47、…

48、Z<字母下划线>::=a

49、…

50、z<字母下划线>::=_<数字>::=0

51、…

52、917用规则产生句子的例子如：用标识符产生式规则产生句子area.<标识符><标识符><字母下划线><标识符>a<标识符><字母下划线>a<标识符>ea<标识符><字母下划线>ea<标识符>rea<字