编译原理第2章文法和语言.ppt

《编译原理第2章文法和语言.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基本概念字母表、符号、符号串、闭包等文法的定义文法的分类Chromsky对文法的分类文法和语言推导、归约、句型、句子、语言语法分析树和二义性第二章文法和语言2.1文法和语言的定义例句：inti=0;包含字母i,n,t,=,0,;,所有字母形成字母表；符号串，如int定义2.1字母表：字母表∑是符号元素的非空有限集合。定义2.2符号（字符）：字母表中的元素。定义2.3符号串（字符串）：字母表中的符号所组成的任何有穷序列。如字母表∑={a,b}，则a,b是字母表∑中的元素，a,b,aa,ab,…都是符号串。空符号串：不含任何符号的符号串，用ε表示。字母表，

2、符号，符号串2.1文法和语言的定义定义2.4符号串x和y的连接：指x和y的符号按先后顺序排列在一起组成的新的符号串，用xy表示。例：若∑={a,b},x=ab,y=ba,则xy=abba,yx=baab。注意：（1）xy≠yx；（2）εx=xε=x。定义2.5符号串的长度：指符号串中符号的个数。例：

3、ab

4、=2,

5、aabb

6、=4,

7、ε

8、=0。字符串连接、字符串长度2.1文法和语言的定义定义2.6符号串的前缀和后缀：分别指符号串的左部和右部任意字符串。例：ab的前缀有ε、a、ab；后缀有ε、b、ab。定义2.7符号串集合的乘积：设A、B是字母表∑上的符号

9、串集合，则定义A与B的乘积：AB={xy

10、x∈A，y∈B}。例：设∑={a，b，c，d}，令A={aa,bb}，B={cc,dd},则AB={aacc,aadd,bbcc,bbdd},BA={ccaa,ccbb,ddaa,ddbb}。显然AB≠BA定义空集合：Φ={ε}，有{ε}A=A{ε}=A。前缀、后缀、乘积2.1文法和语言的定义定义2.8符号串的方幂：设x是符号串，则：x0=ε,x1=x,x2=xx,…,xn=x…x(n个)定义2.9符号串集合A的方幂：A0={ε},A1=A,A2=AA,…,An=A…A(n个A)A的正闭包：A+=A1∪A2∪…

11、A的闭包：A*=A0∪A1∪A2∪…显然：A*=A0∪A+,A+=AA*问题：A={0,1},则A+表示的集合意义？方幂、正闭包、闭包2.1文法和语言的定义什么是文法文法是定义或描述语法结构的一组形式规则，是规则的非空有穷集合规则又称为重写规则，产生式或生成式，每个产生式为αβ或α::=β，α是某字母表A的正闭包A+的一个符号称为规则的左部；β是A*中的一个符号，称为规则的右部。α与β的区别？文法2.1文法和语言的定义什么是文法文法是定义或描述语法结构一组形式规则，是规则的非空又穷集合规则又称为重写规则，产生式或生成式，每个产生式为αβ或α::=β

12、，α是某字母表A的正闭包A+的一个符号称为规则的左部；β是A*中的一个符号，称为规则的右部。α与β的区别？例句：Hegavemeabook.英语中的基本语法规则：<句子><主语><谓语><间接宾语><直接宾语><主语><代词>

13、<名词><谓语><动词><间接宾语><代词><直接宾语><冠词><名词><代词>He

14、me<名词>book<动词>gave<冠词>a

15、an

16、the例句：Hegavemeabook.根据上述语法规则对例句进行分析，可推出该例句。<句子>=><主语><谓语><间接宾语><直接宾语>=><代词><谓语><间接宾语><

17、直接宾语>=>He<谓语><间接宾语><直接宾语>=>He<动词><间接宾语><直接宾语>=>Hegave<间接宾语><直接宾语>=>Hegave<代词><直接宾语>=>Hegaveme<直接宾语>=>Hegaveme<冠词><名词>=>Hegavemea<名词>=>Hegavemeabook文法2.1文法和语言的定义inti=0;i=i+1;<程序>{<句子>}+<句子><声明语句>

18、<赋值语句>

19、……<声明语句><数据类型>{<变量>[=<常量>]}+<赋值语句><变量>=<表达式><变量>(a

20、…

21、z

22、A

23、…

24、Z

25、_)(a

26、…

27、z

28、A

29、

30、…

31、Z

32、_

33、0

34、…

35、9)<数据类型>int

36、char

37、………文法包含的要素：终极字符集：如inti非终极字符集：如<程序>、<句子>产生式：如<程序>{<句子>}+开始符号：<程序>文法2.1文法和语言的定义定义2.10文法是一个四元组：G[S]=(VN,VT,P,S),其中：VN：非终极符集合（变量集）；VT：终极符集合；P：产生式集合，每个产生式为αβ或α::=β，设V=VN∪VT，则α∈V*VNV*，β∈V*；S：开始符号。注意：VN,VT,P三个集合均为非空有穷集合VN∪VT=ФV=VN∪VT表示文法G的字母表或词汇表例2.1G=({N}

38、,{0,1},{N0N,N1N,N0,N1},N)，其中：VN={N};VT={0,1