《上下文无关文法》PPT课件

《《上下文无关文法》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章上下文无关文法研究内容上下文无关文法概述下推自动机非上下文无关语言2021/9/161上下文无关文法的应用上下文无关文法的重要性如下表达能力强大足于表示大多数程序设计语言语法可以构造有效的分析算法以检验一个给定的字符串是否由某个上下文无关文法产生上下文无关语言在实践中的重要意义定义程序设计语言：例如BNF范式描述文档格式：例如XML，HTML使语法分析概念形式化简化程序设计语言的翻译：例如设计语法分析器2021/9/162上下文无关文法的应用语法分析程序语法分析程序生成器超文本标记语言可扩展标记语言2021/9/163文法的形式定义文法G是一个

2、四元组：G=(VN,VT,P,Z)，其中：VN是非终结符的有穷集合，也称为语法单元、语法成分或语法范畴，可分解为若干非终结符或终结符VT是终结符的有穷集合，是基本符号，不能再分解V=VN∪VT称为字汇表(字母表)，VN∩VT=Ф。Z是开始符，Z∈VN，P是规则式（产生式）有穷集合规则式形如：x→y，其中x∈V*VNV*,称为规则式的左部；y∈V*称为右部。2021/9/164文法的类型Chomsky将文法分为四种类型：０型文法（短语结构文法，可压缩的上下文有关文法），最一般的文法，对规则无限制u→wu∈V*VNV*w∈V*（可为ε）相应的自动机是图灵

3、机１型文法（上下文有关文法,不可压缩的上下文有关文法），对规则有些限制xuy→xwyx和y就是上下文，x,y∈V*，u∈V*∪VN,w∈V+（不可为ε），这些限制也可以写成：u→w

4、u

5、≤

6、w

7、意为串的长度不可压缩相应的自动机是线性界限自动机2021/9/165文法的类型２型文法（上下文无关文法，简单短语结构文法），对规则的限制A→wA∈VNw∈V*（可为ε）２型文法与字典定义形式相近（一个字用另一些字定义），与人们习惯一致。相应的自动机是下推自动机，与BNF等价。左部均为非终结符2021/9/166文法的类型３型文法（正规文法，正则文法），规则是线

8、性的，其中左线性：A→BaA→a右线性：A→aBA→aA，B∈VN,a∈VT相应的自动机是有限自动机。在程序设计语言中，单词符号用３型文法定义。2021/9/167上下文无关文法概述上下文无关文法是把变量转化为原语符号串的一组规则，即变量变量或原语符号组成的串上下文无关文法最早被用来描述自然语言的一些规则，在计算机语言学中，Backus范式可以用来表示一种程序设计语言的各种规定，例如字符集、标识字符集、标识符以及各种语句的格式等2021/9/168上下文无关文法概述文法G=(V，，R，S)被称为是上下文无关文法或2型文法。如果对于αβ∈R，均

9、有

10、β

11、≥

12、α

13、，并且α∈V成立。关键：对于A∈V，如果Aβ∈P，则无论A出现在句型的任何位置，我们都可以将A替换成β，而不考虑A的上下文。L(G)叫做2型语言(type2language)或者上下文无关语言(contextfreelanguage,CFL)。2021/9/169上下文无关文法(例子)构造上下文无关文法G，它所产生的语言为字母表{0,1}上所有回文全体，即L(G)={w∈{0,1}*

14、w=wR}G=({S},{0,1};R,S)，其中R：S

15、1

16、0；SOSO

17、1S1分别构造如下三个语言的上下文无关文法L1={anbn

18、n≥1

19、}；L2={anbncmdm

20、n,m≥1}L3={anbmcmdn

21、n,m≥1}G1=({S},{a,b};R1,S)，其中R1：SaSb

22、abG2=({S,A,B},{a,b,c,d};R2,S)，其中R2：SAB，A→aAb

23、ab，BcBd

24、cdG2=({S,A},{a,b,c,d};R3,S)，其中R2：SaSd

25、aAd，A→bAc

26、bc2021/9/1610上下文无关文法的形式化定义定义2.1上下文无关文法是一个4元组G=(V,,R,S)V:一个有穷集，称为变元集:一个有穷集，称为终结符集，(V=)R:有穷规则集，V(V

27、)*SV:起始变元文法G的语言可以表示为L(G)={w*

28、S*w}规则左边是单个变元符号，右边的所有符号属于集合V∪2021/9/1611上下文无关文法的推导和派生设u，v和ω是由变元及终结符构成的字符串，Aω是文法的一条规则，称uAv生成uωv，记作uAv⇒uωv。如果u=v，或者存在序列u1，u2，，uk，使得u⇒u1⇒u2⇒⇒uk⇒v其中k≥0，则称u派生v，记作u⇒*v。该文法的语言是{ω∈∑*

29、S⇒*ω}2021/9/1612上下文无关文法的形式化定义在描述一个文法时，通常只写出它的规则出现在规则左边的符号都是变元，其余的

30、符号都是终结符，按照惯例，起始变元是第一条规则左边的变元2021/9/1613上下文无关文法举例例题2.2：