据我所知(including the one we built)没有一个C前端(解析器、名称/类型解析器)实现了一个上下文敏感的解析器,它使用了你定义的CSG语法规则。 它们中的许多使用自顶向下解析和类型信息的交织收集的组合来区分不明确的情况。 将解析和类型集合编织在一起使得以这种方式构建解析器变得非常混乱和困难,产生了民间定理“C难以解析”。 像许多这样的“定理”一样,它是不正确的,除非您还坚持将一只手绑在背后进行解析(例如,递归下降,LL(k),LALR [例如,YACC])。如果您使用可以处理二义性的解析技术,那么C语法实际上并不那么难。我们(以及其他解析器,如Elsa C解析器)为此使用GLR解析技术。(我们再进一步,捕获宏定义,C语法中的使用和预处理条件,因为我们对在处理器破坏代码之前转换代码感兴趣;通常预处理器指令在独立的预处理器中被完全分开地处理)。 艾尔莎我认为仍然将歧义解决插入到解析过程中,但是因为解析非常干净,所以这更容易做到。我们的前端构建了一个带有歧义节点的AST,在构建树之后,我们使用属性语法评估器来遍历树以收集名称和类型,并消除那些类型不一致的歧义分支。后者是一个非常漂亮的方案,并且完全解耦了解析和名称解析。 真正困难的是名称解析。C有一个非常《双城之战》的查找方式,它分布在600页的标准中,并且被各种方言以各种方式弯曲。将名称解析与解析分开使得这个丑陋的事情更易于管理,但民间定理应该是“C++很难进行名称解析”。
7条答案
按热度按时间9avjhtql1#
据我所知(including the one we built)没有一个C前端(解析器、名称/类型解析器)实现了一个上下文敏感的解析器,它使用了你定义的CSG语法规则。
它们中的许多使用自顶向下解析和类型信息的交织收集的组合来区分不明确的情况。
将解析和类型集合编织在一起使得以这种方式构建解析器变得非常混乱和困难,产生了民间定理“C难以解析”。
像许多这样的“定理”一样,它是不正确的,除非您还坚持将一只手绑在背后进行解析(例如,递归下降,LL(k),LALR [例如,YACC])。如果您使用可以处理二义性的解析技术,那么C语法实际上并不那么难。我们(以及其他解析器,如Elsa C解析器)为此使用GLR解析技术。(我们再进一步,捕获宏定义,C语法中的使用和预处理条件,因为我们对在处理器破坏代码之前转换代码感兴趣;通常预处理器指令在独立的预处理器中被完全分开地处理)。
艾尔莎我认为仍然将歧义解决插入到解析过程中,但是因为解析非常干净,所以这更容易做到。我们的前端构建了一个带有歧义节点的AST,在构建树之后,我们使用属性语法评估器来遍历树以收集名称和类型,并消除那些类型不一致的歧义分支。后者是一个非常漂亮的方案,并且完全解耦了解析和名称解析。
真正困难的是名称解析。C有一个非常《双城之战》的查找方式,它分布在600页的标准中,并且被各种方言以各种方式弯曲。将名称解析与解析分开使得这个丑陋的事情更易于管理,但民间定理应该是“C++很难进行名称解析”。
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();
是函数声明,而不是对象定义)。typename
和template
作为从属名称来解决)。这是通过让词法分析阶段查询符号表来解决的,以便给定的字符串将根据上下文给出一个终端或另一个终端。ffscu2ro3#
@伊拉巴克斯特说:
据我所知,没有任何C前端(解析器,名称/类型解析器)(包括我们构建的)使用您定义的CSG语法规则实现上下文敏感的解析器。
Meta-S发行版中有一个上下文敏感的语法,它处理了大量的C语法分析问题,而不是在语法分析的任何其他阶段。例如-- forward成员数据和成员函数引用可以在内联成员函数中处理,而在语法分析阶段单独处理。
传统的解析在抽象语法树过程中或在编译的其他阶段处理许多CS问题。
所以我的回答是:在“大多数”系统中,二义性是在解析之后处理的。至少在一个系统中,大部分二义性是在解析过程中处理的。因此,“在语法解析C++源代码时,是否有类似后者的表示?”答案是--
是的。至少在Meta-S中,0型CS解析在语法中是可能的。
mm9b1k5b4#
我敢说,任何上下文敏感的问题都应该在语义分析上解决。
i7uaboj45#
编译的哪一部分处理歧义?
在构建语法树之后不应该有歧义。所以最终的语法树AFAIK * 应该准备好翻译 *。简而言之,语法分析器应该在推导过程(AKA * 语法分析 *)中解决上下文相关语法(AKA * 歧义语法 *)。
nzkunb0c6#
你似乎认为编译器是由严格基于语法的阶段构建的。没有什么比这更远离真相了。语法被用来解析输入的一些比特,然后各种启发式方法被用来解析其他比特,然后更多的语法解析被完成等等。教科书中可爱地描述的理想编译器并不存在。
一个简单的例子是递归下降编译器,它使用一个表驱动的解析器来解析算术表达式,反之亦然。
rqqzpn5f7#
由于没有其他人在加强(并承认我对“真实的的”编译器做什么非常粗略):
像这样的陈述的歧义
通过查询符号表来找出语句中任何非关键字、非运算符的类型(这里是
B
和A
),并尝试用它们形成一个可接受的赋值。如果找不到这样的安排,则发出一个错误。这大概是在语法分析过程早期的AST形成期间完成的,但在词法分析完成之后。