利用 Java 实现组合分析器
孙 鸣 和 邓 辉
2010 年 6 月 24 日发布
DSL 设计基础
我们如:Java 实现某一功能时，语言实际上是指挥计算机来完成这一功能。然而，语言能给我们带来的并不局限于此。更重要的是，语言提供了一个框架维和表达计算过程提供了一个框架。这个框架的核心是如何将简单的概念组合成更复杂的概念，同时保持组合方法的封闭，也就是说，组合的复杂概念与简单的概念不同。引用“Structure and Interpretation of Computer Programs”(参见 根据参考资源)，任何强大的语言都是通过以下三种机制实现的:原子:语言中最简单、最基本的实体；
组合方法：将原子组合成更复杂的实体；
抽象：命名复杂实体的方法，命名后的复杂实体可以像原子一样组合成更复杂的实体。
像 Java 这种通用的编程语言注重解决问题的一般方法。因此，这三种机制也是通用的。在解决特定问题时，这一通用手段与特定问题领域的概念和规则之间存在语义差距。因此，在实现某些问题领域，非常清晰的概念和规则可能会变得不那么清晰。作为程序员，使用干净的代码来实现功能只是初级要求，更重要的是提高一般语言的水平，在特定问题领域建立语言(DSL)，在这个过程中，关键是寻找和定义问题领域 原子概念、组合方法和抽象手段。这个 DSL 它不一定像一般语言那样完整。其目标是清晰直观地表达问题领域的概念和规则。其结果是将一般编程语言转化为解决特定问题的特殊语言。
我们曾经在基础 Java 的界面布局 DSL 设计与实现(见 参考资源)一文构建了界面布局的一种 DSL，它体现了上述思想。在本文中，我们将以解析器的结构为例，讨论如何构建一个字符串分析 DSL，这种 DSL 读者可以根据自己的需要可以根据自己的需要定义自己的组合手段。此外，读者还可以从本文中欣赏到 优雅的函数编程。
解析器原子
什么是解析器？什么是最简单的分析器？人们通常认为分析器是判断输入的字符串是否符合给定的语法规则，并在必要时提取相应的语法单位实例。这种理解在概念上没有问题。但是，为了定义用于分析的内容 DSL，然后需要更准确的定义，也就是说，我们需要定义解析器概念的确切类型。在 Java 中，我们用 interface 定义解析器类型如下：interface Parser
{
public Result parse(String target);
}
其中，target 要分析的字符串，Result 这是分析的结果，只要符合接口语义的对象，我们就称之为分析器实例。Result 定义如下：class Result
{
private String recognized;
private String remaining;
private boolean succeeded;
private Result(String recognized, String remaining,
boolean succeeded) {
this.recognized = recognized;
this.remaining = remaining;
this.succeeded = succeeded;
}
public boolean is_succeeded() {
return succeeded;
}
public String get_recognized() {
return recognized;
}
public String get_remaining() {
return remaining;
}
public static Result succeed(String recognized,
String remaining) {
return new Result(recognized, remaining, true);
}
public static Result fail() {
return new Result("", "", false);
}
}
其中，recognized 字段表示分析器所知道的部分，remaining 表示该解析器解析后剩余部分，succeeded 表示分析是否成功，Result 是值对象。有了解析器的精确定义，我们可以定义最简单的解析器。显然，最简单的解析器是什么都不解析的解析器，将目标字符串原样返回，我们称之为 Zero，定义如下：class Zero implements Parser
{
public Result parse(String target) {
return Result.succeed("", target);
}
}
Zero 解析器一定会解析成功，不做任何语法单位识别并直接返回目标字符串。让我们定义另一个非常简单的解析器 Item，只要目标字符串不空，Item 以目标字符串的第一个字符为识别结果，并返回成功，如果目标字符串为空，则返回失败，Item 定义如下：class Item implements Parser
{
public Result parse(String target) {
if(target.length() > 0) {
return Result.succeed(target.substring(0,1),
target.substring(1));
}
return Result.fail();
}
}
Zero 和 Item 是我们的分析器 DSL 在下一节中，我们将定义解析器的组合方法。
分析组合子
我们在上一节中定义了它 Item 解析器，它无条件的解析出目标字符串中的第一个字符，如果我们希望能够变成有条件的解析，就可以定义出一个 SAT 组合子接收条件谓词(predicate)并生成复合解析器，复合分析器的成功分析取决于原分析器的分析结果是否符合给定的条件谓词、条件谓词和 SAT 定义如下：interface Predicate
{
public boolean satisfy(String value);
}
class SAT implements Parser
{
private Predicate pre;
private Parser parser;
public SAT(Predicate predicate, Parser parser) {
this.pre = predicate;
this.parser = parser;
}
public Result parse(String target) {
Result r = parser.parse(target);
if(r.is_succeeded() && pre.satisfy(r.get_recognized())) {
return r;
}
return Result.fail();
}
}
如果我们想定义一个解析单个数字的解析器，我们可以定义它 IsDigit 并通过条件谓词 SAT 把该 IsDigit 和 Item 代码组合如下：class IsDigit implements Predicate
{
public boolean satisfy(String value) {
char c = value.charAt(0);
return c>='0' && c<='9';
}
}
解析单位数字的解析器 digit 定义如下：Parser digit = new SAT(new IsDigit(), new Item());
我们可以用同样的方法组合单个字母、单个大写字母、单个小写字母等分析器。
接下来，我们将定义一个 OR 组合子接收两个分析器，分别用这两个分析器分析一个目标串。只要一个分析成功，就认为分析成功。如果两者都失败了，代码定义如下:class OR implements Parser
{
private Parser p1;
private Parser p;
public OR(Parser p1, Parser p2) {
this.p1 = p1;
this.p2 = p2;
}
public Result parse(String target) {
Result r = p1.parse(target);
return r.is_succeeded() ? r : p2.parse(target);
}
}
我们可以定义出一个新的解析器 digit_or_alpha，如果目标字符是数字或者字母那么该解析器就解析成功，否则就失败。代码如下：
判断是否是字母的条件谓词：class IsAlpha implements Predicate
{
public boolean satisfy(String value) {
char c = value.charAt(0);
return (c>='a' && c<='z') || (c>='A' && c<='Z');
}
}
用于解析单个字母的解析器：Parser alpha = new SAT(new IsAlpha(), new Item());
digit_or_alpha 解析器定义：Parser digit_or_alpha = new OR(digit, alpha);
下面我们来定义一个 顺序组合子 SEQ，该组合子接收两个解析器，先把第一个解析器应用到目标字符串，如果成功，就把第二个解析器应用到第一个解析器识别后剩余的字符串上，如果这两个解析器都解析成功，那么由 SEQ 组合起来的这个复合解析器就解析成功，只要有一个失败，复合解析器就解析失败。当解析成功时，其识别结果由这两个解析器的识别结果连接而成。
为了能够连接两个 Result 中已经识别出来的解析结果，我们在 Result 类中新增一个静态方法：concat，其定义如下：public static Result concat(Result r1, Result r2) {
return new Result(
r1.get_recognized().concat(r2.get_recognized()),
r2.get_remaining(), true);
}
顺序组合子 SEQ 的定义如下：class SEQ implements Parser
{
private Parser p1;
private Parser p2;
public SEQ(Parser p1, Parser p2) {
this.p1 = p1;
this.p2 = p2;
}
public Result parse(String target) {
Result r1 = p1.parse(target);
if(r1.is_succeeded()) {
Result r2 = p2.parse(r1.get_remaining());
if(r2.is_succeeded()) {
return Result.concat(r1,r2);
}
}
return Result.fail();
}
}
现在，如果我们想定义一个解析器用以识别第一个是字母，接下来是一个数字的情况，就可以这样定义：Parser alpha_before_digit = new SEQ(alpha, digit);
接下来我们定义本文中的最后一个组合子：OneOrMany。该组合子接收一个解析器和一个正整数值，其生成的复合解析器会用原始解析器连续地对目标串进行解析，每一次解析时的输入为上一次解析后剩余的字符串，解析的最大次数由输入的正整数值决定。如果第一次解析就失败，那么该复合解析器就解析失败，否则的话，会一直解析到最大次数或者遇到解析失败为止，并把所有成功的解析的识别结果连接起来作为复合解析器的识别结果，OneOrMany 组合子的定义如下：class OneOrMany implements Parser
{
private int max;
private Parser parser;
public OneOrMany(int max, Parser parser) {
this.max = max;
this.parser = parser;
}
public Result parse(String target) {
Result r = parser.parse(target);
return r.is_succeeded() ? parse2(r,1) : Result.fail();
}
private Result parse2(Result pre, int count) {
if(count >= max) return pre;
Result r = parser.parse(pre.get_remaining());
return r.is_succeeded() ?
parse2(Result.concat(pre,r),count+1) : pre;
}
}
使用该组合子，我们可以容易地定义出用于识别由最少一个，最多 10 个字母组成的串的解析器，如下：Parser one_to_ten_alpha = new OneOrMany(10,alpha);
本文的组合子就定义到此，不过读者可以根据自己的需要，用同样的方法容易地定义出符合自己要求其他组合子来。
抽象的手段
如果在 DSL 的构造中，仅仅提供了一些原子和组合手段，并且组合的结果无法再次参与组合，那么这个 DSL 的扩展能力和适用性就会大大折扣。相反，如果我们还能提供出抽象的手段对组合结果进行命名，命名后的复合实体可以像原子一样参与组合，那么 DSL 的扩展能力就会非常的强大，适用性也会大大增加。因此，抽象的手段在 DSL 的构造过程中是至关重要的。
敏锐的读者可能已经发现，对于我们的解析 DSL 来说，其实在前面的小节中已经使用了抽象的手段。比如，我们在 alpha，digit，digit_or_alpha 以及 alpha_before_digit 等复合解析器的定义中已经使用了抽象的手段来对其进行命名，然后可以直接使用这个抽象的名字再次参与组合。由于我们的解析器是基于 Java 语言中的 interface 机制定义的，因此，Java 语言中已有的针对 interface 的抽象支持机制完全适用于我们的解析 DSL。因此，我们就无需定义自己的特定抽象手段，直接使用 Java 语言中的即可。
相信读者已经从上一小节中的例子中看到组合、抽象手段的强大威力。在下一小节中，我们将给出一个更为具体的例子：H.248 协议中 NAME 语法解析器的构造。
一个 H.248 实例
在本小节中，我们将基于前面定义的解析器原子和组合子，实现用于识别 H.248 协议中 NAME 语法的解析器的构造。
H.248 是一个通信协议，媒体网关控制器使用该协议来对媒体网关进行控制。H.248 协议是一个基于 ABNF(扩展 BNF)文法描述的基于文本的协议，协议中定义了 H.248 消息的组成部分和具体内容。关于 H.248 协议的具体细节，我们不在本文中讨论，有兴趣的读者可以从 参考资源 中获取更多内容。我们仅仅关注其中的 NAME 语法定义，如下：NAME = ALPHA *63(ALPHA / DIGIT / "_" )
ALPHA = %x41-5A / %x61-7A ; A-Z, a-z
DIGIT = %x30-39 ; digits 0 through 9
我们首先来解释一下其中的一些规则，*63 其实是 n*m 修饰规则的一个实例，表示最少 n 个最多 m 个，当 n 等于 0 时，可以简略写成 *m。因此，*63 表示最少 0 个，最多 63 个。/ 表示或规则，表示两边的实体可选。()表示其中的实体必须得有一个。- 表示范围。因此，DIGIT 表示单个数字，ALPHA 表示单个字母(大写或者小写)，(ALPHA/ DIGIT/ “_” )表示要么是个字母，要么是个数字，要么是个下划线。*63(ALPHA/ DIGIT/ “_” )表示，最少 0 个，最多 63 个字母或者数字或者下划线。两个实体顺序写在一起，表示一种顺序关系，ALPHA *63(ALPHA/ DIGIT/ “_” ) 表示，以字母开始，后面最少 0 个，最多 63 个 字母或者数字或者下划线。更多的规则可以参见 参考资源。
根据前面的内容可以很容易地直接表达出用于解析这个语法规则的解析器来。如下：class H248Parsec
{
public static Parser alpha() {
return new SAT(new IsAlpha(), new Item());
}
public static Parser digit() {
return new SAT(new IsDigit(), new Item());
}
public static Parser underline() {
return new SAT(new IsUnderline(), new Item());
}
public static Parser digit_or_alpha_or_underline() {
return new OR(alpha(), new OR(digit(), underline()));
}
public static Parser zero_or_many(int max, Parser parser){
return new OR(new OneOrMany(max,parser), new Zero());
}
public static Parser name() {
return new SEQ(alpha(),
zero_or_many(64,
digit_or_alpha_or_underline()));
}
}
可以看出，我们的代码和协议中的语法描述基本上完全一样，我们通过定义自己的面向解析的 DSL，把 Java 这种通用语言变成了用于 ABNF 语法解析的专门语言，符合 Ward Cunningham 关于美的代码的定义。最后，我们用该解析器来做一些关于 NAME 语法识别的实验，如下表所示：输入字符串成功标志识别结果剩余字符串""false""""
"_U"false""""
"2U"false""""
"U"true"U"""
"U{"true"U""{"
"U2{"True"U2""{"
"U_{"true"U_""{"
"U123_{"True"U123_""{"
"USER001"True"USER001"""
"USER001{"True"USER001""{"
"a0123456789
0123456789
0123456789
0123456789
0123456789
0123456789
0123456789"True"a0123456789
0123456789
0123456789
0123456789
0123456789
0123456789
0123""456789"
相关主题