为什么编程语言都是上下文无关文法，不能采用上下文有关文法吗？ 第1页

一个编程语言，从编译器前端的角度看，要经历词法分析、语法（文法）分析、语义分析三个步骤，才能判断出代码是否合法、如果合法表达了什么意思。

每一种流行编程语言的规范都可以厚成一本书，作为语言设计者或者编译器开发者，你必须考虑那么多条规范中，哪一些作为词法处理，哪一些作为语法处理，哪一些作为语义处理。

大部分编程语言（或者说编译器）的语法分析部分都是上下文无关文法，这是因为设计者认为上下文无关文法的复杂度恰好适中。如果使用更简单的文法进行分析，比如限于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的构成规则是上下文无关文法，整个文件不可能用上下文无关文法解决的。

因为最简单的声明变量就是上下文相关的。