翻译 lpeg 入门教程

2015-06-25 发布于文章 5055 字 11 分钟

Python

spin6lock

原文地址：http://lua-users.org/wiki/LpegTutorial

简单匹配

LPeg 是一个用于文本匹配的有力表达方式，比 Lua 原生的字符串匹配和标准正则表达式更优异。但是，就像其他任何语言一样，你需要知道简单的词汇和如何组合他们。

最佳的学习方式，是通过交互式对话，熟悉基本的模式。首先，我们定义一些缩写：

$ lua -llpeg
Lua 5.1.4  Copyright (C) 1994-2008 Lua.org, PUC-Rio
> match = lpeg.match -- match a pattern against a string
> P = lpeg.P -- match a string literally
> S = lpeg.S  -- match anything in a set
> R = lpeg.R  -- match anything in a range

如果你不想自己创建缩写，你可以这样写：

> setmetatable(_ENV or _G, { __index = lpeg or require"lpeg" })

我不建议在工作代码中这样写，但是在探索 LPeg 的时候，则不妨试试，十分方便。

匹配是从字符串的 ** 起始点 ** 开始，如果匹配成功，则返回成功匹配子串的后一个位置，或者返回 nil。（这里我应用了一个简写：f'x' 在 Lua 里等价于 f('x') ; 单引号和双引号等价 )

> = match(P'a','aaa')
2
> = match(P'a','123')
nil

看起来就像 string.find 一样，除了只返回一个索引。

你可以选择按 ** 范围 ** 匹配或者匹配一个 ** 集合内 ** 的字符 :

> = match(R'09','123')
2
> =  match(S'123','123')
2

要匹配超过 1 个子串，可以用 ^ 操作符。在这种情况下，匹配与 Lua 的 ‘^a+’ 等价 - 匹配一个或多个 ‘a’:

> = match(P'a'^1,'aaa')
4

要按顺序合并模式（pattern），可以通过 * 操作符。这等价于 ‘^ab*’ - ‘a’ 后跟着 0 个或多个 ‘b’:

> = match(P'a'*P'b'^0,'abbc')
4

到目前为止，lpeg 只是为我们提供了一个更为灵活的方式去表达正则表达式，但是这些模式是可以 ** 组合 ** - 他们可以由简单的原语组成，避免艰深的字符串操作。因此，lpeg 匹配可以比等价的正则表达式表现得更为易读。注意，你可以在构造 pattern 的时候保留显式的 P 调用。尤其是其中一个参数已经是一个 pattern 的时候：

> maybe_a = P'a'^-1  -- one or zero matches of 'a'
> match_ab = maybe_a * 'b'
> = match(match_ab, 'ab')
3
> =  match(match_ab, 'b')
2
> =  match(match_ab, 'aaab')
nil

+ 操作符表示 ** 任意 ** 一个 pattern:

> either_ab = (P'a' + P'b')^1 -- sequence of either 'a' or 'b'
> = either_ab:match 'aaa'
4
> =  either_ab:match 'bbaa'
5

当然 , S'ab'^1 会更简短 , 但这里的参数可以是任意的模式。

基本捕获

获得 match 后的位置非常有用 , 你可以随后用 string.sub 来取出匹配串。不过，我们也有显式的方法直接获取子串 ** 捕获 **:

> C = lpeg.C  -- captures a match
> Ct = lpeg.Ct -- a table with all captures from the pattern

第一个就好似 ‘(…)’ 在 Lua pattern 里一样，( 或者正则表达式里的 ‘(…)’ )

> digit = R'09' -- anything from '0' to '9'
> digits = digit^1 -- a sequence of at least one digit
> cdigits= C(digits)  -- capture digits
> = cdigits:match '123'
123

所以要获得字符串，我们需要用 C 包裹模式。

这个模式没有覆盖到广义上的整型。因为整型可能包括 ‘+’ 或者 ‘-’ 出现在前面 :

> int = S'+-'^-1 * digits
> = match(C(int),'+23')
+23

不像 Lua 模式或者正则表达式，你不需要担心元字符的转义 - 字符串中的每一个字符都只代表自身 : ‘(’,’+’,’*’, 之类都只匹配他们在 ASCII 码表达里的同类。

有一类特殊的捕获，需要用到 / 操作符 - 他会将所有匹配的子串丢给一个函数或者 table。这里我会向结果加 1，用来演示结果已被 tonumber 转换成 number：

> =  match(int/tonumber,'+123') + 1
124

注意，一个匹配也可以返回多个捕获 , 就像 string.match 一样。等价于 ‘^(a+)(b+)’：

> = match(C(P'a'^1) * C(P'b'^1), 'aabbbb')
aa	bbbb

构建更为复杂的模式

考虑到更为常见的浮点数 :

> function maybe(p) return p^-1 end
> digits = R'09'^1
> mpm = maybe(S'+-')
> dot = '.'
> exp = S'eE'
> float = mpm * digits * maybe(dot*digits) * maybe(exp*mpm*digits)
> = match(C(float),'2.3')
2.3
> = match(C(float),'-2')
-2
> = match(C(float),'2e-02')
2e-02

这个 Lpeg 模式比正则表达式 ‘[-+]?[0-9]+.?[0-9]+([eE][+-]?[0-9]+)?’** 简单 ** 得多。越短越好嘛！其中一个原因，是我们可以将模式表达为 ** 表达式 **: 抽取出常见的模式 , 编写相应的函数来提高可读性，让模式使用起来更方便。另外，这样写并没有任何代价；lpeg 依然可以高效的分析文本！

这些基本构件可以组成更为复杂的结构。例如分析一个列表的浮点数。一个列表是指一个 number 接着 0 个或多个逗号和 number：

> listf = C(float) * (',' * C(float))^0
> = listf:match '2,3,4'
2	3	4

这样很酷，其实还可以更酷一点，直接将其转换为真正的列表。这就是 lpeg.Ct 长处所在；它可以将所有的捕获归集到一个 table 里去。

= match(Ct(listf),'1,2,3')
table: 0x84fe628

默认的 Lua 不能直接打印 table，但你可以使用 [? Microlight] 来完成这个工作 :

> tostring = require 'ml'.tstring
> = match(Ct(listf),'1,2,3')
{"1","2","3"}

这些值依然是字符串。最佳实践是定义一个 listf，让它转换成 number:

> floatc = float/tonumber
> listf = floatc * (',' * floatc)^0

这种捕获列表的方法非常普遍，你可以将 ** 任意 ** 表达式放到 floatc 的位置上去。当然，这个列表匹配还是有局限性，一般我们都希望能够直接忽略空格。

> sp = P' '^0  -- zero or more spaces (like '%s*')
> function space(pat) return sp * pat * sp end -- surrond a pattern with optional space
> floatc = space(float/tonumber) 
> listc = floatc * (',' * floatc)^0
> =  match(Ct(listc),' 1,2, 3')
{1,2,3}

这里有个品味的问题，我个人喜欢将空格的匹配和 ** 匹配项 ** 写在一起 , 而不是和 ** 分隔符 ** ‘,’ 写在一起。

通过 lpeg, 我们就能成为基于模式编程的程序员，并重用模式 :

function list(pat)
    pat = space(pat)
    return pat * (',' * pat)^0
end

所以，一个列表的识别码可以这样写 ( 按平常的写法 ):

> idenchar = R('AZ','az')+P'_'
> iden = idenchar * (idenchar+R'09')^0
> =  list(C(iden)):match 'hello, dolly, _x, s23'
"hello"	"dolly"	"_x"	"s23"

使用显式的 range 好像很老土，并且充满错误。一个更可移植的方案，是使用 lpeg 里的 ** 字符类 **, 字符类是独立于 locale 设置的 :

> l = {}
> lpeg.locale(l)
> for k in pairs(l) do print(k) end
"punct"
"alpha"
"alnum"
"digit"
"graph"
"xdigit"
"upper"
"space"
"print"
"cntrl"
"lower"
> iden =  (l.alpha+P'_') * (l.alnum+P'_')^0

给出 列表 的定义 , 就可以定义一个常用 CSV 格式的子类 , 其中每条纪录都是一个列表，列表之间用换行符分隔 :

> rlistf =  list(float/tonumber)
> csv = Ct( (Ct(listf)+'\n')^1 )
> =  csv:match '1,2.3,3\n10,20, 30\n'
{{1,2.3,3},{10,20,30}}

学习 lpeg 的其中一个理由，是 lpeg 的表现十分令人满意。这种模式匹配 lot 比使用 Lua 的原始字符串匹配要快得多。

字符串替换

接下来，我会演示给大家看，所有 string.gsub 可以做的 lpeg 都可以做，并且更具有一般性，更加灵活。

目前有一个操作符 - 是尚未展示过的 , 它可以表示 ’ 任一 / 或 ‘。考虑双引号字符串的匹配。在最简单的情况下，一般是一个双引号接着其他不是双引号的字符，最后接上一个封闭的双引号。 P(1) 匹配 ** 任一 ** 单个字符 , 就好比字符串模式里的 ‘.’ 。一个字符串可以是空的，于是我们应该匹配 0 个或多个非引号字符：

> Q = P'"'
> str = Q * (P(1) - Q)^0 * Q
> = C(str):match '"hello"'
"\"hello\""

或者，你需要的是捕获字符串里的内容，不包括引号。在这种情况下，只要使用 1 来代替 P(1) 就好，而且这是一个比较常见的表达 ’ 所有不是 P 的 x’ 模式：

> str2 = Q * C((1 - Q)^0) * Q
> = str2:match '"hello"'
"hello"

这种模式可以简单的普及到其他情形里去；结束符（结束模式）不一定是最终的模式：

function extract_quote(openp,endp)
    openp = P(openp)
    endp = endp and P(endp) or openp
    local upto_endp = (1 - endp)^1 
    return openp * C(upto_endp) * endp
end

> return  extract_quote('(',')'):match '(and more)'
"and more"
> = extract_quote('[[',']]'):match '[[long string]]'
"long string"

现在，我们来尝试下把 Markdown 代码块 ( 反斜杠包裹的文本 ) 转换为 Lua wiki ( 双花括号包裹的文本 )。最显浅的办法是抽取出字符串并连接成最终结果，但是这看起来很蠢，而且极大的限制了我们的选项（下文将解析这点）。

function subst(openp,repl,endp)
    openp = P(openp)
    endp = endp and P(endp) or openp
    local upto_endp = (1 - endp)^1 
    return openp * C(upto_endp)/repl * endp
end

> =  subst('`','{{%1}}'):match '`code`'
"{{code}}"
> =  subst('_',"''%1''"):match '_italics_'
"''italics''"

我们之前曾经用过 / 操作符，使用 tonumber 函数来转换 number。它也有跟 string.gsub 极为相似的格式，比如 %n 表示第 n 个匹配。

这个操作可以被表达为：

> = string.gsub('_italics_','^_([^_]+)_',"''%1''")
"''italics''"

优势是我们不在需要写自定义的字符串模式，并费神去转移元字符如 ‘(’ 和 ‘)’。

lpeg.Cs 是一个 ** 替换捕获 **，并提供了一个更一般化的全局字符串匹配模块。在 lpeg 手册里， string.gsub 有这样一个等价的替换：

function gsub (s, patt, repl)
    patt = P(patt)
    local p = Cs ((patt / repl + 1)^0)
    return p:match(s)
end

> =  gsub('hello dog, dog!','dog','cat')
"hello cat, cat!"

要理解其中的区别，可以看看只使用单纯的匹配 C 是怎么使用的 :

> p = C((P'dog'/'cat' + 1)^0)
> = p:match 'hello dog, dog!'
"hello dog, dog!"	"cat"	"cat"

这里的 C 捕获了整个匹配，每一个 ‘/’ 增加了一个新的捕获，捕获的值用替换字符串代替。

而使用 Cs, ** 所有匹配 ** 都被捕获，最后组成一个字符串。其中一些捕获会被 ‘/’ 所修改，所以我们能够获得替换过的字符串。

在 Markdown 里，区块行以 ‘> ’ 开始。

lf = P'\n'
rest_of_line_nl = C((1 - lf)^0*lf)         -- capture chars upto \n
quoted_line = '> '*rest_of_line_nl       -- block quote lines start with '> '
-- collect the quoted lines and put inside [[[..]]]
quote = Cs (quoted_line^1)/"[[[\n%1]]]\n"

> = quote:match '> hello\n> dolly\n'
"[[[
> hello
> dolly
]]]
"

这不是那么正确 - Cs 捕获所有东西 , 包括 ‘> ‘。但我们可以强迫部分捕获返回空字符串： }}}

function empty(p)
    return C(p)/''
end

quoted_line = empty ('> ') * rest_of_line_nl
...

现在一切都可以正常工作了 !

这是最终用来转换 Markdown 文档到 Lua 维基格式的代码 :

local lpeg = require 'lpeg'

local P,S,C,Cs,Cg = lpeg.P,lpeg.S,lpeg.C,lpeg.Cs,lpeg.Cg

local test = [[
## A title

here _we go_ and `a:bonzo()`:

    one line
    two line
    three line
       
and `more_or_less_something`

[A reference](http://bonzo.dog)

> quoted
> lines
 
]]

function subst(openp,repl,endp)
    openp = P(openp)  -- make sure it's a pattern
    endp = endp and P(endp) or openp
    -- pattern is 'bracket followed by any number of non-bracket followed by bracket'
    local contents = C((1 - endp)^1)
    local patt = openp * contents * endp    
    if repl then patt = patt/repl end
    return patt
end

function empty(p)
    return C(p)/''
end

lf = P'\n'
rest_of_line = C((1 - lf)^1)
rest_of_line_nl = C((1 - lf)^0*lf)

-- indented code block
indent = P'\t' + P'    '
indented = empty(indent)*rest_of_line_nl
-- which we'll assume are Lua code
block = Cs(indented^1)/'    [[[!Lua\n%1]]]\n'

-- use > to get simple quoted block
quoted_line = empty('> ')*rest_of_line_nl 
quote = Cs (quoted_line^1)/"[[[\n%1]]]\n"
 
code = subst('`','{{%1}}')
italic = subst('_',"''%1''")
bold = subst('**',"'''%1'''")
rest_of_line = C((1 - lf)^1)
title1 = P'##' * rest_of_line/'=== %1 ==='
title2 = P'###' * rest_of_line/'== %1 =='

url = (subst('[',nil,']')*subst('(',nil,')'))/'[%2 %1]'
 
item = block + title1 + title2 + code + italic + bold + quote + url + 1
text = Cs(item^1)

if arg[1] then
    local f = io.open(arg[1])
    test = f:read '*a'
    f:close()
end

print(text:match(test))

因为这篇维基的转义问题，我需要在这个文本里将 ‘{’ 替换为 ‘[’ 。请注意！

SteveDonovan, 12 June 2012 – 翻译 : @spin6lock

组捕获和反向捕获

本节内容将剖析组捕获和反向捕获 (Cg() 和 Cb() )。

组捕获有两种：命名式及匿名式。

    Cg(C"baz" * C"qux", "name") -- 命名组。

    Cg(C"foo" * C"bar")         -- 匿名组。

我们先看看简单的部分：table 捕获里的命名组。

    Ct(Cc"foo" * Cg(Cc"bar" * Cc"baz", "TAG")* Cc"qux"):match"" 
    --> { "foo", "qux", TAG = "bar" }

在表捕获里，第一个捕获的值 ("bar") 会被分配到对应的 key ("TAG") 里去。就像你看到的那样， Cc"baz" 丢失了。 label 必须是一个字符串 ( 如果是数字，则会被转换为字符串 )。

注意分组必须是 table 的一个直接孩子，否则 table 捕获不会处理 :

    Ct(C(Cg(1,"foo"))):match"a"
    --> {"a"}

捕获和值

在深入研究分组之前，我们需要探索一下捕获如何处理他们的子捕获。

有些捕获是操作它们子捕获的值，有些则是有时候这是反直觉的。

我们看看以下这个例子 :

    (1 * C( C"b" * C"c" ) * 1):match"abcd"
    --> "bc", "b", "c"

就像你看到的一样，它把三个值插入了

我们把它用 table 报装一下：

    Ct(1 * C( C"b" * C"c" ) * 1):match"abcd"
    --> { "bc", "b", "c" }

Ct() 作用于值上面。在上一个例子里面，

现在，我们试试替换捕获 :

    Cs(1 * C( C"b" * C"c" ) * 1):match"abcd"
    --> "abcd"

Cs() 在捕获上操作。它扫描第一层的嵌套捕获，并只取每个捕获的第一个值。在上述的例子中， "b" 和 "c" 因此被抛弃了。这是另外一个更清晰的例子：

    function the_func (bcd) 
        assert(bcd == "bcd")
        return "B", "C", "D" 
    end

    Ct(1 * ( C"bcd" / the_func ) * 1):match"abcde"
    --> {"B", "C", "D"}  -- All values are inserted.

    Cs(1 * ( C"bcd" / the_func ) * 1):match"abcde"
    --> "aBe"   -- the "C" and "D" have been discarded.

其他章节里会更具体的讲述根据值捕获和根据行为捕获的区别。

捕获的不透明性

另外一个重要的事情，大部分的捕获会抑制他们的子捕获，但不是所有都这样。就像你上一个例子看到的，C"bcd" 的值被转到 /function 捕获里去，但最终捕获列表里不会出现。Ct() 和 Cs() 在这种情形下也是透明的。他们只产生一个 table 或者一个字符串。

另一方面， C() 也是透明的。正如我们上面所看到的，C() 的子捕获也会被插入流中。

    C(C"b" * C"c"):match"bc" --> "bc", "b", "c"

唯一透明的捕获是 C() 和匿名的 Cg()。

匿名组

Cg() 将子捕获包装到一个单独的捕获对象里去，但不产生自身的任何产物。根据上下文不同，要么它产生的所有值都被插入，要么只插入第一项。

这是匿名组的一些例子：

    (1 * Cg(C"b" * C"c" * C"d") * 1):match"abcde"
    --> "b", "c", "d"

    Ct(1 * Cg(C"b" * C"c" * C"d") * 1):match"abcde"
    --> { "b", "c", "d" }

    Cs(1 * Cg(C"b" * C"c" * C"d") * 1):match"abcde"
    --> "abe" -- "c" and "d" are dropped.

这些行为有用吗？在折叠模式捕获里有用。

我们来写一个非常简单的计算器，用来加上或减去一位数的。

    function calc(a, op, b)
        a, b = tonumber(a), tonumber(b)
        if op == "+" then 
            return a + b
        else
            return a - b
        end
    end

    digit = R"09"

    calculate = Cf(
        C(digit) * Cg( C(S"+-") * C(digit) )^0
        , calc
    )
    calculate:match"1+2-3+4"
    --> 4

捕获树看起来是这样的 [*]：

    {"Cf", func = calc, children = {
        {"C", val = "1"},
        {"Cg", children = {
            {"C", val = "+"},
            {"C", val = "2"}
        } },
        {"Cg", children = {
            {"C", val = "-"},
            {"C", val = "3"}
        } },
        {"Cg", children = {
            {"C", val = "+"},
            {"C", val = "4"}
        } }
    } }

你可能已经看出来是怎样一回事了。。。就像 Cs() 一样， Cf() 操作捕获对象。它会抽出第一个捕获的第一个值，然后作为初始值。如果没有更多捕获，这些值就会成为 Cf() 的值。

但我们有更多的捕获。在我们的例子里，它会将第二个捕获（组捕获）的所有值传给 calc()，紧跟第一个的值。这是上面 Cf() 的运算过程

    first_arg = "1"
    next_ones: "+", "2"
    first_arg = calc("1", "+", "2") -- 3, calc() returns numbers

    next_ones: "-", "3"
    first_arg = calc(3, "-", "3")

    next_ones: "+", "4"
    first_arg = calc(0, "+", "4")

    return first_arg -- Tadaaaa.

[*] 实际上，在匹配的时候，捕获对象只存储他们的边界和额外的数据 ( 比如为 Cf() 储存 calc() )。实际值会在匹配完成后依次产生，但是，它可以让代码变得更清晰。在上面的例子里，嵌套的 C() 和 Cg(C(), C()) 是每次输出一个，对应到折叠过程里自身的循环中。

命名组

命名组 Cg()/Cb() 跟匿名组 Cg() 有类似的行为，但 ``Cg() 捕获的值不是在局部插入的。他们在 Cb() 的位置插入流中。

举个例子 :

    ( 1 * Cg(C"bc", "FOOO") * C"d" * 1 * Cb"FOOO" * Cb"FOOO"):match"abcde"
    -- > "d", "bc", "bc"

如果有超过一个 Cb()，就会有副本产生。另一个例子：

    ( 1 * Cg(C"b" * C"c" * C"d", "FOOO") * C"e" * Ct(Cb"FOOO") ):match"abcde"
    --> "e", { "b", "c", "d" }

为了让代码更清晰，我一般会将 Cg() 命名为 Tag()。我会在匿名组里使用前者，而在命名组里使用后者。

Cb"FOOO" 会往回查找一个成功的 Cg() 匹配。它会在捕获树里往回和往上查找，并消耗对应的捕获。换句话说，它会搜索比自己更年长的兄弟，以及父母的兄弟，但不会搜索自己的父母。也不会查找他们祖先的兄弟的孩子。

它是像下文一样运行的 ( 从 [ #### ] <--- [[ START ]] 开始，并随着数字回溯 )。

[ numbered ] 是按顺序测试的捕获。用 [ ** ] 标记的则不是，原因见下。有点千头万绪，但是在我能考虑到的范围里是完备的。

    Cg(-- [ ** ] ... This one would have been seen, 
       -- if the search hadn't stopped at *the one*.
       "Too late, mate."
        , "~@~"
    )

    * Cg( -- [ 3 ] The search ends here. <--------------[[ Stop ]]
        "This is *the one*!"
        , "~@~"
    )

    * Cg(--  [ ** ] ... The great grand parent. 
                     -- Cg with the right tag, but direct ancestor,
                     -- thus not checked.

        
        Cg( -- [ 2 ] ... Cg, but not the right tag. Skipped.
            Cg( -- [ ** ] good tag but masked by the parent (whatever its type)
                "Masked"
                , "~@~"
            )
            , "BADTAG"
        )

        * C( -- [ ** ] ... grand parent. Not even checked.

            ( 
                Cg( -- [ ** ] ... This subpattern will fail after Cg() succeeds.
                    -- The group is thus removed from the capture tree, and will
                    -- not be found dureing the lookup.
                    "FAIL"
                    , "~@~"
                ) 
                * false 
            )

            + Cmt(  -- [ ** ] ... Direct parent. Not assessed.
                C(1) -- [ 1 ] ... Not a Cg. Skip.

                * Cb"~@~"   -- [ #### ]  <----------------- [[ START HERE ]] --
                , function(subject, index, cap1, cap2) 
                    return assert(cap2 == "This is *the one*!")
                end
            )
        )
        , "~@~" -- [ ** ] This label goes with the great grand parent.
    )

PierreYvesGerardy 翻译 by：@spin6lock

RecentChanges preferences edit historyLast edited May 24, 2015 11:11 am GMT (diff)