在 上个月的专栏文章中,如果您掌握以下几点的话,那么您会明白,底层代码的可用性不会成为问题:
如何识别配置脚本
如何选择允许哪种配置
识别哪种环境要求黑箱可扩展性
衡量可扩展性所带来的构建复杂性
当提供此扩展性给配置脚本时,您 实际上正在构建一种语言。
您还认识到,考虑到应用程序的黑箱可扩展性,使用 S-expression 是一种快速建立一种配置语言的有效手段。我们将在本文深入研究 S-expression,并提供了一个如何用这些 S-expression 来快速方便地为特定应用程序建立配置语言的示例。
关于 S-expression 的一些知识
让我们回忆一下,S-expression 是由圆括号分隔的元素列表的语法表示法。S-expression 有三种形式:
空元素列表
非空元素列表
单一原子元素(如一个字)
S-expression 作为配置语言非常有用,因为它们易于解析。一般的 S-expression 解析器将数据读入程序,然后这个程序再检查表达式是否遵守更具体的语法约束。用这种方法,我们得到了解析输入的所有好处 — 如早期的错误输入检测和增加的安全性 — 除去了编写和维护常规语法解析器时所带来的精力消耗和开销。同样,不同于解析器生成器所构造的语法解析器,跟踪语法错误来源时,错误消息的输出可以很精确且很有帮助。
“S”较 XML 的优势
正如我在上一篇文章中提到的,使用 S-expression 的许多好处同样可以通过使用基于 XML 的配置语言而获得。基于 S-expression 配置语言较 XML 的主要优势在于它是非常轻量型的而且建立快速。
同样,在许多情况下,基于 S-expression 的配置脚本比等价的基于 XML 的脚本更易于阅读和编辑。当我们讨论下面一些基于 S-expression 脚本的示例时,请考虑在 XML 符号中它们是什么样子。
示例:给编辑器添加宏支持
假定我们希望给文本编辑器添加简单的宏支持,允许用户定义基本操作的复杂序列。我们可能甚至想加入对循环或递归构造的支持。
这里是宏的可能情形的示例:
清单 1. 简单的宏
(define (cutAndPasteAtEnd)(sequence (cut HIGHLIGHTED_TEXT) (move-to END_OF_DOCUMENT) (paste CLIPBOARD))
即使我们还没有讨论我们配置语言的语法和语义,您也许猜出了这个脚本的意图:一个对文本进行 剪切、 移动和 粘贴操作的序列,这些操作通常是应用程序的用户自己做的事情。
写下您希望您的语言能适合的各种脚本的示例是构建您的语言好的开端。事实上,对于您的解释器,这些示例有助于形成良好的单元测试组。
以下是更复杂宏的示例:
清单 2. 内容更丰富的宏
(define (find-and-replace target replacement)(move-to BEGINNING_OF_DOCUMENT)(while (not AT_END) (cut NEXT_WORD) (if (equals CLIPBOARD target) (paste replacement) (paste target)) (move-to NEXT_WORD)))
同样,您也许猜出了这个脚本表示应用程序脚本语言中的 查找并替换的实现。对于不熟悉 Scheme 风格语法的读者,我要指出以下几件事情:
所有操作都使用 前缀符号。这种风格使解析更容易,但对于某些操作,如 equals ,通常写成中缀操作符,这对于初学者来说,看起来会很奇怪。
if语句,如大多数语言中一样,有三个部分:按顺序写出 条件子句、 满足条件时执行的部分和 不满足条件时执行的部分。但是,同样的,为了使解析更容易,我没有用 else 关键字来标记不满足条件时要执行的部分。
这个示例说明了向应用程序添加有充分表达性的脚本语言是用来提高可扩展性的一种较佳的方法。它使得能够添加各种新功能而无须修改甚至查看原始源代码。
示例:确定脚本编制语言
为实现这一脚本编制语言,首先必须确切地说明这个语言到底是什么。这意味着明确语法和语义。
我们可以使用 BNF 符号来说明语法,如下:
清单 3. 明确说明脚本编制语言的语法
) ::= | ::= (define ( ) ) ::= | args | (cut ) | (paste ) | (move-to ) | (sequence ) | (if ) | (while ) | (return ) | ( ) ::= | ::= | ::= | (not ) | (or ) | (and ) | (equals ) | ( ) ::= any word consisting of only letters and numbers (but starting with a letter). ::= BEGINNING_OF_DOCUMENT | END_OF_DOCUMENT | AT_END | CLIPBOARD
深入研究
请注意这种语言包含过程定义。这些过程定义允许用户抽象出经常使用的操作序列,然后在多处应用此抽象,作为值传递给不同参数(类似 Java 语言中的方法定义)。我正在定义一个脚本,这个脚本包含后跟一个表达式的这些定义的序列。
在这个简单语言中遗漏了几件事:
Let表达式,用来绑定过程中的变量;可以用额外的过程定义来模拟 let 表达式,但将它们作为语言的一部分会更方便。
赋值语句
静态类型系统
尤其是,添加静态类型系统将允许解释器在脚本运行之前捕捉到许多错误。
另一方面,静态类型系统也会使语言更冗长,而且不可避免地,它们不仅拒绝真正有错误的程序,还拒绝一些本来运行得很好的程序。出于这些原因,您通常会看到在程序趋于较短时会从脚本语言中省去静态类型。在该示例中我们将省去它们,但如果想添加的话,当然没有问题。
精心编写三阶段解析器
一旦我们对这个语言的语法满意,我们就可以着手写它的语法解析器。这就是使用 S-expression 的优势所在。与编写常规二阶段语法解析器(标记化和解析)不同,我们通过增加额外的阶段来大大简化整个过程。
这个额外的阶段发生在标记化与解析成语法树之间。它包括将输入分割为 S-expression 内部的表达式。这个分割过程基本上等同于圆括号匹配,但这样做使得解析过程更加简单。
从流中抽取表示
假设我们已经使用标记程序(比如,象用于较小规模输入的 java.util.StreamTokenizer 或 StringTokenizer )将数据转换成标记流,其中每个标记要么是左圆括号,右圆括号,要么是词。
操作这个流最方便的办法是堆栈。在清单 5,我定义了接口 StackI 它可以用任何我们喜欢使用的标记程序的适配器来实现。用这种方法,我们可以把注意力放在程序结构上而不用担心任一特定标记程序的细节。然后我们可以编写一些方法来从这个流中构造 S-expression 表达式。
本质上,这个过程涉及解析流中的第一个 S-expression,然后确定这个 S-expression 之后没有东西了(因为整个程序只是一个大的 S-expression)。对 S-expression 的解析可以递归定义,因为一个复杂 S-expression 的元素自身就是较简单的 S-expression:
清单 4. 解析原始标记流
import java.util.LinkedList;import java.util.*;class SExpParseException extends Exception { public SExpParseException(String msg) { super(msg); }}interface StackI { public Object peek(); public Object pop(); public Object push(Object o); public boolean empty();}abstract class SExp { public static final String LEFT_PAREN = '("; public static final String RIGHT_PAREN = ")"; public static SExp parseSExp(StackI tokens) throws SExpParseException { SExp nextSExp = parseNextSExp(tokens); if (tokens.empty()) { // The stack of tokens consisted of a single S-expression // (with possible subexpressions), as expected. return nextSExp; } else { throw new SExpParseException("Extraneous material " + "at end of stream."); } } public static SExp parseNextSExp(StackI tokens) throws SExpParseException { if (tokens.empty()) { throw new SExpParseException("Unexpected end of token stream."); } else { // tokens.pop() succeeds Object next = tokens.pop(); if (next.equals(LEFT_PAREN)) { // The S-expression is a list. Accumulate the subexpressions // this list contains, and return the result. SList result = new SEmpty(); while (! tokens.empty()) { // tokens.pop() succeeds next = tokens.peek(); if (next.equals(RIGHT_PAREN)) { // We've reached the end of the list. We need only // pop off the ending right parenthesis before returning. // Since subexpressions were accumulated in the front // of the list, we must return the reverse of the list // to reflect the proper structure of the S-expression. tokens.pop(); return result.reverse(); } else { // Recursively parse the next subexpression and // add it to result. result = new SCons(parseNextSExp(tokens), result); } } // If we haven't yet returned, then we've reached the end // of the token stream without finding the matching right // paren. throw new SExpParseException("Unmatched left parenthesis."); } else if (next.equals(RIGHT_PAREN)) { // A right parenthesis was encountered at the beginning of // the S-expression! throw new SExpParseException("Unmatched right parenthesis."); } else { // The next S-expression is an atom. return new Atom(next); } } }}abstract class SList extends SExp { abstract SList reverse();}class SEmpty extends SList { public String toString() { return '( )"; } SList reverse() { return this; }}class SCons extends SList { public SExp first; public SList rest; public SCons(SExp _first, SList _rest) { this.first = _first; this.rest = _rest; } SList reverse() { SList result = new SEmpty(); SList elements = this; while (! (elements instanceof SEmpty)) { result = new SCons(((SCons)elements).first, result); elements = ((SCons)elements).rest; } return result; }}class Atom extends SExp { public Object value; public Atom(Object _value) { this.value = _value; }}
定义用于解析语法树的类
现在,与解析原始标记流相比,将 S-expression 解析为语法树就是小事一桩。但为了这么做,我们将需要为语法中每个语法结构定义一个单独的类:
清单 5. 为每个语法结构定义单独的类
import java.util.LinkedList;abstract class SyntaxTree { public abstract Object accept(SyntaxTreeVisitor that);}class Script. extends SyntaxTree { LinkedList definitions; Expression body; public Script(LinkedList _definitions, Expression _body) { this.definitions = _definitions; this.body = _body; } public Object accept(SyntaxTreeVisitor that) { return that.forScript(this); }}abstract class Statement extends SyntaxTree {}class CutStatement extends Statement { Name name; public CutStatement(Name _name) { this.name = _name; } public Name getName() {return this.name;} public Object accept(SyntaxTreeVisitor that) { return that.forCutStatement(this); }}...abstract class Expression extends SyntaxTree {}...abstract class Name extends SyntaxTree {}...abstract class SyntaxTreeVisitor { public abstract Object forScript(Script. that); public abstract Object forCutStatement(CutStatement that); ...}
一系列的定义过程。对于语法中每个非终端符号,我们需要一个抽象类,对那个非终端符号的每种格式,我们需要一个具体类。我们还将希望定义这个类层次结构的访问者(visitor)。
为了给您启发,我仅提供了一些必要的代码。扩展它非常简单。类似这样的代码非常适合于自动代码生成。
递归定义解析方法
在定义完所有这些类之后,我们可以递归地为每个语法结构定义解析方法:例如 parseStatement 、 parseExpression 。
每个方法将接受一个 S-expression。它的主体将由一个大的 if-then-else 语句组成,这个语句检查 SExp 的第一个元素,然后确定它符合哪个语法结构。在这一点上,我们简单地检查一下 SExp 的格式是否符合那个结构的有效格式(例如, if 语句由三个部分组成:一个表达式和两个语句),然后调用适当的构造器,递归解析子部分。
例如,清单 6 显示我们将如何解析 if 语句:
清单 6. 解析 if 语句
parseStatement(SExp sExp) { ... } else if (sExp.nth(0).equals("if") && sExp.length() == 4) { return new IfStatement(parseExp(sExp.nth(1)), parseStatement(sExp.nth(2)), parseStatement(sExp.nth(3))); } ...}
在这个 if-then-else 语句结束部分是 else 子句,这个子句对应于 S-expression 与语法结构有效格式不匹配的情况。在此情况下, SyntaxError 连同适当的错误信息一同抛出。
下一步:求值
在脚本被解析为这种格式之后,我们可以轻易地实现解释过程的其它阶段。假如我们的语言包含静态类型系统,则这时应该包含类型检查程序。
同样,此时应该包含用于任何其它语言约束的检查程序。例如,如果我们的脚本编制语言包含类的层次关系,则我们应该希望检查这个层次结构中不包含循环。
实现这些不同阶段的一种好方法是对每个阶段使用语法树的访问者。那样的话,针对特定阶段的所有代码都放在一个地方。此外,在额外阶段添加也较容易 — 我们只要编写另一个访问者并将它放在这个序列中。这样做的结果是,根本无需修改其它类。
但在我们的示例语言中,没有添加这样的约束,我们可以继续到解释的最终阶段:求值。象解析之后的其它阶段一样,本阶段也可以作为语法树的访问者实现,并且我由衷地推荐这么做。
访问者中每一个 for 子句将描述如何对特定形式的程序构造求值。对我们的语言中基本操作的求值将符合所支持应用程序的方法调用。
清单 7. for 子句描述了构造求值
class Evaluator extends SyntaxTreeVisitor { Application app; public Object forCutStatement(CutStatement that) { app.cut(that.getName()); // A VoidObject is returned as the result of evaluating statements, to meet the signature of the for methods. return new VoidObject(); } ...}
至于更复杂的操作,我们可以依靠 Java 语言的底层程序构造轻易地实现这些操作。例如,这里是如何实现 if 和 while 构造的例子:
清单 8. 实现 if 和 while 构造
public Object forWhileStatement(WhileStatement that) { while (that.getTest().accept(this).equals(new Boolean(true))) { that.getBody().accept(this); } return new VoidObject(); } public Object forIfStatement(IfStatement that) { if (that.getTest().accept(this).equals(new Boolean(true))) { that.getConsequent.accept(this); } else { that.getAlternative.accept(this); } return new VoidObject(); }}
读取良好的脚本
现在,该是我们的语言所编写的脚本的解释了,这将涉及包含该脚本的文件(或其它流)中的简单读取,然后通过本文所描述的那些阶段来处理它。
应用程序的用户和开发人员都能以各种方法扩展这个应用程序而不必涉及源代码。所以您拥有了:通过基于 S-expression 语言的黑箱可扩展性。
这是关于由四部分组成的添加应用程序可扩展性的小系列文章的最后一篇。我要再次强调的是:这些技术就象锋利的双刃剑 — 有利也有弊。它们可以是实现代码有效复用的功效强大的手段,但也会是非常危险的:如果您过于不加选择和草率地使用它们添加可扩展性 — 您的应用程序的复杂性会膨胀到失去控制。那时要小心了!
遇见你,是我一生的幸运;爱上你,