Parse 简介

作者: Taozii | 来源:发表于2017-12-06 11:04 被阅读74次

导言

提到Rebol语言的优秀特性那就不得不说它的解析引擎，简称Parse。这项来自Carl Sassenrath的伟大设计，在过去的15年里，使得Rebol用户免受正则表达式（以不可维护著称）的折磨。现如今，Parse的增强版本在Red语言中重装上阵。

简而言之，Parse是一个使用语法规则来解析输入序列的内部DSL（在Rebol生态圈称为“方言”）。Parse方言是TDPL家族的突出一员。常用来校验，验证，分解，修改输入的数据，甚至是实现内部或者外部DSL。

parse函数的用法很简单：

parse <输入序列> <规则>
<输入序列>: 任意序列类型的值（字符串，文件，区块，路径...）
<规则>: 一个区块（包含有效的Parse方言）

下面的示例代码可以直接复制到Red控制台中运行，即便你不懂Red和Parse方言，也能观其大略，不像正则表达式那样让人不知所云。

使用语法规则验证一些字符串和区块的输入：

parse "a plane" [["a" | "the"] space "plane"]  ;规则中可以包含子规则
parse "the car" [["a" | "the"] space ["plane" | "car"]]

parse "123" ["1" "2" ["4" | "3"]]
parse "abbccc" ["a" 2 "b" 3 "c"] ;指定数量
parse "aaabbb" [copy letters some "a" (n: length? letters) n "b"] ;将匹配绑定到变量，使用小括号执行Red表达式

parse [a] ['b | 'a | 'c]
parse [hello nice world] [3 word!] ;匹配区块可以使用类型
parse [a a a b b b] [copy words some 'a (n: length? words) n 'b]

下面展示如何解析IPv4地址：

four:     charset "01234" ;charset函数用于创建一个bitset!类型的值
half:     charset "012345"
non-zero: charset "123456789"
digit:    union non-zero charset "0" ;bitset!类型可以使用Red的集合运算union函数进行组合

byte: [
      "25" half
    | "2" four digit
    | "1" digit digit
    | non-zero digit
    | digit
]
ipv4: [byte dot byte dot byte dot byte]

parse "192.168.10.1" ipv4
parse "127.0.0.1"    ipv4
parse "99.1234"      ipv4
parse "10.12.260.1"  ipv4

data: {
    ID: 121.34
    Version: 1.2.3-5.6
    Your IP address is: 85.94.114.88.
    NOTE: Your IP Address could be different tomorrow.
}
parse data [some [copy value ipv4 | skip]]
probe value                      ; 输出: "85.94.114.88"

一个粗糙然而实用的email地址验证器：

digit:   charset "0123456789"
letters: charset [#"a" - #"z" #"A" - #"Z"]
special: charset "-"
chars:   union union letters special digit
word:    [some chars]
host:    [word]
domain:  [word some [dot word]]
email:   [host "@" domain]

parse "john@doe.com" email
parse "n00b@lost.island.org" email
parse "h4x0r-l33t@domain.net" email

验证字符串形式的数学表达式（来自Rebol/Core手册）

expr:    [term ["+" | "-"] expr | term]     ;规则可以递归定义
term:    [factor ["*" | "/"] term | factor]
factor:  [primary "**" factor | primary]
primary: [some digit | "(" expr ")"]
digit:   charset "0123456789"
    
parse "1+2*(3-2)/4" expr        ; 返回 true
parse "1-(3/)+2" expr           ; 返回 false

创建简单的解析器用于解析一个HTML子集：

html: {
    <html>
        <head><title>Test</title></head>
        <body><div><u>Hello</u> <b>World</b></div></body>
    </html>
}

ws: charset reduce [space tab cr lf]

parse html tags: [
    collect [any [
        ws
        | "</" thru ">" break
        | "<" copy name to ">" skip keep (load name) opt tags
        | keep to "<"
    ]]
]

; parse函数将会返回如下区块树
[
    html [
        head [
                title ["Test"]
            ]
        body [
            div [
                u ["Hello"]
                b ["World"]
            ]
        ]
    ]
]

Parse方言

Parse的核心原则如下：

输入序列的位置由语法规则驱动前进，直到顶层规则匹配失败（parse函数返回false）或者遇到输入序列的末尾（parse函数返回true）。（*）
有顺序地匹配（例如，在["a" | "ab"]这个规则来说，第二个选项不会被匹配）。
语法规则可无限组合。
有限的回溯：只有输入和规则的位置可回溯，其他改动仍然保留。
两种模式：字符串解析（例如实现外部DSL）或者区块解析（例如实现内部DSL）。

（*）只要规则中使用了collect关键字，parse函数就返回一个区块，不论顶层规则是否匹配成功。

Parse的规则由如下元素构成：

关键字：Parse方言预留的单词（见下表）。
单字(word)：单字所绑定的值被用于规则。
设字(word:)：将单字绑定到当前的输入流位置。
取字(:word)：恢复单字绑定的输入流位置。
整型数值：指定规则重复的数量或者范围。
字面值：匹配输入流中对应的字面值。
| : 回溯并且尝试匹配其他可选规则。
[rules]：子规则区块。
(expression)：脱离Parse方言转而执行Red表达式，执行完毕后返回到Parse方言。

Red的Parse实现可以使用下面的关键字，这些关键字可以自由组合。（共分成了5类）

匹配

ahead rule :预匹配规则，但是输入流位置不前进

end :当前输入流位置处于末尾则返回成功

none :总是返回成功（通用规则）（译者注：有误？实验结果更像是匹配空而不是通配）

not rule :反转子规则的结果

opt rule :预匹配规则，可选性地匹配该规则。

quote value :以字面值匹配（用于Parse方言的转义）

skip :输入流位置前进一个元素（字符或者一个值）

thru rule :前进输入流位置直到成功匹配规则，并将输入流位置放到匹配之后。

to rule :前进输入流位置直到成功匹配规则，并将输入流位置放到匹配之前。

控制流

break :中断匹配循环并返回成功

if (expr) :对Red表达式求值，如果为false或者none，匹配失败并回溯

into rule :转换输入流为已匹配的序列（字符串或者区块）并且使用指定的规则近一步解析

fail :强制当前规则匹配失败并回溯

then :不论接下来的匹配是否成功，都跳过下一个替代规则

reject :中断匹配循环并返回失败

迭代

any rule :重复匹配零次或者多次rule直到匹配失败或者输入流不再前进

some rule :重复匹配一次或者多次rule直到匹配失败或者输入流不再前进

while rule :重复匹配一次或者多次rule直到匹配失败并且忽略输入流是否前进

分解

collect [rule] :以区块的形式返回在匹配规则中收集到的值

collect set word [rule] :将匹配规则中收集到的值放入区块，并将区块绑定到word

collect into word [rule] :将匹配规则中收集到的值插入到word所引用的区块

copy word rule :拷贝匹配的内容并绑定到word

keep rule :拷贝匹配的内容并添加到一个区块

keep (expr) :将Red表达式中的最后一个值添加到一个区块

set word rule :将匹配的第一个值绑定到word

修改

insert only value :在当前输入流的位置插入一个值并将位置放置到该值之后

remove rule :删除匹配项

在Parse的核心原则中提到了两种解析模式。这在Red中是很有必要的（Rebol亦然），因为我们有两种基本的序列类型：string!和block!。当前字符串类型是由Unicode代码点的数组表示的（后来的Red版本中将会支持字符数组），区块类型是任意Red值的数组（包括其他区块）。

这在Parse方言的使用中引起了一些微小的差别。例如，新增的bitset!数据类型可以定义任意地字符集，用于在字符串中一次性匹配大量的字符。下面是使用bitset和迭代进行匹配的示例：

letter: charset [#"a" - #"z"]
digit:  charset "0123456789"

parse "hello 123 world" [5 letter space 3 digit space some letter]

Bitset! 数据类型

bitset值是一个存储布尔值的bit数组。在Parse上下文中，bitset可以表达整个Unicode范围内的任意字符集，并用来在单个操作内匹配一个输入字符，这相当有用。bitset!类型是在这次的0.4.1版本引入的，因而对其支持的特性有必要作一番概述。它和Rebol3中的bitset!实现基本是同一个水平。

要创建一个bitset，你需要提供一个或者多个字符作为基本规格。可以使用不同的形式提供：表示Unicode代码点的整型数值，char!类型的值，string!类型的值，前面几种元素的范围或者组合。一个新的bitset使用如下语法创建：

make bitset! <基本规格>
<基本规格>：char!, integer!, string! or block!

例如：

; 创建一个空的bitset，至少可以容纳50个bits
make bitset! 50

; 创建一个bitset，第65位bit被设置
make bitset! #"A"

; 创建一个bitset，第104，105位bit被设置
make bitset! "hi"

; 使用不同的值设置bit位
make bitset! [120 "hello" #"A"]

; 使用char!值的范围来创建bitset
make bitset! [#"0" - #"9" #"a" - #"z"]

两个值（只允许char!和integer!类型）加一个破折号定义了一个范围。

bitset的大小是根据提供的基本规格调整的。跟最高位的字节边界对齐。

charset函数用于方便的创建bitset，因此你可以这样写：

charset "ABCDEF"
charset [120 "hello" #"A"]
charset [#"0" - #"9" #"a" - #"z"]

要读写bitset的某个bit位，路径表示法再方便不过了：

bs: charset [#"a" - #"z"]
bs/97     ; will return true
bs/40     ; will return false
bs/97: false
bs/97     ; will return false

(注意：bitset的索引是从0开始的)

除此之外，bitset类型还支持下面的操作：
pick, poke, find, insert, append, copy, remove, clear, length?, mold, form

关于这些操作的详细用法请参考Rebol3的bitset文档

为了处理Unicode字符这么大的范围，bitset之外的bit位被当作虚拟位来处理，因此访问或者设置这些位不会发生错误，bitset会根据需要自动扩展。然而这还是不足以应付很大的范围，比如除了数字以外的所有Unicode字符。这种情况下通过定义bitset的补集，既可以表达大范围的字符又占用很少的空间。

bitset补集的创建方式和普通bitset一样，只是需要使用not开头而且一般使用区块作为规格：

; 除数字以外的所有字符
charset [not "0123456789"]

; 除十六进制符号外的所有字符
charset [not "ABCDEF" #"0" - #"9"]

; 除空白字符外的所有字符
charset reduce ['not space tab cr lf]

集合运算对于bitset也是可用的，然而当前Red只支持union（毕竟这是bitset用得最多的函数）。使用union，你可以将两个bitset合并为一个新的bitset：

digit: charset "0123456789"
lower: charset [#"a" - #"z"]
upper: charset [#"A" - #"Z"]

letters:  union lower upper
hexa:     union upper digit
alphanum: union letters digit

Parse的实现

Red中的Parse方言是使用FSM实现的，不同于Rebol3依赖于递归函数调用。使用FSM使得一些有趣的特性成为可能，例如暂停和恢复解析，序列化解析状态然后发送到远端，然后重新加载并继续解析。现在这些都可以轻易办到。

Red的Parse由接近1300行Red/System代码实现，其中相当一部分用于优化常见使用情况下的迭代循环。手写了大约770个单元测试用于覆盖基本特性。

当前Parse是以解释器模式运行的，这对于大部分使用情况都足够快了。为了满足那些需要最大化性能的严重依赖解析的应用，给parse添加静态编译器的相关工作也已经开展。到时生成的Red/System代码应该平均比解释器版本快一个量级。当Red实现自举后，还会实现一个Parse的JIT编译器用于处理静态编译器不能处理的问题。

当Red有了更多新特性后，Parse也会相应的持续改进以便利用这些新特性。将来的多项改进包括，当binary!类型可用后，Parse也会添加对binary!类型的解析，并且当port!类型可用时，流解析也将成为可能。

Red的Parse还支持一个公开的面向事件API，你可以通过/trace refinement给parse函数传递一个回调函数。

parse/trace <输入> <规则> <回调函数>

<回调函数> 规格:

func [
    event   [word!]   ; 跟踪事件
    match?  [logic!]  ; 上次匹配操作的结果
    rule    [block!]  ; 当前位置的对应规则
    input   [series!] ; 将要匹配的下一个位置的输入序列
    stack   [block!]  ; 内部的解析规则栈
    return: [logic!]  ; TRUE: 继续匹配, FALSE: 退出
]

事件列表:
- push    : 当一个规则或者区块入栈时
- pop     : 当一个规则或者区块出栈之前
- fetch   : 当一个新的规则被采用之前
- match   : 当一个值匹配发生了
- iterate : 当一个新的迭代开始了 (ANY, SOME, ...)
- paren   : 当一个小括号中的表达式被求值后
- end     : 当到达输入末尾时

该API将来会扩展出更多细粒度的事件。该API可以被用于对Parse进行跟踪，获取状态，调试，... 咱们且拭目以待Red用户们会玩出什么新的花样！;-)

有一个默认的回调函数被用于跟踪。你可以方便的通过使用parse-trace函数来使用它：

parse-trace <输入> <规则>

你可以试着用一些简单的解析规则来查看输出结果。

关于DSL支持

Parse是实现DSL（内部或者外部）解析器的强大工具，它可以在规则中内联Red表达式，从而能够轻易的将DSL语法和其语义关联起来。为了表明这点，下面是一个Parse写的解释器示例，用于解释著名的晦涩语言Brainfuck。

bf: function [prog [string!]][
    size: 30000
    cells: make string! size
    append/dup cells null size

    parse prog [
        some [
              ">" (cells: next cells)
            | "<" (cells: back cells)
            | "+" (cells/1: cells/1 + 1)
            | "-" (cells/1: cells/1 - 1)
            | "." (prin cells/1)
            | "," (cells/1: first input "")
            | "[" [if (cells/1 = null) thru "]" | none]
            | "]" [
               pos: if (cells/1 <> null)
               (pos: find/reverse pos #"[") :pos
               | none
              ]
            | skip
        ]
    ]
]

; This code will print a Hello World! message
bf {
    ++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.
    >++.<<+++++++++++++++.>.+++.------.--------.>+.>.
}

; This one will print a famous quote
bf {
    ++++++++[>+>++>+++>++++>+++++>++++++>+++++++>++++++++>
    +++++++++>++++++++++>+++++++++++>++++++++++++>++++++++
    +++++>++++++++++++++>+++++++++++++++>++++++++++++++++<
    <<<<<<<<<<<<<<<-]>>>>>>>>>>>----.++++<<<<<<<<<<<>>>>>>>
    >>>>>>.<<<<<<<<<<<<<>>>>>>>>>>>>>---.+++<<<<<<<<<<<<<>>
    >>>>>>>>>>>>++.--<<<<<<<<<<<<<<>>>>>>>>>>>>>---.+++<<<<
    <<<<<<<<<>>>>.<<<<>>>>>>>>>>>>>+.-<<<<<<<<<<<<<>>>>>>>>
    >>>>>>+++.---<<<<<<<<<<<<<<>>>>.<<<<>>>>>>>>>>>>>>--.++
    <<<<<<<<<<<<<<>>>>>>>>>>>>>>-.+<<<<<<<<<<<<<<>>>>.<<<<>
    >>>>>>>>>>>>>+++.---<<<<<<<<<<<<<<>>>>>>>>>>>>>>.<<<<<<
    <<<<<<<<>>>>>>>>>>>>>>-.+<<<<<<<<<<<<<<>>>>>>>>>>>>>>-.
    +<<<<<<<<<<<<<<>>>>>>>>>>>>>>--.++<<<<<<<<<<<<<<>>>>+.-
    <<<<.
}

注意：为了使得实现更加简短，该实现仅限于处理一层的"[...]"结构。使用Parse写的稍长和稍复杂的完整实现点这里。

所以当前应付较小的DSL应该不在话下。对于较复杂的DSL理论上也没问题，然而当DSL的语义变得更复杂时，Parse能起的作用就没这么大了。对于大部分的用户来说，实现一个较高级DSL的解释器或者编译器都绝非易事。针对这个问题，Red将来要着手在Parse之上提供一套元DSL(meta-DSL)包装，暴露一组更高级的API用于抽象解释器或者编译器的核心组件，使得编写复杂DSL变得更容易。要实现一个DSL用来创建其他DSL的想法绝不是痴人说梦，Rascal语言中已经存在这种强大的形式了。Red也会朝着这个方向迈进，然而不会有Rascal这么复杂。

Parse 简介

导言

Parse方言

匹配

控制流

迭代

分解

修改

Bitset! 数据类型

Parse的实现

关于DSL支持

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读