c++ - 如何在 C++ 中为 Backus Naur Form 创建规则？-

Question

我是 BNF 的新手，我真的不知道/不明白如何制定规则以及如何在 C++ 上检查它。我看到了一些示例，但没有解释它是如何工作的以及规则如何检查输入；

例如我们的老师给我们的课举了这个例子，

<palindrome>::=<empty>|a|b|a<palindrome>a|b<palindrome>b

sample input: abba

how it checks:
<empty>

a<palindrome>a

ab<palindrome>a
abba

谢谢。

Answer 1

您可以试试 Boost.Spirit X3。为此你必须稍微重写你的规则，因为 Boost.Spirit 一旦找到匹配的东西就会停止解析，即在字符串 abba 中它会匹配 a 和停止。

#include <iostream>
#include <string>

#include <boost/spirit/home/x3.hpp>

namespace x3 = boost::spirit::x3;

auto const a = x3::char_('a');
auto const b = x3::char_('b');
auto const aa = x3::lit("aa");
auto const bb = x3::lit("bb");

x3::rule<class palindrome> const palindrome = "palindrome";
auto const palindrome_def
    = a >> palindrome >> a
    | b >> palindrome >> b
    | aa
    | bb
    | a
    | b;

BOOST_SPIRIT_DEFINE(palindrome);

int main() {
    std::string input = "abba";
    auto first = input.begin();
    auto last = input.end();

    bool r = parse(first, last, palindrome);

    if (!r || first != last) {
        std::cerr << "Parsing failed at " << std::string{first,last} << '\n';
        return 1;
    }
    std::cout << "Success :)\n";
}

Live on Wandbox