1

我想解析一个由这个 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"));
}

此代码输出 parse 的结果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 正确解析该程序？

4

1 回答 1

2

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

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

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

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

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

这里有一个带有 nom 的这种方法的简单示例

于 2021-06-16T03:18:12.177 回答