百科问答小站 logo
百科问答小站 font logo



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

  

user avatar   SegFaultCoreDump 网友的相关建议: 
      

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

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

大部分编程语言(或者说编译器)的语法分析部分都是上下文无关文法,这是因为设计者认为上下文无关文法的复杂度恰好适中。如果使用更简单的文法进行分析,比如限于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解释器将不再使用上下文无关文法


user avatar   Ivony 网友的相关建议: 
      

绝大多数编程语言都是上下文相关文法!


但是为了简化处理,也为了更好的提示错误,编译器不会直接用文法处理引擎来解析程序,而是先分解成各种语法单元,然后再逐一处理。这些语法单元就是Token。

为了简化Token的解析,所以Token通常会采用正则文法(如名称、运算符、常量、注释),和上下文无关文法(如表达式、语句)处理。



所谓的语言都是上下文无关文法,他们说的是statement的构成规则是上下文无关文法,整个文件不可能用上下文无关文法解决的。


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




  

相关话题

  为什么要有头文件? 
  中文编程什么时候才能在中国崛起?英文编程是不是总有一个学习转换的过程使慢一拍? 
  为什么大学不教javaScript? 
  如何看待go语言泛型的最新设计? 
  如果计算机是由中国人发明的,那么编程时写代码会是全中文吗? 
  如何从头开始系统学习VHDL语言? 
  你见过哪些令你瞠目结舌的C#代码? 
  准大一,零基础自学C语言,有什么简单易懂的自学书籍和课程推荐吗? 
  如何利用 R 语言来获得某个具体地址的经纬度? 
  我是不是应该放弃 C# 了? 

前一个讨论
欧阳娜娜入职阿里,对其他程序员是否公平?
下一个讨论
为什么叫.NET?它和C#是什么关系?





© 2024-11-21 - tinynew.org. All Rights Reserved.
© 2024-11-21 - tinynew.org. 保留所有权利