哈Ha！ 我向您介绍了文章“使用Rust学习解析器组合器”的翻译 。
本文为已经熟悉Rust的人们讲授了组合解析器的基础知识。 假定不需要其他知识，并且将解释与Rust不直接相关的所有内容以及其使用的某些意外方面。 如果您还不了解Rust，那么本文将不会帮助您学习Rust，在这种情况下，您很可能不会很好地理解组合解析器。 如果您想学习Rust，建议您阅读“ Rust编程语言”一书。
从初学者的角度
在每个程序员的生活中，总有一段时间需要解析器。
新手程序员会问：“解析器是什么？”
中级程序员会说：“很简单，我会写一个正则表达式。”
主程序员会说：“滚开，我知道lex和yacc。”
新手认为最好。
并不是说正则表达式不好。 （但是，请不要尝试将复杂的解析器编写为正则表达式。）并不是说，使用强大的工具（如解析器和lexer生成器）经过了几千年的完善，并没有什么乐趣。 但是学习解析器的基础是一种乐趣 。 如果您在使用正则表达式或解析器生成器时感到恐慌，这也是您将错过的地方，这两者都只是对实际问题的抽象。 正如一个人所说 ，在初学者的心中，有很多可能性。 据专家说，只有一个正确的选择。
在本文中，我们将学习如何使用以下命令从头构建解析器：
使用函数编程语言中常见的一种称为组合解析器的方法 。 它们的优点是，一旦您掌握了它们的基本概念，便会出奇地强大，同时又非常接近基本原理。 因为这里唯一的抽象将是您自己创建的抽象。 您将在此处使用的主要组合器将构建您自己。
如何使用本文
强烈建议您从一个新的Rust项目开始，并在阅读时在src/lib.rs编写代码段（您可以直接从页面粘贴它，但输入得更好，因为这会自动确保您可以完全阅读它）。 文章中按顺序排列了您需要的所有代码部分。 请记住，有时会引入您先前编写的函数的修改版本，在这种情况下，您必须用新版本替换旧版本。
该代码是使用2018语言版本为rustc版本1.34.0编写的。 您可以使用任何版本的编译器，请确保您使用的版本支持2018版（请确保您的Cargo.toml包含edition = "2018" ）。 该项目不需要外部依赖项。
为了执行本文中介绍的测试，如预期的那样，使用了cargo test 。
Xcruciating标记语言
我们将为XML的简化版本编写一个解析器。 看起来像这样：
<parent-element> <single-element attribute="value" /> </parent-element>
XML元素以<字符和一个标识符组成，标识符由一个字母和一个字母后跟任意数量的字母，数字和- 。 其后是空格和一个可选的属性对列表：另一个如先前定义的标识符，其后是=和双引号的字符串。 最后，要么有一个结束/>字符来指示一个没有子元素的元素，要么有一个>来指示下一个子元素序列的存在，一个以</开头的结束标签，后跟一个必须与开始标签匹配的标识符，以及一个结束字符> 。
这就是我们将支持的一切。 将没有名称空间，文本节点，并且最肯定的是将没有架构检查。 我们甚至不必担心转义字符串的引号-它们以第一个双引号开始，然后以下一个双引号结束，仅此而已。
我们将把这些元素解析成如下所示的结构：
#[derive(Clone, Debug, PartialEq, Eq)] struct Element { name: String, attributes: Vec<(String, String)>, children: Vec<Element>, }
没有花哨的类型，只有名称的字符串（这是每个标签开头的标识符），成对的字符串（标识符和值）形式的属性以及与父项完全相似的子项列表。
（如果要打印，请确保包括derive部分。稍后将需要它。）
解析器定义
好了，该写解析器了。
解析是从信息流中获取结构化数据的过程。 解析器就是产生这种结构的原因。
在我们要研究的学科中，解析器以最简单的形式出现，它是一个函数，它接受一些输入并返回已解析的输出以及其余的输入，或者返回一个错误，提示“我无法解析”。
解析器还以更复杂的形式显示。 您可以使输入，输出和错误的含义复杂化，如果需要的错误消息也很复杂，但是解析器保持不变：某些东西会消耗输入并产生某种形式的解析输出以及输入遗留下来的内容，或让您知道它无法将输入解析为输出。
让我们将其编写为一种函数。
Fn(Input) -> Result<(Input, Output), Error>
更具体地说：在我们的情况下，我们要填充类型并获得与此功能类似的功能。 我们要做的就是将字符串转换为Element结构。 目前，我们不想深入了解错误消息，因此只需返回行中我们无法解析的部分即可。 结果，我们的函数将如下所示：
Fn(&str) -> Result<(&str, Element), &str>
我们使用字符串切片是因为它是指向字符串片段的有效指针，然后我们可以根据需要通过“消耗”输入数据，切出已分析的片段并将其余部分与结果一起返回来分离它。
使用&[u8] （与ASCII字符匹配的字节切片）作为输入类型可能会更干净，尤其是因为字符串切片的行为与大多数切片有所不同-尤其是因为无法用一个索引它们数字input[0] ，应使用片段input[0..1] 。 另一方面，它们有许多方法可用于解析没有字节片的字符串。
实际上，由于Unicode，我们将依靠方法而不使用字符索引。 在UTF-8中，所有Rust字符串都是有效的UTF-8字符串，这些索引并不总是对应于单个字符，因此，所有相关方最好要求标准库为我们使用它。
我们的第一个解析器
让我们尝试编写一个仅查看字符串中第一个字符的解析器
并确定它是否为字母a 。
fn the_letter_a(input: &str) -> Result<(&str, ()), &str> { match input.chars().next() { Some('a') => Ok((&input['a'.len_utf8()..], ())), _ => Err(input), } }
首先，让我们看一下输入和输出的类型：我们将一个字符串切片作为输入，并使用(&str, ())返回Result ，或者使用&str一个错误。 这对(&str, ())很有意思：正如我们说过，我们应该返回以下内容的元组，
解析结果和其余输入。 &str是下一个输入，结果只是一个块类型() ，因为如果此解析器成功运行，它只能有一个结果（我们找到字母a ），并且我们实际上不需要返回
在这种情况下，字母a只需要表明我们设法找到它即可。
因此，让我们看一下解析器本身的代码。 我们并不是在开玩笑，依靠标准库可以避免Unicode带来的麻烦：我们使用chars()方法对字符串的chars()进行迭代，并从中获取第一个字符。 这将是Option中包装的char类型的元素，其中None表示我们试图从空字符串中提取char 。
更糟糕的是， char甚至不一定像您认为的Unicode字符一样。 这很可能是Unicode所称的“字素簇” ，它可以由几个char组成，这些char实际上是“标量值” ，位于字素簇下面两个级别。 但是，这条路径会导致精神错乱，就我们的目的而言，老实说，我们不太可能看到ASCII以外的字符，因此我们就此停止。
我们映射到Some('a')模式，这是我们正在寻找的特定结果，如果匹配，则返回成功值：
Ok((&input['a'.len_utf8()..], ())) 。 也就是说，我们从线切片中删除了刚解析的部分（ 'a' ），然后将其余部分连同我们的解析值一起返回，该值只是空的
() 。 始终记住Unicode怪物，在剪切之前，我们会通过标准库找出字符'a' UTF-8长度-为1（但不要忘记Unicode怪物）。
如果得到任何其他Some(char) ，或者得到None ，则返回错误。 您还记得，我们的错误类型只是一个字符串切片，我们将其作为input传递并且无法解析。 它不是以开头，所以这是我们的错误。 这不是一个大错误，但至少比“某处有问题”要好一些。
我们实际上并不需要此解析器来解析XML，但是我们要做的第一件事是找到开头字符< ，因此我们需要非常相似的东西。 我们还需要专门分析> ， /和= ，所以也许我们可以创建一个为所需字符构建解析器的函数？
创建一个解析器
我们甚至考虑一下：我们将编写一个函数，该函数为任意长度的静态字符串（不仅仅是一个字符）创建一个解析器。 这甚至更简单，因为该行片段已经是有效的UTF-8线切片，并且我们无需考虑Unicode怪物。
fn match_literal(expected: &'static str) -> impl Fn(&str) -> Result<(&str, ()), &str> { move |input| match input.get(0..expected.len()) { Some(next) if next == expected => { Ok((&input[expected.len()..], ())) } _ => Err(input), } }
现在看起来有些不同。
首先，让我们看一下类型。 现在，我们的函数将expected字符串作为参数，并返回类似于解析器的内容，而不是解析器本身。 这是一个返回高阶函数的函数 。 本质上，我们正在编写一个使该函数与我们的the_letter_a函数相似的函数。
因此，我们将返回执行此工作的闭包，而不是在函数主体中执行工作，该闭包与上一个分析器的类型签名相对应。
模式匹配看起来是一样的，除了我们不能直接匹配字符串文字，因为我们不知道到底是什么，因此if next == expected ，我们将使用匹配条件。 否则，它与之前的电路完全相同，只是在电路的内部。
测试我们的解析器
让我们为此做一个测试，以确保我们做对了。
#[test] fn literal_parser() { let parse_joe = match_literal("Hello Joe!"); assert_eq!( Ok(("", ())), parse_joe("Hello Joe!") ); assert_eq!( Ok((" Hello Robert!", ())), parse_joe("Hello Joe! Hello Robert!") ); assert_eq!( Err("Hello Mike!"), parse_joe("Hello Mike!") ); }
首先，我们创建一个解析器： match_literal("Hello Joe!") 。 它应该使用字符串"Hello Joe!" 然后返回字符串的其余部分，或者失败并返回整个字符串。
在第一种情况下，我们只是将期望的确切行传递给它，然后看到它返回一个空字符串和value () ，这意味着“我们已经分析了期望的字符串，不需要返回它。”
在第二个中，我们输入字符串"Hello Joe! Hello Robert!" 我们看到他确实使用了字符串"Hello Joe!" 并返回输入的其余部分： " Hello Robert!" （领先的空间以及其他所有功能）。
在第三行中，我们输入了错误的输入： "Hello Mike!" 并请注意，它确实拒绝输入错误。 并不是说Mike是错的，通常不是解析器在寻找什么。
解析器针对不太具体的内容
因此，这使我们能够分析< ， > ， =甚至</和/> 。 我们快完成了！
开头字符<之后的下一个是元素的名称。 我们不能通过简单的字符串比较来做到这一点。 但是我们可以使用正则表达式...
...但是让我们退缩。 这将是一个正则表达式，将非常容易以简单的代码复制，为此，我们不需要使用regex包。 让我们看看是否可以仅使用标准的Rust库来为此编写自己的解析器。
回忆一下元素名称标识符的规则，它看起来像这样：一个字母字符，后跟零个或多个任何字母符号，
字符，数字或破折号。
fn identifier(input: &str) -> Result<(&str, String), &str> { let mut matched = String::new(); let mut chars = input.chars(); match chars.next() { Some(next) if next.is_alphabetic() => matched.push(next), _ => return Err(input), } while let Some(next) = chars.next() { if next.is_alphanumeric() || next == '-' { matched.push(next); } else { break; } } let next_index = matched.len(); Ok((&input[next_index..], matched)) }
和往常一样，我们首先看一下类型。 这次，我们没有编写用于创建解析器的函数，只是第一次编写了解析器本身。 这里值得注意的区别是，除了返回结果类型()我们在元组中返回一个String以及其余的输入。 该String将包含我们刚刚解析的标识符。
考虑到这一点，我们首先创建一个空String并将其命名为matched 。 这将是我们的结果。 我们还将为input的字符获得一个迭代器，我们将开始拆分。
第一步是查看开头是否有符号。 我们从迭代器中提取第一个字符，并检查它是否为字母： next.is_alphabetic() 。 当然，标准的Rust库将帮助我们使用Unicode-它对应于任何字母的字母，而不仅仅是ASCII。 如果是字母，则将其放在matched变量的字符串中；如果不是字母，则不查看该元素的标识符，并立即返回错误。
在第二步中，我们继续从迭代器中提取字符，将其发送到我们创建的行，直到is_alphanumeric()不满足is_alphanumeric()函数is_alphanumeric()字符（它与is_alphabetic()类似，但它还包括任何字母的数字）或破折号'-' 。
当我们初次看到不符合这些条件的内容时，便完成了解析，中断了循环并返回了String ，切记要从input剪切我们使用的片段。 同样，如果字符以迭代器结尾，则意味着我们已经到达输入的结尾。
值得注意的是，当我们看到的不是字母数字或破折号时，我们不会返回错误。 匹配第一个字母后，我们已经足够创建一个有效的标识符，并且很正常的情况是，解析我们的标识符后，输入行中会包含更多元素以供分析，因此我们只需停止解析并返回结果即可。 只有在连第一个字母都找不到的情况下，我们实际上会返回错误，因为在这种情况下，肯定没有标识符。
请记住， Element结构就是我们将XML文档解析为的结构。
struct Element { name: String, attributes: Vec<(String, String)>, children: Vec<Element>, }
实际上，我们刚刚完成了第一部分的分析器，即name字段。 我们的解析器返回String直接进入那里。 对于每个attribute的第一部分，它也是正确的解析器。
让我们来看看。
#[test] fn identifier_parser() { assert_eq!( Ok(("", "i-am-an-identifier".to_string())), identifier("i-am-an-identifier") ); assert_eq!( Ok((" entirely an identifier", "not".to_string())), identifier("not entirely an identifier") ); assert_eq!( Err("!not at all an identifier"), identifier("!not at all an identifier") ); }
我们看到在第一种情况下，字符串"i-am-an-identifier"完全解析，仅留下一个空字符串。 在第二种情况下，解析器返回"not"作为标识符，而字符串的其余部分作为剩余输入返回。 在第三种情况下，解析器立即失败，因为它找到的第一个字符不是字母。
组合器
现在我们可以解析开始字符< ，我们可以解析下一个标识符，但是我们需要解析两者 。 因此，下一步是编写另一个组合解析器函数，但是该函数将两个解析器作为输入并返回一个新的解析器 ，按顺序解析这两个解析器 。 换句话说，解析器组合器是因为它将两个解析器组合成一个新的解析器。 让我们看看是否可以做到这一点。
fn pair<P1, P2, R1, R2>(parser1: P1, parser2: P2) -> impl Fn(&str) -> Result<(&str, (R1, R2)), &str> where P1: Fn(&str) -> Result<(&str, R1), &str>, P2: Fn(&str) -> Result<(&str, R2), &str>, { move |input| match parser1(input) { Ok((next_input, result1)) => match parser2(next_input) { Ok((final_input, result2)) => Ok((final_input, (result1, result2))), Err(err) => Err(err), }, Err(err) => Err(err), } }
这里有点棘手，但是您知道该怎么做：从查看类型开始。
首先，我们有四种类型的变量： P1 ， P2 ， R1和R2 。 它们是Parser 1 ， Parser 2 ， Result 1和Result 2 。 P1和P2是函数，您会注意到它们遵循解析器函数的完善模式：就像返回值一样，它们以&str作为输入，并返回Result一对剩余的输入和结果，否则返回错误。
但是，请看一下每个函数的结果类型： P1是成功时给出R1的解析器， P2也给出R2 。 从我们的函数返回的最后一个解析器的结果是(R1, R2) 。 因此，此解析器的任务是首先在输入端启动分析器P1 ，保存其结果，然后在返回P1的输入端启动P2 ，如果两个都起作用，我们将两个结果合并为一个元组(R1, R2)
代码显示这正是他所做的。 我们从在输入端启动第一个分析器开始，然后是第二个分析器，然后将两个结果合并为一个元组并返回它。 如果这些解析器中的任何一个失败，我们将立即返回其发出的错误。
因此，我们必须能够组合我们的两个解析器match_literal和identifier ，以便实际match_literal我们的第一个XML标签match_literal第一个片段。 让我们编写一个测试，看看它是否有效。
#[test] fn pair_combinator() { let tag_opener = pair(match_literal("<"), identifier); assert_eq!( Ok(("/>", ((), "my-first-element".to_string()))), tag_opener("<my-first-element/>") ); assert_eq!(Err("oops"), tag_opener("oops")); assert_eq!(Err("!oops"), tag_opener("<!oops")); }
似乎可以工作！ 但是看看这种类型的结果： ((), String) 。 显然，我们只对正确的值String感兴趣。 这将经常发生-我们的某些解析器仅匹配输入中的模式而不会产生值，因此可以安全地忽略它们的输出。 为了适应这种模式，我们将使用pair组合器编写另外两个组合器： left ，它丢弃第一个解析器的结果，仅返回第二个解析器，而相反的是right 。 我们在上面的测试中使用了解析器，该解析器丢弃了左侧的部分，仅保存了String ，而不是pair 。
函子介绍
但是在深入之前，让我们介绍另一个组合器，它将大大简化这两个编写器： map 。
该组合器有一项任务：更改结果的类型。 , , , ((), String) , String .
, , . : |(_left, right)| right . , Fn(A) -> B A — , B — .
fn map<P, F, A, B>(parser: P, map_fn: F) -> impl Fn(&str) -> Result<(&str, B), &str> where P: Fn(&str) -> Result<(&str, A), &str>, F: Fn(A) -> B, { move |input| match parser(input) { Ok((next_input, result)) => Ok((next_input, map_fn(result))), Err(err) => Err(err), } }
? P — . A . F — , P , , P , — B A
parser(input) , , result map_fn(result) , A B , .
, , map , Result :
fn map<P, F, A, B>(parser: P, map_fn: F) -> impl Fn(&str) -> Result<(&str, B), &str> where P: Fn(&str) -> Result<(&str, A), &str>, F: Fn(A) -> B, { move |input| parser(input) .map(|(next_input, result)| (next_input, map_fn(result))) }
— , «» Haskell , . A , map , A B , B , . Rust, Option , Result , Iterator Future , . : - Rust, , , , , map .
, , : Fn(&str) -> Result<(&str, Output), &str> . , , , , , , , .
, :
type ParseResult<'a, Output> = Result<(&'a str, Output), &'a str>;
, , , ParseResult<String> . , , Rust . , rustc , , .
'a , , .
. , , . , .
trait Parser<'a, Output> { fn parse(&self, input: &'a str) -> ParseResult<'a, Output>; }
: parse() , : , , .
, , :
impl<'a, F, Output> Parser<'a, Output> for F where F: Fn(&'a str) -> ParseResult<Output>, { fn parse(&self, input: &'a str) -> ParseResult<'a, Output> { self(input) } }
, , , Parser , .
, , . map , .
fn map<'a, P, F, A, B>(parser: P, map_fn: F) -> impl Parser<'a, B> where P: Parser<'a, A>, F: Fn(A) -> B, { move |input| parser.parse(input) .map(|(next_input, result)| (next_input, map_fn(result))) }
: , parser.parse(input) , , P , , Parser , , Parser . , . 'a' , , .
pair , :
fn pair<'a, P1, P2, R1, R2>(parser1: P1, parser2: P2) -> impl Parser<'a, (R1, R2)> where P1: Parser<'a, R1>, P2: Parser<'a, R2>, { move |input| match parser1.parse(input) { Ok((next_input, result1)) => match parser2.parse(next_input) { Ok((final_input, result2)) => Ok((final_input, (result1, result2))), Err(err) => Err(err), }, Err(err) => Err(err), } }
: parser.parse(input) parser(input) .
, pair , map .
fn pair<'a, P1, P2, R1, R2>(parser1: P1, parser2: P2) -> impl Parser<'a, (R1, R2)> where P1: Parser<'a, R1>, P2: Parser<'a, R2>, { move |input| { parser1.parse(input).and_then(|(next_input, result1)| { parser2.parse(next_input) .map(|(last_input, result2)| (last_input, (result1, result2))) }) } }
and_then Result map , , Result , Result . match . and_then , , map , left right .
Left Right
pair map , left right :
fn left<'a, P1, P2, R1, R2>(parser1: P1, parser2: P2) -> impl Parser<'a, R1> where P1: Parser<'a, R1>, P2: Parser<'a, R2>, { map(pair(parser1, parser2), |(left, _right)| left) } fn right<'a, P1, P2, R1, R2>(parser1: P1, parser2: P2) -> impl Parser<'a, R2> where P1: Parser<'a, R1>, P2: Parser<'a, R2>, { map(pair(parser1, parser2), |(_left, right)| right) }
pair , , map , .
, , .
, Parser ParseResult . match_literal :
fn match_literal<'a>(expected: &'static str) -> impl Parser<'a, ()> { move |input: &'a str| match input.get(0..expected.len()) { Some(next) if next == expected => Ok((&input[expected.len()..], ())), _ => Err(input), } }
, , — &'a str , rustc .
identifier , , , :
fn identifier(input: &str) -> ParseResult<String> {
. () . .
#[test] fn right_combinator() { let tag_opener = right(match_literal("<"), identifier); assert_eq!( Ok(("/>", "my-first-element".to_string())), tag_opener.parse("<my-first-element/>") ); assert_eq!(Err("oops"), tag_opener.parse("oops")); assert_eq!(Err("!oops"), tag_opener.parse("<!oops")); }
. < . ? .
, , . , .
, , - , : .
( ) . .
— , <element attribute="value"/> , . , , .
identifier , . , .
fn one_or_more<'a, P, A>(parser: P) -> impl Parser<'a, Vec<A>> where P: Parser<'a, A>, { move |mut input| { let mut result = Vec::new(); if let Ok((next_input, first_item)) = parser.parse(input) { input = next_input; result.push(first_item); } else { return Err(input); } while let Ok((next_input, next_item)) = parser.parse(input) { input = next_input; result.push(next_item); } Ok((input, result)) } }
, , , A , Vec<A> — A .
identifier . , , . , , .
, : ? :
fn zero_or_more<'a, P, A>(parser: P) -> impl Parser<'a, Vec<A>> where P: Parser<'a, A>, { move |mut input| { let mut result = Vec::new(); while let Ok((next_input, next_item)) = parser.parse(input) { input = next_input; result.push(next_item); } Ok((input, result)) } }
, , .
#[test] fn one_or_more_combinator() { let parser = one_or_more(match_literal("ha")); assert_eq!(Ok(("", vec![(), (), ()])), parser.parse("hahaha")); assert_eq!(Err("ahah"), parser.parse("ahah")); assert_eq!(Err(""), parser.parse("")); } #[test] fn zero_or_more_combinator() { let parser = zero_or_more(match_literal("ha")); assert_eq!(Ok(("", vec![(), (), ()])), parser.parse("hahaha")); assert_eq!(Ok(("ahah", vec![])), parser.parse("ahah")); assert_eq!(Ok(("", vec![])), parser.parse("")); }
: one_or_more , , zero_or_more , .
, , . one_or_more zero_or_more , - :
fn one_or_more<'a, P, A>(parser: P) -> impl Parser<'a, Vec<A>> where P: Parser<'a, A>, { map(pair(parser, zero_or_more(parser)), |(head, mut tail)| { tail.insert(0, head); tail }) }
Rust, cons Vec , , Lisp, , . , : .
, : , . : ( ). , , Clone , , , .
. , one_or_more , , , , , - , , RangeBound : range(0..) zero_or_more , range(1..) one_or_more , range(5..=6) , .
. zero_or_more one_or_more .
, — , Rc ?
, one_or_more zero_or_more .
, . , . , , , > /> . , . , , , , .
. .
-. match_literal , . ? - , Unicode, . Rust, , char is_whitespace , is_alphabetic is_alphanumeric .
-. , , is_whitespace , identifier .
-. , . any_char , char , , pred , , : pred(any_char, |c| c.is_whitespace()) . , , : .
any_char , , UTF-8.
fn any_char(input: &str) -> ParseResult<char> { match input.chars().next() { Some(next) => Ok((&input[next.len_utf8()..], next)), _ => Err(input), } }
pred , , . , . , true , . , .
fn pred<'a, P, A, F>(parser: P, predicate: F) -> impl Parser<'a, A> where P: Parser<'a, A>, F: Fn(&A) -> bool, { move |input| { if let Ok((next_input, value)) = parser.parse(input) { if predicate(&value) { return Ok((next_input, value)); } } Err(input) } }
, , :
#[test] fn predicate_combinator() { let parser = pred(any_char, |c| *c == 'o'); assert_eq!(Ok(("mg", 'o')), parser.parse("omg")); assert_eq!(Err("lol"), parser.parse("lol")); }
, whitespace_char :
fn whitespace_char<'a>() -> impl Parser<'a, char> { pred(any_char, |c| c.is_whitespace()) }
, whitespace_char , , , , , . space1 space0 .
fn space1<'a>() -> impl Parser<'a, Vec<char>> { one_or_more(whitespace_char()) } fn space0<'a>() -> impl Parser<'a, Vec<char>> { zero_or_more(whitespace_char()) }
? , , . identifier ( , any_char pred *_or_more ). match_literal("=") = . , . , , .
fn quoted_string<'a>() -> impl Parser<'a, String> { map( right( match_literal("\""), left( zero_or_more(pred(any_char, |c| *c != '"')), match_literal("\""), ), ), |chars| chars.into_iter().collect(), ) }
, , , , .
map - , , , , , : . map right , right — , : match_literal("\"") . .
right — . left , , left , , , match_literal("\"") — . , — .
pred any_char , , , zero_or_more , :
right left .
, . , zero_or_more ? Vec<A> A . any_char char . , , Vec<char> . map : , Vec<char> String , , String Iterator<Item = char> , vec_of_chars.into_iter().collect() , String .
, , , , , , , , .
#[test] fn quoted_string_parser() { assert_eq!( Ok(("", "Hello Joe!".to_string())), quoted_string().parse("\"Hello Joe!\"") ); }
, , , , .
,
, , = . , .
. , Vec<(String, String)> , (String, String) , zero_or_more . , .
fn attribute_pair<'a>() -> impl Parser<'a, (String, String)> { pair(identifier, right(match_literal("="), quoted_string())) }
! : pair , identifier , String , right = , , quoted_string , String .
zero_or_more , , .
fn attributes<'a>() -> impl Parser<'a, Vec<(String, String)>> { zero_or_more(right(space1(), attribute_pair())) }
: ,
. right .
.
#[test] fn attribute_parser() { assert_eq!( Ok(( "", vec![ ("one".to_string(), "1".to_string()), ("two".to_string(), "2".to_string()) ] )), attributes().parse(" one=\"1\" two=\"2\"") ); }
! !
, , rustc , , . , . , rustc, , , #![type_length_limit = "…some big number…"] , . , #![type_length_limit = "16777216"] , . , !
, , , , NP-. element: , , , zero_or_more , ?
, , . , , , : < , . , (String, Vec<(String, String)>) .
fn element_start<'a>() -> impl Parser<'a, (String, Vec<(String, String)>)> { right(match_literal("<"), pair(identifier, attributes())) }
, , .
fn single_element<'a>() -> impl Parser<'a, Element> { map( left(element_start(), match_literal("/>")), |(name, attributes)| Element { name, attributes, children: vec![], }, ) }
, , — Element !
.
#[test] fn single_element_parser() { assert_eq!( Ok(( "", Element { name: "div".to_string(), attributes: vec![("class".to_string(), "float".to_string())], children: vec![] } )), single_element().parse("<div class=\"float\"/>") ); }
… , .
single_element , , , . , , , — , — .
, , ...
- Rust, , , .
. , :
enum List<A> { Cons(A, List<A>), Nil, }
rustc , List<A> , List::<A>::Cons List<A> , . rustc, , , .
, Rust. , Rust, , , , . , .
, . , List::Cons A A , A A . , , , , List::Cons , . , Rust — Box .
enum List<A> { Cons(A, Box<List<A>>), Nil, }
Box , . , , Box<dyn Parser<'a, A>> .
. ? , - , , . : . . , , SIMD ( ).
, Parser Box , .
struct BoxedParser<'a, Output> { parser: Box<dyn Parser<'a, Output> + 'a>, } impl<'a, Output> BoxedParser<'a, Output> { fn new<P>(parser: P) -> Self where P: Parser<'a, Output> + 'a, { BoxedParser { parser: Box::new(parser), } } } impl<'a, Output> Parser<'a, Output> for BoxedParser<'a, Output> { fn parse(&self, input: &'a str) -> ParseResult<'a, Output> { self.parser.parse(input) } }
, , BoxedParser box . BoxedParser ( BoxedParser , ), BoxedParser::new(parser) , , Box . , Parser , .
Box , BoxedParser Parser , . , , , , , , , , . .
, , , .
, ? , , . quoted_string :
fn quoted_string<'a>() -> impl Parser<'a, String> { map( right( match_literal("\""), left( zero_or_more(pred(any_char, |c| *c != '"')), match_literal("\""), ), ), |chars| chars.into_iter().collect(), ) }
, . Parser ?
, , impl Trait , impl Trait .
… BoxedParser . , impl Parser<'a, A> , , BoxedParser<'a, A> .
, , , Parser .
map , Parser :
trait Parser<'a, Output> { fn parse(&self, input: &'a str) -> ParseResult<'a, Output>; fn map<F, NewOutput>(self, map_fn: F) -> BoxedParser<'a, NewOutput> where Self: Sized + 'a, Output: 'a, NewOutput: 'a, F: Fn(Output) -> NewOutput + 'a, { BoxedParser::new(map(self, map_fn)) } }
'a , , . , — , , impl Trait .
quoted_string :
fn quoted_string<'a>() -> impl Parser<'a, String> { right( match_literal("\""), left( zero_or_more(pred(any_char, |c| *c != '"')), match_literal("\""), ), ) .map(|chars| chars.into_iter().collect()) }
, , .map() right() .
pair , left right , , , , pair . , , map , .
— pred . Parser :
fn pred<F>(self, pred_fn: F) -> BoxedParser<'a, Output> where Self: Sized + 'a, Output: 'a, F: Fn(&Output) -> bool + 'a, { BoxedParser::new(pred(self, pred_fn)) }
quoted_string pred , :
zero_or_more(any_char.pred(|c| *c != '"')),
, , , zero_or_more — « any_char », . , zero_or_more one_or_more .
quoted_string , map single_element :
fn single_element<'a>() -> impl Parser<'a, Element> { left(element_start(), match_literal("/>")).map(|(name, attributes)| Element { name, attributes, children: vec![], }) }
element_start , , , . ...
… , . , .
map pred Box — !
. single_element , , > , /> . , , .
fn open_element<'a>() -> impl Parser<'a, Element> { left(element_start(), match_literal(">")).map(|(name, attributes)| Element { name, attributes, children: vec![], }) }
, ? , , , zero_or_more , ? , , — : , , .
, , : , , . , , , . , , , , , , .
fn either<'a, P1, P2, A>(parser1: P1, parser2: P2) -> impl Parser<'a, A> where P1: Parser<'a, A>, P2: Parser<'a, A>, { move |input| match parser1.parse(input) { ok @ Ok(_) => ok, Err(_) => parser2.parse(input), } }
element , , ( open_element , element ).
fn element<'a>() -> impl Parser<'a, Element> { either(single_element(), open_element()) }
. , , , . , ?
fn close_element<'a>(expected_name: String) -> impl Parser<'a, String> { right(match_literal("</"), left(identifier, match_literal(">"))) .pred(move |name| name == &expected_name) }
pred , ?
, :
fn parent_element<'a>() -> impl Parser<'a, Element> { pair( open_element(), left(zero_or_more(element()), close_element(…oops)), ) }
close_element ? , .
. , parent_element , open_element element parent_element , , XML.
, , and_then ? , . and_then : -, , , , . pair , , , , . , and_then Result Option , , , Result Option , , ( , )).
, .
fn and_then<'a, P, F, A, B, NextP>(parser: P, f: F) -> impl Parser<'a, B> where P: Parser<'a, A>, NextP: Parser<'a, B>, F: Fn(A) -> NextP, { move |input| match parser.parse(input) { Ok((next_input, result)) => f(result).parse(next_input), Err(err) => Err(err), } }
, , P , , A . F , map A B , , and_then A NextP , B . — B , , , NextP .
: , , , , f ( A ), , f(result) , B . . , , , B
: P , , f P , NextP , , .
Parser , map , .
fn and_then<F, NextParser, NewOutput>(self, f: F) -> BoxedParser<'a, NewOutput> where Self: Sized + 'a, Output: 'a, NewOutput: 'a, NextParser: Parser<'a, NewOutput> + 'a, F: Fn(Output) -> NextParser + 'a, { BoxedParser::new(and_then(self, f)) }
, , ?
, pair :
fn pair<'a, P1, P2, R1, R2>(parser1: P1, parser2: P2) -> impl Parser<'a, (R1, R2)> where P1: Parser<'a, R1> + 'a, P2: Parser<'a, R2> + 'a, R1: 'a + Clone, R2: 'a, { parser1.and_then(move |result1| parser2.map(move |result2| (result1.clone(), result2))) }
, : parser2.map() parser2 , Fn , FnOnce , parser2 , . , Rust. , , pair .
, Rust, close_element , , .
:
fn parent_element<'a>() -> impl Parser<'a, Element> { pair( open_element(), left(zero_or_more(element()), close_element(…oops)), ) }
, and_then , close_element .
fn parent_element<'a>() -> impl Parser<'a, Element> { open_element().and_then(|el| { left(zero_or_more(element()), close_element(el.name.clone())).map(move |children| { let mut el = el.clone(); el.children = children; el }) }) }
, and_then open_element() , , close_element . , open_element and_then . , Element open_element , , , .
, map , Element ( el ) . clone() , Fn . ( Vec<Element> ) Element , .
, , element , open_element parent_element , , , , !
"" ?
, , map «» Haskell?
and_then — , Rust, , map . flat_map Iterator , , .
— "". Thing<A> , and_then , A Thing<B> , Thing<B> — .
, , Option<A> , , Some(A) None , , Some(A) , Some(B)
. , Future<A> , and_then Future<B> , Future<B> Future<A> , Future<A> . Future<A> , — 1 , Future<B> . , Future , and_then , Future , . , Future , .
, Rust , , , , , , , . .
, Redux
.
, XML, . , ( , , < div / > , ).
.
fn whitespace_wrap<'a, P, A>(parser: P) -> impl Parser<'a, A> where P: Parser<'a, A>, { right(space0(), left(parser, space0())) }
element , element , , , .
fn element<'a>() -> impl Parser<'a, Element> { whitespace_wrap(either(single_element(), parent_element())) }
!
, ! , .
#[test] fn xml_parser() { let doc = r#" <top label="Top"> <semi-bottom label="Bottom"/> <middle> <bottom label="Another bottom"/> </middle> </top>"#; let parsed_doc = Element { name: "top".to_string(), attributes: vec![("label".to_string(), "Top".to_string())], children: vec![ Element { name: "semi-bottom".to_string(), attributes: vec![("label".to_string(), "Bottom".to_string())], children: vec![], }, Element { name: "middle".to_string(), attributes: vec![], children: vec![Element { name: "bottom".to_string(), attributes: vec![("label".to_string(), "Another bottom".to_string())], children: vec![], }], }, ], }; assert_eq!(Ok(("", parsed_doc)), element().parse(doc)); }
, - , , :
#[test] fn mismatched_closing_tag() { let doc = r#" <top> <bottom/> </middle>"#; assert_eq!(Err("</middle>"), element().parse(doc)); }
, . , , , , . , , , , . , , , , , .
: , ! , , , 2 .
, , . !
, , Rust , , - , , , .
, pom , , .
Rust nom , pom ( , ), , .
Rust combine , .
Haskell Parsec .
, « Haskell» , , Haskell.
Bodil Stokke Creative Commons Attribution-NonCommercial-ShareAlike 4.0. , http://creativecommons.org/licenses/by-nc-sa/4.0/ .
1: .
2: , .
andreevlex funkill