C++模板”>>”编译问题与词法消歧设计
(感谢 @文艺复兴记(todd) 投递此文)
在编译理论中,通常将编译过程抽象为5个主要阶段:词法分析(Lexical Analysis),语法分析(Parsing),语义分析(Semantic Analysis),优化(Optimization),代码生成(Code Generation)。这5个阶段类似Unix管道模型,上一个阶段的输出作为下一个阶段的输入。其中,词法分析是根据输入源代码文本流,分割出词,识别类别,产生词法元素(Token)流,如:
int a = 10;
经过词法分析会得到[(Type, “int”), (Identifier, “a”), (AssignOperator, “=”), (IntLiteral, 10)],在后续的语法分析阶段,就会根据这些词法元素匹配相应的语法规则。在我学习编译原理时,教科书中对于词法分析的介绍主要是基于正则表达式的,言下之意就是普通语言的词法规则是可以通过正则表达式描述的。比如,C语言的变量名规则是“包含字母、数字或下划线,并且以字母或下划线开头”,这就可以用正则表达式[a-zA-Z_][a-zA-Z0-9_]*
表达。但是,在实践中我发现不管是主流语言,还是自己设计的DSL都大量存在不能简单通过正则表达式进行词法分析的例子。来看C++98的模版例子:
map<int, vector<int>>
上面这段代码会被C++98编译器中报语法错误,原因在于它把“>>”识别成了位右移运算符而不是两个模版右括号,在C++98中必须在两个括号中间加空格,写成
map<int, vector<int> >
除此了C++模版,据我所知,经典的FORTRAN语言的语法规则更是大量存在词法歧义。
我认为从本质上讲,这类问题的根源在于词法分析的依据只是简单的词法规则,并不具备所有的语法信息,而词法歧义必须提升一层在语法规则中消除。所以,在我自己设计一些DSL的时候干脆就把词法分析和语法分析合二为一了,相当于让语法分析在字符层次上去进行,而不是经典的词法元素层次上,这就是所谓的Scannerless Parsing。采用这种方法的例子并不少见,TeX, Wiki, Makefile和Perl 6等语言的语法分析器都属此类。
Scannerless Parsing方法弥补了词法规则无法消歧的问题,但是同时也破坏了词法和语法分析简单清晰的管道结构,总体上增加了实现和理解的复杂度。另外,像C++这样大型的语言,如果开始是有词法分析的,稍微碰到一个歧义就整个转成Scannerless Parsing未免也显得太夸张了。这个问题困扰了我很久,直到最近才找到了一个满意的解决方案。还是以上面”>>”为例,我们知道现在C++11已经允许不加空格了,那么C++11编译器是如何处理这个词法歧义的呢?答案是:词法分析阶段既然分析不好”>>”,干脆就不分析了,直接把”>” “>”交给语法分析器来分析,其他没有词法歧义的照旧。当我知道这个方案的时候不由得感叹:妙!理论上,词法分析是可以什么也不做的,全部把字符一一交给语法分析器也没有问题,所以,干脆让词法分析只做有把握的部分,解决不了的交给语法分析器,这样就既保留了管道结构,又解决了词法歧义。
下面我们再来看看C++11规范关于这个问题的定义:
14.2 Names of template specializations [temp.names] ###
After name lookup (3.4) finds that a name is a template-name or that an operator-function-id or a literal-operator-id refers to a set of overloaded functions any member of which is a function template if this is followed by a <, the < is always taken as the delimiter of a template-argument-list and never as the less-than operator. When parsing a template-argument-list, the first non-nested > is taken as the ending delimiter rather than a greater-than operator. Similarly, the first non-nested >> is treated as two consecutive but distinct > tokens, the first of which is taken as the end of the template-argument-list and completes the template-id. [ Note: The second > token produced by this replacement rule may terminate an enclosing template-id construct or it may be part of a different construct (e.g. a cast).—end note ]
可见,在C++11中,词法分析器是把”>>”直接当成两个”>”传给了语法分析器,然后在语法分析中如果匹配了template-argument-lis语法,第一个”>”符号会被直接认为是模版结束符,而不是大于,也不是位移符号。根据这个定义,我构造了一个例子:
template<int N> class Foo { }; Foo<3>>1> foo;
这个例子在C++98中是能正确编译的,”>>”被解释成了位移运算,但是它反而不能在C++11中编译了,因为根据规范第一个”>”被解释成了模版参数结束符。如果要在C++11中编译,需要显式地加上括号:
Foo<(3>>1)> foo;
(转载本站文章请注明作者和出处 宝酷 – sou-ip ,请勿用于任何商业用途)
《C++模板”>>”编译问题与词法消歧设计》的相关评论
我不是很清楚标准中的意思,如果按照这样子直接将>传递给语法分析器,那么下面的语法会不会通过
int a = 0;
a > > 2;
这里的“> >”会不被解释为“>>”???
g++ 出错,>空格>不会解释成>>
@g++
那么按照楼主的解释就不对了,如果是词法分析器传递两个>给文法分析器,那么文法分析器不会直到两个>之间有空格。这里应该会编译通过的
好早 C艹 就这么干了. 而且不仅语法跟词法, 还跟语义纠结在一起, 比如
a c;
这个有两种解释
* 变量定义
* (a 小于 b) 大于 c
每次语法分析器看到标识符后, 会去符号表查词元的类型, 再决定该如何解析.
@Neuron Teckid
sou-ip 居然没把 转义么
不过我想到了一个法子,可以把token中的>分为前面有空白和没有空白的两个token。这样子只要写多一点文法分析程序就可以了,正确解析这个问题了。
至于Nerron Teckid说的问题,是文法二义性的问题而已,所有的语言都有这个问题。这个解决方案已经非常多了。
例如C语言中的
Number * value;
可以是将value定义了一个指向Number类型的指针。也可以是int类型的Number乘以了value的值。
符号表是从词法分析到文法分析到语义分析的桥梁。这三个阶段离开符号表都不能联系在一起。
据说go语言设计的目的之一就是去除符号表,这个有点夸张,值得研究一下。
我记得我学lex&yacc的时候都是直接把’>’这样的单字符直接传给yacc的,懒得再为’>>’定义一个token了
这一篇,略水啊,没啥含量
@g++
会不会不是简单的直接传递,而是在传递一个字符时先查询下上次传递的是什么字符,然后再根据具体情况具体分析??
受教了!设计一个编译器果真是相当复杂,还没有涉及到面向对象模型呢!
存在词法歧义,是否算是语言设计者的耻辱?
类定义的最后要加一个“;”,不然,新手可能理解起来比较困惑。
template
class Foo {
};
按例膜拜
刚好在看编译原理的时候想过这个问题,自己想的是就分成 ‘<' '<'交给paser处理,书上说的是lexer也要前后看看做做分析
在浩哥微博看到的题目,终于等到解答了,先顶再看。