26 个版本 (13 个稳定版)
3.4.0 | 2024年3月6日 |
---|---|
3.3.0 | 2023年6月19日 |
3.2.0 | 2020年9月17日 |
3.1.0 | 2020年1月6日 |
0.1.0 | 2016年12月30日 |
在 解析工具 中排名第4
每月下载量 41,722
在 122 个 包(直接 26 个)中使用
175KB
1.5K SLoC
pon
使用运算符重载创建的 PEG 解析器组合器,不使用宏。
文档
- 教程
- API 参考文档
- 使用 Rust 学习解析器组合器 - 作者:Bodil Stokke
PEG 是什么?
PEG 代表解析表达式语法,是一种分析形式语法,即它用一组规则来描述一种形式语言,这些规则用于识别语言中的字符串。与 CFG 相比,PEG 不能是歧义的;如果字符串可以解析,则它只有一个有效的解析树。每个解析函数在概念上接受一个输入字符串作为其参数,并产生以下结果之一
- 成功,在这种情况下,函数可以可选地向前移动或消费它所提供的输入字符串中的一个或多个字符,或者
- 失败,在这种情况下,不消费任何输入。
更多内容请参阅 维基百科。
解析器组合器是什么?
解析器组合器是一种接受多个解析器作为输入并返回新解析器作为输出的高阶函数。解析器组合器启用递归下降解析策略,该策略便于模块化分片构建和测试。
使用组合器构建的解析器结构简单,易于阅读,模块化,结构良好且易于维护。使用运算符重载,解析器组合器可以采用中缀运算符的形式,用于将不同的解析器粘合在一起形成完整的规则。因此,解析器组合器允许以嵌入式方式定义解析器,其代码结构与形式语法的规则相似。并且代码比宏更容易调试。
主要优点是您不需要经过任何代码生成步骤,您始终在底层使用纯语言。除了构建问题(以及围绕错误消息和可调试性的通常问题,公平地说,它们与宏和代码生成一样糟糕)之外,通常更容易自由混合语法表达式和普通代码。
预定义解析器和组合器的列表
基本解析器 | 描述 |
---|---|
empty() | 始终成功,不消费任何输入。 |
end() | 匹配输入的结尾。 |
any() | 匹配任何符号并返回该符号。 |
sym(t) | 匹配单个终结符 t。 |
seq(s) | 匹配符号序列。 |
list(p,s) | 匹配由 p 和 s 分隔的列表。 |
one_of(set) | 如果当前输入符号是集合中的一个,则成功。 |
none_of(set) | 如果当前输入符号不是集合中的一个,则成功。 |
is_a(predicate) | 如果谓词对当前输入符号返回 true,则成功。 |
not_a(predicate) | 如果谓词对当前输入符号返回 false,则成功。 |
take(n) | 读取 n 个符号。 |
skip(n) | 跳过 n 个符号。 |
call(pf) | 调用解析器工厂,可用于创建递归解析器。 |
解析器组合器 | 描述 |
---|---|
p | q | 匹配 p 或 q,返回第一个成功的结果。 |
p + q | 匹配 p 和 q,如果都成功则返回结果对的组合。 |
p - q | 匹配 p 和 q,如果都成功则返回 p 的结果。 |
p * q | 匹配 p 和 q,如果都成功则返回 q 的结果。 |
p >> q | 解析 p 并获取结果 P,然后解析 q 并返回 q(P) 的结果。 |
-p | 如果 p 成功,则成功,不消耗输入。 |
!p | 如果 p 失败,则成功,不消耗输入。 |
p.opt() | 使解析器成为可选。返回一个 Option 。 |
p.repeat(m..n) | p.repeat(0..) 重复 p 0 次或更多次p.repeat(1..) 重复 p 1 次或更多次p.repeat(1..4) 匹配 p 至少 1 次且最多 3 次p.repeat(5) 重复 p 正好 5 次 |
p.map(f) | 将解析器结果转换为所需值。 |
p.convert(f) | 将解析器结果转换为所需值,转换错误时失败。 |
p.pos() | 获取匹配 p 后的输入位置。 |
p.collect() | 收集所有匹配的输入符号。 |
p.discard() | 丢弃解析器输出。 |
p.name(_) | 给解析器命名以识别解析错误。 如果启用了 trace 功能,则将解析和解析结果的基本跟踪输出到 stdout。 |
p.expect(_) | 将解析器标记为期望的,在有序选择失败时提前终止。 |
操作符的选择由它们的运算符优先级、元数和 "含义" 确定。使用 *
忽略表达式开始时第一个操作符的结果,+
和 -
可以满足表达式其余部分的需求。
例如,A * B * C - D + E - F
将返回 C 和 E 作为一对的结果。
示例代码
use pom::parser::*;
let input = b"abcde";
let parser = sym(b'a') * none_of(b"AB") - sym(b'c') + seq(b"de");
let output = parser.parse(input);
assert_eq!(output, Ok( (b'b', vec![b'd', b'e'].as_slice()) ) );
示例 JSON 解析器
extern crate pom;
use pom::parser::*;
use pom::Parser;
use std::collections::HashMap;
use std::str::{self, FromStr};
#[derive(Debug, PartialEq)]
pub enum JsonValue {
Null,
Bool(bool),
Str(String),
Num(f64),
Array(Vec<JsonValue>),
Object(HashMap<String,JsonValue>)
}
fn space() -> Parser<u8, ()> {
one_of(b" \t\r\n").repeat(0..).discard()
}
fn number() -> Parser<u8, f64> {
let integer = one_of(b"123456789") - one_of(b"0123456789").repeat(0..) | sym(b'0');
let frac = sym(b'.') + one_of(b"0123456789").repeat(1..);
let exp = one_of(b"eE") + one_of(b"+-").opt() + one_of(b"0123456789").repeat(1..);
let number = sym(b'-').opt() + integer + frac.opt() + exp.opt();
number.collect().convert(str::from_utf8).convert(|s|f64::from_str(&s))
}
fn string() -> Parser<u8, String> {
let special_char = sym(b'\\') | sym(b'/') | sym(b'"')
| sym(b'b').map(|_|b'\x08') | sym(b'f').map(|_|b'\x0C')
| sym(b'n').map(|_|b'\n') | sym(b'r').map(|_|b'\r') | sym(b't').map(|_|b'\t');
let escape_sequence = sym(b'\\') * special_char;
let string = sym(b'"') * (none_of(b"\\\"") | escape_sequence).repeat(0..) - sym(b'"');
string.convert(String::from_utf8)
}
fn array() -> Parser<u8, Vec<JsonValue>> {
let elems = list(call(value), sym(b',') * space());
sym(b'[') * space() * elems - sym(b']')
}
fn object() -> Parser<u8, HashMap<String, JsonValue>> {
let member = string() - space() - sym(b':') - space() + call(value);
let members = list(member, sym(b',') * space());
let obj = sym(b'{') * space() * members - sym(b'}');
obj.map(|members|members.into_iter().collect::<HashMap<_,_>>())
}
fn value() -> Parser<u8, JsonValue> {
( seq(b"null").map(|_|JsonValue::Null)
| seq(b"true").map(|_|JsonValue::Bool(true))
| seq(b"false").map(|_|JsonValue::Bool(false))
| number().map(|num|JsonValue::Num(num))
| string().map(|text|JsonValue::Str(text))
| array().map(|arr|JsonValue::Array(arr))
| object().map(|obj|JsonValue::Object(obj))
) - space()
}
pub fn json() -> Parser<u8, JsonValue> {
space() * value() - end()
}
fn main() {
let input = br#"
{
"Image": {
"Width": 800,
"Height": 600,
"Title": "View from 15th Floor",
"Thumbnail": {
"Url": "http://www.example.com/image/481989943",
"Height": 125,
"Width": 100
},
"Animated" : false,
"IDs": [116, 943, 234, 38793]
}
}"#;
println!("{:?}", json().parse(input));
}
您可以使用以下命令运行此示例
cargo run --example json
基准测试
解析器 | 解析相同 JSON 文件的时间 |
---|---|
pom: json_byte | 621,319 ns/iter (+/- 20,318) |
pom: json_char | 627,110 ns/iter (+/- 11,463) |
pest: json_char | 13,359 ns/iter (+/- 811) |
生命周期和文件
字符串字面量具有静态生命周期,因此它们可以与从 pom::Parser
导入的静态版本解析器一起工作。从文件读取的输入具有更短的生命周期。在这种情况下,您应该导入 pom::parser::Parser
并在您的解析器函数上声明生命周期。因此
fn space() -> Parser<u8, ()> {
one_of(b" \t\r\n").repeat(0..).discard()
}
将变为
fn space<'a>() -> Parser<'a, u8, ()> {
one_of(b" \t\r\n").repeat(0..).discard()
}
依赖项
~625KB