woaidongmao

文章均收录自他人博客,但不喜标题前加-[转贴],因其丑陋,见谅!~
随笔 - 1469, 文章 - 0, 评论 - 661, 引用 - 0
数据加载中……

关于正则表达式、正则文法、NFA、LR(1)

昨天和Sumtec谈到自动机和语法分析,一下子脑子有点混乱,把一些概念搞混了,看了半天清华的编译书也没有整明白...今天早上起来看了《离散数学及其应用》里的自动机一部分,才厘清了头绪。还是外国人的书讲得清楚一点。 clip_image001

 

昨天主要是把NFA和语法分析中的LL(1) LR(1)搞混了。事实上LL(1)分析也好LR(1)分析也好,使用的是一个基于下推自动机的计算模型,而不是有限自动机。下推自动机的计算能力要比有限自动机强。

 

其次就是NFADFA的计算能力确实是等价的,也就是对于任意一个NFA都可以找到一个与之等价的DFA(可以使用子集法来构造这样一个DFA)

为了说明有限自动机与LL(1) LR(1)等分析法的关系,先概述一下文法的分类

 

文法分为四类:

(1)短语文法(0型文法)

(2)上下文相关文法(1型文法)

(3)上下文无关文法(2型文法)

(4)正规()文法(3型文法)

 

上面四种文法有包含的关系,1型文法是0型文法的一个子集,2型文法是1型文法的一个子集,,3型文法是2型文法的一个子集。

 

我们主要研究2型和3型方法。

 

3型文法(正则文法)与正则表达式(Regular Expression)是等价的,任意一个正则文法总是可以转化成一个等价的正则表达式。同时正则表达式与有限自动机是等价的。一个能由有限自动机识别的语言,必然可以用正则表达式来表示,而一个用正则表达式表示的语言一定可以用一个有限自动机来识别。

 

但是正则文法不足以描述程序设计语言(比如,不能用正则表达式定义带有括号的数学表达式),现在流行的程序设计语言如C#, java等都是用2型文法,也就是上下文无关文法来定义的。因此有限自动机没有能力来识别程序设计语言(最后我会举个例子)。因此提出来下推自动机的模型。下推自动机具有限自动机的所有部件,如状态、状态转移表等,同时它比有限自动机多一个堆栈,常称为计算栈。下推自动机可以根据情况将终结符或者非终结符压入栈,或者弹出栈。

 

LL(1)LR(1)等分析法就是用来分析上下文无关文法的,基于下推自动机的模型。这也是为什么介绍语法分析时,所有的书都会说一个基于LR(1)分析法的预测分析器,都会有三部分组成:状态转移表、控制器和计算栈。而所谓的移进与归约就是入栈与出栈的问题。

 

最后,举一个例子(好象大家都睡着了 -_-b)

 

先给出一个文法:

 

S->0S1 | 01

 

其中01是终结符。

 

这样一个文法描述的语言其实就是n0加上相等数量的n1,这里n是某个整数。

 

这个文法是一个上下文无关文法,但不是一个正则文法。所以说我们没办法写出一个正则表达式来描述这样一个语言。等于一个能识别这个文法中的任意句子的NFA,我们总能找到这样一个句子,它不是由该文法所定义的,却能被这个NFA接受。换句话说,任意NFA都不能用来判断某个句子是不是由以上这个文法所定义。说得实际一点,如果要求写一个着色程序,输入的文件是一串01组成的序列,要求把其中n0n1的序列用红色着色,而其它用黑色的话,我们就不能光用正则表达式匹配来完成这一任务了。

 

如果上面这个例子还比较抽象的话,那么对于“带有括号的数学表达式”这样一个语言,也是没有办法用正则表达式来进行匹配的。因为描述“带有括号的数学表达式”的文法,也不是一个正则文法,因为其中带有类似:

F->(E)

这样的部分。

而正则文法要求所有的产生式都必须是A->aB或者A->a这样的形式的(其中AB是非终结符,a是终结符)

 

posted on 2009-09-29 13:54 肥仔 阅读(766) 评论(0)  编辑 收藏 引用 所属分类: 状态机 & 自动机 & 形式语言


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理