共有回帖数 0 个
-
0. Foreword
· 这是一篇教程，但不是一篇c教程。读者应当能够读通一部分类c语言，并对求值这一概念有基本的认识。
· 我会在文中介绍我认为需要提出和注意的背景知识，但不代表每个读者都能通过这些简陋的文字获得自己能够接受程度的理解。稍稍进行一些搜索会很有帮助。我不会赘述语法分析方面的内容，请读者自行参考。
· 主要的材料来自[Hutton92]，我认为这是一个相对容易的实现。读者可以参考[Hutton96]和[Frost96]获得进一步的材料（比如单子化的组合子和加入记忆化搜索的组合子）。
· 读者可能会希望用一下boost.spirit.
· 一等函数（first-class function）。函数是对象，可以与变量关联，可以返回。这与实现关系不大，一等函数仍然可以在不少逻辑上分立的I空间/D空间上实现。教程中的代码倾向于返回成吨的函数，请习惯。
· 克里化（currying）。现在开始，我们所谈论的函数都是一元函数；显而易见，需要给出表示多元函数的方法。这里我们将多元函数表示为一元函数的复合，举例而言，
f(x, y) = x + y ...(1)
将会被表示为
f = x.y.x + y ...(2).
(2)是一个lambda演算的记法。这意味着它定义了一个自变量为x、因变量为某个函数的函数；而这一因变量是一个自变量为x, 因变量的计算法为x + y的函数，其中的x来自对f的首次参数应用，比如
f 1 -(beta) y.1 + y ...(3).
再次应用2, 容易得到f 1 2 -(beta) 1 + 2 = 3. 回过头来。读者会看到类似这样的代码：
sub { my $x = $_[0]; sub { my $y = $_[0]; $x } }
实际上这就是一个所谓的闭包（closure）。在前述的基础上，我们引入这样的函数类型记法：
g :: A - B - C
结合克里化的知识，你会发现函数g的类型实际上是A - (B - C). 注意类型X - Y是一个函数，将X类型映射到Y类型。Haskell用户大概会熟悉这样的记法。
教程中的部分函数不会被克里化，而是保持其目，以便于书写。
1. 基本模型
语法分析器（parser）是一个函数。它接受一个串作为输入，输出对(v, xs)的列表[ (v, xs) ]。（记法上的提示。文中用方括号[]表示列表，用圆括号()表示有序对。它们具有不同的意义，虽然读者很容易用相同的方式给出二者的实现——实际上我也是这么做的。）为了方便写出函数的类型，这里给出一个类似于类型构造器（type constructor）的记法来表示语法分析器类型：
parser c t = [c] - [ (t, [c]) ]
这里隐含的一点是：字符串的类型是字符类型（c）元素组成的列表类型（[c]）。类型parser c t意味着此类语法分析器函数处理的输入/输出字符类型为c, 分析结果的类型为t. 回顾记法(v, xs)并对比记法(t, [c])，这两个记法都指出了语法分析器的任务——给出分析结果并“消耗”输入。纯函数支持者们自然会指出，这里的消耗只是观念上的，实际上语法分析器返回了尚未被处理的串。这个记法可以用索引进一步改进以节省空间，这里出于书写和实现方便的考虑就不再探讨了。
举例而言，假如要实现一个计算整数四则运算的计算器，我们可以期望这样一个语法分析器：
calc :: parser Char Integer
而当我们写下calc "1+2+3-4"这个表达式的时候，应该能在输出中得到正确的分析结果(2, "")。之所以这么说，是因为语法分析器会产生一系列的分析结果，其中包含了所有符合语法的分析结果；产生这一现象的原因会在随后的实现中逐渐明晰，现在读者只需要注意这一点——语法分析组合子会返回多个结果，其中有若干个是正确的（多个正确结果对应有二义性的语言；如果语言不具二义性，正确结果是唯一的；所谓正确，是指输入串被消耗完，这时我们可以确定输入的句子是符合文法的）。
2. 基本算子
基本算子是构建分析器的基本部分，它们只关心输入如何映射到单纯的输出，而不试图去组合算子。
第一个基本算子succeed对应空串。在任何输入上，空串都能够进行下去，反映出当前的分析状态；举例而言，若当前的分析状态之一是(v, xs)，那么succeed执行之后的分析状态仍然是(v, xs).
或许读者会闻到一点危险的气味。不过考虑到这是空串，所以倒不见得多危险。
succeed :: t - parser c t
succeed v inp = [ (v, inp) ]
实现是显而易见的：
our $succeed =
sub {
my $v = $_[0];
sub {
my $u = (ref($v) eq "ARRAY") ? $v : [ $v ];
[ [ $u, $_[0] ] ]
}
};
虽然显而易见，但也有一处额外的处理：$u. 有关这个处理的细节会在组合子部分涉及。
第二个算子对应失败的情况。
fail :: parser c t
fail inp = []
全部输入被丢弃，后续算子只能见到空串。实现很直白：
our $fail =
sub {
[]
};
第三个算子satisfy用于识别输入串的首字符。这一功能由参数谓词给出实作。如果谓词返回真，说明字符匹配成功，算子返回被匹配的字符同时消耗输入串的首字符，否则失败。容易想像这是实际消耗输入的部分，熟悉其他语法分析方法的读者会意识到，这里是处理终结符（terminal symbol）的地方。
satisfy的类型和形式如下所示：
satisfy :: (c - bool) - parser c c
satisfy p [] = fail []
satisfy p (x:xs) = succeed x xs, p x
= fail xs, otherwise
为不熟悉列表解析和模式匹配的读者解释一下这里的写法。satisfy本身是个一参的函数，但注意到它返回了一个语法分析器，所以这并不妨碍我们对satisfy p应用第二个参数，也就是输入串。对输入串按空串和非空串进行讨论：空串返回fail []而非空串被解析为串首字符x和尾串xs两个部分，再按p x的真值进行讨论。余谈，其实礼节上看来p x很可能不是个常见意味上的卫式（guard expression），虽然p可以被实现成无副作用的。
这样看来，satisfy算子的实现也足够直白了：
our $satisfy =
sub {
my $p = $_[0];
sub {
if (my ($x, $xs) = ($_[0] =~ /(.)(.*)/s) ) {
if ($p-($x)) {
return $succeed-($x)-($xs);
} else {
return $fail-($xs);
}
} else {
return $fail-( [] );
}
}
};
在satisfy的基础上，实现literal算子：
literal :: c - parser c c
literal x = satisfy(=x)
our $literal =
sub {
my $y = $_[0];
$satisfy-(
sub {
$y eq $_[0]
}
)
};
literal用于匹配一个字符。现在我们可以写$literal('3')-('345'), 得到结果[ (3, "45") ].
不过仔细阅读了程序的读者会发现，实际上我们得到的Perl数据会是[ [ [3], "45" ] ]。换言之，对(v, xs)中的首元v还是个列表。我们希望保持这个形式——语法分析器可能会返回一系列的分析结果，它们不应当影响(v, xs)这个形式。这有利于我们书写语义动作。
3. 基本组合子
明确目标：我们需要处理EBNF. 为此我们至少要准备两个操作——或操作和序列操作。在准备这些操作之前，先审视一眼我们手头要处理的数据结构：[ [ [v], xs ] ]。下面看或组合子alt:
alt :: parser c t - parser c t - parser c t
(alt p1 p2) inp = p1 inp ++ p2 inp
++是列表连接操作，代表将右运算数中的所有元素顺序加入左操作数的表尾。而我们面对的是列表之列表，换言之，需要一个显式的展平操作，也即实现++算符。我把这个操作写为$concat, 读者可以自行实现它。[Hutton96]指出了[Hutton92]中提出的then组合子（也即教程所展示的两个组合子）的这一缺陷——我们立刻会看到它——同时引入了单子化组合子bind和一次concat解决，但实际上呢？
[Hutton92]中，序列组合子then的形式如下：
then :: parser c t1 - parser c t2 - parser c (t1, t2)
(then p1 p2) inp = [ ( (v1, v2), out2 ) | (v1, out1) - p1 inp; (v2, out2) - p2 out1 ]
同样注意到这里的(v1, v2)应该是v1 ++ v2, 以避免嵌套元组。
then组合子的书写方式是一个列表推导式（list comprehension）。竖线前给出了列表元素的形式，竖线后则指出了两个生成器（generator），形如 x - L, 其中x是元素而L是列表。从意义上看来，then顺序连接了两个语法分析器p1和p2的分析结果，并附以最终的剩余串。
这里，alt和then的实现同样不具有技巧性。给出then的实现，而alt的实现留给读者。
our $then =
sub {
my ($p1_, $p2_) = @_;
sub {
my ($p1, $p2) = (descalar($p1_), descalar($p2_));
my $inp = $_[0];
my $reslist1 = $p1-($inp);
my $finlist = [];
for my $respair (@$reslist1) {
my ($v1, $reslist2) = ( $respair-[0], $p2-($respair-[1]) );
for my $finpair (@$reslist2) {
my $val1 = (ref($v1) eq "ARRAY") ? $v1 : [ $v1 ];
my $val2 = (ref($finpair-[0]) eq "ARRAY") ? $finpair-[0] : [ $finpair-[0] ];
push @$finlist, [ $concat-($val1, $val2), $finpair-[1] ];
}
}
$finlist
}
};
4. 语义动作和量词
语义动作的实现由using组合子给出。
using :: parser c t1 - (t1 - t2) - parser c t2
(using p f) inp = [ (f v, out) | (v, out) - p inp ]
简而言之，将f应用到p的输出结果上。藉由这个算子，我们可以给出自定义的语义动作。
our $using =
sub {
my ($p_, $f) = @_;
sub {
my $p = descalar($p_);
my $inp = $_[0];
my $reslist = $p-($inp);
my $finlist = [];
for my $respair (@$reslist) {
push @$finlist, [ $f-($respair-[0]), $respair-[1] ];
}
$finlist
}
};
下一个是*量词many. 这里我简化了[Hutton92]中的定义，因为不再需要额外的concat了：
many :: parser c t - parser c t
many p = alt (then p (many p)) (succeed [])
小心这个定义。我一直在用Perl实现这些算子，而Perl是及早求值的（而且求值序基本会是applicative order）。如果直接实现了many, 那么将会陷入合理而无限的递归当中。——不过如果意识到了这里需要惰性求值，那么我们很容易构造一个惰性求值的then对强制惰性求值的many p延迟其求值时机。下面的解法很丑，读者可以随意调整：
my $then_lazy =
sub {
my ($p1, $p2) = @_;
sub {
my $inp = $_[0];
my $reslist1 = $p1-($inp);
my $finlist = [];
for my $respair (@$reslist1) {
my ($v1, $reslist2) = ( $respair-[0], $p2-()-($respair-[1]) );
for my $finpair (@$reslist2) {
my $val1 = (ref($v1) eq "ARRAY") ? $v1 : [ $v1 ];
my $val2 = (ref($finpair-[0]) eq "ARRAY") ? $finpair-[0] : [ $finpair-[0] ];
push @$finlist, [ $concat-($val1, $val2), $finpair-[1] ];
}
}
$finlist
}
};
sub many_s {
my $p = $_[0];
$alt-($then_lazy-($p, sub { many_s($p) }), $succeed-( [] ))
}
our $many = &many_s;
读者可以试验一下many算子。$many-($literal-('a'))-('aaab')这样的尝试应当返回四个结果，因为many算子匹配至少零个a字符。
5. 测试：算术表达式计算
我们为下面的文法提供语法规则定义和语义动作：
E - T + E | T - E | T
T - F * T | F / T | F
F - (E) | number
sub do_add {
my $l = $_[0];
[ $l-[0] + $l-[2] ]
}
sub do_sub {
my $l = $_[0];
[ $l-[0] - $l-[2] ]
}
sub do_mul {
my $l = $_[0];
[ $l-[0] * $l-[2] ]
}
sub do_div {
my $l = $_[0];
# XXX Beware of bad matching
if ($l-[2] == 0) {
$l-[2] = 1;
}
[ $l-[0] / $l-[2] ]
}
my ($expn, $term, $factor);
$expn =
$alt-(
$using-($then-($term, $then-($literal-('+'), $expn)), &do_add),
$alt-(
$using-($then-($term, $then-($literal-('-'), $expn)), &do_sub),
$term
)
);
$term =
$alt-(
$using-($then-($factor, $then-($literal-('*'), $term)), &do_mul),
$alt-(
$using-($then-($factor, $then-($literal-('/'), $term)), &do_div),
$factor
)
);
$factor =
$alt-(
$using-(number(), sub { my $l = $_[0]; my $val = undef; for my $i (@$l) { $val .= $i; } [ $val ] } ),
$using-($then-($literal-('('), $then-($expn, $literal-(')'))), sub { my $l = $_[0]; [ $l-[1] ] } )
);
sub number {
$many-($literals-('0123456789'))
}
# simple tests
print $expn-('2+(4-1)*3+4-2')-[0]-[0]-[0], "n";
print $expn-('1+2+3-2*7/2')-[0]-[0]-[0], "n";
注意到do_div里有个很糙的除零处理。由于组合子语法分析会产生无法继续分析的中间结果，所以可能出现除零的情况，这里粗糙地予以避免。实际上比较理智的方式是生成延迟求值的中间表示（比如AST），从分析结果中筛选出来再进行求值。
这里的结果输出是个巧合。读者仍然应该注意到，对(v, xs)是正确的最终结果当且仅当xs是空串。
在BNF的书写过程中，我预先声明了规则变量，并传递了对规则变量的引用。仔细阅读了程序的读者会发现一个没给出实现的函数descalar, 这一函数用于对引用的引用进行一次解引用，从而获得实际的规则；由于descalar被调用的时机均在算子返回的函数获得输入串之后，我们可以获得正确的规则，而不必受制于循环的依赖。
完整的实现可以在 github.com/Akvelog/a-little-five/blob/master/_5wraith.pl 找到。
参考文献
[Hutton92] Graham Hutton, Higher-Order Functions for Parsing, Journal of Functional Programming 2(3):323–343, July 1992.
[Hutton96] Graham Hutton, Erik Meijer, Monadic Parser Combinators, 1996.
[Frost96] Richard A. Frost, Barbara Szydlowski, Memoizing purely functional top-down backtracking language processors, Science of Computer Programming 27(3):263-288, 1996.
楼主 2015-10-25 13:56 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
