岁月流转,往昔空明

C++博客 首页 新随笔 联系 聚合 管理
  118 Posts :: 3 Stories :: 413 Comments :: 0 Trackbacks

起源:词法分析

不管你学什么样的外语,大约都是从词汇开始。词,是一个语言里最小的语义单元。编译器阅读你的语言,也是如此。所以第一件事情,就是要把整个文法打散成一个一个的单词。在这里,我们把这些单词叫token。

怎么进行词法分析,此处就不再赘述,这是一个上下文无关文法的匹配问题。如果需要理解词法分析的原理,或者手工编写词法分析工具,可以参考陈梓翰提供的两篇极好的教程。在SASL里,我们不再发明轮子,而选用已有的词法分析工具。

可选的词法分析工具很多,例如出名的Lex及其改进Flex,ANTLR等。对于C++而言,这些方法多属于产生式的方法,就是用一段不太靠谱的代码去生成另外一些更不靠谱的代码。更重要的是,这些代码的编译、调试都不方便。所以最终我们还是选择了一个在用C++实现、并且可以直接在C++里书写词法和语法的分析器产生工具,它就是Spirit。

Spirit V1.8和V2.1都是Boost库里的一个部分。需要注意的是,Spirit的V1和V2是完全不兼容的两个库。在这里,我们选择了V2作为我们的词法和语法分析工具。Spirit V2总共分为3个部分,负责语法分析的Qi,格式化打印的Karma,和词法分析器Lex。此外,Spirit还有一个类似于boost.mpl和boost.lambda的库phoenix,这个库也常被用于词法和语法分析中。详细的使用指南和参考,可以参见Spirit的文档。

由于Spirit.Lex大量运用了Template Meta-Programming和编译器推导,因此编译时很容易出错,而且错误信息难于定位;同时Spirit.Lex的指南也写得非常简单,它所演示的特性,不足以用来实现一个完整的编译器。因此,这里我们也将给出另外一个快速指南,以展示那些我们在撰写编译器时所用到的技术和特性。

这里我们仍然以A+B这样一个简单的表达式为例,其中A和B都是一个字面值的整数,A+B之间没有其他空格填充。这样我们就可以把这个“句子”拆分成A,+,B三个token。例如“33+65”就可以被拆分成“33”,“+”,“65”三个token。对于这样一个表达式,我们只需要下面两个正则就可以完成词法分析:

literal_int = “[0-9]+”;

literal_add=”\+”;

由于C++里面“\”是转义符,因此实际上literal_add实际上应该写成“\\+”。然后我们需要用Spirit来实现。

Spirit中,首先定义一个tokens列表:

template <typename BaseLexerT>

struct sasl_tokens : public boost::spirit::lex::lexer< BaseLexerT > {

    sasl_tokens(){

        littok_int = "[0-9]+";

        optok_add = "[\\+]";

 

        this->self =

            littok_int

            | optok_add;

    }

    boost::spirit::lex::token_def<> littok_int, optok_add;

};

 

然后,我们利用这个token列表生成一个词法分析器sasl_tokenizer:

 

typedef boost::spirit::lex::lexertl::lexer<> sasl_lexer_base;

typedef sasl_tokens<sasl_lexer_base> sasl_tokenizer;

 

最后来执行一下我们的tokenizer。在执行之前,我们写一个callback函数,这个函数在每分析出一个词之后,都会被调用一下,我们用它来判断我们分出的词正确与否:

struct token_printer{

    template <typename TokenT> bool operator()( const TokenT& tok ){

        cout << "token: " << tok.value() << endl;

        return true;

    }

};

最后执行一下词法分析:

boost::spirit::lex::tokenize(first, last, sasl_tok, token_printer());

first,last是输入字符串的迭代器。如果输入为“55+65”,那么屏幕上就会依次打印出“55”,“+”,“65”的三行。

不过,如果你在“55+65”之间敲入一个空格,例如“55+_65”(‘_’代表空格)这样的,那么词法分析就会失败。因为“_”这个字符,没有合适的词可以匹配。即便是匹配了,空白这个Token也没办法用在语法树之中,最终也会导致语法分析失败。而在程序语言里,支持空白符号的过滤掉是必不可少的。所以,下一次,我们就要将语法,顺便过滤掉空白符,让我们可以自由写出美观的语句。

posted on 2009-12-13 00:31 空明流转 阅读(1832) 评论(2)  编辑 收藏 引用

评论

# re: 实用编译器构建指南(三) 2009-12-13 12:58 黑色灵猫
非常好的boost解析器教程  回复  更多评论
  

# re: 实用编译器构建指南(三) 2009-12-13 14:35 正心
围观  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理