用自定义BNF规则解析bnf语法

Question

假设我有BNF语法，如下所示。现在，一个“列表”将对应于“\”符号之前的所有术语。然而，我想把每一个“列表”的最后一个数字作为“列表”的一个属性来阅读。

<code> ::= <code> <line> 12 2 | <line> 24 4 
<line> ::= <ifte> 13 23 | <loop> 24 34 | <action> 15 3 
<ifte> ::= if <cond> {<code>} else {<code>} 12

此外，最后一个数字(List属性)可以是可选的；为了使这更容易，我想我可能不得不使用一些符号来括住数字，以便更容易地解析，例如<<23>>。

来自代码的这里编译，但它不解析上面的语法：

//#define BOOST_SPIRIT_DEBUG
#include <boost/spirit/include/qi.hpp>
#include <boost/fusion/adapted.hpp>
/*#include <fmt/ranges.h>
#include <fmt/ostream.h>*/
#include <iomanip>

namespace AST {

    struct Name : std::string {
        using std::string::string;
        using std::string::operator=;

        friend std::ostream &operator<<(std::ostream &os, Name const &n) {
            return os << '<' << n.c_str() << '>';
        }
    };

    using Term = boost::variant<Name, std::string>;

    struct List {
        std::vector<Term> terms;
        int number;
    };

    using Expression = std::vector<List>;

    struct Rule {
        Name name; //rhs
        Expression rhs;
    };

    using Syntax = std::vector<Rule>;
}
BOOST_FUSION_ADAPT_STRUCT(AST::List, terms, number)
BOOST_FUSION_ADAPT_STRUCT(AST::Rule, name, rhs)

namespace Parser {

    namespace qi = boost::spirit::qi;
    template<typename Iterator>
    class BNF : public qi::grammar<Iterator, AST::Syntax()> {
    public:
        BNF() : BNF::base_type(start) {
            start       = qi::skip(blank)[rule % +qi::eol];
            _rule_name  = qi::hold[qi::char_('<') >> (qi::alpha >> *(qi::alnum | qi::char_('-'))) >> qi::char_('>')];
            _list       = +term >> qi::uint_;
            term        = _literal | _rule_name;
            _literal    = qi::hold['"' >> *(character - '"') >> '"']
                        | qi::hold["'" >> *(character - "'") >> "'"]
                        | qi::hold[+(qi::graph - qi::char_("<|>") - "::=")];
            character   = qi::alnum | qi::char_("\"'| !#$%&()*+,./:;>=<?@]\\^_`{}~[-");
            _expression = _list % '|';

            rule = _rule_name >> "::=" >> _expression;

            BOOST_SPIRIT_DEBUG_NODES((rule)(_expression)(_list)(term)(_literal)(
                character)(_rule_name))
        }

    private:
        qi::rule<Iterator> blank;
        qi::rule<Iterator, AST::Syntax()>     start;
        qi::rule<Iterator, AST::Rule(),       qi::rule<Iterator>> rule;
        qi::rule<Iterator, AST::Expression(), qi::rule<Iterator>> _expression;
        qi::rule<Iterator, AST::List(),       qi::rule<Iterator>> _list;
        qi::rule<Iterator, AST::Term()>       term;
        qi::rule<Iterator, AST::Name()>       _rule_name;
        qi::rule<Iterator, std::string()>     _literal;
        qi::rule<Iterator, char()>            character;
    };
}

int main() {
    Parser::BNF<std::string::const_iterator> const  parser;
}

如何修复/修改上面的代码链接以满足我的需要。

Answer 1

我想还不清楚你想支持什么输入语法。

例如，

1. 当list属性可以是可选的时，这是否意味着它不是<code> <line> 12 2，而是一个没有属性：<code> <line> 12 2的有效列表？如何避免将12解析为属性？
2. 您的输入使用{}中的名称--您所显示的解析器实现不支持这些名称。你需要支持吗？多么?

让我们把它们都说出来

广告2:修改您的输入

让我们假设您真的不希望{}具有魔法意义，而是希望它们在语法中成为文字。就像“如果”和“其他”一样，它们需要是文字，所以：

<ifte> ::= 'if' <cond> '{' <code> '}' 'else' '{' <code> '}' 23

或

<ifte> ::= "if" <cond> "{" <code> "}" "else" "{" <code> "}" 23

修复您的示例：在编译器资源管理器上直播

code ::= <code><line> 34 | <line> 34
line ::= <ifte> 23 | <loop> 34 | <action> 23
ifte ::= if<cond>{<code>}else{<code>} 23
Remaining: "
"

ad 1.：可选属性

让我们表达一下我们的意图：

using ListAttribute = int;

struct List {
    std::list<Term> terms;
    ListAttribute attribute;
};

然后在语法中添加一个词汇规则(没有船长)：

qi::rule<Iterator, Ast::ListAttribute()> _attribute;

然后我们实施如下：

_attribute  = lexeme [ "<<" >> qi::uint_ >> ">>" ] 
            | qi::attr(0);
_list       = +_term >> _attribute;

现在，它将只将<>识别为列表属性：

在编译器资源管理器上直播

std::string const input =
    "<code> ::= <code> <line> | <line>\n"
    "<line> ::= <ifte> | <loop> | <action>\n"
    "<ifte> ::= 'if' <cond> '{' <code> '}' 'else' '{' <code> '}'\n"

    "<code> ::= <code> <line> <<34>> | <line> <<34>>\n"
    "<line> ::= <ifte> <<23>> | <loop> <<34>> | <action> <<23>>\n"
    "<ifte> ::= 'if' <cond> '{' <code> '}' 'else' '{' <code> '}' <<23>>\n"

    // and the disambiguated example from the question
    "<code> ::= <code> <line> '34' | <line> '12' <<2>>\n"
;

打印

code ::= <code><line> 0 | <line> 0
line ::= <ifte> 0 | <loop> 0 | <action> 0
ifte ::= if<cond>{<code>}else{<code>} 0
code ::= <code><line> 34 | <line> 34
line ::= <ifte> 23 | <loop> 34 | <action> 23
ifte ::= if<cond>{<code>}else{<code>} 23
code ::= <code><line>34 0 | <line>12 2
Remaining: "
"

汇总/奖金

我刚刚意识到，您不需要在12 2和12 (缺失属性)之间消除歧义，因为12无论如何都不是一个有效的输入令牌(文字/名称以<"'之一开头)，因此如下所示：

在编译器资源管理器上直播

//#define BOOST_SPIRIT_DEBUG
#include <boost/spirit/include/qi.hpp>
#include <boost/fusion/adapted.hpp>
#include <fmt/ranges.h>
#include <fmt/ostream.h>
#include <iomanip>
namespace qi = boost::spirit::qi;

namespace Ast {
    struct Name : std::string {
        using std::string::string;
        using std::string::operator=;

        friend std::ostream& operator<<(std::ostream& os, Name const& n) {
            return os << '<' << n.c_str() << '>';
        }
    };

    using Term = boost::variant<Name, std::string>;

    using ListAttribute = int;

    struct List {
        std::list<Term> terms;
        ListAttribute attribute;

        friend std::ostream& operator<<(std::ostream& os, List const& l) {
            for (auto& t : l.terms)
                os << t;
            return os << " " << l.attribute;
        }
    };

    using Expression = std::list<List>;

    struct Rule {
        Name name; // lhs
        Expression rhs;
    };

    using Syntax = std::list<Rule>;
}

BOOST_FUSION_ADAPT_STRUCT(Ast::List, terms, attribute)
BOOST_FUSION_ADAPT_STRUCT(Ast::Rule, name, rhs)

namespace Parser {
    template <typename Iterator>
    struct BNF: qi::grammar<Iterator, Ast::Syntax()> {
        BNF(): BNF::base_type(start) {
            using namespace qi;
            start = skip(blank) [ _rule % +eol ];

            _rule       = _rule_name >> "::=" >> _expression;
            _expression = _list % '|';
            _attribute  = uint_ | qi::attr(0);
            _list       = +_term >> _attribute;
            _term       = _literal | _rule_name ;
            _literal    = '"' >> *(_character - '"') >> '"'
                        | "'" >> *(_character - "'") >> "'";
            _character  = alnum | char_("\"'| !#$%&()*+,./:;>=<?@]\\^_`{}~[-");
            _rule_name  = '<' >> (alpha >> *(alnum | char_('-'))) >> '>';

            BOOST_SPIRIT_DEBUG_NODES(
                (_rule)(_expression)(_list)(_attribute)(_term)
                (_literal)(_character)
                (_rule_name))
        }

      private:
        qi::rule<Iterator, Ast::Syntax()>     start;
        qi::rule<Iterator, Ast::Rule(),       qi::blank_type> _rule;
        qi::rule<Iterator, Ast::Expression(), qi::blank_type> _expression;
        qi::rule<Iterator, Ast::List(),       qi::blank_type> _list;
        // lexemes
        qi::rule<Iterator, Ast::ListAttribute()> _attribute;
        qi::rule<Iterator, Ast::Term()>          _term;
        qi::rule<Iterator, Ast::Name()>          _rule_name;
        qi::rule<Iterator, std::string()>        _literal;
        qi::rule<Iterator, char()>               _character;
    };
}

int main() {
    Parser::BNF<std::string::const_iterator> const parser;

    std::string const input =
        "<code> ::= <code> <line> | <line>\n"
        "<line> ::= <ifte> | <loop> | <action>\n"
        "<ifte> ::= 'if' <cond> '{' <code> '}' 'else' '{' <code> '}'\n"

        "<code> ::= <code> <line> 34 | <line> 34\n"
        "<line> ::= <ifte> 23 | <loop> 34 | <action> 23\n"
        "<ifte> ::= 'if' <cond> '{' <code> '}' 'else' '{' <code> '}' 23\n"

        // and the disambiguated example from the question
        "<code> ::= <code> <line> '34' | <line> '12' 2\n"
    ;

    auto it = input.begin(), itEnd = input.end();

    Ast::Syntax syntax;
    if (parse(it, itEnd, parser, syntax)) {
        for (auto& rule : syntax)
            fmt::print("{} ::= {}\n", rule.name, fmt::join(rule.rhs, " | "));
    } else {
        std::cout << "Failed\n";
    }

    if (it != itEnd)
        std::cout << "Remaining: " << std::quoted(std::string(it, itEnd)) << "\n";
}

打印

code ::= <code><line> 0 | <line> 0
line ::= <ifte> 0 | <loop> 0 | <action> 0
ifte ::= if<cond>{<code>}else{<code>} 0
code ::= <code><line> 34 | <line> 34
line ::= <ifte> 23 | <loop> 34 | <action> 23
ifte ::= if<cond>{<code>}else{<code>} 23
code ::= <code><line>34 0 | <line>12 2
Remaining: "
"