好像好多地方的 Literal 都拼写成 Literial 了……只能说这是一个 feature。

Parser 的组成和原理

这里模仿该作者的 Parser 库，对 LL(1) 语法分析器生成器（后面都称其为 Parser）进行实现。这里因为我觉得作者的代码结构非常复杂且难以理解，因此就按照自己的意愿进行了修改。再次确认其功能——根据用户给定的匹配模式（Element 序列）对 Token 序列进行匹配，生成一定的抽象语法树。

语法分析最终生成的 AST 可以认为包含四种元素——

Token：来自词法分析的 Token 将会成为 ASTLeaf，即叶节点的成员，每一个叶节点都将对应一个 Token；
ASTList 和 ASTLeaf：没有被给予更丰富信息的原始 AST 节点。ASTList 将持有一个 ASTree 的数组，ASTLeaf 将持有 Token；
继承节点类：用户和库中预先定义的一些节点类，比如 NumberLiterial，WhileStatement，PrimaryExpr 等，这些类将继承 ASTList 或 ASTLeaf 类，同时对 eval 方法进行实现（这并非语法分析的范畴）。这个类群是 AST 中最重要的部分——对 AST 的编译或解释执行必须要利用其类型信息。如果想要对语言进行扩展，就必须要在该类群中编写新类，同时将其在 Parser 中引入。甚至可以要求不允许使用原生 ASTList，ASTLeaf，而必须完全使用继承节点类来构造 AST。
ParserPattern：用户自定义的语法分析器，其实质是一种匹配模式，其将通过 Java 方法的链式调用对 EBNF 进行表达，同时规定其将生成的 AST 节点的根结点以及子节点的信息。

Parser 所要做的，就是提供给用户这些功能——

通过 Java 代码对 EBNF 进行直接描述。
在能够描述 EBNF 的基础上，能够在进行匹配时，自定义能够保留哪些内容，生成哪些内容，也就是说自定义子树序列的结构（总不能把匹配到的东西全都拿走吧？）。
在能够描述 EBNF 的基础上，能够自定义生成的子树根结点的类型，或者推断出一个类型（这里说的类型指上面的第三种元素）。

这些功能总结来说，就是让用户能够根据 EBNF 和 Java 代码定义语法规则以及生成 AST 结构。

关于第 2 步的具体含义，这里举用作者的 Parser 库一个例子——对这样一个 BNF 范式——

1	`adder : NUMBER "+" NUMBER`

使用下面两种 Parser 代码，对字符串25 + 17能够生成两种不同结构的 AST——

1 2	`ParserPattern adder = rule(PlusExpr.class) .number().sep("+").number(); // sep 表示匹配分隔符，因此将丢弃`

可以看到，这个 AST 中+被舍弃掉了，如果想要对这个 AST 进行计算，则必须利用 PlusExpr 这个根结点的类型信息。下面是另一种实现——

1 2	`ParserPattern adder = rule(Expr.class) number().identifier("+").number(); // identifier 表示匹配且保留特定标识符`

显然，这个实现更具一般性，能够表达所有的双目运算。而且还能玩花活——中间的 ASTLeaf 可以被替换成树，或者说，表达式！返回一个中缀运算符的表达式！就如同下面的 Scheme 代码一样。

1 2	`(define a-plus-abs-b (a b) ((if (> b 0) + -) a b))`

Parser 的设计和实现

Parser 库的编写包括两个部分——ParserElement，ParserPattern，其关系就像原作者代码中的 Element 和 Parser，只不过将其分离到不同文件中。

ParserElement 以及一些例子

ParserElement 表示解析器的“元素”，ParserPattern 由 ParserElement 序列组成，利用其来表示一整个模式，模式也是一种“元素”。任何 EBNF 都将表示为 ParserElement 的序列，并能够依序进行解析。

ParserElement 的定义如下——

public interface ParserElement {
    Class<? extends ASTree> getTargetClass(); // 目标类应当是继承 ASTree 接口的，这是毋庸置疑的——它要充当 AST 中的特定节点
    Optional<ASTree> parse(Lexer lexer);
    boolean match(Lexer lexer);
}

每一个 ParserElement 都代表一种特定的匹配规则的实现，这种规则通常能够和 EBNF 中的元符号对应。ParserElement 有三个方法——getTargetClass：标识这个模式元素进行匹配后返回的 AST 子树的类型；parse：对该模式元素进行应用，通过词法分析器获取到 ASTree 并返回。这里使用了 Optional，标识其可能返回空值——就如上面示例中的 sep 方法；match：查看是否可以解析。

下面举几个示例——NumberLiterialElement，SepElement。

首先是 SepElement，它能够读取和丢弃非终结符。

/**
 * 识别形如"{"，")"的终止符的 Parser 元素
 */
class SepElement implements ParserElement {
    String[] sepNames;
    public SepElement(String[] names) {
        sepNames = names;
    }
    @Override
    public Class<? extends ASTree> getTargetClass() {
        return null;
    }
    // 不返回结果，直接丢弃
    @Override
    public Optional<ASTree> parse(Lexer lexer) {
        if (!match(lexer)) throw new ParseException(lexer.peek(0));
        lexer.read();
        return Optional.empty();
    }
    @Override
    public boolean match(Lexer lexer) {
        if (!lexer.peek(0).isIdentifier())
            return false;
        for (String name : sepNames)
            if (Objects.equals(name, lexer.peek(0).getText()))
                return true;
        return false;
    }
}

然后是 NumberLiterialElement，它能够读取一个数值字面量并返回一个 NumberLiteral——这是预先定义的一个继承 ASTLeaf 的类——如果没有特别指定返回类型的话。

public class NumberLiteralElement implements ParserElement {
    private final Class<? extends ASTLeaf> clazz;

    public NumberLiteralElement(Class<? extends ASTLeaf> clazz) {
        this.clazz = clazz;
    }
    public NumberLiteralElement() {
        this.clazz = null;
    }
    @Override
    public Class<? extends ASTree> getTargetClass() {
        return this.clazz;
    }
    @Override
    public Optional<ASTree> parse(Lexer lexer) {
        if (clazz == null)
            return Optional.of(new NumberLiteral(lexer.read()));
        try {
            ASTree res = clazz.getDeclaredConstructor(Token.class).newInstance(lexer.read());;
            return Optional.of(res);
        } catch (Exception e) {
            e.printStackTrace();
            return Optional.empty();
        }
    }
    @Override
    public boolean match(Lexer lexer) {
        return lexer.peek(0).isNumber();
    }
}

显然，ParserPattern 也应当是 ParserElement——元素实际上也是一种模式，模式也可以当作一个元素来看待，其也能够和其他元素相组合成为更复杂的模式。

ParserPattern

ParserPattern 是最主要的类——用户通过声明和构造特定 ParserPattern 来使其能够和特定 EBNF 范式对应。ParserPattern 实际上也是一种 ParserElement，区别在于其并非是原子的，而是包括了一个 Element 序列，其本身不负责具体的匹配（但是仍旧是保存有返回类型的），而是将匹配工作委托给其 Element 序列去执行。

下面是 ParserPattern 的源代码——

public class ParserPattern implements ParserElement {
    private final List<ParserElement> parserElems;
    private final Class<? extends ASTree> clazz;

    private ParserPattern() {
        this(null);
    }
    private ParserPattern(Class<? extends ASTList> rootClazz) {
        this.clazz = rootClazz;
        this.parserElems = new ArrayList<>();
    }
    public static ParserPattern rule() {
        return rule(null);
    }
    public static ParserPattern rule(Class<? extends ASTList> rootClazz) {
        return new ParserPattern(rootClazz);
    }

    @Override
    public Class<? extends ASTree> getTargetClass() {
        return this.clazz;
    }

    // 可见，其将委托给 Element 序列进行匹配并返回结果
    // 这里强制要求，ParserPattern 必须返回 ASTList 及其子类
    // 这是非常不优雅的，解决方案有几个——要么在创建过程时就进行修正，要么在创建完成后进行操作。否则这会对求值造成影响
    @Override
    public Optional<ASTree> parse(Lexer lexer) {
        List<ASTree> res = new ArrayList<>();
        for (ParserElement elem : parserElems)
            elem.parse(lexer).ifPresent(res::add);
        if (this.clazz == null)
            return Optional.of(new ASTList(res));
        try {
            ASTree tmpTree = clazz.getDeclaredConstructor(res.getClass()).newInstance(res);
            return Optional.of(tmpTree);
        } catch (Exception e) {
            e.printStackTrace();
            return Optional.empty();
        }
    }

    @Override
    public boolean match(Lexer lexer) {
        if (parserElems.size() == 0) return true;
        return parserElems.get(0).match(lexer);
    }

    public ParserPattern sep(String...sepNames) {
        parserElems.add(new SepElement(sepNames));
        return this;
    }

    public ParserPattern number(Class<? extends ASTLeaf> clazz) {
        parserElems.add(new NumberLiteralElement(clazz));
        return this;
    }
    public ParserPattern number() {
        parserElems.add(new NumberLiteralElement(null));
        return this;
    }
	// ....
}

ParserPattern 的使用方法上面已经描述了。匹配简单的终结符的 Element 是容易编写的，但是那些复杂的呢？对非终结符如何处理？[]，{}，|元符号该如何处理？这才是最大的考验。

必须的非终结符（ast）

首先解决非终结符。非终结符的实现还是容易想到的——它也是用户所定义的 ParserPattern，因此它甚至都不需要另外定义，加一个方法即可——

public class ParserPattern implements ParserElement {
    // ....
	public ParserPattern ast(ParserPattern parserPattern) {
        parserElems.add(parserPattern);
        return this;
    }
    // ....
}

下面对其进行一下测试，看能否行得通，试一个非常简单的 EBNF——

1
2
3

adder : NUMBER add NUMBER
add   : add1
add1  : "+"

对应的定义代码如下——

// 这里其实没必要这样定义——只有在有递归定义的时候才需要这样。但这样清晰些
ParserPattern adder_ = rule();
ParserPattern add_ = rule();
ParserPattern add1_ = rule();

ParserPattern adder = adder_.number().ast(add_).number();
ParserPattern add = add_.token(add1_);
ParserPattern add1 = add1_.sep("+");

对字符串25 + 17最终结果如图。

虽然实现了，但是这种嵌套有点离谱——这是 ParserPattern 返回 ASTList 导致的必然结果。因此对其的修改势在必行，但是现在先把所有功能都搭起来先。

元符号|（or）

|是原始 BNF 范式中仅有的元符号。其的实现也是容易理解的——它保存一个 ParserPattern 集合。在进行匹配时，遍历集合，找到同其能够进行匹配的 ParserPattern 并利用其进行解析。考虑到这里实现的语法分析器是 LL(1) 的，因此并不考虑有多匹配的情况（这么看起来，好像 LL(k) 实现起来并不复杂）。

public class OrElement implements ParserElement {
    // ....
	private ParserPattern choose(Lexer lexer) { // 选择 parser 的方法
            for (ParserPattern parser : parsers)
                if (parser.match(lexer))
                    return parser;
            return null;
        }
    @Override
    public Optional<ASTree> parse(Lexer lexer) {
        ParserPattern p = choose(lexer);
        if (p == null) throw new ParseException(lexer.peek(0)); // 一个都没找到说明出现语法错误
        return p.parse(lexer);
    }
    // ....
}

实验 or 的方法比较简单——处理不定长度的字符串试试。测试的 BNF 和 Java 定义如下——

// adder : "+" expr | EOL // 试了好多次，终于写出来啦……
// expr : NUMBER adder
ParserPattern adder_ = rule();
ParserPattern expr_ = rule();

ParserPattern adder = adder_.or(
    rule().token("+").ast(expr_),
    rule().sep("\\n") // 似乎不使用 EBNF 的话，必须要给定空终结符才能进行这种递归…
);
ParserPattern expr = expr_.number().ast(adder_);

对1 + 2 + 3 + 4 + 5 + 6，其生成的 AST 令人感叹——(1 ((+ (2 ((+ (3 ((+ (4 ((+ (5 ((+ (6 (())))))))))))))))))，图就不画了，总之验证这种写法确实达到了效果。出现这种情况的原因是 ASTList 默认的创建方式——把所有生成的 AST 节点全当成子树。

接下来还有{}元符号，[] 元符号，其分别对应 repeat 方法，maybe 和 option 方法。在这里，关于 repeat 方法需要注意的是，其是贪婪的，将会持续进行匹配直到不再合法，书中好像没有明确体现这一点。对其的实现留待之后吧。毕竟到周一啦。

进行了更多思考，觉得对于 Parser 的设计，应当只提供一些最基本的方法——即能够对非终结符，终结符，各种 EBNF 元符号进行表述的方法，并要求用户来提供/自定义其他方法（无论是通过继承还是通过组合，委托都可），从而给予用户最大的可扩展性。

自上次写这玩意已经过了两个星期了，本打算另开文章再水一篇笔记，想想还是算了，同时决定从实践的角度再次重新看待我正在学习的东西。

我学习编译原理的目的并非是做出来一个通用编程语言——当前对其的学习只是为了让我能够对编程语言的底层，如符号表，作用域之类的概念能够有更加深刻的理解，仅此而已，编写新语言既困难也无必要——而是帮助我能够更好地利用编译原理的知识**编写 DSL **来辅助特定工作。考虑到我总是一头扎进技术细节里，必须时时刻刻提醒自己这一点。

其他元符号

接下来的任务是解决、{}和、[] 元符号，其意义分别是：贪婪地匹配 0 次或无数次；匹配 0 次或一次。这里使用 repeat 和 maybe 为这两个元符号命名。

当前的 Stone 语言中 block 和 statement 比较典型地使用了这两个元符号——

block		: "{" [ statement ] {(";" | EOL) [statement]} "}" 
statement	: "if" expr block [ "else" block ]
		| "while" expr block
		| simple

其在作者的 Java 代码表述如下。

Parser block = rule(BlockStmnt.class)
    .sep("{").option(statement0)
    .repeat(rule().sep(";", Token.EOL).option(statement0))
    .sep("}");
Parser statement = statement0.or(
    rule(IfStmnt.class).sep("if").ast(expr).ast(block)
    	.option(rule().sep("else").ast(block)),
    rule(WhileStmnt.class).sep("while").ast(expr).ast(block),simple);

元符号、{}——repeat

首先需要明确，repeat 和 maybe 解析的结果是什么？这是容易想到的——repeat 应当返回一个 ASTList，因为其可能匹配多次，需要保存这无数次匹配之结果，maybe 可以返回一个 ASTLeaf，也可以返回一个 ASTList，通过其子树数量为 0 还是 1 来表示其是否匹配到了，这里使用 ASTList。

expr : factor { OP factor }也是一个、{}符号使用的一个典型例子，但是对其不适合直接使用 repeat 方法：能拿它的解析结果——一个 factor 和一个 ASTList——整什么花活？它生成的 AST 没有任何意义！比如对1 + 2 * 3 + 4 / 5，它将生成类似这样的 AST，它显然是没有任何价值的——

为此，作者专门提供了 expression 方法用来对表达式进行描述。其使用了算符优先分析法。这个在之后再进行实现（大概罢！）。

repeat 的实现仍旧是简单的——匹配过程中维护一个 ASTree 的 List，不断循环进行匹配，保存匹配结果直到无法再匹配下去，然后返回一个以该 List 为子树集合的 ASTList。其关键 Java 代码如下——

public Optional<ASTree> parse(Lexer lexer) {
    ASTList lst = new ASTList(new ArrayList<>());
    while (pattern.match(lexer)) { // 贪婪！
        lst.children().add(pattern.parse(lexer).get());
    }
    return Optional.of(lst);
}

对前面实现过的四则运算语言，其将这样表述——

/*
    factor		:	NUMBER | "(" expr ")"
    term		:	factor { ("*" | "/") factor }
    expr		:	term { ("+" | "-") term }
*/
ParserPattern factor_ = rule();
ParserPattern term_ = rule();
ParserPattern expr_ = rule();

ParserPattern factor = factor_.or(
    rule().number(),
    rule().sep("(").ast(expr_).sep(")")
);
ParserPattern term = term_.ast(factor_).repeat(rule().token("*", "/").ast(factor_));
ParserPattern expr = expr_.ast(term_).repeat(
    rule().or(rule().token("+", "-").ast(term_))
);

下图展示了1 + 2 * 3，1 * 2 + 3“修剪”后所代表 AST，可以看到其优先级确实被表达了，且其结构较为规整，通过后序遍历仍旧可以得到结果——

显然，repeat 的局限性很大——它生成的 AST 结构有时候会比较复杂，难以理解。因此应当被用到有序并列结构的表达，如代码块中各语句，就极其适合使用 repeat。

元符号、[]——maybe

既然 repeat 已经能够实现，maybe 的实现也不是问题——匹配到就匹配到，匹配不到就给个空的 ASTList。

@Override
public Optional<ASTree> parse(Lexer lexer) {
	if (pattern.match(lexer))
    	return pattern.parse(lexer);
    return Optional.of(new ASTList(new ArrayList<>()));
}
@Override
public boolean match(Lexer lexer) {
	return true;
}

现在实现一个 if-then-else 进行测试。

// ifStmnt : "if" expr "then" expr ["else" expr]
ParserPattern ifStmnt = 
    rule().sep("if").ast(expr).sep("then").ast(expr)
    	.maybe(rule().sep("else").ast(expr));

其生成 AST 是可以预料的，因此不进行展示。

决定就到这里，虽然对这个语法分析器生成器的实现很不满意，但是我认为没必要钻得更深，使用现成的如 JavaCC 之类的开源工具即可。对这本书的学习也告一段落，去研究 DSL 去，这对框架编写可能会有帮助。

编译原理

本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 协议，转载请注明出处！

【转载】面向对象随想——多用组合来代替继承上一篇

关于 graphviz 的使用（残卷）下一篇

《两周自制脚本语言》笔记 5——关于语法分析器生成器的实现