Red 中的 Parse

Parse 入门

Rebol 语言最大的特色之一就是它的解析引擎,简称为 Parse。这是卡尔·萨森拉斯(Carl Sassenrath)的一个惊人设计,在过去的15年里,所有 Rebol 用户都免于使用臭名昭著的无法维护的 regexp痛苦。现在,Parse 也可用于 Red 用户,而且是增强版!

那么,简而言之,什么是 Parse?它是一个嵌入式 DSL(我们称之为 Rebol 世界中的“方言”),用于使用语法规则解析输入序列。 Parse 方言是 TDPL 家族的增强成员。 Parse 的常见用法是检查,验证,提取,修改输入数据,甚至实现嵌入式和外部 DSL。

parse 函数调用语法很简单:

1
2
3
4
parse <input> <rules>  

<input>: 任意系列值 (字符串, 文件, 块儿, 路径, ...)
<rules>: 块儿! 具有有效 Parse 方言内容的值

这里有几个例子,即使你不懂 Red 和解析方言,你仍然可以“获得”它们中的大多数,不像正则表达式。您可以将它们直接复制/粘贴到 Red 控制台中。

使用语法规则进行字符串或块输入验证的一些简单示例:

1
2
3
4
5
6
7
8
9
10
parse "a plane" [["a" | "the"] space "plane"] ;-- rule 中的空格需要用 space 显式声明
parse "the car" [["a" | "the"] space ["plane" | "car"]]

parse "123" ["1" "2" ["4" | "3"]] ;-- rule 中的空格默认被忽略
parse "abbccc" ["a" 2 "b" 3 "c"] ;-- 一个 a, 俩个 b, 三个 c
parse "aaabbb" [copy letters some "a" (n: length? letters) n "b"]

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 地址:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
four:     charset "01234"
half: charset "012345"
non-zero: charset "123456789"
digit: union non-zero charset "0"

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 ; will ouput: "85.94.114.88"

一个粗略但实用的电子邮件地址验证器:

1
2
3
4
5
6
7
8
9
10
11
12
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 手册):

1
2
3
4
5
6
7
8
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 ; will return true
parse "1-(3/)+2" expr ; will return false

创建一个简单的 HTML 子集解析器:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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 "<"
]]
]

; will produce the following tree of blocks as output of parse:
[
html [
head [
title ["Test"]
]
body [
div [
u ["Hello"]
b ["World"]
]
]
]
]

Parse 方言

Parse 的核心原则是:

  • 通过匹配 grammar 规则推进输入系列,直到顶级规则失败(返回 false)或输入耗尽(返回 true)(*)
  • 有序选择(例如在[“a”|”ab”]规则中,第二个将永远不会成功)
  • 规则可组合性(无限制)
  • 有限的回溯:只有输入和规则位置被回溯,其他变化仍然存在
  • 两种模式:字符串解析(例如:外部 DSL)或块解析(例如:嵌入式 DSL)

(*) 如果在任何规则中以最简单的形式使用 collect 关键字,则无论 root 规则是否成功,都将通过 parse 返回一个块。

Parse规则可以来自:

  • keyword : 方言保留字(见下表)
  • word : word 会被求值并将其值用作规则
  • word: : 将单词设置为当前输入位置
  • :word : 在单词引用的位置继续输入
  • integer value : 指定具有固定数量或迭代范围的迭代规则
  • value : 将输入与值匹配
  • | : 回溯并匹配下一个备用规则
  • [rules] : 子规则块
  • (expression) : 转义 Parse方言,计算 Red 表达式并返回 Parse 方言

Red 的 Parse 实现中目前提供以下关键字。它们可以自由组合在一起。

匹配


  • ahead rule : 向前查看规则, 匹配规则, 但不推进输入
  • end : 如果当前输入位置到终点了则返回成功
  • none : 总是返回成功(catch-all 规则)
  • not rule : 反转子规则的结果
  • opt rule : 向前查看规则, 可选地匹配规则
  • quote rule : 按字面意思匹配下一个值(用于方言转义需求)
  • skip : 将输入推进一个元素(一个字符或一个值)
  • thru rule : 推进输入直到规则匹配, 输入设置在匹配的后面
  • to rule : 推进输入直到规则匹配, 输入设置在匹配的开头

控制流


  • break : 跳出匹配循环, 返回成功
  • if(expr) : 计算 Red 表达式,如果为 false 或 none,则失败并回溯
  • into rule : 将输入切换到匹配的系列(字符串或块)并用规则解析它
  • fail : 强制当前规则失败并回溯
  • then : 无论后续的失败或成功, 跳过下一个备用规则
  • reject : 跳出匹配循环, 返回失败

迭代


  • any rule : 重复规则零次或多次直到失败或输入没有推进
  • some rule : 重复规则一次或多次直到失败或输入没有推进
  • while 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 : 在当前输入位置插入[/only]值并在值后面推进输入
  • remove rule : 删除匹配的输入

核心原则提到了两种解析模式。这在 Red 中是必要的(就像在 Rebol 中),因为我们有两个基本的系列数据类型 : string!block!string! datatype 当前是一个 Unicode 代码点数组( Red 将在未来版本中支持字符数组),而 block! datatype 是一个任意 Red 值的数组(包括其他块)。

在实践中,这导致 Parse 方言使用中的一些细微差别。例如,可以使用新的 bitset! 数据类型定义任意字符集!这仅对 string! 解析有用以便一次匹配大量字符。以下是仅使用 bitsets 匹配和迭代器的示例 :

1
2
3
4
letter: charset [#"a" - #"z"]
digit: charset "0123456789"

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

Bitset! 数据类型

bitset 值是用于存储布尔值的 bit 位数组。在 Parse 的上下文中,bitsets 对于在整个 Unicode 范围内表示任意字符集非常有用,可以在单个操作中与输入字符进行匹配。因为 bitset! 在此 0.4.1 版本中引入,值得概述下所支持的功能。基本上,它与 Rebol3 的 bitset! 实现相同。

要创建 bitset,您需要提供一个或多个字符作为基本规范。它们可以以不同的形式提供:codepoint 整数值,char! 值,string! 值,一个范围或一组之前的元素。使用以下语法创建新的 bitset:

1
2
3
make bitset! <spec>

<spec>: char!, integer!, string! or block!

例如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
; create an empty bitset with places at least for 50 bits
make bitset! 50

; create a bitset with bit 65 set
make bitset! #"A"

; create a bitset with bits 104 and 105 set
make bitset! "hi"

; create and set bits using different values representations
make bitset! [120 "hello" #"A"]

; create a bitset using ranges of values
make bitset! [#"0" - #"9" #"a" - #"z"]

范围使用两个值(允许 char!integer!)定义,用破折号字分隔。

Bitsets 自动调整大小以适应所提供的规格值。大小舍入到高位字节边界。

还提供了快捷 charset 功能以供实际使用,因此您可以编写:

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

对于读写单个 bits 位,路径表示法是最简单的方法:

1
2
3
4
5
bs: charset [#"a" - #"z"]
bs/97 ; will return true
bs/40 ; will return false
bs/97: false
bs/97 ; will return false

(注意:bitset 索引从零开始。)

此外,bitset! 数据类型支持以下操作:

pick, poke, find, insert, append, copy, remove, clear, length?, mold, form

有关这些操作的使用的详细信息,请参阅 Rebol3 bitset 文档

为了处理各种 Unicode 字符,bitsets 之外的位被视为虚拟位,因此可以无错误地测试和设置它们,bitset 的大小将根据需要自动扩展。但这仍然不足以处理大的范围,例如除了数字之外的所有 Unicode 字符的 bitset。对于这种情况,可以定义补充的 bitset,该 bitset 表示指定位的补码范围。这使得在仅使用微小的存储器部分存储大的 bitset 成为可能。

补充的 bitsets 的创建方式与普通 bitsets 相同,但它们需要以 not 单词开头并始终对于他们的规格使用 block!

1
2
3
4
5
6
7
8
; all characters except digits
charset [not "0123456789"]

; all characters but hexadecimal symbols
charset [not "ABCDEF" #"0" - #"9"]

; all characters except whitespaces
charset reduce ['not space tab cr lf]

设置操作也是可能的,但目前只有 union 用 Red 实现了(它对于 bitsets 来说是最常用的)。使用 union,您可以将两个 bitsets 合在一起以形成一个新的 bitsets,这在实践中非常有用:

1
2
3
4
5
6
7
digit: charset "0123456789"
lower: charset [#"a" - #"z"]
upper: charset [#"A" - #"Z"]

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

Parse 实现

Parse 方言已经实现为 FSM,它不同于依赖于递归函数调用的 Rebol3 实现。 FSM 方法可以实现几个有趣的功能,例如能够停止解析并在以后恢复它,甚至序列化解析状态,远程发送它并重新加载它以继续解析。现在可以用最少的努力来实现这些功能。

Red Parse 实现大约有1300行 Red/System 代码,其中很大一部分花在了针对常见情况的优化迭代循环上。大约有770个单元测试是手写的,以涵盖基本的 Parse 功能。

当前的 Parse 作为解释器运行,对于大多数用例来说都足够快。对于需要最高性能的情况,已经开始在 Parse 静态编译器上开始工作,以便尽快为 Parse 密集型 Red 应用程序提供最快的速度。生成的代码是纯 Red/System 代码,平均比解释版本快一般。当 Red 将自托管时,将提供 Parse JIT 编译器来处理静态编译器无法处理的情况。

随着 Red 获得更多功能,Parse 将继续得到改进以利用它们。其他未来的改进,binary! 解析将尽快添加一旦 binary! 数据类型可用,当 port! 数据类型出现时流解析也将成为可能。

Red Parse 还以可选的回调函数的形式公开面向公共事件的 API,可以使用/trace 细化传递给 parse

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
parse/trace <input> <rules> <callback>

<callback> specification:

func [
event [word!] ; Trace events
match? [logic!] ; Result of last matching operation
rule [block!] ; Current rule at current position
input [series!] ; Input series at next position to match
stack [block!] ; Internal parse rules stack
return: [logic!] ; TRUE: continue parsing, FALSE: exit
]

Events list:
- push : once a rule or block has been pushed on stack
- pop : before a rule or block is popped from stack
- fetch : before a new rule is fetched
- match : after a value matching occurs
- iterate : after a new iteration pass begins (ANY, SOME, ...)
- paren : after a paren expression was evaluated
- end : after end of input has been reached

此 API 将在未来进行扩展,以获得更细粒度的事件。这个 API 可用于为 Parse 提供跟踪,统计,调试……让我们看看 Red 用户会想出什么! ;-)

已实现默认回调以进行跟踪。可以使用方便的解析跟踪函数包装器访问它:

1
parse-trace <input> <rules>

您可以使用简单的解析规则来尝试查看结果输出。

DSL 支持怎么样?

Parse 是实现 DSL 解析器(嵌入式和外部式)的强大工具,这要归功于它能够将 Red 表达式直接内联到规则中,从而可以轻松地将 DSL 语法与其相应的语义链接起来。为了说明这一点,这里是一个使用 Parse 编写的著名混淆语言的简单解释器:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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 非常有用。对于更复杂的 Parse,Parse 仍然可以正常工作,但随着 DSL 语义变得更加复杂,它可能没那么有用。对于大多数用户而言,为更高级的 DSL 实现解释器或编译器并非易事。 Red 将通过在Parse 之上提供元 DSL 包装器来解决这个问题,通过抽象出解释器或编译器的核心部分来暴露更高级别的 API 以构建更复杂的 DSL。用于构建其他 DSL 的 DSL 并不是一个疯狂的想法,它已经以一种非常强大的形式存在,例如Rascal 语言。 Red 将提供的只是朝这个方向迈出的一步,但没有像 Rascal 那样精密(和复杂)。

此版本中的其他更改

只是提到这个版本中的其他变化,现在我们摆脱了房间里的800磅大猩猩。此版本为 Red 和 Red/System 带来了大量的错误修复。此外,多亏了 qtxie,ELF 文件发射器在生成共享库时现在与其他文件发射器相当。

感谢所有参与帮助实现这一重大发布的人员,包括设计修复和改进,测试,错误报告和测试编写。

请享用! :-)

链接