jillus - A type-safe parser combinator in Java

先放代码：https://github.com/henix/jillus

什么是 Parsing

把序列化的数据变成你自己的数据结构（参见：三大 DSL）
处理的数据结构通常带递归

如何描述语法，或：带递归的数据结构

EBNF - 请参见编译教科书
PEG - Parsing Expression Grammar（jillus 采用这个）

区别：

Exp := int | "(" Exp ")"

“或”（|）的语义

EBNF 的或在尝试某个分支时，如果后面失败，会回溯，然后尝试别的分支
PEG 的或，一旦分支本身匹配成功，不管后面如何，都不会回溯

PEG 不能包含左递归

更多 PEG 的例子：lpeg 主页

Different approaches to parser tools

parser generator (DSL) 程序员用 DSL 描述语法，生成目标语言的代码
- flex + bison (for EBNF, C)
- Mouse (for PEG, Java)
parser combinator (Embedded DSL) 程序员直接用目标语言书写
- lpeg (for PEG, lua)
- jillus (for PEG, Java)

一个例子：hamcrest-text-patterns：Java 的正则表达式的 EDSL

jillus：类型安全的 parser combinator

先声明你要 parse 出来的数据结构
Parser<T> // 把 String 变成 T

一个例子：日期 (\d+)-(\d+)-(\d+)

使用 lpeg：

require 'lpeg'

local digit = lpeg.R("09")
local digits = digit^1
local mydate = lpeg.C(digits) * "-" * lpeg.C(digits) * "-" * lpeg.C(digits)

local d = {lpeg.match(mydate, "3001-4-1")}

io.write("year = ", d[1], ", month = ", d[2], ", day = ", d[3], '\n')

说明：

lpeg.R 匹配范围中的一个字符
^1 表示至少一个 / 一个或多个
- 表示连接两个 pattern
用 lpeg.C 创建捕获组

优点：

简洁快速

缺点：

通过下标访问捕获 / 捕获不是类型安全的（当然这是 lua 这个动态语言的固有限制）

一个例子（续）：使用 jillus

1. 定义数据结构：

  public static class MyDate {
    public int year;
    public int month;
    public int day;
  }

2. 定义 ValueCreator ：怎样把 String 转换成 Integer

	static final ValueCreator<Integer> intParser = new ValueCreator<Integer>() {
		public Integer create(String capture) {
			return Integer.valueOf(capture);
		}
	};

（P.S. 毕竟 Java 不是函数式语言，只能匿名内部类了）

3. 定义语法：

import static henix.jillus.Pegs.*;

	static final PegPattern digit = charInRange('0', '9');

	static final Capturer<Integer> aint = capture(intParser, atLeast(1, digit)); // [0-9]+

	static final Capturer<MyDate> mydate = asStruct(MyDate.class, sequence(
		bindField(MyDate.class, Integer.class, "year", aint),
		bindNothing("-"),
		bindField(MyDate.class, Integer.class, "month", aint),
		bindNothing("-"),
		bindField(MyDate.class, Integer.class, "day", aint)
	));

类型安全体现在哪里？

Capturer<MyDate> 表示最后可以出来一个 MyDate 的 pattern
bindField 是类型安全的，通过反射将内层捕获到的值绑定到外层对象上
asStruct 是类型安全的，它用于创建一个复合类型（many-of datatype）

4. 执行：

	@Test
	public void main() {
		final PatternExecutor executor = new PatternExecutor(new StringSource("3001-4-1"));
		final MyDate result = executor.execute(mydate);

		Assert.assertEquals(3001, result.year);
		Assert.assertEquals(4, result.month);
		Assert.assertEquals(1, result.day);
	}

完整的例子：

https://github.com/henix/jillus/blob/master/src/test/java/henix/jillus/test/SimpleDateTest.java

parser's "Hello world" 之计算器（从 String 到 AST ，然后对 AST 求值）：

https://github.com/henix/jillus/blob/master/src/test/java/henix/jillus/test/CalcTest.java

计算器的例子展示了：

多选一类型（one-of datatype）的运用：Expr 是一个多选一类型，而 BinaryExpr 则是复合类型。
如何使用非终结符（non terminal）

extra：复合类型和多选一类型

复合类型(many-of type)

一个值包含着多个值

C：struct
Java：class
函数式语言：record

多选一类型（one-of type）

一个值，可能是多种值之一

C：union + 一个指示器指示当前是哪个值（tagged union）
Java：用若干子类继承某个超类，若一个对象声明为此超类的类型，它的实际类型是这些子类中的某一个
函数式语言：代数数据型（Algebraic data type）

如何从多选一类型知道当前是哪一个

C：根据指示器的值
Java：instanceof
函数式语言：pattern matching

与 PEG 表达式的对应关系：

复合类型 - sequence(Attacher<? super T>...)
多选一类型 - orderChoice(Capturer<? extends T>...)

注意到一个的参数类型是 T 的超类，另一个是 T 的子类

总结

从代码上看，jillus 比 lpeg 更多、更复杂，因为 jillus 是类型安全的。（个人 prefer 静态类型）
以后的改进：提供错误处理和恢复（error recovery / error fallback）

henix/jillus-intro.md