使用 C++ BNF 类 EDSL 的公式编译器

• 下载公式编译器 - 20.8 KB

前言

有没有一个领域可以应用从零开始开发的新编程语言？乍一看，没有现有的语言无法满足的需求。然而，这样的领域确实存在，例如需要并行计算的系统。值得注意的是，计算机界一直在寻找一种能够自身支持语法解析器的语言！BNF（巴克斯范式）及其变体（ABND、EBNF等）被广泛用于编程语言的形式化规范。

虽然这些规范对于需求和设计都非常好，但它们对于解析器编程没有帮助。另一种方法是生成解析器代码。最著名的工具是yacc（Yet Another Compiler Compiler），它是一个预编译程序，可以从BNF类形式的语法定义生成C解析器代码。这种解决方案被认为过于笨重，社区一直在寻找更简单的东西。

对于C++来说，方法很明显：一个轻量级的解决方案应该作为嵌入式领域特定语言（EDSL）呈现。这意味着BNF类语句必须映射到C++关键字和重载运算符。一个已知的例子是boost::spirit模板库。本文介绍了BNFLite C++模板库，并演示了如何使用此工具创建最简单的字节码公式编译器。

BNFLite简介

BNFLite实现了用于语法规范的嵌入式领域特定语言方法，其中所有“产生式规则”都构建为C++类的实例，并通过重载的算术运算符连接。例如，BNF规范中的整数可以描述为

    <digit> ::= <0> | <1> | <2> | <3> | <4> | <5> | <6> | <7> | <8> | <9>
    <number> ::= <digit> | <digit> <number>

使用BNFlite方法，此表示可以写成C++

    #include "bnflite.h" // include source code lib
    using namespace bnf;
    Lexem Digit = Token("0") | "1"  | "2" | "4" | "5" | "6" | "7" | "8" | "9";
    Lexem Number;
    Number = Digit | Digit + Number;

执行此C++代码会生成一个内部数据结构，用于后续的解析过程。

公式编译器要求

让我们指定要开发的公式编译器语言的基本要求。

1. 字节码编译器应基于类表达式的语言
   1. 应支持以下基本类型：<INTEGER> | <FLOAT> | <STRING>
   2. 编译器应支持一元负运算和基本二元算术运算
   3. 编译器应能够生成代码来调用主程序中定义的C++函数

这足以设计一种简单的编程语言，可以用巴克斯范式描述。

形式化的BNF术语称为“产生式规则”。除“终端”外的每个规则都是一系列更具体的规则或终端的组合：production_rule ::= <rule_1>...<rule_n> | <rule_n_1>...<rule_m>。因此，设计的类表达式语言可以用以下术语表示

<operand> ::= <INTEGER> | <FLOAT> | <STRING>
<operator> ::= "+" | "-" | "*" | "/"
<arguments> ::= <EMPTY> | <expression> | < arguments> "," <expression>
<function> ::= <IDENTIFIER> "(" < arguments > ")"
<expression> ::= <operand> | <function> | "-" 
<expression> | <expression> <operator> <expression> | "(" <expression> ")"

这种描述在形式上是正确的，但存在两个已知问题。首先，没有表示二元运算符的优先级。其次，它包含过多的递归，可以被重复所取代。

增强型BNF规范引入了诸如<a>*<b><element> 之类的构造来支持重复，其中<a>和<b>表示元素出现的最少<a>次和最多<b>次。例如，3*3<element>表示正好三次，而1*2<element>表示一次或两次。*<element>简化构造允许任意次数（从0到无穷大）。或者，1*<element>包含一个可选元素（至少一次），并且可以表示为[element]。

ABNF形式的公式编译器语言的完整规范并不复杂

ALPHA  =  'A'-'Z' | 'a'-'z'
DIGIT  =  '0'-'9'
digit1_9 =  '1'-'9'
string  = '\"' *( ALPHA  | DIGIT | '_' ) '\"'
e = 'e' | 'E'            
exp = e ['-' | '+'] 1*DIGIT
frac = '.' 1*DIGIT
int = '0' | ( digit1_9 *DIGIT )
number = [ '-' ] int [ frac ] [ exp ]
operand = int | number | string
operator = '+' | '-' | '*' | '/'
identifier =  (ALPHA | '_') *( ALPHA  | DIGIT | '_' )
arguments ::=  expression *( ',' expression )
function ::= identifier '(' [arguments]  ')'
elementary ::= operand | function | ('-' elementary) | ('(' expression ')')
primary = elementary *(('/' elementary) | ('*' elementary))
expression = primary *(('-' primary) | ('+' primary))

这些规范比以前的更适合计算机。

简要设计说明

简单的字节码编译器是表达式计算器的次要扩展。例如，表达式2 + 3 * 4可以转换为树。

└──+
   ├── 2
   └──*
      ├── 3
      └── 4

它可以用C语言方式写成“add(2, mul(3, 4))”的形式。我们反过来写：“ (2,(3,4)mul)add”。这种形式称为逆波兰表示法（RPN），并且可以轻松生成字节码。

Int(2) Int(3), Int(4), Mul<I,I>, Addl<I,I>

Int（数字）操作将数字压入堆栈。Mul/Add操作弹出堆栈上的两个参数并将结果压入。

公式编译器的实际好处仅在于使用函数时。让我们考虑“线性映射”2 + 3 *GetX()。字节码将是

Int(2) Int(3), Call<0>, Mul<I,I>, Addl<I,I>

例如，此功能可以循环应用于X数据库列以获得Y列（此外，提供的演示同时进行了四次计算，但这更像是另一篇论文的范围）。

所有字节码都由两个字段组成：用于整数、浮点数和字符串指针的类型和联合。

struct byte_code
{
    OpCode type;
    union {
        int val_i;
        float val_f;
        const char* val_s;
    };
    byte_code(): type(opNop), val_i(0) {};
    /* … */

联合表示简单“立即寻址模式”的操作数。类型是基于以下枚举器的操作码

enum OpCode
{
    opFatal = -1, opNop = 0,
    opInt = 1,  opFloat = 2,  opStr = 3,  opMaskType = 0x03,
    opError = 1, opNeg = 2, opPos = 3, opCall = 4,
    opToInt = 5,  opToFloat = 6, opToStr = 7,
    opAdd = 2,  opSub = 3,  opMul = 4,  opDiv = 5,
};

实际操作码稍微复杂一些。它包含堆栈操作数的类型。

BNFLite语法类（Token、Lexem和Rule）

BNFLite描述类似于上面的EBNF规范。

数字

Token digit1_9('1', '9');
Token DIGIT("0123456789");
Lexem i_digit = 1*DIGIT;
Lexem frac_ = "." + i_digit;
Lexem int_ = "0" | digit1_9  + *DIGIT;
Lexem exp_ = "Ee" + !Token("+-") + i_digit;
Lexem number_ = !Token("-") + int_ + !frac_ + !exp_;
Rule number = number_;

Token类表示符号（终端）。Lexem构造符号的string。解析是分析输入流中的标记和词素的过程。一元C运算符`*`表示构造可以重复0到无穷次。二进制C运算符`*`表示1*DIGIT之类的构造可以重复1到无穷次。一元C运算符`!`表示构造是可选的。

实际上，Rule与Lexem类似，除了回调和对空格的敏感度。构造Rule number_ = !Token("-") + int_ + !frac_ + !exp_;允许不正确的空格，例如在整数和分数部分之间。

字符串和标识符

    Token az_("_"); az_.Add('A', 'Z'); az_.Add('a', 'z');
    Token az01_(az_); az01_.Add('0', '9');
    Token all(1,255); all.Remove("\"");
    Lexem identifier = az_  + *(az01_);
    Lexem quotedstring = "\"" + *all + "\"";

Token all表示除引号之外的所有符号；

主要解析规则

    Rule expression;
    Rule unary;
    Rule function = identifier + "(" + !(expression + *("," + expression)) +  ")";
    Rule elementary = AcceptFirst()
            | "(" + expression + ")"
            | function
            | number
            | quotedstring + printErr
            | unary;
    unary = Token("-") + elementary;
    Rule primary = elementary + *("*%/" + elementary);
    /* Rule */ expression = primary + *("+-" + primary);

Expression和unary规则是递归的。它们需要提前声明。AcceptFirst()语句将解析器的行为从默认模式更改为当前Rule的“接受最佳”模式。之后，解析器会选择第一个合适的构造，而不是最合适的。

解析器调用和回调

递归下降解析器意味着树的组成。用户需要一种方法来跟踪树的遍历递归。首先，应指定用于与解析器交互的接口对象结构。

typedef Interface< std::list<byte_code> > Gen;
/* ... */
const char* tail = 0;
Gen result;
int tst = Analyze(expression, expr.c_str(), &tail, result);

解析通过Analyze调用开始，并附带以下参数

• expression – BNFlite语法的根Rule对象
• expr.c_str() – 要编译为字节码的表达式字符串
• tail – 如果解析成功，则指向文本末尾的指针；如果由于错误停止解析，则指向停止解析的位置
• result – 来自用户回调的最终对象
• tst – 包含解析结果，以位标志形式表示；如果为负，则为错误

回调函数接受早先形成的字节码列表向量。它返回新形成的字节码列表。例如，Gen DoNumber(std::vector<Gen>& res)接受表示数字的单元素向量。它必须返回包含用户data（Int<>或Float<>）的Gen对象。

通常情况下，回调Gen DoBinary(std::vector<Gen>& res)接受左字节码向量、运算符号（+**/）和右字节码向量。回调函数仅连接左右字节码向量，并根据符号生成尾部字节码。

与Boost::Spirit实现的比较

这是使用boost::spirit模板库实现的语法部分

namespace q = boost::spirit::qi;

typedef boost::variant<
    int, float, std::string,
    boost::recursive_wrapper<struct binary_node>,
    boost::recursive_wrapper<struct unary_node>,
    boost::recursive_wrapper<struct call_node>
> branch_t;

template <typename Iterator>
struct SParser: q::grammar<Iterator, branch_t, q::space_type>
{
    q::rule<Iterator, branch_t, q::space_type> expression, primary, elementary, unary;
    q::rule<Iterator, std::string()> quotedstring;
    q::rule<Iterator, std::string()> identifier;
    q::rule<Iterator, std::vector<branch_t>, q::space_type> arglist;
    q::rule<Iterator, call_node, q::space_type> function;

    SParser() : SParser::base_type(expression)
    {
    using boost::phoenix::construct;
        
    expression = primary[q::_val = q::_1]
        >> *('+'  > primary[q::_val = construct<binary_node>(q::_val, q::_1, '+')]
            | '-' > primary[q::_val = construct<binary_node>(q::_val, q::_1, '-')] );
    primary =   elementary[q::_val = q::_1]
        >> *('*'  > elementary[q::_val = construct<binary_node>(q::_val, q::_1, '*')]
            | '/' > elementary[q::_val = construct<binary_node>(q::_val, q::_1, '/')] );
    unary = '-' > elementary[q::_val = construct<unary_node>(q::_1, '-')]; 

    elementary = q::real_parser<float, q::strict_real_policies<float>>()[q::_val = q::_1]
        | q::int_[q::_val = q::_1]
        | quotedstring[q::_val = q::_1]
        | ('(' > expression > ')')[q::_val = q::_1]
        | function[q::_val = q::_1]
        | unary[q::_val = q::_1];

    quotedstring = '"' > *(q::char_ - '"') > '"';
    identifier = (q::alpha | q::char_('_')) >> *(q::alnum | q::char_('_'));

    arglist = '(' > (expression % ',')[q::_val = q::_1] > ')';
    function = (identifier > arglist)[q::_val = construct<call_node>(q::_1, q::_2)];

    on_error(expression, std::cout << boost::phoenix::val("Error "));
    }
};

有关详细信息，请参阅boost::spirit文档。提供此示例是为了演示boost::spirit语法与BNFlite语法的相似性。

Boost::spirit是一个更成熟的工具，不使用回调。对于每个“规则”，它会调用应该属于boost::variant的类的构造函数。因此，boost::spirit不能用于*单遍编译器*。然而，如果需要更复杂的东西（例如，*字节码优化器*），boost::variant会很有用。

boost::spirit的问题在于另一个领域。任何包含boost::spirit的引入都会大大增加项目的编译时间。boost::spirit另一个显著的缺点与语法的运行时调试有关——根本不可能！

BNFLite语法的调试

使用EDSL编写语法是不寻常的，用户并不完全理解解析器。如果Analyze调用对正确的文本返回错误，那么用户应始终考虑语法可能存在bug的可能性。

返回码

Analyze调用返回的代码可以包含与语法相关的标志。例如，eBadRule、eBadLexem标志表示规则树未正确构建。

名称和断点

用户可以为Rule指定名称。这有助于使用Rule::_parse函数跟踪递归下降解析器。调试器堆栈（函数调用历史）可以告知哪个Rule何时被应用。用户只需关注this.name变量。这并不像初看起来那么困难。

语法子集

Analyze函数可以作为单元测试应用于任何代表语法子集的Rule。

跟踪

函数原型为“bool foo(const char* lexem, size_t len)”的函数可以用于BNFLite表达式，目的有两个：获取临时结果和通知预测错误。

此函数将打印解析的数字

static bool DebugNumber(const char* lexem, size_t len)
{    printf("The number is: %.*s;\n", len, lexem);    return true; }
    /* … */
Rule number = number_ + DebugNumber;

如果结果正确，函数应返回true。

假设不允许带有前导“+”的数字。

static bool ErrorPlusNumber(const char* lexem, size_t len)
{printf("The number %.*s with plus is not allowed\n", len, lexem); return false;}
    /* … */
Lexem number_p = !Token("+") + int_ + !frac_ + !exp_ + ErrorPlusNumber;
Rule number = number_ | number_p;

函数应返回false以通知解析器结果不合适。C++11的构造如下也可能

Rule number = number_ | [](const char* lexem, size_t len)
{ return !printf("The number %.*s with plus is not allowed\n", len, lexem); }

构建和运行

附带的最简单的公式编译器包包含以下C++文件

1. main.cpp - 字节码编译器和解释器的启动程序
2. parser.cpp - BNFLite解析器，包含语法部分和回调
3. code_gen.cpp - 字节码生成器
4. code_lib.cpp - 几个内置函数的示例（例如POW(2,3) - 幂：2*2*2）
5. code_run.cpp - 字节码解释器（使用SSE2并行计算4个公式）

该包有几个预构建项目，但通常可以构建为

>$ g++ -O2 -march=pentium4 -std=c++14 -I.. code_gen.cpp  parser.cpp  code_lib.cpp  main.cpp code_run.cpp

函数GetX()返回四个值：0, 1, 2, 3。它可以在要编译和计算的表达式中使用

> $ a.exe "2 + 3 *GetX()"  
5 byte-codes in: 2+3*GetX()
Byte-code: Int(2),Int(3),opCall<I>,opMul<I,I>,opAdd<I,I>;
result = 2, 5, 8, 11;

结论

所 presented的公式编译器是为了演示其可行性而实现的几个想法。首先，它是根据编译的公式进行并行计算。其次，它引入了BNFLite头库，以推广BNF形式适用性的现有概念。现在，可以轻松地为使用BNF类语言的特定客户需求创建快速的解析器实现。

参考文献

• [1] BNFLite及部分示例，https://github.com/r35382/bnflite