自制编程语言（一）：EBNF表达式及Boost.Spirit的使用

大家有没想过，编程语言是如何被编译或解释执行的？使用sscanf还是正则表达式？今天我们一起来揭开编程语言的神秘面纱。
程序语言按照层次，可以分为普通语言以及语法描述语言。普通语言包括出语法描述语言外的其他所有语言。简单的说，C++，C#，Java、XML、JSON等等都属于这类；语法描述语言是用来描述一门语言的语法，通常一门语法描述语言就能描述所有的语言的语法。这类语言最著名的叫EBNF（扩展巴克斯范式）。
这类语言的作用就是定义一门语言的语法。语法定义完毕后，语言会按照设计思路，生成AST（抽象语法树）。抽象语法树能非常方便的生成中间语言。通常，这个过程就叫编译器前端。相应的，编译器后端是指将中间语言优化，再解析为本地字节码的过程，叫编译器后端。一般来说，生成AST后，一个语言基本上就设计完成了，后端可以自己撸，也可以对接llvm等，很方便就能实现一门编程语言。
语言前端基于EBNF的工具有很多，看一些工具的名称就能看出来，比如yacc（又一个编译器的编译器）。C++的“准”标准库也提供了全套库，叫“Boost.Spirit”。后面的代码我将以这个工具来举例。
说及这个库，首先不得不谈这个EBNF表达式。下面我给大家展示一个用于描述四则运算的EBNF代码：

1
2
3
4
5
6

expr1 := oper1 ('+' | '-') (expr1 | oper1)
expr2 := oper2 ('*' | '/') (expr2 | oper2)
oper1 := expr2 | integer | block;
oper2 := integer | block;
block := '(' oper ')';
oper := expr1 | expr2 | integer | block;


这个表达式和网上的不太一样，网上的主要用于计算，所以三行就完事。但我们这儿是描述语言，使用最细的方式给大家讲解如何描述语言，以及为啥要拆成六行。这儿参照的夜神的语法描述代码，在此对夜神表示感谢！
在讲解这个代码前，我先说说这个公式代表的含义。:=为赋值运算符，将右侧的公式放入左侧的符号中。这个不是程序语言中的变量，仅仅代表一个符号而已。
第一行，expr1的意思是加减法的表达式的描述语句，右边是表达式的描述。表达式分为三个部分。第一个部分是oper1，也就是加号左边那个数字；第二个括起来的('+' | '-')，代表这个符号是加法或者减法中的其中一个，中间的|符号代表二选一；后面的(expr1 | oper1)代表加号后面的也是一个加减法语句，或者是一个数字。
举个例子，1+2，这个表达式中，1对应公式的oper1，+对应公式('+' | '-')的加号，2对应公式(expr1 | oper1)的oper1。
再举个例子，1+2+3，这个表达式中，1对应公式的oper1，+对应公式('+' | '-')的加号，2+3对应公式(expr1 | oper1)的expr1，然后expr1再次解析一次2+3。
语法看起来比较奇怪，不要介意，相信我，后面会更绕的。第二行，整体看起来和第一行挺像，唯一不同的是，名称都换了，另外符号也换成了乘号和除号。
可能大家会觉得比较奇怪，为什么加减法与乘除法的操作数要分开。这是为了将运算符的优先级完全分开，便于首先拆分加减，再拆分乘除。
第三行，oper1的意思是加减法的操作数，可以取的值是乘除法公式值比如2*3，或者整数比如4，或者一个块比如(2+2)。
第四行，oper2的意思是乘除法的操作数，只能去两个值整数比如4，或者一个块比如(2+2)。
第五行block意思是定义一个块，也就是括号括起来的部分优先计算。
第六行的意思是定义读取的值，可以是一个加减法公式，可以是一个乘除法公式，可以是一个整数，也可以是一个块。

了解的差不多之后，开始实际操作了。下面来一个实际的代码（下面的代码部分来自boost官方文档，部分来自我对库的思路的总结）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <boost/config/warning_disable.hpp>
#include <boost/spirit/include/qi.hpp>
#include <boost/phoenix/phoenix.hpp>
 
namespace qi = boost::spirit::qi;
namespace ascii = boost::spirit::ascii;
using qi::int_;
 
int main () {
    std::cout << "Give me a number." << std::endl;
    std::cout << "Type [q or Q] to quit" << std::endl << std::endl;
 
    std::string str;
    while (getline (std::cin, str)) {
        if (str.empty () || str[0] == 'q' || str[0] == 'Q')
            break;
 
        bool r = qi::phrase_parse (str.begin (), str.end (), int_, ascii::space);
        if (r) {
            std::cout << "-------------------------" << std::endl;
            std::cout << "Parsing succeeded" << std::endl;
            std::cout << " Parses OK" << std::endl;
        } else {
            std::cout << "-------------------------" << std::endl;
            std::cout << "Parsing failed" << std::endl;
        }
        std::cout << "-------------------------" << std::endl;
    }
    return 0;
}

这段代码能识别出输入的内容是否为一个整数。如果为整数那么返回值为true，否则为false。这段代码的关键函数为qi::phrase_parse，有一个和它类似的函数是qi::parse，这两者区别是，前者只能解析段语句，并且解析短句比较方便，后者适合解析大篇的代码或数据。
四个参数，前两个是分别为迭代器头与迭代器尾，第三个为解析器语法，第四个为忽略格式的空格。
这一段代码只能验证输入的是否为数字，并不能留存结果。下面我们将结果打印出来，引用部分加上一行代码：

1

namespace phoenix = boost::phoenix;

然后，代码改为如下形式：

1
2
3
4
5
6

        // ...
        int n;
        bool r = qi::phrase_parse (str.begin (), str.end (), int_[phoenix::ref (n) = qi::_1], ascii::space);
        // ...
            // 解析成功后，这儿显示结果
            std::cout << "number is: " << n << std::endl;

方括号里面是赋值操作，将qi::_1赋值给n的引用。注意这儿的等号，在需要时完全可以改为其他赋值符号，比如+=、*=、<<=、^=等赋值符号。 这儿的语法可能比较奇怪，所以一般对其包装一下，如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <boost/config/warning_disable.hpp>
#include <boost/spirit/include/qi.hpp>
#include <boost/phoenix/phoenix.hpp>
#include <boost/bind/bind.hpp>
 
namespace qi = boost::spirit::qi;
namespace ascii = boost::spirit::ascii;
namespace phoenix = boost::phoenix;
using qi::int_;
 
class writer {
public:
    void print (int const& i) const {
        std::cout << i << std::endl;
    }
 
    template <typename Iterator>
    bool parse_members (Iterator first, Iterator last) {
        bool r = qi::phrase_parse (first, last,
            int_[boost::bind (&writer::print, this, boost::placeholders::_1)],
            ascii::space);
        return r;
    }
};
 
int main () {
    std::cout << "please press a int number: ";
    std::string str;
    writer w;
    while (getline (std::cin, str)) {
        if (str.empty () || str[0] == 'q' || str[0] == 'Q')
            break;
 
        bool r = w.parse_members(str.begin(), str.end());
        if (r) {
            std::cout << "-------------------------" << std::endl;
            std::cout << "Parsing succeeded" << std::endl;
        } else {
            std::cout << "-------------------------" << std::endl;
            std::cout << "Parsing failed" << std::endl;
        }
        std::cout << "-------------------------" << std::endl;
    }
    return 0;
}

将解析器封装为一个类，然后用类的成员函数去解析它。需要注意的是，直接赋值的_1与std::bind的_1不是同一个，需要区分开。然后，如果我们想一次性读取一个vector的数据呢，可以这样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <boost/config/warning_disable.hpp>
#include <boost/spirit/include/qi.hpp>
#include <boost/phoenix/phoenix.hpp>
#include <boost/bind/bind.hpp>
 
namespace qi = boost::spirit::qi;
namespace ascii = boost::spirit::ascii;
namespace phoenix = boost::phoenix;
using qi::int_;
 
class writer {
public:
    template <typename Iterator>
    bool parse_members (Iterator first, Iterator last, std::vector<int> &v) {
        bool r = qi::phrase_parse (first, last,
            int_[phoenix::push_back (phoenix::ref (v), qi::_1)] >> *( ',' >> int_[phoenix::push_back (phoenix::ref (v), qi::_1)]),
            ascii::space);
        return r;
    }
};
 
int main () {
    std::cout << "please press a comma separated list of numbers: ";
    std::string str;
    writer w;
    while (getline (std::cin, str)) {
        if (str.empty () || str[0] == 'q' || str[0] == 'Q')
            break;
 
        std::vector<int> v;
        bool r = w.parse_members(str.begin(), str.end(), v);
        if (r) {
            std::cout << "-------------------------" << std::endl;
            std::cout << "Parsing succeeded" << std::endl;
            for (int i : v)
                std::cout << i << "  ";
            std::cout << std::endl;
        } else {
            std::cout << "-------------------------" << std::endl;
            std::cout << "Parsing failed" << std::endl;
        }
        std::cout << "-------------------------" << std::endl;
    }
    return 0;
}

push_back是一个封装器的函数，对v进行push操作。*代表后面这一段内容可能重复零次或多次。
phrase_parse这一段代码可以再优化一下：

1
2
3

        bool r = qi::phrase_parse (first, last,
            int_[phoenix::push_back (phoenix::ref (v), qi::_1)] % ',',
            ascii::space);

百分号的含义是，左侧的内容通过右侧的分隔符进行分割。对于列表型数据，还能再通过语法糖进行优化：

1
2
3

        bool r = qi::phrase_parse (first, last,
            int_ % ',',
            ascii::space, v);

下面我们来设计一种解析器，用来解析罗马数字。罗马数字由I、V、X等字符构成，比如从1到10为：I、II、III、IV、V、VI、VII、VIII、IX、X。
解析器在程序中用来读取数据并生成结果。比如上面的qi::int_解析器，就是将字符串数据中的数字ASCII码组合转为整型数据。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <boost/config/warning_disable.hpp>
#include <boost/spirit/include/qi.hpp>
#include <boost/phoenix/phoenix.hpp>
#include <boost/bind/bind.hpp>
 
namespace qi = boost::spirit::qi;
namespace ascii = boost::spirit::ascii;
namespace phoenix = boost::phoenix;
using qi::int_;
using qi::_val;
using qi::_1;
 
struct roman_100_t : qi::symbols<char, unsigned> {
    roman_100_t () {
        add ("C", 100) ("CC", 200) ("CCC", 300) ("CD", 400) ("D", 500) ("DC", 600) ("DCC", 700) ("DCCC", 800) ("CM", 900);
    }
} roman_100;
 
struct roman_10_t : qi::symbols<char, unsigned> {
    roman_10_t () {
        add ("X", 10) ("XX", 20) ("XXX", 30) ("XL", 40) ("L", 50) ("LX", 60) ("LXX", 70) ("LXXX", 80) ("XC", 90);
    }
} roman_10;
 
struct roman_1_t : qi::symbols<char, unsigned> {
    roman_1_t () {
        add ("I", 1) ("II", 2) ("III", 3) ("IV", 4) ("V", 5) ("VI", 6) ("VII", 7) ("VIII", 8) ("IX", 9);
    }
} roman_1;
 
template <typename Iterator>
struct roman_grammar : qi::grammar<Iterator, unsigned ()> {
    roman_grammar () : roman_grammar::base_type (start) {
        start = qi::eps[_val = 0] >> (
            +qi::lit ('M')[_val += 1000] || roman_100[_val += _1] || roman_10[_val += _1] || roman_1[_val += _1]
        );
    }
 
    qi::rule<Iterator, unsigned ()> start;
};
 
int main () {
    std::cout << "please press a roman numbers: ";
    std::string str;
    roman_grammar<std::string::iterator> roman;
    while (getline (std::cin, str)) {
        if (str.empty () || str[0] == 'q' || str[0] == 'Q')
            break;
 
        int n;
        bool r = qi::phrase_parse (str.begin (), str.end (), roman, ascii::space, n);
        if (r) {
            std::cout << "-------------------------" << std::endl;
            std::cout << "Parsing succeeded" << std::endl;
            std::cout << " Parses OK: " << n << std::endl;
        } else {
            std::cout << "-------------------------" << std::endl;
            std::cout << "Parsing failed" << std::endl;
        }
        std::cout << "-------------------------" << std::endl;
    }
    return 0;
}

这次我们一次性写了三个解析器，第一个解析器，输入MMCDXXXIX，不出意外，结果为2439。解析器通过识别出指定字符，然后返回字符所代表的数字，然后对其相加。
然后，我们设计一个能读取指定结构的解析器，能解析出一个结构体中的内容。示例代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <boost/config/warning_disable.hpp>
#include <boost/spirit/include/qi.hpp>
#include <boost/phoenix/phoenix.hpp>
#include <boost/bind/bind.hpp>
 
namespace qi = boost::spirit::qi;
namespace ascii = boost::spirit::ascii;
namespace phoenix = boost::phoenix;
using qi::int_;
using qi::_val;
 
struct user {
    std::string name;
    int age;
};
 
BOOST_FUSION_ADAPT_STRUCT (
    user,
    (std::string, name)
    (int, age)
)
 
template <typename Iterator>
struct user_parser : qi::grammar<Iterator, user (), ascii::space_type> {
    user_parser () : user_parser::base_type (start) {
        using qi::int_;
        using qi::char_;
 
        quoted_string %= qi::lexeme['"' >> +(char_ - '"') >> '"'];
        start %= qi::lit ("user") >> '{' >> quoted_string >> ',' >> int_ >> '}';
    }
 
    qi::rule<Iterator, std::string (), ascii::space_type> quoted_string;
    qi::rule<Iterator, user (), ascii::space_type> start;
};
 
int main () {
    std::cout << "please press a user struct: ";
    std::string str;
    user_parser<std::string::iterator> parser;
    user e;
    while (getline (std::cin, str)) {
        if (str.empty () || str[0] == 'q' || str[0] == 'Q')
            break;
 
        bool r = qi::phrase_parse (str.begin (), str.end (), parser, ascii::space, e);
        if (r) {
            std::cout << "-------------------------" << std::endl;
            std::cout << "Parsing succeeded" << std::endl;
            std::cout << " Parses OK: " << "user name=" << e.name << ", age=" << e.age << std::endl;
        } else {
            std::cout << "-------------------------" << std::endl;
            std::cout << "Parsing failed" << std::endl;
        }
        std::cout << "-------------------------" << std::endl;
    }
    return 0;
}

这个结构已经非常像最终的解析器了，多个结构组合即可实现程序语法解析。

Published by

fawdlstty

又一只萌萌哒程序猿~~

发表评论

电子邮件地址不会被公开。 必填项已用*标注