企业网站推荐,php 网站 服务器,网站首页布局,时尚类网站设计公司简介#xff1a;Ward Cunningham 曾经说过#xff0c;干净的代码清晰地表达了代码编写者所 想要表达的东西#xff0c;而优美的代码则更进一步#xff0c;优美的代码看起来就像是专门为了 要解决的问题而存在的。在本文中#xff0c;我们将展示一个组合式解析器的设计、实…简介Ward Cunningham 曾经说过干净的代码清晰地表达了代码编写者所 想要表达的东西而优美的代码则更进一步优美的代码看起来就像是专门为了 要解决的问题而存在的。在本文中我们将展示一个组合式解析器的设计、实现 过程最终的代码是优美的极具扩展性就像是为了解析特定的语法而存在的 。我们还会选取 H.248 协议中的一个例子用上述的组合式解析器实现其语法 解析器。读者在这个过程中不仅能体会到代码的美感还可以学习到函数式编程 以及构建 DSL 的一些知识。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 c0 c9;}}解析单位数字的解析器 digit 定义如下Parser digit new SAT(new IsDigit(), new Item());我们可以采用同样的方法组合出单个字母、单个大写 字母、单个小写字母等解析器来。接下来我们定义一个 OR 组合子 其接收两个解析器并分别用这两个解析器去解析一个目标串只要有一个解析 成功就认为解析成功如果两个都失败则认为失败代码定义如下class OR implements Parser{private Parser p1;private Parser p2;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 (ca cz) || (cA cZ);}}用于解析单个字母的解析器 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),count1) : pre;}}使用该组合 子我们可以容易地定义出用于识别由最少一个最多 10 个字母组成的串的解 析器如下Parser one_to_ten_alpha new OneOrMany (10,alpha);本文的组合子就定义到此不过读者可以根据自己 的需要用同样的方法容易地定义出符合自己要求其他组合子来。抽象 的手段如果在 DSL 的构造中仅仅提供了一些原子和组合手段并且组 合的结果无法再次参与组合那么这个 DSL 的扩展能力和适用性就会大大折扣 。相反如果我们还能提供出抽象的手段对组合结果进行命名命名后的复合实 体可以像原子一样参与组合那么 DSL 的扩展能力就会非常的强大适用性也 会大大增加。因此抽象的手段在 DSL 的构造过程中是至关重要的。敏 锐的读者可能已经发现对于我们的解析 DSL 来说其实在前面的小节中已经 使用了抽象的手段。比如我们在 alphadigitdigit_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 消 息的组成部分和具体内容。我们仅仅关注其中的 NAME 语法定义如下NAME ALPHA *63(ALPHA / DIGIT / _ )ALPHA %x41-5A / %x61-7A ; A-Z, a-zDIGIT %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 语法识别的实验如下表所示
