一个编程语言,从编译器前端的角度看,要经历词法分析、语法(文法)分析、语义分析三个步骤,才能判断出代码是否合法、如果合法表达了什么意思。
每一种流行编程语言的规范都可以厚成一本书,作为语言设计者或者编译器开发者,你必须考虑那么多条规范中,哪一些作为词法处理,哪一些作为语法处理,哪一些作为语义处理。
大部分编程语言(或者说编译器)的语法分析部分都是上下文无关文法,这是因为设计者认为上下文无关文法的复杂度恰好适中。如果使用更简单的文法进行分析,比如限于LL文法,那么就会有更多的任务被分配给语义分析或者词法分析,导致语义分析任务过重,难以设计;反之如果使用更复杂的上下文相关文法,那么语法分析本身就会变得复杂、低效。
所以,语法分析可以用上下文相关文法,但一般没必要,因为上下文相关的工作可以交给语义分析去做。
很多答案提到了Python和C++这两个例子,我觉得有必要指出,相对于课本内容这两种语言都是特例,而且大部分答案说的都有错误。
首先说Python。一些答案指出,Python的缩进规则无法用LR文法表达,这是不准确的。
实际情况是:在Python 3.8的解释器中,语法分析部分确实是上下文无关文法,但它的词法分析部分不是正则语言。
按照正则语言,词法分析会分析出这样的东西:(示意)
if x < 0: <缩进> x = -x <缩进> neg_cnt += 1 sum += x
但事实上,Python词法分析给出的最终结果是:
if x < 0: <缩进增> x = -x neg_cnt += 1 <缩进减> sum += x
可以看到<缩进增>和<缩进减>其实就是C-like的花括号,所以接下来的语法分析你一定知道怎么做了。
然后说C++,这玩意更麻烦,有千层饼潜质。
一些答案认为,C++不是上下文无关文法,因为变量需要先定义后使用。这是不准确的,先定义后使用是由语义分析负责的,语法分析并不考虑这个问题。
那么C++的文法是上下文无关的吗?
它是上下文相关的。
(╯°□°)╯︵ ┻━┻
请尝试解释以下代码中“>>”是什么符号:
a<b<c>> d
一般人想到的应该是模板套模板,“>>”是两层右尖括号
vector<vector<int>> matrix;
但是,C++中bool可以当int用,所以以下表达式完全合法,都不需要操作符重载:
int x = 4 < 3 < 2 >> 1; // x == 1
所以,在确定a是否为模板名之前,鬼知道“>>”是右尖括号还是右移操作符 ¯_(ツ)_/¯
右尖括号需要和左尖括号匹配,右移操作符则不需要,如果不弄清楚它的意思,编译器甚至无法判断代码是否合法。
那么C++编译器是怎么做的呢?答曰:试。
C++编译器会把每种可能的解释都记住,然后分别按照每种解释继续往下分析,出错了就回滚,最后只剩一种合法解释那就是正确答案。
最后总结:
更新:根据PEP 617,Python解释器将不再使用上下文无关文法
绝大多数编程语言都是上下文相关文法!
但是为了简化处理,也为了更好的提示错误,编译器不会直接用文法处理引擎来解析程序,而是先分解成各种语法单元,然后再逐一处理。这些语法单元就是Token。
为了简化Token的解析,所以Token通常会采用正则文法(如名称、运算符、常量、注释),和上下文无关文法(如表达式、语句)处理。
所谓的语言都是上下文无关文法,他们说的是statement的构成规则是上下文无关文法,整个文件不可能用上下文无关文法解决的。
因为最简单的声明变量就是上下文相关的。