使用 parsertl 和 lexertl 将 EBNF 转换为 BNF

引言

手动将 EBNF 转换为 BNF 并不困难，但经过几次迭代后很快就会变得繁琐。 肯定有更好的方法吧？ 事实证明，是的！

背景

今年我将 parsertl 调整到最佳状态后，我想尝试一些实际的语法。 由于我们在工作中将 IronPython 作为我们产品的一部分，这似乎是一个理想的候选者。 在网上查找，语法是 公开可用的，但它是用 EBNF 描述的。

使用代码

为了使用以下代码，您需要 parsertl 和 lexertl

http://www.benhanson.net/parsertl.html

http://www.benhanson.net/lexertl.html

#include <functional>
#include "../parsertl17/include/parsertl/generator.hpp"
#include "../lexertl17/include/lexertl/iterator.hpp"
#include <iostream>
#include "../parsertl17/include/parsertl/lookup.hpp"
#include "../lexertl17/include/lexertl/memory_file.hpp"

void read_ebnf(const char *start_, const char *end_str_)
{
    using token = parsertl::token<lexertl::citerator>;
    parsertl::rules grules_;
    lexertl::rules lrules_;
    lexertl::state_machine lsm_;

    struct tdata
    {
        parsertl::state_machine _sm;
        parsertl::match_results _results;
        token::token_vector _productions;
        std::string _lhs;
        std::stack<std::string> _rhs;
        std::map<std::string, std::size_t> _new_rule_ids;
        std::stack<std::pair<std::string, std::string>> _new_rules;
        std::map<std::pair<std::string, std::string>, std::string> _seen;
    } data_;

    std::map<std::size_t, void (*) (tdata &)> actions_map_;

    grules_.token("IDENTIFIER LHS TERMINAL");
    grules_.push("start", "grammar");
    grules_.push("grammar", "rule "
        "| grammar rule");
    actions_map_[grules_.push("rule", "lhs rhs_or opt_semi")] =
        [](tdata &data_)
    {
        assert(data_._rhs.empty() || data_._rhs.size() == 1);
        std::cout << data_._lhs << ": ";

        if (!data_._rhs.empty())
        {
            std::cout << data_._rhs.top();
            data_._rhs.pop();
        }

        std::cout << ";\n";

        while (!data_._new_rules.empty())
        {
            std::cout << data_._new_rules.top().first;
            std::cout << ": ";
            std::cout << data_._new_rules.top().second;
            std::cout << ";\n";
            data_._new_rules.pop();
        }
    };
    grules_.push("opt_semi", "%empty | ';'");
    actions_map_[grules_.push("lhs", "LHS")] =
        [](tdata &data_)
    {
        const token &token_ = data_._results.dollar(0, data_._sm, data_._productions);
        const char *end_ = token_.second - 1;

        while (strchr(" \t\r\n", *(end_ - 1))) --end_;

        data_._lhs.assign(token_.first, end_);
    };
    grules_.push("rhs_or", "opt_list");
    actions_map_[grules_.push("rhs_or", "rhs_or '|' opt_list")] =
        [](tdata &data_)
    {
        const token &token_ = data_._results.dollar(1, data_._sm, data_._productions);
        std::string r_ = token_.str() + ' ' + data_._rhs.top();

        data_._rhs.pop();

        if (data_._rhs.empty())
        {
            data_._rhs.push(r_);
        }
        else
        {
            data_._rhs.top() += ' ' + r_;
        }
    };
    grules_.push("opt_list", "%empty | rhs_list");
    grules_.push("rhs_list", "rhs");
    actions_map_[grules_.push("rhs_list", "rhs_list opt_comma rhs")] =
        [](tdata &data_)
    {
        std::string r_ = data_._rhs.top();

        data_._rhs.pop();
        data_._rhs.top() += ' ' + r_;
    };
    grules_.push("opt_comma", "%empty | ','");
    actions_map_[grules_.push("rhs", "IDENTIFIER")] =
        [](tdata &data_)
    {
        const token &token_ = data_._results.dollar(0, data_._sm, data_._productions);

        data_._rhs.push(token_.str());
    };
    actions_map_[grules_.push("rhs", "TERMINAL")] =
        [](tdata &data_)
    {
        const token &token_ = data_._results.dollar(0, data_._sm, data_._productions);

        data_._rhs.push(token_.str());
    };
    actions_map_[grules_.push("rhs", "'[' rhs_or ']'")] =
        [](tdata &data_)
    {
        std::size_t &counter_ = data_._new_rule_ids[data_._lhs];
        std::pair<std::string, std::string> pair_;

        pair_.second = "%empty | " + data_._rhs.top();

        auto pair2_ = std::pair(data_._lhs, pair_.second);
        auto iter_ = data_._seen.find(pair2_);

        if (iter_ == data_._seen.end())
        {
            ++counter_;
            pair_.first = data_._lhs + '_' + std::to_string(counter_);
            data_._rhs.top() = pair_.first;
            data_._new_rules.push(pair_);
            data_._seen[pair2_] = pair_.first;
        }
        else
        {
            data_._rhs.top() = iter_->second;
        }
    };
    actions_map_[grules_.push("rhs", "rhs '?'")] =
        [](tdata &data_)
    {
        std::size_t &counter_ = data_._new_rule_ids[data_._lhs];
        std::pair<std::string, std::string> pair_;

        ++counter_;
        pair_.first = data_._lhs + '_' + std::to_string(counter_);
        pair_.second = "%empty | " + data_._rhs.top();
        data_._rhs.top() = pair_.first;
        data_._new_rules.push(pair_);
    };
    actions_map_[grules_.push("rhs", "'{' rhs_or '}'")] =
        [](tdata &data_)
    {
        std::size_t &counter_ = data_._new_rule_ids[data_._lhs];
        std::pair<std::string, std::string> pair_;

        ++counter_;
        pair_.first = data_._lhs + '_' + std::to_string(counter_);
        pair_.second = "%empty | " + pair_.first + ' ' + data_._rhs.top();
        data_._rhs.top() = pair_.first;
        data_._new_rules.push(pair_);
    };
    actions_map_[grules_.push("rhs", "rhs '*'")] =
        [](tdata &data_)
    {
        std::size_t &counter_ = data_._new_rule_ids[data_._lhs];
        std::pair<std::string, std::string> pair_;

        ++counter_;
        pair_.first = data_._lhs + '_' + std::to_string(counter_);
        pair_.second = "%empty | " + pair_.first + ' ' + data_._rhs.top();
        data_._rhs.top() = pair_.first;
        data_._new_rules.push(pair_);
    };
    actions_map_[grules_.push("rhs", "'{' rhs_or '}' '-'")] =
        [](tdata &data_)
    {
        std::size_t &counter_ = data_._new_rule_ids[data_._lhs];
        std::pair<std::string, std::string> pair_;

        ++counter_;
        pair_.first = data_._lhs + '_' + std::to_string(counter_);
        pair_.second = data_._rhs.top() + " | " +
            pair_.first + ' ' + data_._rhs.top();
        data_._rhs.top() = pair_.first;
        data_._new_rules.push(pair_);
    };
    actions_map_[grules_.push("rhs", "rhs '+'")] =
        [](tdata &data_)
    {
        std::size_t &counter_ = data_._new_rule_ids[data_._lhs];
        std::pair<std::string, std::string> pair_;

        ++counter_;
        pair_.first = data_._lhs + '_' + std::to_string(counter_);
        pair_.second = data_._rhs.top() + " | " +
            pair_.first + ' ' + data_._rhs.top();
        data_._rhs.top() = pair_.first;
        data_._new_rules.push(pair_);
    };
    actions_map_[grules_.push("rhs", "'(' rhs_or ')'")] =
        [](tdata &data_)
    {
        std::size_t &counter_ = data_._new_rule_ids[data_._lhs];
        std::pair<std::string, std::string> pair_;

        pair_.second = data_._rhs.top();

        auto pair2_ = std::pair(data_._lhs, pair_.second);
        auto iter_ = data_._seen.find(pair2_);

        if (iter_ == data_._seen.end())
        {
            ++counter_;
            pair_.first = data_._lhs + '_' + std::to_string(counter_);
            data_._rhs.top() = pair_.first;
            data_._new_rules.push(pair_);
            data_._seen[pair2_] = pair_.first;
        }
        else
        {
            data_._rhs.top() = iter_->second;
        }
    };

    parsertl::generator::build(grules_, data_._sm);

    lrules_.insert_macro("NAME", "[A-Za-z][_0-9A-Za-z]*");
    lrules_.push("{NAME}", grules_.token_id("IDENTIFIER"));
    lrules_.push("{NAME}\\s*[:=]", grules_.token_id("LHS"));
    lrules_.push(",", grules_.token_id("','"));
    lrules_.push(";", grules_.token_id("';'"));
    lrules_.push("\\[", grules_.token_id("'['"));
    lrules_.push("\\]", grules_.token_id("']'"));
    lrules_.push("[?]", grules_.token_id("'?'"));
    lrules_.push("[{]", grules_.token_id("'{'"));
    lrules_.push("[}]", grules_.token_id("'}'"));
    lrules_.push("[*]", grules_.token_id("'*'"));
    lrules_.push("[(]", grules_.token_id("'('"));
    lrules_.push("[)]", grules_.token_id("')'"));
    lrules_.push("[|]", grules_.token_id("'|'"));
    lrules_.push("[+]", grules_.token_id("'+'"));
    lrules_.push("-", grules_.token_id("'-'"));
    lrules_.push("'(\\\\([^0-9cx]|[0-9]{1,3}|c[@a-zA-Z]|x\\d+)|[^'])+'|"
        "[\"](\\\\([^0-9cx]|[0-9]{1,3}|c[@a-zA-Z]|x\\d+)|[^\"])+[\"]",
        grules_.token_id("TERMINAL"));
    lrules_.push("#[^\r\n]*|\\s+|[(][*](.{+}[\r\n])*?[*][)]", lrules_.skip());
    lexertl::generator::build(lrules_, lsm_);

    lexertl::citerator iter_(start_, end_str_, lsm_);
    lexertl::citerator end_;

    data_._results.reset(iter_->id, data_._sm);
    std::cout << "%%\n";

    while (data_._results.entry.action != parsertl::action::error &&
        data_._results.entry.action != parsertl::action::accept)
    {
        if (data_._results.entry.action == parsertl::action::reduce)
        {
            auto i_ = actions_map_.find(data_._results.entry.param);

            if (i_ != actions_map_.end())
            {
                i_->second(data_);
            }
        }

        parsertl::lookup(iter_, data_._sm, data_._results, data_._productions);
    }

    if (data_._results.entry.action == parsertl::action::error)
        throw std::runtime_error("Syntax error");
    else
        std::cout << "%%\n"; 
}

int main()
{
    try
    {
        lexertl::memory_file mf_("grammars/python/python.ebnf");

        read_ebnf(mf_.data(), mf_.data() + mf_.size());
    }
    catch (const std::exception &e)
    {
        std::cout << e.what() << '\n';
    }
}

关注点

请注意，使用 EBNF 的语法通常使用多字符字面量。 虽然 parsertl 接受这些，因为它会自动为 token 定义 id，但如果您想将生成的 BNF 语法与 yacc 或 bison 一起使用，则必须手动将这些转换为普通 token。

请注意，大多数 EBNF 语法实际上描述的是 LL 语法，虽然 LL 是 LR 的子集，但它不是 LALR 的子集。 这适用于我之前提到的 Python 语法。 幸运的是，一些手动干预可以解决在通过 parsertl 或 bison 运行转换后的语法时出现的警告。

首先我们添加 token

%token DEDENT ENDMARKER INDENT NAME NEWLINE NUMBER STRING

删除或注释掉以下规则

single_input
eval_input
eval_input_1
encoding_decl

更改

import_from_4: import_from_2 dotted_name | import_from_3;

to

import_from_4: dotted_name | import_from_3 dotted_name | import_from_3;

并删除规则 import_from_2。

理想情况下，我也希望此类转换能够自动化。 这需要更多的研究，如果无法合理实现，鉴于其在现代实际语法（如 Python）中的流行程度，在 parsertl 中除了 LALR(1) 之外，还支持 LL(1) 可能是值得的。

历史

16/04/01 初次发布。

16/04/04 现在可以处理空规则。

16/04/05 现在显示将 Python 的 BNF 手动转换为 LALR(1) 兼容格式（无警告）。

16/09/28 通过引入 LHS token 修复了歧义语法。 引入了用于操作的 lambda 映射。

18/03/22 将 .|\n 切换为 .{+}[\r\n] 以包含 Windows 用户中的 \r。

19/04/30 更正了 #include 路径。

19/05/06 现在自动去重 [] 和 () 的规则。 更新了 Python 部分到最新版本。

23/01/21 更新到最新的 parsertl 接口。

24/02/15 更新到 lexertl17 和 parsertl17。