在C++编译过程中,上下文敏感性在哪里得到解决?

lymnna71  于 2023-03-25  发布在  其他
关注(0)|答案(7)|浏览(134)

昨天我问了关于C上下文敏感性的问题,见here。在许多优秀的答案中,这里是被接受的一个,由dmckee
然而,我仍然认为这是有道理的(也许是一些术语上的混淆?)。问题是:编译的哪一部分处理歧义?
澄清我的术语:CFG是在规则的左手边只有一个非终结符的语法(例如A->zC),CSG是在左手边有一个终结符(加上一个非终结符)的语法(aAv->QT),其中大写字母是非终结符,小写字母是终结符。
在解析C
源代码的语法中是否有类似后者的表示?
谢谢你,抱歉把这个问题推给你。

9avjhtql

9avjhtql1#

据我所知(including the one we built)没有一个C前端(解析器、名称/类型解析器)实现了一个上下文敏感的解析器,它使用了你定义的CSG语法规则。
它们中的许多使用自顶向下解析和类型信息的交织收集的组合来区分不明确的情况。
将解析和类型集合编织在一起使得以这种方式构建解析器变得非常混乱和困难,产生了民间定理“C
难以解析”。
像许多这样的“定理”一样,它是不正确的,除非您还坚持将一只手绑在背后进行解析(例如,递归下降,LL(k),LALR [例如,YACC])。如果您使用可以处理二义性的解析技术,那么C语法实际上并不那么难。我们(以及其他解析器,如Elsa C解析器)为此使用GLR解析技术。(我们再进一步,捕获宏定义,C语法中的使用和预处理条件,因为我们对在处理器破坏代码之前转换代码感兴趣;通常预处理器指令在独立的预处理器中被完全分开地处理)。
艾尔莎我认为仍然将歧义解决插入到解析过程中,但是因为解析非常干净,所以这更容易做到。我们的前端构建了一个带有歧义节点的AST,在构建树之后,我们使用属性语法评估器来遍历树以收集名称和类型,并消除那些类型不一致的歧义分支。后者是一个非常漂亮的方案,并且完全解耦了解析和名称解析。
真正困难的是名称解析。C
有一个非常《双城之战》的查找方式,它分布在600页的标准中,并且被各种方言以各种方式弯曲。将名称解析与解析分开使得这个丑陋的事情更易于管理,但民间定理应该是“C++很难进行名称解析”。

nkhmeac6

nkhmeac62#

首先是语言和语法之间的区别。语言是一组字符串。语法是描述一组字符串的一种方式(人们经常说语法“生成”字符串)。一种给定的语言可以由几种语法描述。
最广为人知的语法类型是基于产生式的语法。

  • 不受限制的文法,在产生式的两边可以有任何东西
  • 单调语法,其中左手边最多与右手边一样长
  • 上下文相关,其中仅展开一个非终结符
  • 上下文无关,其中产生式的左手仅由一个非终结符组成
  • 常规语法,其中产生式的左手侧仅由一个非终结符组成,并且产生式的右手侧可以仅具有一个非终结符,作为最新元素。

单调和上下文相关的语法也被称为类型1语法。它们能够生成相同的语言。它们不如类型0语法强大。AFAIK,虽然我已经看到了一些语言具有类型0语法但没有类型1语法的证据,但我不知道任何例子。
上下文无关文法被称为类型2文法。它们比类型1文法更不强大。没有类型2文法而有类型1文法的语言的标准例子是由相等数目的a、b和c组成的字符串集,其中a在b之前,b在c之前。
正则文法也被称为3型文法。它们的功能不如2型文法强大。没有3型文法但有2型文法的语言的标准示例是具有正确匹配括号的字符串的集合。
语法中的二义性是层次结构之外的东西。如果一个给定的字符串可以用几种方式生成,那么这个语法就是二义性的。有明确的类型1语法,也有二义性的类型3语法。
还有其他类型的语法,它们不属于乔姆斯基分类(两级语法,属性语法,树邻接语法......),即使它们是基于产生式的。其中一些甚至能够描述编程语言的语义。
然后是解析算法。这些算法通常基于CFG,并施加更多限制以获得更好的解析速度(解析CSG需要指数时间,CFG需要立方时间,常见算法只需线性时间)。这些限制引入了其他类别的语法。
CSG和单调语法实际上在描述或编译编程语言时用处不大:它们的全局行为并不明显,并且是从局部属性合成的,因此它们很难理解,并且将语义附加到产品是有问题的,解析它们的成本很高-通常是指数级的-并且错误处理很困难。
回到C++。该标准用上下文无关语法描述了 C++ ,但

  • 有歧义(著名的“最令人烦恼的解析”)。所以编译器必须识别歧义并使用正确的解释(即C x();是函数声明,而不是对象定义)。
  • 该语法不是LR(1)(CFG的最著名的子集之一,对于该子集存在线性解析算法)。使用其他算法(可能在时间或空间上更昂贵),或者基于更一般的理论,或者通过对线性算法进行微调以使它们适应C++规则。简化语法并拒绝语义分析中不正确接受的程序也是可能的。
  • 字符串和终端之间的对应关系被修改(主要是通过类型和模板声明,在模板定义中考虑到这一点的需要已经通过使用typenametemplate作为从属名称来解决)。这是通过让词法分析阶段查询符号表来解决的,以便给定的字符串将根据上下文给出一个终端或另一个终端。
  • 还有一些额外的约束(需要声明一些标识符,类型检查,...)用更不正式的英语变体描述。这通常被认为是语义的,即使一些更强大的语法描述可以处理它们。
ffscu2ro

ffscu2ro3#

@伊拉巴克斯特说:
据我所知,没有任何C前端(解析器,名称/类型解析器)(包括我们构建的)使用您定义的CSG语法规则实现上下文敏感的解析器。
Meta-S发行版中有一个上下文敏感的语法,它处理了大量的C
语法分析问题,而不是在语法分析的任何其他阶段。例如-- forward成员数据和成员函数引用可以在内联成员函数中处理,而在语法分析阶段单独处理。
传统的解析在抽象语法树过程中或在编译的其他阶段处理许多CS问题。
所以我的回答是:在“大多数”系统中,二义性是在解析之后处理的。至少在一个系统中,大部分二义性是在解析过程中处理的。因此,“在语法解析C++源代码时,是否有类似后者的表示?”答案是--
是的。至少在Meta-S中,0型CS解析在语法中是可能的。

mm9b1k5b

mm9b1k5b4#

我敢说,任何上下文敏感的问题都应该在语义分析上解决。

i7uaboj4

i7uaboj45#

编译的哪一部分处理歧义?
在构建语法树之后不应该有歧义。所以最终的语法树AFAIK * 应该准备好翻译 *。简而言之,语法分析器应该在推导过程(AKA * 语法分析 *)中解决上下文相关语法(AKA * 歧义语法 *)。

nzkunb0c

nzkunb0c6#

你似乎认为编译器是由严格基于语法的阶段构建的。没有什么比这更远离真相了。语法被用来解析输入的一些比特,然后各种启发式方法被用来解析其他比特,然后更多的语法解析被完成等等。教科书中可爱地描述的理想编译器并不存在。
一个简单的例子是递归下降编译器,它使用一个表驱动的解析器来解析算术表达式,反之亦然。

rqqzpn5f

rqqzpn5f7#

由于没有其他人在加强(并承认我对“真实的的”编译器做什么非常粗略):
像这样的陈述的歧义

B = A();

通过查询符号表来找出语句中任何非关键字、非运算符的类型(这里是BA),并尝试用它们形成一个可接受的赋值。如果找不到这样的安排,则发出一个错误。
这大概是在语法分析过程早期的AST形成期间完成的,但在词法分析完成之后。

相关问题