07正则表达式与正则语言

《07正则表达式与正则语言》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、形式语言与自动机FormalLanguagesandAutomataTheory第六章上下文无关语言教师：胡春明、赵永望http://act.buaa.edu.cn/zhaoyw/course/flat_2012.html第六章上下文无关语言及其性质上下文无关文法的引入上下文无关文法的派生上下文无关文法的化简上下文无关文法的规范形式上下文无关语言的性质文法的乔姆斯基体系定义2.6：设G=(V,T,P,S)，P=，(VT)+，(VT)*1）G叫作0型文法，或短语结构文法（PSG）；对应地，L（G）叫0型语言或短语结构语言（PSL）、递归可枚

2、举集。2）如果对于∈P，均有

3、

4、≥

5、

6、，则称G为1型文法，或上下文有关文法（CSG）；对应地，L（G）叫1型语言或上下文有关语言(CSL).3）如果对于∈P，均有

7、

8、≥

9、

10、，并且∈V，则称G为2型文法，或上下文无关文法（CFG）；对应地，L（G）叫2型语言或上下文无关语言（CFL）。4）如果对于∈P，均具有以下形式：Aω，AωB；其中，A,B∈V，ω∈T+，则称G为3型文法，或正则文法（RG）；对应地，L（G）叫3型语言或正则语言（RL）。关于乔姆斯基麻省理工学院语言学的荣誉退休教授美国《科学》杂志评选出的2

11、0世纪全世界前10名最伟大的科学家中目前唯一的在世者http://zh.wikipedia.org/wiki/乔姆斯基http://baike.baidu.com/view/67358.htm上下文无关文法的提出问题提出：1、正则表达式：电子邮箱:zhaoyw@buaa.edu.cn(w+.)*w+@(w+.)+[A-Za-z]+URL:http://www.google.comhttps?://[-w.]+(:d+)?(/([w/_.]*)?)?IP地址:192.168.0.1(((d{1,2})

12、(1d{2})

13、(2[0-4]

14、d)

15、(25[0-5])).){3}((d{1,2})

16、(1d{2})

17、(2[0-4]d)

18、(25[0-5]))http://zh.wikipedia.org/wiki/正则表达式上下文无关文法的提出问题提出：2、正则语言描述模型能力有限，无法描述高级程序设计语言表达式中“良嵌套”的括号对、(begin…end)以及HTML中标记对…等配对符号序列的语法规则。正则文法：Aω，AωB例如，描述L（G）={(n1)n1(n2)n2…(nk)nk}的文法G：SS（S）

19、ε可证明G不是正则文法3、高级程序设计语言语法结构绝大多数都用上下

20、文无关文(CFG)描述。上下文无关文法的提出问题提出：4、BNF：Backusnormalform，巴克斯范式，又叫Backus-naurform。是CFG的一种特殊形式，在计算机中很常见，常用于表达语言的文法结构C、C++、Java等语言语法http://javacc.java.net/有很多语言的BNF范式上下文无关文法定义6-1：对于所有产生式A，均有

21、

22、≥

23、A

24、，并且，AV,(VT)，文法G=（V，T，P，S）被称为上下文无关文法。“上下文无关”：对于所有AV，如果A∈P，则无论A出现在句型的什么位置，都可以用自由替换A，无

25、需考虑A出现的上下文。第六章上下文无关语言及其性质上下文无关文法的引入上下文无关文法的派生上下文无关文法的化简上下文无关文法的规范形式上下文无关语言的性质上下文无关文法的派生定义6-2：设有CFGG=（V,T,P,S），G的派生树是满足如下条件的有序树：1、树的每个节点都有一个标记X，X∈V∪T∪ε。2、树的根节点的标记为S。3、如果X是一个非叶节点的标记，则有X∈V。4、如果一个非叶节点v的标记为A，v的子节点从左到右依此为v,v,…,12v,并且，它们分别标记为X,X,…,X，则有AX,X,…,X∈P。n12n12n5、如果一个节点v标记为ε，则v是

26、该树的叶节点，并且，v是其父节点的唯一子节点。别称：生成树、分析树(parsetree)、语法树(syntaxtree)派生树定义6-3：设有文法G的一棵派生树T，v1,v2是T的两个不同的顶点，如果存在顶点v，v至少有两个儿子，使得v1是v的较左儿子的后代，v2是v的较右儿子的后代，则称顶点v1在顶点v2的左边，顶点v2在顶点v1的右边。定义6-4：设有文法G的一棵派生树T，T的所有叶子顶点从左到右依次标记为X1,X2,…Xn，则称符号串X1X2…Xn是T的结果。G的结果为a的派生树，简称句型a的派生树文法、派生及派生树举例例：算术表达式的派生文法：派生

27、子树定义6-2的基础上去掉其第2条限制：设有CFGG=（V,T,P