正则表达式，PEG 以及 parser combinator

2022-02-28

上次年终总结中提到，cora 接下来计划的其中一个方向，考虑像 babashka 那样子做成日常的脚本来使用。 如果是当作日常脚本使用，其中很重要的一块是文本处理能力。而说到文本处理，对于正则表达式的支持首先就出现在了脑海里。所以这一篇的话题就讨论正则表达式，PEG 以及 parser combinator。

正则当然可以用一些三方库，但是作为一个完善语言的库的过程，所以我想自己撸一些东西。

正经的正则的实现可以参考 russ cox 写过一系列关于正则表达式的文章，做法是编译成 NFA 或者 DFA。 也有一些极简的取巧做法是像《代码之美》的书里面，有一章专门讲这个话题，如果是 toy 级别的实现，当然也可以这么干。但是其实老实说，我并不太喜欢正则，所以找一找正则表达式的替代品。

然后就回想起 PEG(Parsing Expression Grammars) 了。我记得之前读过 Janet 的一篇博客，是实现 PEG 的，当时觉得特别精妙！所以这个周末我又翻出来拜读了一遍。

把里面的例子 port 成 cora 代码之后，大概就是这样一个函数：

(func match-peg
      ['! x] text => (let pos (match-peg x text)
			  (if (> pos 0)
			      0
			      1))
      ['+ x y] text => (let pos (match-peg x text)
			    (if (= pos 0)
				(match-peg y text)
				pos))
      ['* x y] text => (let pos1 (match-peg x text)
			    (if (> pos1 0)
				(let pos2 (match-peg y (string/slice text pos1))
				     (if (> pos2 0)
					 (+ pos1 pos2)
					 0))
				0))
      peg text => (if (string/has-prefix? text peg)
		      (string/length peg)
		      0))

match-peg 接受一个 PEG 的 pattern，以及输入的字符串，返回匹配到的位置。如果没匹配上，则返回 0。 pattern 有几种基本操作：或，且，非。这里分别是用的 '+ '* '! 表示的，可以组合起来。

比如说想要匹配数字，这个 PEG 可以写成用"或"处理 0~9 的每一个：

(set ' ['+ "0" ['+ "1" ['+ "2" ['+ "3"
   ['+ "4" ['+ "5" ['+ "6" ['+ "7" ['+ "8" "9"]]]]]]]]])

然后日期中的年是一个四位数字，就可以用顺序的串起来 4 个 digits：

(set ' ['*  ['*  ['*  ]]])

如果我们想要匹配 "2019-06-10" 这样的日期，完整的 PEG 语法就类似这样子：

(set ' ['+ "0" ['+ "1" ['+ "2" ['+ "3"
   ['+ "4" ['+ "5" ['+ "6" ['+ "7" ['+ "8" "9"]]]]]]]]])
(set ' ['*  ['*  ['*  ]]])
(set ' ['*  ])
(set ' )
(set ' ['*  ['* "-" ['*  ['* "-" ]]]])

然后就可以执行：

(match-peg  "2019-06-10")

demo 的代码在这里。

如果是像 cora 这种 lisp 语言，弄 PEG 的库，可以利用其代码即数据的能力，去做 DSL。

我突然又联想到，其它的语言，做 PEG 会怎么处理。然后去翻了一下 Go 的。发现 Go 的版本是用了代码生成，像 peg 或者 pigeon 都是。可以理解，毕竟 Go 的 DSL 能力是很弱的。但是我还是不太喜欢像 parser generator 这种形式额外引入一套语法，使用起来有学习成本，而且 parser generator 的东西，调试起来特别不方便。

然后又联想到，PEG 其实跟另外一个东西很像 – parser combinator。

两者的区别是：PEG 实现中，第一个参数是语法规则，第二个参数是输入文本。内部会有解释器根据语法规则，去匹配输入。 而 parser combinator 中，没有解释器了，语法规则和解释器融合到了一起，变成了函数。

我尝试了一下 parser combinator 用 Go 的实现做，首先是定义一个接口：

type Parser interface {
	Parse(input string) (bool, string)
}

然后可以定义一些基础的 parser，比如专门解析字符串常量的 parser：

type Literal string

func (s Literal) Parse(input string) (bool, string) {
	if len(input) >= len(s) && input[:len(s)] == string(s) {
		return true, input[len(s):]
	}
	return false, input
}

接下来是核心部分，组合子。比如说 OR 组合子接受多个 Parser，返回一个新的 Parser。效果是其中某一个 Parser 能解析输入，则处理成功。

func OR(ps ...Parser) Parser {
	return orC(ps)
}

type orC []Parser

func (c orC) Parse(input string) (bool, string) {
	for _, p := range c {
		succ, remain := p.Parse(input)
		if succ {
			return succ, remain
		}
	}
	return false, input
}

SEQ 组合子接受多个 parser，用它们依次按顺序去解析文本。第一个成功后，再用第二个解析剩下的文本。如果中间有失败了，就失败了。 关键点是，通过组合子，能够可以把一些基础的 parser 组合起来，变成处理复杂语法的 parser。还是上面的处理 iso date 的例子，可以这么弄：

func TestISODate(t *testing.T) {
	var tmp [10]Byte
	for i := '0'; i < '9'; i++ {
		tmp[i-'0'] = Byte(i)
	}
	digits := OR(tmp[0], tmp[1], tmp[2], tmp[3], tmp[4], tmp[5], tmp[6], tmp[7], tmp[8], tmp[9])
	year := SEQ(digits, digits, digits, digits)
	month := SEQ(digits, digits)
	day := SEQ(digits, digits)
	xx := Byte('-')
	date := SEQ(year, xx, month, xx, day)

	input := "2021-10-23"
	succ, remain := date.Parse(input)
	require.True(t, succ)
	require.Equal(t, remain, "")
}

Byte 是最基础 parser，通过 OR 组合之后变成可以处理 digits 的 parser，而四个 digits 通过 SEQ 组合之后可以处理 year 格式解析，year / month / day 都定义出来之后，用 SEQ 组合子串到一起就处理 date 格式了。

parser combinator 的组合能力，跟 PEG 的组合能力是一样强大的。都是从最基本的 or, sequence, not 等组合起来。

我试着写了一点代码来解析 Go 的 benchmark 时打印的像这样 "Benchmark FuncnameXXX 23132 ns/op 823032 bytes/op 41 allocs/op" 的文本。

type BenchResult struct {
	OP    Number
	Byte  Number
	Alloc Number
}

func (r *BenchResult) Parse(input string) (bool, string) {
	WS := WhiteSpace{}
	Benchmark := Literal("Benchmark")
	Funcname := Funcname{}
	NSOP := Literal("ns/op")
	BytesOP := Literal("bytes/op")
	AllocsOP := Literal("allocs/op")
	pattern := SEQ(Benchmark, WS, Funcname,
		WS, &r.OP, WS, NSOP,
		WS, &r.Byte, WS, BytesOP,
		WS, &r.Alloc, WS, AllocsOP)
	return pattern.Parse(input)
}

它可以把字符串解析出来，并且把结果(需要的几个字段)存到结构体里面去。

感觉可以。demo 代码在这里。其实关于保存 parser 出来的结果，是有一些技巧性的...不展开了。

结论是：不想用正则的情况下，如果语言对 DSL 的支持比较友好，用 PEG 挺好的。 否则，用 parser combinator 可能会更方便。