自制编程语言(一):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;
}

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

发布者

fawdlstty

又一只萌萌哒程序猿~~

发表评论

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