如何使用 Rust 的解析器库 nom 正确解析这个程序

Question

我想解析一个由这个 BNF 表示的程序：

<log_and_expression> := <and_expression> (<space>* "&&" <space>* <and_expression>)*
<and_expression>     := <unary_expression> (<space>* "&" <space>* <unary_expression>)*
<unary_expression>   := ("&" <space>*)* <identifier>
<identifier>         := "a" | "b" | "c" | ...
<space>              := " " | "\t" | "\n" | "\r"

这个BNF解析小程序。 log_and 表示逻辑与。

我使用解析器库 nom 编写了 Rust 程序：

use nom::{
    branch::{alt, permutation},
    bytes::complete::{escaped_transform, is_not, tag, take_while_m_n},
    character::complete::{
        char, digit1, hex_digit1, line_ending, multispace0, multispace1, none_of, space0, space1,
    },
    combinator::{all_consuming, map, opt, value},
    error::VerboseError,
    multi::{many0, many1},
    number::complete::double,
    sequence::{delimited, tuple},
    IResult,
};

#[derive(Debug, PartialEq, Clone)]
pub struct LogAndExpression {
    pub and_expression: AndExpression,
    pub tail: Vec<AndExpression>,
}
#[derive(Debug, PartialEq, Clone)]
pub struct AndExpression {
    pub unary_expression: UnaryExpression,
    pub tail: Vec<UnaryExpression>,
}
#[derive(Debug, PartialEq, Clone)]
pub struct UnaryExpression {
    pub unary_operators: Vec<String>,
    pub identifier: String,
}

pub fn log_and_expression(s: &str) -> IResult<&str, LogAndExpression> {
    map(
        tuple((
            and_expression,
            many0(
                map(
                    tuple((
                        multispace0,
                        tag("&&"),
                        multispace0,
                        and_expression,
                    )),
                    |(_, _, _, expression)| expression,
                )
            ),
        )),
        |(expression, vec)| LogAndExpression {
            and_expression: expression,
            tail: vec,
        },
    )(s)
}

pub fn and_expression(s: &str) -> IResult<&str, AndExpression> {
    map(
        tuple((
            unary_expression,
            many0(
                map(
                    tuple((
                        multispace0,
                        tag("&"),
                        multispace0,
                        unary_expression,
                    )),
                    |(_, _, _, expression)| expression,
                )
            ),
        )),
        |(expression, vec)| AndExpression {
            unary_expression: expression,
            tail: vec,
        },
    )(s)
}

pub fn unary_expression(s: &str) -> IResult<&str, UnaryExpression> {
    map(
        tuple((
            many0(
                map(
                    tuple((
                        tag("&"),
                        multispace0
                    )),
                    |(opr, _): (&str, &str)| opr.to_owned(),
                )
            ),
            is_not(" &"),
        )),
        |(unary_operators, identifier)| UnaryExpression {
            unary_operators: unary_operators,
            identifier: identifier.to_owned(),
        },
    )(s)
}

fn main() {
    println!("{:?}", log_and_expression("a && b"));
}

这段代码输出解析a && b的结果。 log_and_expression 解析程序。

我想要的结果是a LogAnd b。但结果是：

Ok(("", LogAndExpression { and_expression: AndExpression { unary_expression: UnaryExpression { unary_operators: [], identifier: "a" }, tail: [UnaryExpression { unary_operators: ["&"], identifier: "b" }] }, tail: [] }))

这意味着 a And &b。

如何使用 nom 正确解析这个程序？

Answer 1

列出的 BNF 规则不明确，因为没有简单的方法来区分正确的解析方法 a&&b。它可以被解析为 a && b 或 a & &b，并且由于后一个选项是 nom 解析器版本将尝试解析的第一件事，它将首先 return 该选项。

在 log_and_expression 函数中，解析器将调用 and_expression 函数，该函数将正确匹配后跟第一个 & 的 a 标识符，然后它将调用 unary_expression 函数来解析余数，在这种情况下可以将其正确解析为一元 & b 表达式，因为该规则明确允许 & 和 [=] 之间的 spaces 21=]。这给你你得到的输出（这不是你想要的）

解决此问题的一种方法是重写解析器，使其匹配最小的一元表达式，后跟 many0 或者 && 后跟另一个一元表达式，或者 & 后跟一元表达式。像

<expr> = <unary_expression> (<space>* <operator_pair> <space>*)*
<operator_pair> = ("&&" <space>* <unary_expression>) | ("&" <space>* <unary_expression>)

如果它首先尝试匹配 &&，那么这将是解析 a&&b 的首选方式，并且只有用 space 编写的替代形式才能被解析如 a& &b。这可能需要构建“运算符”和“一元表达式”对的列表，然后需要将其重新组合成您正在寻找的正确的树状格式。将此作为一个 2 阶段过程执行的优点是，当支持具有不同优先级的多个运算符时，您可以正确地应用操作顺序。

有一个关于这种方法的简单示例 here

如何使用 Rust 的解析器库 nom 正确解析这个程序

How can I parse this program correctly using Rust's parser library nom

rust

nom