第2章编形式语言概论ppt课件.ppt

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

1、编译原理1第2章形式语言概论2本讲主要内容及重点主要内容符号串；文法和语言的形式定义；文法的分类；语法树和二义性；文法的限制和变换重点文法和形式语言的基本概念，尤其是上下文无关文法与上下文无关语言3形式语言概论一个程序设计语言是一个记号系统，其完整的定义应包括语法和语义两个方面语言的语法是指一组规则，用它可以形成和产生一个合适的程序上下文无关文法语法只定义什么样的符号序列是合法的，与这些符号的含义毫无关系PASCAL语言中：A:=B+C合乎语法规则，A:=B+不合乎语法规则阐明语法的一个工具是文法，这是形式

2、语言理论的基本概念之一4形式语言概论主要内容几个概念字母表、符号、符号串等文法的定义文法的分类Chromsky对文法的分类文法和语言句型、句子分析树和二义性分析方法简介5几个概念字母表元素的非空有限集，记为。例：={a，b，c}字母表中的元素称为符号。例：a，b，c，字母表包含了语言中所允许出现的所有符号符号串符号的有穷序列。例：a,aa,ac,abc，..，无任何符号的符号串称为空符号串，记为ε6几个概念符号串运算符号串长度x为符号串,其长度

3、x

4、等于组成该符号串的符号个数。例：x=string，则

5、

6、x

7、=6,

8、ε

9、=0符号串连接若x、y是定义在Σ上的符号串，则xy称为x和y的连接，xy也是Σ上的符号串εx＝xε=x7几个概念符号串集合的乘积令A、B为符号串集合，定义符号串集合乘积AB＝{xy

10、x∈A,y∈B}符号串集合的方幂符号串集合A，定义A0={ε},A1=A,A2=AA,A3=A2A,…,An＝An-1A=AAn-1，n>0符号串集合的正闭包A+=A1∪A2∪…∪An…符号串集合的自反闭包A*={ε}∪A+8文法的直观描述什么是文法文法是定义或描述语法结构一组形式规则例句：Hegavemeabo

11、ok.英语中的基本语法规则：<句子><主语><谓语><间接宾语><直接宾语><主语><代词>

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

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

14、an

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

16、语>=>Hegave<间接宾语><直接宾语>=>Hegave<代词><直接宾语>=>Hegaveme<直接宾语>=>Hegaveme<冠词><名词>=>Hegavemea<名词>=>Hegavemeabook10用图形化方式表示这种推导，形成一颗语法分析树。<句子><主语><代词><冠词>Hea<谓语><间接宾语><直接宾语><动词>gave<代词>me<名词>book语法成分（在形式语言中又称“非终结符”）单词符号（在形式语言中又称“终结符号”)11上述定义英文句子的规则可以说就是一个上下文无关文法归纳起

17、来，一个上下文无关文法G包括四个组成部分：一组终结符号一组非终结符号一个开始符号一组产生式12文法形式化定义文法定义成一个四元组G=(VN,VT,S,P)VN:非空有限的非终结符集；VT:非空有限的终结符集；S:开始符号；P:产生式集合。其中，VN∩VT=Φ，S∈VNP中产生式一般形式为:Aα

18、β，其中A∈VN，α,β∈（VN∪VT）*13例2.9的文法文法G=(VN,VT,S,P)，其中VN={S}，VT={0，1}，P={S→0S1，S→01}。这里，非终结符集中只含一个元素S；终结符集由两个元素0和

19、1组成；有两条产生式；开始符号是S14一个文法的几种写法①G=({S,A}，{a,b}，P，S)　其中P：S→aAb　　　　A→ab　　　　A→aAb　　　　A→ε②G：S→aAb　　A→ab　　　A→aAb　　　A→ε③G[S]：A→abA→aAbA→εS→aAb④G[S]：A→ab

20、aAb

21、εS→aAb15文法的分类对产生式施加不同的限制得到不同类型的文法0型（无限制文法）:G=(VN,VT,S,P)规则形式：;(VNVT)+,(VNVT)*且中至少含有一个非终

22、结符1型（上下文有关）:规则有1,其中=γ1Aγ2,=γ1δγ2;AVN,δ(VNVT)+,γ1,γ2(VNVT)*.规则形式γ1Aγ2γ1δγ2;2型（上下文无关）:规则形式:Aδ,AVN，δ(VNVT)+3型（右线性和正规文法）:规则形式:AB或A（右线性）A,BVN,(VT)*.16左线性文法规则形式:AB或A（左线性）A,BVN,(