《编译原理》第2章文法和语言的形式定义.pdf

《《编译原理》第2章文法和语言的形式定义.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、编译原理武汉大学计算机学院编译原理课程组前述内容回顾·编译程序·编译方式与解释方式的根本区别·编译程序的工作过程·编译程序的结构·编译程序的组织方式·编译程序的构造本章内容简介·文法的形式定义·语言的形式定义·为语言构造文法·和语法分析有关的概念·文法的实用限制第2章文法和语言的形式定义编译程序使得高级语言源程序所描述的功能得以在计算机上实现。编译程序的设计者就是高级语言的实现者，源程序的编写者就是高级语言的使用者，他们必须遵循同样的准则——高级语言程序的构成规则，才能使写出的源程序能够被成功地翻译，文法就是描述的就是高级语言程序的构成规则。2.1

2、字母表与符号串1.1字母表字母表是元素的有穷非空的集合。字母表中的元素称为符号。例如{a，b，……，y，z}，{0，1}等。2.1字母表与符号串1.2符号串与符号串集合符号串是字母表中的符号所组成的任何有穷序列，通常用小写的字母表示。不包含任何符号的符号串为空串，记为ε。①符号串的长度②符号串的连接③符号串集合的乘积④符号串的方幂⑤符号串集合的方幂⑥符号串集合的正闭包A+⑦符号串集合的闭包A*2.2文法及其分类2.2.1文法1．终结符号：终结符号是组成语言的基本符号，如保留字、标识符、常数、运算符、界限符等。终结符号是语言的不可再分的基本符号。终结

3、符号形成的集合记为V。T2．非终结符号：非终结符号用来表示语言的语法成分（或语法范畴、语法单位），例如“赋值语句”。非终结符号所形成的集合记为V。NV∩V=∅TN2.2文法及其分类3．产生式产生式（规则）是一个有序对（α,β），通常写作：α→β（或α∷=β）其中α称为产生式的左部，β称为产生式的右部。α∈(V∪V)+，TNβ∈(V∪V)*。TN产生式是用来定义一个语法成分的。它描述了一个语法成分的形成规则。例如标识符的构成规则可描述为：<标识符>→<字母>

4、<标识符><字母>

5、<标识符><数字>假如有若干条规则有相同的左部，通常写作：α→β

6、β

7、…

8、

9、β12n2.2文法及其分类文法是产生式的有穷非空的集合。文法G是一个四元组，G[S]=（V，V，P，S）。TNV——终结符号集。TV——非终结符号集。NS——开始符号。至少要在一条产生式中作为左部出现。P——表示产生式的有穷非空的集合。例1定义标识符的文法G[<标识符>]=（{A,B,…,Y,Z,0,1,…,9}，{<标识符>,<字母>,<数字>}，P，<标识符>）P定义为：<标识符>→<字母>

10、<标识符><字母>

11、<标识符><数字><字母>→A

12、B

13、C

14、D

15、E

16、F

17、G

18、……

19、U

20、V

21、W

22、X

23、Y

24、Z<数字>→0

25、1

26、2

27、3

28、4

29、5

30、6

31、7

32、8

33、9

34、2.3文法的分类2.2.2文法分类乔姆斯基（Chomsky）把文法分成四种类型，即0型、1型、2型和3型。这四类文法的区别在于：对产生式规则的形式上施加不同的限制。2.3文法的分类0型文法α→βα∈(V∪V)+，β∈(V∪V)*NTNT1型文法α→β1≤

35、α

36、≤

37、β

38、α∈(V∪V)+，β∈(V∪V)*NTNT2型文法A→βA∈V，β∈(V∪V)*NNT3型文法A→a或A→aBA,B∈V，a∈VNT2.3文法的分类文法——举例例1.文法G[Z]：1G[Z]=({S，B，C，D}，{a，b，c}，P，S)，其中P为1S→aSBC

39、aBCCB→CDCD→

40、BDBD→BCaB→abbB→bbbC→bccC→ccα→β1≤

41、α

42、≤

43、β

44、，α∈(V∪V)+，β∈(V∪V)*NTNT2.3文法的分类文法——举例例2.文法G[Z]：2G[Z]=({Z，S，A，B，C}，{a，b，c}，P，Z)，2其中P为：Z→SCS→aAcA→aAc

45、bBbC→aCb

46、εB→bB

47、ε2型文法要求：A→βA∈V，β∈(V∪V)*NNT2.3文法的分类文法——举例例3.文法G[Z]：3G[Z]=({Z，U，V}，{0，1}，P，Z)，其中P为3Z→U0

48、V1U→Z1

49、1V→Z0

50、0左线性3型文法要求：A→a或A→Ba，A,B∈V

51、，a∈VNT2.3语言和语法树语法成分的构成可用文法予以描述。给定文法后，可以通过推导得到该文法所描述的语言。2.3语言和语法树——推导1.直接推导如果α→β是文法G的一条产生式，而γ，δ是(V∪V)*中任TN意一个符号串，则将α→β作用于符号串γαδ上得到符号串γβδ，称符号串γβδ是符号串γαδ的直接推导，记为γαδ⇒γβδ直接推导的逆过程称为直接归约，即由符号串γβδ可直接归约到γαδ。直接推导举例文法G[E]：E→E+T

52、TTE+T

53、TT→T*FT*F

54、FF

55、FF→（E）

56、i**TFTF⇒*T*FF2.3语言和语法树——推导2.推导设α、α

57、、…α（n>0）均为(V∪V)*中的符号串，且有01nTNα⇒α⇒α⇒…α⇒α012n-1n则称以上序列是长度为n的推导，