Janet 的 PEG 模块是如何工作的
Janet 的 PEG 模块是如何工作的
2019-06-10
在开发 Janet 时，我受到了 REBOL 的 Parse 模块和 LPeg 的启发，希望包含一个通用的库，用于基于 Parsing Expression Grammars，或 PEGs 来解析文本和任何字节序列。 我也愿意从核心库中排除其他形式的解析工具，例如正则表达式，因为 PEGs 比正则表达式更通用、更容易阅读，并且可以在匹配文本时捕获错误位置。 Janet 中 PEGs 的开发特别顺利，这得益于简单的 PEG 形式、Janet 的基本数据结构和一个非常简单的子程序线程解释器。 虽然 Janet 的 PEG 模块的大部分可以在任何语言中实现，但 Janet 的 C API 和丰富的核心数据结构使得在 Janet 中实现 PEGs 变得容易。
这篇文章是关于 Janet 的 PEG 引擎是如何实现的；它不是关于如何使用 PEGs 的指南。 虽然代码是用 Janet 编写的，但它可以直接翻译成大多数编程语言，因为我们没有特别使用数组和哈希表之外的任何数据结构。 有关使用 Janet 的 PEG 模块的信息，请参阅 Janet PEG 文档。
PEG 快速概览
Parsing Expression Grammar 形式起源于 Bryan Ford 于 2004 年发表的论文，他在论文中介绍了模型和一种在线性时间内识别任何 PEG 语法的算法。 我们的 PEG 引擎不会在线性时间内解析所有模式，但将使用类似的语义来定义我们的语法。 PEGs 和更传统的解析器生成器（例如 YACC 和 Bison 使用的那些）之间的一个区别是有序选择运算符。 为了这篇文章的目的，+ 是有序选择运算符。 例如，使用 PEG 语法的伪语法，其中 MAIN 规则是语法的入口点，我们可以编写一个匹配以 a、b 或 c 开头的任何文本的语法。
MAIN: "a" + "b" + "c"
这个语法将匹配 "apple pie"、"banana split" 和 "coconut cluster"，但不匹配 "orange soda"、"watermelon taffy" 或 "lemon snap"。
使用有序选择运算符也很容易编写冗余语法。 以下语法将仅匹配第一个 "a"，永远不会匹配 "ab" 或 "abc"。 任何以 "ab" 或 "abc" 开头的内容也以 "a" 开头，因此可以从语法中删除它们而不会改变其行为。
MAIN: "a" + "ab" + "abc"
+ 运算符的有序属性意味着所有 PEG 语法都是确定性的 - 如果它们匹配一个字符串，它们将只以一种方式匹配它。 这也意味着 PEG 和解析器之间存在直接对应关系。 这在编写 PEGs 时非常方便，因为您的规范和解析器通常可以是同一个。 传统的解析器生成器是非确定性的，需要额外的规则来解决歧义。
为了完成我们的 PEG 模型，我们只需要几个运算符。 以下是 PEG 形式尽可能通用所需的所有运算符和特性。
"..." - 字符串字面量
+ - 选择运算符
* - 序列运算符（在我们的伪语法中是隐式的）
! - 布尔反转
上述特性，以及由顶级语法引入的递归，可以表达所有 PEGs。 这是原始论文中提出的内容的精简版本，但其他运算符可以替换为上述运算符的组合。 匹配上下文无关语法所需的另一个非常重要的特性是递归，否则我们的模型将仅限于匹配正则表达式。
使用这种形式，我们可以编写一个简单的语法来匹配 ISO 8601 格式的日期。 这样的日期看起来像
2019-06-10
下面提供了一个匹配日期的简单语法（但不验证日期 - 9999-99-99 将匹配）。 这也要求年份用 4 位数字指定。
DIGIT: "0" + "1" + "2" + "3" + "4" + "5" + "6" + "7" + "8" + "9"
YEAR: DIGIT DIGIT DIGIT DIGIT
MONTH: DIGIT DIGIT
DAY: DIGIT DIGIT
MAIN: YEAR "-" MONTH "-" DAY
这看起来非常类似于上下文无关语法，并且在简单情况下，语法是相同的。
代码中的一个简单的 PEG 引擎
使用上面我们的 PEG 定义，我们可以编写一个简单的 match-peg 函数，它接受一个规则和一个要匹配的字符串，并测试字符串是否与该规则匹配。 如果存在匹配，将返回匹配的字节数，以帮助我们找到开始下一个匹配的位置。 否则，我们将返回 nil，或一些指示没有匹配的 token。 此代码将用 Janet 编写，但可以很容易地用任何语言编写。 我们在这里使用 Janet 的 match 宏，它对参数进行模式匹配。
(defn match-peg
[peg text]
(match peg
@[:! x] (unless (match-peg x text) 0)
@[:+ x y] (or (match-peg x text) (match-peg y text))
@[:* x y] (if-let [lenx (match-peg x text)]
(if-let [leny (match-peg y (string/slice text lenx))]
(+ lenx leny)))
# default is peg is a string literal
(and (string/has-prefix? peg text) (length peg))))
这是一个非常简单但有效的 peg 实现。 它不支持捕获、各种其他运算符，但在大约 10 行代码中捕获了 PEGs 的基础知识，甚至可以用于递归语法。
(def digits [:+ "0" [:+ "1" [:+ "2" [:+ "3"
[:+ "4" [:+ "5" [:+ "6" [:+ "7" [:+ "8" "9"]]]]]]]]])
(def year [:* digits [:* digits [:* digits digits]]])
(def month [:* digits digits])
(def day month)
(def iso-date [:* year [:* "-" :* month [:* "-" day]]])
(match-peg iso-date "2019-06-10") # -> 10
(match-peg iso-date "201-06-10") # -> nil
此实现非常类似于树遍历解释器，并且是实现 PEG 的最简单方法。 Janet 的 peg 实现做了一些非常相似的事情，尽管语法树首先被编译成字节码形式并进行验证以获得更好的速度。
使运算符可变参数
虽然不是绝对必要，但我们希望运算符看起来和行为更像可变参数的 lisp 运算符。 这将使长的序列或选择链更容易编写。
(defn match-peg
[peg text]
(match peg
@[:! x] (unless (match-peg x text) 0)
@[:+] (some (fn [x] (match-peg x text)) (tuple/slice peg 1))
@[:*] (do
(var len 0)
(var subtext text)
(var ok true)
(loop [x :in (tuple/slice peg 1)
:let [lenx (match-peg x subtext)
_ (set ok lenx)]
:while ok]
(set subtext (string/slice subtext lenx))
(+= len lenx))
(if ok len))
# default is peg is a string literal
(and (string/has-prefix? peg text) (length peg))))
我们的 ISO-date 语法可以修改为看起来更自然一点。
(def digits [:+ "0" "1" "2" "3" "4" "5" "6" "7" "8" "9"])
(def year [:* digits digits digits digits])
(def month [:* digits digits])
(def day month)
(def iso-date [:* year "-" month "-" day])
(match-peg iso-date "2019-06-10") # -> 10
(match-peg iso-date "201-06-10") # -> nil
添加递归
早些时候我说过递归对于使 PEGs 有用非常重要，虽然我们可以以临时的方式进行递归，但我们可以使用 Janet tables 使我们的递归语法看起来更像我们的原始语法。 我们可以创建一个将关键字映射到 PEG 表达式的表，如果 peg 是一个关键字，我们会在语法表中查找它的定义。 我们可以向 match-peg 添加一个额外的参数，它将是我们的语法表。
(defn match-peg
[peg text grammar]
(match peg
@[:! x] (unless (match-peg x text grammar) 0)
@[:+] (some (fn [x] (match-peg x text grammar)) (tuple/slice peg 1))
@[:*] (do
(var len 0)
(var subtext text)
(var ok true)
(loop [x :in (tuple/slice peg 1)
:let [lenx (match-peg x subtext grammar)
_ (set ok lenx)]
:while ok]
(set subtext (string/slice subtext lenx))
(+= len lenx))
(if ok len))
(x (keyword? x)) (match-peg (grammar x) text grammar)
# default is peg is a string literal
(and (string/has-prefix? peg text) (length peg))))
使用我们的语法表，我们可以在单个结构中定义我们的语法。
(def grammar
{:digit [:+ "0" "1" "2" "3" "4" "5" "6" "7" "8" "9"]
:year [:* :digit :digit :digit :digit]
:month [:* :digit :digit]
:day [:* :digit :digit]
:main [:* :year "-" :month "-" :day]})
(match-peg (grammar :main) "2019-06-10" grammar) # -> 10
添加规则
到目前为止，我们的 match-peg 函数并不是很有表现力。 我们的字符类、可选匹配和正则表达式中的其他花哨的特性在哪里？ 虽然我们可以简单地为每个字符类（:d 代表数字，:w 代表字母数字）向我们的语法添加术语，但我们还有其他想要的功能，例如 Kleene 星号、字符集等。 幸运的是，向树遍历解释器添加功能非常容易。 我们可以根据需要添加任意数量的运算符。 例如，我们可以添加 :set 运算符，如果一个字符出现在一个集合中，它将匹配 1 个字符。
(defn match-peg
[peg text grammar]
(match peg
@[:set chars] (if (string/check-set chars text) 1)
@[:! x] (unless (match-peg x text grammar) 0)
@[:+] (some (fn [x] (match-peg x text grammar)) (tuple/slice peg 1))
@[:*] (do
(var len 0)
(var subtext text)
(var ok true)
(loop [x :in (tuple/slice peg 1)
:let [lenx (match-peg x subtext grammar)
_ (set ok lenx)]
:while ok]
(set subtext (string/slice subtext lenx))
(+= len lenx))
(if ok len))
(x (keyword? x)) (match-peg (grammar x) text grammar)
# default is peg is a string literal
(and (string/has-prefix? peg text) (length peg))))
我们的日期语法也会变得更清晰。
(def grammar
{:digit [:set "0123456789"]
:year [:* :digit :digit :digit :digit]
:month [:* :digit :digit]
:day [:* :digit :digit]
:main [:* :year "-" :month "-" :day]})
(match-peg (grammar :main) "2019-06-10" grammar) # -> 10
大多数 PEG 库都有更多的规则，以便更容易编写有用的语法，但所有规则都可以以几乎相同的方式编写，作为我们顶级匹配表达式中的用例。 我们的 PEG 引擎也缺少捕获，速度相当慢，没有进行尾调用优化，并且缺少 Janet 或 REBOL 等其他 PEG 引擎中存在的许多功能。 但由于它的所有问题，match-peg 是通用模式匹配功能的一个很好的起点。
版权所有 © Calvin Rose 2019