Permalink
Switch branches/tags
Nothing to show
Find file
Fetching contributors…
Cannot retrieve contributors at this time
775 lines (752 sloc) 32 KB
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<meta HTTP-EQUIV="content-type" CONTENT="text/html; charset=gb2312">
<head>
<title>report - 编译技术课程设计报告:从正则表达式到 DFA</title>
<link rel="stylesheet" href="images/Active.css" type="text/css" />
<link rev="made" href="mailto:" />
</head>
<body>
<table border="0" width="100%" cellspacing="0" cellpadding="3">
<tr><td class="block" valign="middle">
<big><strong><span class="block">&nbsp;report - 编译技术课程设计报告:从正则表达式到 DFA</span></strong></big>
</td></tr>
</table>
<p><a name="__index__"></a></p>
<!-- INDEX BEGIN -->
<ul>
<li><a href="#NAME">NAME</a></li>
<li><a href="#AUTHOR">AUTHOR</a></li>
<li><a href="#VERSION">VERSION</a></li>
<li><a href="#DESCRIPTION">DESCRIPTION</a></li>
<li><a href="#DOWNLOAD">DOWNLOAD</a></li>
<li><a href="#Modules">Modules</a></li>
<ul>
<li><a href="#re3a3aParser">re::Parser</a></li>
<li><a href="#re3a3are">re::re</a></li>
<li><a href="#re3a3aXML">re::XML</a></li>
<li><a href="#re3a3aNFA">re::NFA</a></li>
<li><a href="#re3a3aDFA">re::DFA</a></li>
<li><a href="#re3a3aDFA3a3aMin">re::DFA::Min</a></li>
<li><a href="#re3a3aGraph">re::Graph</a></li>
<li><a href="#re3a3aDFA3a3aPerl">re::DFA::Perl</a></li>
<li><a href="#re3a3aDFA3a3aC">re::DFA::C</a></li>
<li><a href="#re3a3aDFA3a3aEval">re::DFA::Eval</a></li>
</ul>
<li><a href="#Utilities">Utilities</a></li>
<ul>
<li><a href="#re2re">re2re</a></li>
<li><a href="#re2xml">re2xml</a></li>
<li><a href="#re2nfa">re2nfa</a></li>
<li><a href="#re2dfa">re2dfa</a></li>
<li><a href="#re2pl">re2pl</a></li>
<li><a href="#re2c">re2c</a></li>
<li><a href="#evalre">evalre</a></li>
</ul>
<li><a href="#Test20Suit">Test Suit</a></li>
<li><a href="#Important20Issues">Important Issues</a></li>
<ul>
<li><a href="#Nullable20Regexes">Nullable Regexes</a></li>
<li><a href="#Error20State">Error State</a></li>
<li><a href="#Regex20Ambiguity">Regex Ambiguity</a></li>
</ul>
<li><a href="#re2dDFA20versus20JFLAP">re-DFA versus JFLAP</a></li>
<li><a href="#TODO">TODO</a></li>
<li><a href="#COPYRIGHT">COPYRIGHT</a></li>
</ul>
<!-- INDEX END -->
<hr />
<p>
</p>
<h1><a name="NAME">NAME</a></h1>
<p>report - 编译技术课程设计报告:从正则表达式到 DFA</p>
<p>
</p>
<hr />
<h1><a name="AUTHOR">AUTHOR</a></h1>
<p>章亦春 &lt;<a href="mailto:agentzh@gmail.com">agentzh@gmail.com</a>&gt;</p>
<p>3030602110 计算机0304班</p>
<p>计算机科学与通信工程学院 江苏大学</p>
<p>
</p>
<hr />
<h1><a name="VERSION">VERSION</a></h1>
<pre>
Maintainer: Agent Zhang &lt;agentzh@gmail.com&gt;
Date: 30 June 2006
Last Modified: 30 June 2006
Version: 0.01</pre>
<p>
</p>
<hr />
<h1><a name="DESCRIPTION">DESCRIPTION</a></h1>
<p>本文档描述了我的编译技术课程设计的一个项目,re-DFA. 该项目的目标是实现一个简单的正则
表达式编译器,能够解析基本的正则表达式,生成对应的 NFA 和 DFA(可以生成漂亮的 PNG 图
片),并从最小化以后的 DFA 生成功能等价的目标代码(比如 C/C++/Java/Perl 之类)。
该编译器本身是用纯 Perl 编写的,
大部分骨架代码来自于我前不久开发的 Kid 语言编译器项目。</p>
<p>在这篇文档中,我将简略地介绍一下 re-DFA 的主要方面。</p>
<p>
</p>
<hr />
<h1><a name="DOWNLOAD">DOWNLOAD</a></h1>
<p>re-DFA 的源代码和文档和我的其他项目一来,处于 Subversion (SVN) 版本控制系统的管理
之下。其 SVN 仓库的 URL 如下:</p>
<p><a href="https://svn.berlios.de/svnroot/repos/unisimu/Compilers/re-DFA/">https://svn.berlios.de/svnroot/repos/unisimu/Compilers/re-DFA/</a></p>
<p>您可以使用任何的 SVN 客户端(比如 TortoiseSVN)从上面的位置下载(或者直接在 Web 浏
览器中进行查看)。</p>
<p>我已经将最新的二进制版本的 re-DFA 安装到了 AgentPerl 当中,您可以从我的主页下载
最新的 AgentPerl:</p>
<p><a href="http://yxy.ujs.edu.cn/images/AgentPerl-5.8.7.exe">http://yxy.ujs.edu.cn/images/AgentPerl-5.8.7.exe</a></p>
<p>运行其安装程序之后,就可以在命令行上执行 re2re, re2xml, re2nfa, re2dfa, re2c,
re2pl, 和 evalre 这些 re-DFA 的实用程序了!</p>
<p>发布 re-DFA 的更优雅的方式应当是利用 <code>pp</code> 和 InnoSetup 的组合专门为其制做一个
小巧的 Win32 安装程序,但我目前没有足够多的时间(尽管并不是很难)。</p>
<p>下面我们切入正题。:=)</p>
<p>
</p>
<hr />
<h1><a name="Modules">Modules</a></h1>
<p>在这一节中,我们将简单地介绍 re-DFA 内部的各个 Perl 模块。这些模块实现了 re-DFA 的
核心功能。作为最终用户,可以跳过此节,直接参考下一节中介绍的命令行实用工
具 (Utilities). 那些工具其实在内部调用了这一节中列举的模块。</p>
<p>
</p>
<h2><a name="re3a3aParser">re::Parser</a></h2>
<p>re::Parser 是 re-DFA 的正则表达式解析器。该解析器是利用 Damian Conway 的
<code>Parse::RecDescent</code> 模块从一个语法文件自动生成的。</p>
<p>有趣的是,正则表达式虽然表达能力极其强大,但是正则表达式本身作为一种语言,却无法
用自身来描述。在 re-DFA 项目中,我使用了 Parse::RecDescent 模块提供的 BNF
记法对正则表达式的语法进行了定义,该语法说明书如下所示:</p>
<p><strong>re.grammar</strong></p>
<pre>
&lt;autotree&gt;
program: expression eofile
| &lt;error&gt;
expression: &lt;skip:''&gt; alternation
| &lt;error&gt;
eofile: /^\Z/
alternation: concat(s /\|/)
concat: modified_atom(s?)
modified_atom: atom modifier(?)
modifier: /[*]/
atom: char
| '(' &lt;commit&gt; expression ')'
| &lt;error?&gt; &lt;reject&gt;
char: /\\.|[^*|()]/</pre>
<p>如果用比较``正统''的 BNF 来表达,大约是下面这个样子:</p>
<pre>
expression: alternation
;</pre>
<pre>
alternation: alternation '|' concat
| concat
;</pre>
<pre>
concat: concat modified_atom
|
;</pre>
<pre>
modified_atom: atom modifier
| atom
;</pre>
<pre>
modifier: '*'</pre>
<pre>
atom: char
| '(' expression ')'
;</pre>
<p>未来还会增加更多的语法结构,比如修饰符 <code>+</code>, <code>?</code>,以及通配符 <code>.</code>, <code>\w</code>,
<code>\d</code>, <code>\s</code> 等等。值得注意的是,实际使用的语法文件中并没有出现``左递归'',因
为 <code>Parse::RecDescent</code> 生成的解析器是递归下降的。</p>
<p>目前已经 re-DFA 已经实现了该类型的正则表达式的解析器,能够从任意合法的正
则表达式生成对应的语法树 (parse tree)。Parse tree 的结构与前面的``左递归''
版本的语法定义是一一对应的。比如正则表达式 ``<code>(a|b)*</code>'' 将生成类似下面的语法树:</p>
<pre>
program
expression
alternation
concat
modified_atom
atom
expression
alternation
concat
modified_atom
atom
char
'a'
concat
modified_atom
atom
char
'b'
modifier
'*'</pre>
<p>
</p>
<h2><a name="re3a3are">re::re</a></h2>
<p><code>re::re</code> 是 re-DFA 众多后端 (backends) 中的一个。该后端是正则表达式的反生成
器,它能从语法树``还原''出原始的正则表达式。该后端可以用于测试解析器生成的语法树是否
完整,同时这个 re =&gt; re 的编译器还可以去除正则表达式中多余的括号,比如 <code>((aa))*</code>
经过 <code>re::re</code> 处理后得到的是 <code>(aa)*</code>. 有关 <code>re::re</code> 后端的更多示例,可以
从 <code>re::re</code> 的测试脚本中得到:</p>
<p><a href="http://svn.berlios.de/svnroot/repos/unisimu/Compilers/re-DFA/t/re-re/basic.t">http://svn.berlios.de/svnroot/repos/unisimu/Compilers/re-DFA/t/re-re/basic.t</a></p>
<p>
</p>
<h2><a name="re3a3aXML">re::XML</a></h2>
<p><code>re::XML</code> 模块实现的是一个 XML 的发射器,它能从语法树生成对应的 XML 描述,比如正则
表达式 <code>abc</code> 将生成如下所示的 XML 描述:</p>
<pre>
&lt;expression&gt;
&lt;alternation&gt;
&lt;concat&gt;
&lt;modified_atom&gt;
&lt;atom&gt;
&lt;char&gt;a&lt;/char&gt;
&lt;/atom&gt;
&lt;/modified_atom&gt;
&lt;modified_atom&gt;
&lt;atom&gt;
&lt;char&gt;b&lt;/char&gt;
&lt;/atom&gt;
&lt;/modified_atom&gt;
&lt;modified_atom&gt;
&lt;atom&gt;
&lt;char&gt;c&lt;/char&gt;
&lt;/atom&gt;
&lt;/modified_atom&gt;
&lt;/concat&gt;
&lt;/alternation&gt;
&lt;/expression&gt;</pre>
<p>我猜,XML 应该会让 Java 程序员心动的,呵呵。</p>
<p>
</p>
<h2><a name="re3a3aNFA">re::NFA</a></h2>
<p><code>re::NFA</code> 是 NFA 发射后端。从正则表达式生成 NFA 是生成 DFA 的一个中间步骤。
NFA 在 re-DFA 项目内部是用有向图来表示的,对应于类 <code>re::Graph</code>,具体使用的
数据结构是哈希+数组。<code>re::Graph</code> 类可以<strong>自动</strong>生成 PNG 格式的图片,从而形象
地刻画出构造出的 NFA 的结构。在 <code>re::NFA</code> 的测试集中有下面这几个例子:</p>
<p>对于正则表达式 <code>a</code>,生成如下所示的 NFA:</p>
<center><img src="images/01NFA.png"></center><p>对于正则表达式 <code>ab</code>,则构造出下面的 NFA 图:</p>
<center><img src="images/02NFA.png"></center><p>正则表达式 <code>a*</code> 是这个样子:</p>
<center><img src="images/03NFA.png"></center><p>``重复''的 NFA 转换与老师介绍的略有不同,但从功能上讲还是完全等价的。</p>
<p>下一个例子是带有``替换'' (alternation) 的:<code>a|b</code>:</p>
<center><img src="images/04NFA.png"></center><p>我们不得不承认,AT&amp;T 的 Graphviz 库画出来的有向图真的很漂亮。</p>
<p>上面给出的示例都是最基本的,这儿有一个比较复杂的正则表达式,就是老师上课时用作示
例的,<code>(a|b)*(aa|bb)(a|b)*</code>,所对应的 NFA(原图片经过了缩放,故不太清晰):</p>
<center><img src="images/05NFA.png"></center><p>
</p>
<h2><a name="re3a3aDFA">re::DFA</a></h2>
<p><code>re::DFA</code> 是从 NFA 到 DFA 的转换模块。</p>
<p>我注意到一个有趣的现象,我们得到的 NFA 一般只有一个初态和一个终态,而且不
存在一个状态既是初态又是终态;但是从 NFA 转换得到的 DFA 常常会出现多个终
态,而且有的终态同时也是初态。</p>
<p>从 NFA 到 DFA 的转换所需的 Perl 代码比我想象的要少得多,<code>re::DFA</code>
模块连注释和空行在内,也不过 113 行代码。而其中计算``空闭包''的函
数 <code>eps_closure</code> 由于采用了递归实现,总共只有 20 几行代码,但它能自动
缓存已计算过的结果,从而获得很高的执行效率。</p>
<p><code>re::DFA</code> 生成的 DFA 并不是最简形式,因此需要 <code>re::DFA::Min</code> 模块
将 <code>re::DFA</code> 发射的 DFA 最小化 (minimize).</p>
<p>下面是 <code>re::DFA</code> 正则表达式 (a|b)*(aa|bb)(a|b)* 的 DFA:</p>
<center><img src="images/05DFA.png"></center><p>
</p>
<h2><a name="re3a3aDFA3a3aMin">re::DFA::Min</a></h2>
<p>DFA 的``最小化变换''模块 <code>re::DFA::Min</code> 只用了一个上午的时间便通过了我
准备的所有的综合测试和单元测试。我当时看了一下,该模块的规模也不过 100 多行代码
而已,不过其中却浓缩了相当复杂的集合分割算法,花费了我不少心思,呵呵。</p>
<p>下面是我们一直作为样例的正则表达式 <code>(a|b)*(aa|bb)(a|b)*</code> 所对应的最小化 DFA:</p>
<center><img src="images/05minDFA.png"></center><p><code>re::DFA::Min</code> 的完成意味着,从任意的正则表达式到最简 DFA 的完整通路便构建起来了:</p>
<pre>
regex =&gt; [ re::Parser ] =&gt; regex parse tree =&gt; [ re::NFA ] =&gt; NFA
=&gt; [ re::DFA ] =&gt; DFA =&gt; [ re::DFA::Min ] =&gt; Minimized DFA</pre>
<p>
</p>
<h2><a name="re3a3aGraph">re::Graph</a></h2>
<p>在 re-DFA 系统中,DFA 和 NFA 使用同一种数据结构,即 <code>re::Graph</code>
提供的基于哈希和匿名数组的有向图存储方式。</p>
<p>下面有选择地介绍一下 <code>re::Graph</code> 类的一些重要的方法:</p>
<dl>
<dt><strong><a name="item_as_png">as_png</a></strong><br />
</dt>
<dt><strong><a name="item_visualize">visualize</a></strong><br />
</dt>
<dd>
<code>re::Graph</code> 类自身提供了绘制函数 <a href="#item_as_png"><code>as_png</code></a> 和 <a href="#item_visualize"><code>visualize</code></a>,
因此我的 <code>re::DFA</code> 模块和 <code>re::NFA</code> 模块都无需自己实现画图功能。
</dd>
<p></p>
<dt><strong><a name="item_build">build</a></strong><br />
</dt>
<dd>
<code>re::Graph</code> 类的 <a href="#item_build"><code>build</code></a> 方法提供了一种微型语言解释器,可以从简
洁的文本描述快速构建出有向图结构。比如 NFA
</dd>
<center><img src="images/01NFA.png"></center><p>可以用下面的文本来描述:</p>
<pre>
entry: 1
exit: 2
1,2: a</pre>
<p>假设这个字符串保存在了变量 <code>$s</code> 中,则我们可以利用下面这行代码快速地构造出
这个 DFA 所对应的 <code>re::Graph</code> 对象:</p>
<pre>
$graph = re::Graph-&gt;build( $s );</pre>
<p>这种技术对于测试台而言非常重要。我正是使用这种方法来对``空闭包''的计算函
数 <code>eps_closure</code> 进行单元测试的。为测试方便专门定义一种内部语言的解
释器,听起来似乎有些得不偿失,但别忘了我们使用的是 Perl 语言,
整个 <a href="#item_build"><code>build</code></a> 方法,连解析器、执行器和出错处理在内,总共也不过 22 行代码。</p>
<p></p>
<dt><strong><a name="item_normalize">normalize</a></strong><br />
</dt>
<dd>
<a href="#item_normalize"><code>normalize</code></a> 方法通过对节点进行重新编号来对有向图进行``规格化''
(normalization) 变幻。具体的编号方法是:从入口节点出发,利用广度优先搜索算
法,逐一地对遇到的节点进行累加性编号;而对于兄弟节点,则按其边上的权值的字母
顺序,对它们进行编号。
</dd>
<dd>
<p>这样,DFA 和 NFA 的``初态''便总为 1,而``终态''总是比较大的编号(但不一定是最大的),
而其他节点,距离``初态''近一些的则编号小一些,距离``初态''远一些的,则编号大一些。
这样一来,DFA 只要拓扑结构一致,经过 normalize 规格化之后的形式也就会完全一致
了。这无疑大大方便了自动化测试,因为原先, NFA 到 DFA 的转换算法中的随机性会使
每次得到的 DFA 的节点编号都会有所不同,从而给基于图片或数据结构精确比较的回归测试
带来了不小的麻烦。</p>
</dd>
<dd>
<p>同时,normalize 对节点的编号方法也符合我们人类的习惯,从而也提高了 re-DFA 生成的
.png 图片的质量。不过,我注意到 NFA 进行``规格化''之后,会破坏一些暗示性的结构化布
局,所以 <a href="#re2nfa">re2nfa</a> 工具并未启用 normalize 功能。而 DFA 则不存在这样的问题,
因此 <a href="#re2dfa">re2dfa</a> 在生成图片之前,总是先执行``规格化''操作。</p>
</dd>
<dd>
<p>作为例子,下图是未经过规格化处理的两个 DFA:</p>
</dd>
<center><img src="images/05minDFA2.png">
&nbsp;&nbsp;&nbsp;<img src="images/06minDFA2.png">
</center><p>而下图则是规格化以后所对应的 DFA:</p>
<center><img src="images/05minDFA.png">
&nbsp;&nbsp;&nbsp;<img src="images/06minDFA.png">
</center><p>显然后者比前者更“规整”,呵呵。</p>
<p></p></dl>
<p>
</p>
<h2><a name="re3a3aDFA3a3aPerl">re::DFA::Perl</a></h2>
<p>我们知道,从 DFA 到词法分析代码只有一步之遥,但是做法却可以分为两种。一种是将状
态机用 while 循环和 if/else 语句进行``硬连接'' (hard-wired) 编码。另一种是方
法是将 DFA 对应的数据表格输出为目标语言中的某种数据结构,然后利用一小段通用的代
码在执行词法分析的过程中,对该数据结构进行存取。</p>
<p>硬连接方法,生成器的代码比较难写一些,而且生成的目标代码会随正则表达式的复杂度而
膨胀得比较厉害,但是目标代码的执行效率一般很高。这很像 CPU 控制器的``硬连接''逻辑。</p>
<p>数据表驱动方法,生成器的代码相对要简单的多,而且目标代码是固定的,唯一变化的是使
用的 DFA 所对应的数据结构。这种方法的缺点是,目标代码存取数据表增加了时间上的开
销,而且从 DFA 得到的数据表倾向于变得很大。</p>
<p>re-DFA 目前的 C 和 Perl 两个代码生成器采用的都是第一种方法,即``硬连接''的方法,
因为我希望生成的目标代码可读性更好,执行效率更高。</p>
<p>re-DFA 中的新增模块 <code>re::DFA::Perl</code> 用于从 DFA (不一定是经过最小化的 DFA)
生成完全独立的 Perl 词法分析代码。利用我的 <a href="#re2pl">re2pl</a> 工具可以在命令行上访问到该模块
的这个功能:</p>
<pre>
D:\&gt;re2pl -n match &quot;a|b&quot;
sub match {
my $s = shift;
return undef if !defined $s;
my $pos = 0;
my $state = 1;
my $done;
while (1) {
my $char = substr($s, $pos, 1);
if ($state == 1) {
last if !defined $char;
if ($char eq 'a') {
$state = 2;
next;
}
if ($char eq 'b') {
$state = 2;
next;
}
last;
}
if ($state == 2) {
$done = $pos;
last;
}
die &quot;error: Unknown state: $state&quot;;
} continue {
$pos++;
}
if (!defined $done) { return undef; }
substr($s, 0, $done);
}</pre>
<p>我们看到,<a href="#re2pl">re2pl</a> 工具从正则表达式 <code>a|b</code> 生成了一个名为 match 的 Perl
例程,用于完成与原正则表达式完全相同的文本匹配功能。该例程的名字 match
我们是在命令行上用 -n 选项指定的。在没有指定 -n 选项的情况下,默认生成的是匿名的
Perl 例程。</p>
<p>这里有几组测试演示了 <a href="#re2pl">re2pl</a> 生成的 Perl 例程的用法:</p>
<pre>
is match('a'), 'a';
is match('b'), 'b';
ok !defined match('c');</pre>
<pre>
is match('ac'), 'a';
is match('bb'), 'b';
ok !defined match('ca');</pre>
<p>这里的 match 函数执行正则表达式 <code>a|b</code> 的匹配功能。它总是从输入串的开头开始匹配,
然后按照最长子串原则进行匹配。能匹配多少字符就匹配多少字符,即 match 不要求整个输
入串都匹配对应的正则表达式。当匹配成功时,match 函数返回匹配部分的子串(可以为
空);当匹配失败时,返回未定义值 undef.</p>
<p>注意上面这个 match 函数本身未使用任何 Perl 正则表达式,因此我们可以很容易地用类似
的代码模板生成其他任何语言,比如 C/C++, Java, C#, Python, Ruby, Tcl, VB...
事实上,我正是通过对 <code>re::DFA::Perl</code> 中使用的 Perl 目标代码的 TT 模板进行少许
修改,得到了从 DFA 生成等效的 C 词法分析代码的 <code>re::DFA::C</code> 模块。</p>
<p>我对 <a href="#re3a3adfa3a3aperl">re::DFA::Perl</a> 和 <a href="#re3a3adfa3a3ac">re::DFA::C</a> 这两个 DFA 代码生成后端进行了广泛的
测试。编写这些测试的时候,我感觉自己真的是在做一个正则表达式的计算引擎了。
<code>re::DFA::Perl</code> 的测试集在这个位置:</p>
<p><a href="http://svn.berlios.de/svnroot/repos/unisimu/Compilers/re-DFA/t/re-DFA-Perl/">http://svn.berlios.de/svnroot/repos/unisimu/Compilers/re-DFA/t/re-DFA-Perl/</a></p>
<p>
</p>
<h2><a name="re3a3aDFA3a3aC">re::DFA::C</a></h2>
<p><code>re::DFA::C</code> 可以从 DFA 自动生成独立的 C 词法分析代码。通过 re-DFA 的 <a href="#re2c">re2c</a> 脚
本可以访问 <code>re::DFA::C</code> 提供的这个功能。下面是一个示例:</p>
<pre>
D:\&gt;re2c -n match &quot;a|b&quot;
int match (char* s) {
int pos = -1;
int state = 1;
int done = -1;</pre>
<pre>
while (1) {
char c;
c = s[++pos];
if (state == 1) {
if (c == '\0') break;
if (c == 'a') {
state = 2;
continue;
}
if (c == 'b') {
state = 2;
continue;
}
break;
}
if (state == 2) {
done = pos;
break;
}
fprintf( stderr, &quot;error: Unknown state: %d&quot;, state );
exit(2);
}
return done;
}</pre>
<p>这里生成的 C 版本的 match 函数与前面的 Perl 版本相比,接口上略微有了上些变化。
下面这组测试演示了这个 C match 函数的用法:</p>
<pre>
is( match(&quot;a&quot;), 1 );
is( match(&quot;b&quot;), 1 );
is( match(&quot;c&quot;), -1 );</pre>
<pre>
is( match(&quot;ac&quot;), 1 );
is( match(&quot;bb&quot;), 1 );
is( match('ca'), -1 );</pre>
<p>请注意,这里当匹配成功时,match 函数不再返回匹配部分的整个子串了,而是返回匹配
部分的末尾在原串中的偏移量,数值上也等于匹配部分子串的长度。因此正则表达式 <code>a*</code>
生成的 C 函数在匹配输入串 <code>aaaabc</code> 的时候返回数值 4,因为匹配部分是 <code>aaaa</code>.
当匹配失败时,C 函数返回 -1. 因为返回 0 时表示成功匹配了一个空串。匹配空串与匹
配失败具有本质的区别。</p>
<p>而 <code>re::DFA::C</code> 的测试集则在这个位置:</p>
<p><a href="http://svn.berlios.de/svnroot/repos/unisimu/Compilers/re-DFA/t/re-DFA-C/">http://svn.berlios.de/svnroot/repos/unisimu/Compilers/re-DFA/t/re-DFA-C/</a></p>
<p>这些 .t 测试脚本中使用了一些非常有趣的高级技术。比如这两个目录中的 eval.t 文件都
使用了 typeglob 技术在运行时动态地修改 Perl 的符号表,从而创建新的 Perl 例程。
另外,更有趣的是,re-DFA-C 中的 eval.t 在运行的时候可以动态地从正则表达式
生成 C 代码,然后自动调用外部的 C 编译器进行编译,接着自动将编译链接得到
的 DLL 文件加载到 Perl 运行时环境,最后调用 DLL 里执行匹配的 C 函数。
事实上,该``解释''C 代码的特性是 <code>re::DFA::C</code> 模块通过 Ingy 的 <code>Inline::C</code>
模块实现的。</p>
<p>
</p>
<h2><a name="re3a3aDFA3a3aEval">re::DFA::Eval</a></h2>
<p><code>re::DFA::Eval</code> 模块提供了“解释” <a href="#re3a3adfa3a3aperl">re::DFA::Perl</a> 和 <a href="#re3a3adfa3a3ac">re::DFA::C</a> 生成
的词法分析代码的功能。具体信息请参见 <a href="#evalre">evalre</a>.</p>
<p>
</p>
<hr />
<h1><a name="Utilities">Utilities</a></h1>
<p>re-DFA 本身是一个类库,为了向用户、尤其是非 Perl 程序员提供更加友好的接口,
re-DFA 所有的编译器后端都提供了一个命令行实用工具。有趣的是,它们的程序名都以
re2 起始,意为 regex to... 下面我们就逐一地来介绍一下这些 utilities.</p>
<p>
</p>
<h2><a name="re2re">re2re</a></h2>
<p><code>re2re</code> 程序解析用户提供的正则表达式,然后在内部生成一棵 Parse Tree,
最后再反生成正则表达式。下面是我机器上的屏幕快照:</p>
<pre>
C:\&gt;re2re &quot;(a|b)*(aa|bb)(a|b)*&quot;
(a|b)*(aa|bb)(a|b)*</pre>
<pre>
C:\&gt;re2re &quot;((a))*&quot;
a*</pre>
<p>我们看到,<code>re2re</code> 可以去除正则表达式中多余的括号,这也算是它的一点儿``实用价值''了。
如果用户提供的正则表达式是非法的,则 <code>re2re</code> 工具会报错(其他的 re2* 工具也一样,
因为它们都共享同一个正则解析器):</p>
<pre>
C:\&gt;re2re &quot;(a*&quot;</pre>
<pre>
ERROR (line 1): Invalid program: Was expecting eofile but
found &quot;(a*&quot; instead</pre>
<p>
</p>
<h2><a name="re2xml">re2xml</a></h2>
<p><code>re2xml</code> 工具可以从用户给定的正则表达式生成其对应的语法树的 XML 描述:</p>
<pre>
C:\&gt;re2xml &quot;a*&quot;
&lt;expression&gt;
&lt;alternation&gt;
&lt;concat&gt;
&lt;modified_atom&gt;
&lt;atom&gt;
&lt;char&gt;a&lt;/char&gt;
&lt;/atom&gt;
&lt;modifier&gt;*&lt;/modifier&gt;
&lt;/modified_atom&gt;
&lt;/concat&gt;
&lt;/alternation&gt;
&lt;/expression&gt;</pre>
<pre>
C:\&gt;re2xml &quot;aa&quot;
&lt;expression&gt;
&lt;alternation&gt;
&lt;concat&gt;
&lt;modified_atom&gt;
&lt;atom&gt;
&lt;char&gt;a&lt;/char&gt;
&lt;/atom&gt;
&lt;/modified_atom&gt;
&lt;modified_atom&gt;
&lt;atom&gt;
&lt;char&gt;a&lt;/char&gt;
&lt;/atom&gt;
&lt;/modified_atom&gt;
&lt;/concat&gt;
&lt;/alternation&gt;
&lt;/expression&gt;</pre>
<p>这里我没使用很复杂的正则表达式作为示例是因为 XML 输出会变得太 FUD,呵呵。
<code>re2xml</code> 也具有完善的出错处理。</p>
<p>
</p>
<h2><a name="re2nfa">re2nfa</a></h2>
<p>re-DFA 提供的最有意思的命令行工具莫过于 <code>re2nfa</code> 和 <code>re2dfa</code> 了。我们首先来看
<code>re2nfa</code>。</p>
<p><code>re2nfa</code> 根据用户提供的正则表达式生成对应的``非确定性有穷自动机'' (NFA) 的图形化
描述:</p>
<pre>
C:\&gt;re2nfa &quot;(a|b|c|d)(a(b|c)*)*&quot;
NFA.png generated.</pre>
<pre>
C:\&gt;re2nfa &quot;&quot;
NFA.png generated.</pre>
<p>我们看到,<code>re2nfa</code> 工具会在当前工作目录生成一个名为 <em>NFA.png</em> 的图片文件,我们可以
在自己喜爱的图片浏览器中查看。</p>
<p>
</p>
<h2><a name="re2dfa">re2dfa</a></h2>
<p><code>re2dfa</code> 应该算是 re-DFA 中最重要的工具了。它从用户给定的一个正则表达式生成两张图
片,分别名为 <em>DFA.png</em> 和 <em>DFA.min.png</em>。前者是未化简的 DFA 示意图,而后者是经
过最小化的 DFA。典型的屏幕快照如下所示:</p>
<pre>
C:\&gt;re2dfa &quot;(())*&quot;
DFA.png generated.
DFA.min.png generated.</pre>
<pre>
C:\&gt;re2dfa &quot;&quot;
DFA.png generated.
DFA.min.png generated.</pre>
<p>
</p>
<h2><a name="re2pl">re2pl</a></h2>
<p><code>re2pl</code> 脚本是 <a href="#re3a3adfa3a3aperl">re::DFA::Perl</a> 的命令行接口。具体用法请参见 <a href="#re3a3adfa3a3aperl">re::DFA::Perl</a>
一节。</p>
<p>
</p>
<h2><a name="re2c">re2c</a></h2>
<p><code>re2c</code> 脚本是 <a href="#re3a3adfa3a3ac">re::DFA::C</a> 的命令行接口。具体用法请参见 <a href="#re3a3adfa3a3ac">re::DFA::C</a>
一节。</p>
<p>
</p>
<h2><a name="evalre">evalre</a></h2>
<p>我为 re-DFA 编写了一个名为 <a href="#evalre">evalre</a> 的命令行工具,可以``解释'' DFA 的代码生成器
生成的 C 代码和 Perl 代码。这样我的 re-DFA 就可以像正则表达式的计算引擎那样使
用了!下面是几个示例:</p>
<pre>
D:\Vc7&gt;evalre &quot;(a|b)*&quot; &quot;baabac&quot;
match: 'baaba'</pre>
<pre>
D:\Vc7&gt;evalre -c &quot;(a|b)*&quot; &quot;baabac&quot;
match: 'baaba'</pre>
<p>注意,使用 -c 选项时,evalre 会从正则表达式生成 C 代码,然后自动进行编译、
链接和执行,所以此时运行速度会比较缓慢。我们平常说 C 程序一般很快,显然没
有算上编译和链接的时间。由此可见,编译器与解释器在构造的时候,采取的策略还
是有很大区别的。</p>
<p>匹配失败时的输出如下所示:</p>
<pre>
D:\&gt;evalre &quot;a&quot; &quot;bbcc&quot;
fail to match</pre>
<p>
</p>
<hr />
<h1><a name="Test20Suit">Test Suit</a></h1>
<p>re-DFA 和许多其他 Perl 项目一样,拥有比较完整的测试集和对应的自动化测试台。
测试集中既收入了每个模块的单元测试,又编入了综合测试;既有白箱测试,又有黑
盒测试。下面是测试台一次典型运行的屏幕输出:</p>
<pre>
t/re-DFA-C/code.........ok
t/re-DFA-C/eval.........ok
t/re-DFA-Min/basic......ok
t/re-DFA-Min/unit.......ok
t/re-DFA-Perl/code......ok
t/re-DFA-Perl/eval......ok
t/re-DFA/basic..........ok
t/re-DFA/eps_closure....ok
t/re-Graph/basic........ok
t/re-Graph/table........ok
t/re-NFA/basic..........ok
t/re-re/basic...........ok
t/re-XML/basic..........ok
t/scripts...............ok
All tests successful.
Files=14, Tests=308, 173 wallclock secs ( 0.00 cusr + 0.00 csys = 0.00 CPU)</pre>
<p>我们看到,到写这篇文档时为止,re-DFA 的测试集已有 308 个回归测试。之所以运行整个测试
集花了 173 秒这么长的时间,是因为上面那次测试是在我的赛扬 330 的老机器上进行的。</p>
<p>
</p>
<hr />
<h1><a name="Important20Issues">Important Issues</a></h1>
<p>
</p>
<h2><a name="Nullable20Regexes">Nullable Regexes</a></h2>
<p>在开始 <code>re::DFA::Min</code> 的 DFA 最小化之旅以前,我想先讨论一下正则表达式中的
``空字''问题。</p>
<p>re-DFA 对``空字''提供完整的支持。比如整个正则表达式现在允许为空,即 ``'',它可以
匹配任何空串。空正则表达式的 NFA 和 DFA 分别为:</p>
<center><img src="images/08NFA.png">&nbsp;&nbsp;&nbsp;&nbsp;
<img src="images/08DFA.png"></center><p>我们看到,空的正则表达式也是合法的表达式,而且从它生成的 NFA 具有两个状态和一条弧;
空正则表达式的 NFA 和 DFA 其实都不为``空'',因为对于自动机而言,无论如何
都得有``初态''和``终态''。</p>
<p>同样的,正则表达式</p>
<pre>
(a|)b*</pre>
<p>现在也是完全合法的。该正则表达式对应的 NFA 和最小化 DFA 如下所示:</p>
<center><img src="images/07NFA.png">
&nbsp;&nbsp;&nbsp;<img src="images/07minDFA.png">
</center><p>在正则表达式级别上对``空字'' (eps) 进行支持,有着特殊的重要意义。因为许多实用
的正则表达式中的修饰符 (<code>?</code>) 正需要``空字''来进行``脱糖''。举例来说,正则表达
式 <code>a?b*</code> 的脱糖形式正是前面的 <code>(a|)b*</code>,这里 <code>a?</code> 被转换
成了 <code>(a|)</code> 的形式。</p>
<p>
</p>
<h2><a name="Error20State">Error State</a></h2>
<p>在用子集分割法对 DFA 进行最小化处理时,必须对 DFA 中隐含的``出错状态''进行讨论。
毕竟,在 DFA 中,许多到``出错态''的转移都被省略掉了,但这并不是说它们总是可退
到后台。</p>
<p>当一个状态没有画出在字符 <code>a</code> 上的转换时,其实就是说,该状态在遇到字
符 <code>a</code> 时应该跳转到``出错态''。而当一个集合中的状态 m 在字符 <code>a</code> 上存在
到``出错态''的转换,而另一个状态 n 在字符 <code>a</code> 上却跳转到一个普通的状态,
这时便意味着字符 <code>a</code> 区分出了状态 m 和状态 n,也就是说,这两个状态所在
的集合需要进行分割。</p>
<p>这意味着,在我的 <code>re::DFA::Min</code> 模块中需要显式地引入``出错态''以避免得到
``过简''的 DFA。</p>
<p>
</p>
<h2><a name="Regex20Ambiguity">Regex Ambiguity</a></h2>
<p>我通过 re-DFA 的 <a href="#evalre">evalre</a> 工具比较了一下我们的基于 DFA 的正则表达式引擎
与 Perl 自身的基于NFA 的正则引擎在二义性处理上的区别。老师在课堂上没有提及正
则表达式的``二义性''问题,比如正则表达式 <code>a|ab</code> 在匹配字符串 ``<code>ab</code>'' 时匹配
部分究竟是单个字符 ``<code>a</code>'' 呢,还是整个 ``<code>ab</code>''?</p>
<p>DFA 引擎一般遵循最长子串原则,因此匹配结果是 ``<code>ab</code>'' 而不是 ``<code>a</code>'',我们的 evalre
的行为证明了这一点:</p>
<pre>
D:\&gt;evalre &quot;a|ab&quot; &quot;ab&quot;
match: 'ab'</pre>
<p>而对基于 NFA 的实现而言,出于效率方面的考虑,往往只尝试``选择''(alternation)
中第一个成功的匹配,因此正则表达式中的选择 a 比选择 ab 具有更高的``优先级''。
因此一旦 <code>a</code> 匹配成功,NFA 匹配引擎将不再去考虑下一个选择 <code>ab</code> 了。Perl
正则引擎的行为应证了这个推断:</p>
<pre>
D:\&gt;perl -e &quot;print 'ab' =~ /(a|ab)/&quot;
a</pre>
<p>哈哈,我终于盼到这一天了,我对我自己的正则引擎与 Perl 的正则引擎进行行为上的比
较——哇,这真是太棒了!</p>
<p>
</p>
<hr />
<h1><a name="re2dDFA20versus20JFLAP">re-DFA versus JFLAP</a></h1>
<p>在 re-DFA 的开发过程中,我在网上找到了一个由美国 Duke 大学开发、受美国国
家科学基金资助的一个 Java 项目,名为 JFLAP。它从教学的角度,对有穷自动机
理论、文法构造等编译原理进行了可视化。它的主页是</p>
<p><a href="http://www.cs.duke.edu/csed/jflap/">http://www.cs.duke.edu/csed/jflap/</a></p>
<p><a href="http://www.cs.duke.edu/csed/jflap/new/DOCS/gui.minimize.MinimizePane.html">http://www.cs.duke.edu/csed/jflap/new/DOCS/gui.minimize.MinimizePane.html</a></p>
<p>该软件可以免费下载,只要我们提供一些用户信息。我试用了一下,感觉还行,它可以从正
则表达式生成最小化的 DFA,可以从 DFA 反生成上下文无关文法和正则表达式。这些功能
都是我的 re-DFA 原先想要实现的。同时,JFLAP 还支持许多 re-DFA 范畴以外的与语法
分析原理有关的特性。</p>
<p>JFLAP 使用的正则表达式的语法有些古怪,比如我们上课时的那个例子</p>
<pre>
(a|b)*(aa|bb)(a|b)*</pre>
<p>在它那里必须得写成</p>
<pre>
(a+b)*(aa+bb)(a+b)*</pre>
<p>即``或''是用加号(+)而不是竖线(|)来表示的:这的确很奇怪。</p>
<p>根据该软件的文档,它目前支持的正则语法极其有限,只有重复(*),选择(|)和括号(
当然还有连接了)。经过测试,JFLAP不支持空字,比如下面这个正则表达式就被认为是非
法的:</p>
<pre>
(a+)b*</pre>
<p>而在我的 re-DFA 中可以写成</p>
<pre>
(a|)b*</pre>
<p>这是完全可以识别的。未来,re-DFA 将会通过``脱糖'' (desugar) 的方式,支持许
多 Perl 正则表达式中的高级结构,比如 <code>?</code>, <code>+</code>, <code>{m}</code>, <code>{m,n}</code>,
<code>[a-z0-9]</code>, <code>\w</code>, <code>\s</code>, <code>.</code>, <code>\d</code>, <code>\D</code> 之类。</p>
<p>JFLAP 为 DFA 和 NFA 生成的有向图,说实话,真不如 Graphviz 生成的图片漂亮。
另外,它的 GUI 界面使用起来有些不方便。把一个正则表达式转换为最小化的 DFA 这
么基本的一个操作,居然需要用鼠标在那么多的窗口中,一步一步地点击那么多次;而
在 re-DFA 中将只需要一个命令。再有就是,在 JFLAP 中,最后生成的有向图如果很
大的话,就会很不清楚,似乎没有提供放大工具。</p>
<p>基于上述理由,我认为 re-DFA 比 JFLAP 更有理由获得美国国家科学基金的赞助,呵呵。</p>
<p>
</p>
<hr />
<h1><a name="TODO">TODO</a></h1>
<ul>
<li></li>
向 re-DFA 支持的正则表达式添加更多的修饰符和元标记,如 <code>?</code>, <code>+</code>, <code>[a-z]</code> 之类
<p></p>
<li></li>
为 re-DFA 编写详尽的 API 文档和用户手册
<p></p>
<li></li>
利用 InnoSetup 将 re-DFA 及其依赖项 (Graphviz) 打包成独立的 Win32 安装程序。
<p></p>
<li></li>
将 re-DFA 以 Regexp::DFA 的形式发布到 CPAN:
<p><a href="http://search.cpan.org">http://search.cpan.org</a></p>
<p></p>
<li></li>
对 re-DFA 的瓶颈部件进行性能优化。
<p></p></ul>
<p>对于这些 TODO,我非常希望能从老师和同学那里得到帮助,毕竟我一个人的时间和精力还是很
有限的。:=)</p>
<p>
</p>
<hr />
<h1><a name="COPYRIGHT">COPYRIGHT</a></h1>
<p>Copyright (c) 2006 Agent Zhang (章亦春). All rights reserved.</p>
<p>This library is free software; you can redistribute it and/or
modify it under the same terms as Perl itself.</p>
<table border="0" width="100%" cellspacing="0" cellpadding="3">
<tr><td class="block" valign="middle">
<big><strong><span class="block">&nbsp;report - 编译技术课程设计报告:从正则表达式到 DFA</span></strong></big>
</td></tr>
</table>
</body>
</html>