使用 LPeg 解析语法

LPeg 是一个 Lua 的模式匹配库. 笔者刚刚接触到 LPeg 时, 以为它只是另一种形式的正则表达式; 深入了解才发现, 它的功能远远强于正则表达式, 能够轻易匹配正则表达式难以匹配的复杂模式, 乃至解析语法. 事实上, LPeg 即是 Parsing Expression Grammars for Lua, 它设计出来就是用来解析语法的. 使用 LPeg 能够轻松地解析各种语法, 比如用四百行代码将 Lua 源码解析成抽象语法树. 有了它, 静态分析代码, 自定义 DSL(Domain Specific Language) 将会变得易如反掌.

本文不会详细介绍 LPeg 中的每一个函数, 每一个操作符, 这些内容官方文档中都很清楚; 这里主要介绍 LPeg 的匹配机制以及使用思路. 如果你是第一次接触 PEG 和 LPeg, 可以先阅读本文, 实践时需要了解详细用法再参阅官方文档. 由于 LPeg 是 PEG 的 Lua 实现, 我们先从 PEG 说起.

PEG(Parsing Expression Grammars)

说到模式匹配, 很多同学首先想到的是正则表达式. 对于简单的模式而言, 正则表达式是很方便的; 然而一旦情况变得复杂, 正则表达式就显得力不从心了. 你能想象使用正则表达式匹配条件表达式吗? 此外正则表达式存在效率问题, 一些奇怪的正则表达式可能导致反复回溯, 甚至达到指数级的时间复杂度. 为了匹配复杂的模式, 我们需要更加强大的工具, PEG 就是其中一个.

介绍

PEG 最早是在 2004 年 MIT 的一篇论文 Parsing Expression Grammars: A Recognition-Based Syntactic Foundation 中提出的. 它很像 CFG(Context-Free Grammars), 不同的是 CFG 是对语言的描述, 而 PEG 是对语言的解析, 稍后我们能看到这一区别. Lua 文档的最后一节有一份用 BNF(Backus Naur Form) 描述的完整语法, BNF 就是 CFG 的一种表示法. 下面是用 PEG 对其语法的自描述:

grammar     <-  (nonterminal ’<-’ sp pattern)+
pattern     <-  alternative (’/’ sp alternative)*
alternative <-  ([!&]? sp suffix)+
suffix      <-  primary ([*+?] sp)*
primary     <-  ’(’ sp pattern ’)’ sp / ’.’ sp / literal /
                charclass / nonterminal !’<-’
literal     <-  [’] (![’] .)* [’] sp
charclass   <-  ’[’ (!’]’ (. ’-’ . / .))* ’]’ sp
nonterminal <-  [a-zA-Z]+ sp
sp          <-  [ \t\n]*

如第 1 行所示, PEG 语法由一条以上的规则组成, 每条规则均由 <- 分隔开的非终结符(nonterminal)和模式(pattern)组成. 接下来的规则会依次表示非终结符和模式又是由什么组成的, 直到字符级别. 其中的一些规则与正则表达式类似, 例如 + 表示前面的模式重复 1 次以上, * 表示重复 0 次以上, ? 表示出现 1 次或 0 次 (见第 4 行 suffix); [] 表示字符的集合 (见第 8 行 charclass) 等. 为了消除歧义, 字面量需要放在 ’’ 之间 (见第 7 行 literal). 此外还有 ! 表示不匹配紧随其后的模式 (当且仅当随后的模式匹配失败时匹配成功), & 表示匹配紧随其后的模式但不消耗输入 (见第 3 行 alternative).

如第 2 行所示, 每个模式可以包含多个可选项(alternative), 由斜杠 / 隔开, 这有点像 BNF 中的 |. 例如第 5 行表示非终结符 primary 可以由括号包裹的模式, 或者表示任意字符的通配符 ., 或者字面量, 或者字符类, 或者后面不紧跟 <- 的非终结符组成. 与 CFG 不同的是, 这些可选项是有顺序的, 只有前面的选项匹配失败才会去匹配后面的选项. 因为 PEG 是用于描述一种自顶向下的解析语法的方式, 有序的可选项能够让解析没有歧义.

有限回溯

PEG 的一大优势是, 它能够将回溯限制在一条匹配规则内. 一旦一个选择确定, 就不会因为后续的匹配失败而改变. 例如, 考虑下列语法:

S   <-  A B
A   <-  E1 / E2 / E3
B   <-  ...

当我们尝试让字符串匹配 S 的时候, 会先匹配 A 再匹配 B. 当匹配 A 时, 由于 A 有三个可选项, 因此会先尝试匹配模式 E1, 如果匹配失败, 就回溯, 然后匹配 E2, 以此类推. 一旦匹配上了任意一个选项, 这条规则就不会再回溯了. 例如选择了 E2 作为 A 的匹配项后, 如果接下来 B 匹配失败了, 那么整个模式都匹配失败, B 的失败不会让 A 重新选择. 这一特性保证了 PEG 的效率, 不会出现正则表达式一样的无限回溯.

贪婪匹配与非贪婪匹配

了解正则表达式的同学应该都比较熟悉正则表达式的贪婪匹配和非贪婪匹配. 例如, 匹配字符串 abcdXefghXijk, 使用正则表达式 /.*X/ 将匹配到第二个 X, 这是贪婪匹配, .* 会尽可能地匹配更多的字符; 而使用 /.*?X/ 将匹配到第一个 X, 这是非贪婪匹配, .*? 会尽可能匹配少的字符. 这种方式虽然方便, 但是不够优雅: 例如 /.*?X/, .* 的含义是匹配 0 个以上的任意字符, X 显然包含在通配符 . 中; 只因为后面跟了一个 X, /.*?X/ 却要在匹配到第一个 X 的时候停下. /.*X/ 就更奇怪了: 它居然需要在遇到最后一个 X 的时候停下! 正则表达式的这种方式虽然符合人类的直觉, 但是在逻辑上是很奇怪的.

PEG 的做法就简单很多. PEG 总是会执行贪婪盲匹配, 也就是尽可能地匹配更多的字符, 并且不考虑前后的其他模式. 例如, 如下的 PEG

S   <-  .* ’X’

看上去类似于正则表达式 /.*X/, 但是实际上它无法匹配任何字符串. 因为 .* 会一直匹配所有字符, 直到字符串结尾; 而一旦到达字符串结尾, 就没有任何字符可匹配, 于是匹配失败.

要想实现正则表达式 /.*?X/ 的效果, 注意 . 会匹配任意字符, 为了让它在遇到第一个 X 的时候停下, 我们只需把匹配任意字符改成匹配除 X 外的字符即可. 使用如下的 PEG 即可:

S   <-  (!’X’ .)* ’X’

由于 !’X’ 的存在, 一旦遇到 X 就会匹配失败, 这样 !’X’ . 就会匹配除 X 外的任意字符. 这样的 PEG 虽然写起来比正则表达式长, 但是逻辑更明确.

我们还可以使用递归的方式实现同样的效果:

S   <-  ’X’ / . S

匹配时依次扫描字符串. 对于每个字符, 先尝试匹配 ’X’, 如果匹配失败, 则会匹配 . S. 这个模式会匹配任意一个字符, 然后再匹配模式 S 本身 – – 也就是为下一个字符执行同样的操作. 直到遇到字符 X, 匹配结束.

/.*X/ 就要更有趣些. 它要求匹配到字符串的最后一个 X 时停下. 不扫描完整个字符串怎么知道最后一个 X 在哪呢? 我们需要如下的 PEG:

S   <-  . S / ’X’

对于每个字符, 会先尝试匹配 . S. 这其中的 . 会匹配任意一个字符, 然后再匹配模式 S 本身, 也就是为下一个字符执行同样的操作. 这会一直持续到字符串的最后一个字符:

abcdXefghXijk
            ^
            match `k` with `. S / ’X’`

当 k 与 . S 匹配时, 通配符 . 会匹配字符 k, 然后为下一个字符 – – 字符串结尾 与 S 相匹配, 自然会匹配失败. 于是可选项 . S 匹配失败, PEG 会回溯, 尝试匹配 ’X’, 自然也是失败. 也就是说 k 匹配 . S / ’X’ 失败了. 这会导致整个字符串匹配失败吗? 当然不会! 注意整个操作是递归的, 最后一个字符 k 匹配的模式 . S / ’X’, 也是倒数第二个字符 j 匹配的模式 . S / ’X’ 中的 S. 因此 PEG 会再次回溯, 以此类推, 直到最后一个字符 X.

其他机制

PEG 不需要类似正则表达式中的 ^ 或 $ 表示字符串开头或结尾. 首先 PEG 一定会从字符串开头开始匹配; 对于字符串结尾, 使用模式 !. 即可, 它不匹配任何一个字符 – – 只有在字符串结尾才满足这一条件.

如上面所提到的, & 表示匹配紧随其后的模式但不消耗输入. 例如 ’a’ ’a’ 不能匹配字符串 "a", 因为它要求两个连续的 a, 但是 &’a’ ’a’ 却能匹配它, 因为当 &’a’ 匹配上字符 a 之后, 不会消耗输入, 指针不会往后移, 因此后一个模式 ’a’ 仍然能匹配它.

总之, 虽然 PEG 相比正则表达式不那么符合人类直觉, 但是其规则更简单, 更接近模式匹配的本质.

LPeg

LPeg 是 PEG 的 Lua 实现. LPeg 并没有实现 PEG 的语法, 相反, 它使用 Lua 的特性, 实现一系列的函数, 对象, 通过重载运算符来构造模式. 我们先来看 LPeg 的几个基本函数和操作:

Operator	Description
lpeg.P(string)	匹配字面量 string. 相当于 PEG 中的 ’’
lpeg.P(n)	匹配 n 个任意字符
lpeg.S(string)	匹配 string 中的任意字符. 相当于 PEG 中的 []
lpeg.R("xy")	匹配 x 至 y 范围内的所有字符. 相当于 PEG 中的 [x-y]
patt ^ n	patt 重复至少 n 次
patt ^ -n	patt 重复至多 n 次
patt1 * patt2	patt1 后紧跟 patt2. 相当于 PEG 中的 patt1 patt2
patt1 + patt2	顺序选择. 匹配 patt1 或 patt2. 相当于 PEG 中的 patt1 / patt2
patt1 - patt2	只有 patt2 不匹配, 才匹配 patt1. 相当于 PEG 中的 !patt2 patt1. 可以理解成差集
-patt	相当于 "" - patt. 不匹配 patt. 相当于 PEG 中的 !patt
#patt	匹配 patt 但是不消耗输入. 相当于 PEG 中的 &patt

可以看到, LPeg 与 PEG 大同小异, 只是换了一个形式而已. lpeg.P, lpeg.S, lpeg.R 等方法都会返回 pattern 对象, pattern 对象重载了运算符, 可以与其他 pattern 执行各种运算, 这些运算的结果仍是 pattern. 例如前面提到的 S <- (!’X’ .)* ’X’ 使用 LPeg 就可以写成这样:

local lpeg = require "lpeg"
local S = (lpeg.P(1) - "X") ^ 0 * "X"

调用 pattern 的 match 方法可匹配字符串, 会返回匹配结束的位置:

S:match("abcdXefghXijk") --> 6

如何实现 S <- ’X’ / . S 这样的递归模式呢? lpeg.P 还支持传入一个 table. 这个 table 包含一系列键值 k = v, 键代表一个非终结符, 值定义模式. 使用 lpeg.V 引用其他非终结符. 此外还要求这个 table 的第一个值 table[1] 为初始符号, 因为 Lua 的 table 是无序的. 例如 S <- ’X’ / . S 用 LPeg 就可以写成这样:

local lpeg = require "lpeg"
local P, V = lpeg.P, lpeg.V

local S = P{"S",
    S = P"X" + P(1) * V"S"
}

下面是一个稍复杂的例子:

local lpeg = require "lpeg"
local P, V = lpeg.P, lpeg.V

local S = P{"S",
    S = "a" * V"B" + "b" * V"A" + "";
    A = "a" * V"S" + "b" * V"A" * V"A";
    B = "b" * V"S" + "a" * V"B" * V"B";
}

这等价于下面的 PEG:

S   <-  ’a’ B / ’b’ A / ’’
A   <-  ’a’ S / ’b’ A A
B   <-  ’b’ S / ’a’ B B

捕获

只能匹配字符串返回位置未免太乏味了. LPeg 的功能远不止这些, LPeg 还有强大的捕获功能. 下面列出了一些 LPeg 的捕获方法:

Operation	What it Produces
lpeg.C(patt)	匹配模式 patt 并捕获它
lpeg.Ct(patt)	将 patt 产生的所有捕获放在一个 table 中
lpeg.Cs(patt)	将 patt 中的所有匹配都视为捕获, 并将他们拼接成一个字符串
lpeg.Cc(values)	匹配空串并将给定值 values 作为捕获
lpeg.Cp()	匹配空串并将当前位置作为捕获
lpeg.Cf(patt, f)	将 patt 产生的所有捕获依次传入函数 f, 类似于 reduce 操作. 如 patt 产生捕获 \(C_1, C_2, ..., C_n\) , 则会执行 \(f(...f(f(C_1, C_2), C_3)..., C_n)\) , 最后以函数的最终返回值作为捕获
patt / string	将 patt 的捕获结果替换为字符串 string
patt / number	取 patt 的第 n 个捕获结果. 如果为 0 则无捕获结果
patt / table	若 patt 的捕获结果为 c, 则将 table[c] 作为捕获结果
patt / function	将 patt 的捕获结果传入 function, 取其返回值作为捕获结果

需要说明的是只有在对应模式匹配成功时才会产生捕获结果. 例如模式 lpeg.C(lpeg.P"a" ^ -1) 在匹配不以 a 开头的字符串时会返回空串.

例如, 用指定字符分割字符串, 就可以这样写:

function split(s, sep)
    sep = lpeg.P(sep)
    local elem = lpeg.C((1 - sep) ^ 0)
    local p = elem * (sep * elem) ^ 0
    return p:match(s)
end

其中 1 - sep 匹配不为分隔符的任意字符, 然后再 ^ 0 让其重复 0 次以上; 然后 elem * (sep * elem) ^ 0 让这种分割模式重复若干次.

如果需要将结果放在一个 table 里, 只需这样写:

function split(s, sep)
    sep = lpeg.P(sep)
    local elem = lpeg.C((1 - sep) ^ 0)
    local p = lpeg.Ct(elem * (sep * elem) ^ 0)   -- make a table capture
    return p:match(s)
end

LPeg 的官网有很多类似的例子, 可自行参阅.

应用

LPeg 是一个很强大的工具, 可以说掌握了它就能够随心所欲地操纵字符串. 它可以做很多有趣的事.

静态分析代码

我们可以使用 LPeg 分析语法. 比如说分析 SQL 语句, 拦截不允许执行的危险操作, 如 update 或者 delete 不加 where 之类; 比如某些用户接口, 只允许执行 select 语句等. 我们就可以使用 LPeg 解析 SQL 语句, 能够准确地知道一条 SQL 语句会做什么, 甚至检查出语法错误. 我们还可以分析 create table 语句, 得到期望的表结构, 与数据库中的表结构相比较, 检查是否一致, 乃至自动迁移数据.

这个 repo 使用 LPeg 将 Lua 源码解析成抽象语法树. 整个解析代码只有 400 行左右. 我们可以利用它为代码作静态分析, 比如分析出某个函数的调用, 对某些表达式静态求值等.

自定义 DSL

语法不够用了怎么办? 自己创造! 有了 LPeg 就可以自己定义语法, 定义自己的语言. 例如在游戏编程中, 策划常常需要配置触发器. 触发器的条件有时就比较复杂, 比如 “血量小于 10% 或怒气大于 90 时有 50% 的概率触发”, 这样的条件就很难用特定格式描述, 直接让策划写代码又不够安全. 这种场景我们就可以自定义 DSL, 配置表就可以配一个字符串, 例如这个条件就可以用字符串表示为

(hp < 10% || wrath > 90) && random() > 0.5

然后预先使用 LPeg 将字符串编译成一个 Lua 函数, 运行时调用它即可.

---

参考资料:

• A Text Pattern-Matching Tool based on Parsing Expression Grammars
• LPeg - Parsing Expression Grammars For Lua