在C语言中如何处理左递归语法

2020-11-07 11:06:14

在过去的几个月里,我一直在用C语言编写一个C编译器,这是一次非常困难的经历。我这么做是为了看看能不能把《龙》这本著名的书中提到的理论概念用上,其中有几个让我有点摸不着头脑。

所以我做了一个小程序,简单地声明了`x`,并给它赋值,这个值是`x`的乘法。

这是可以编译的,但我想知道编译器如何决定在RHS上设置‘x’的值来消除它的递归。

我的编译器可以在这里找到。我正在把它写在我的自述文件中:https://github.com/AlysonBee/C_Compiler/blob/master/README.md。

第一级,int x=x*42;是否有效(或者如果有效,它的语义是什么)与一种语言的语法是否保持递归无关。事实上,任何左递归语法都可以重写成不是左递归的,而不会改变什么是语法有效的,什么是不是语法有效的。

在任何语言中,如果允许变量声明的形式为int x=Expression;并且允许x*42作为有效的表达式,则int x=x*42;在语法上是有效的。然而,在许多语言中,这将是在语义分析阶段捕捉到的作用域错误。不过,这取决于语言的作用域规则,而不是语法。

在C的特定情况下,int x=x*42;不是作用域错误(x在=右侧的作用域中),而是在运行时调用未定义的行为,因为x在未初始化的情况下使用。在这种情况下,常用的C编译器将发出警告(假设您启用了警告),因此您的C编译器可能也应该发出警告。

级别2那么在实践中,理解消除左递归的概念的重要性是什么呢?这是否只有在您从头开始设计自己的语言时才适用呢?C似乎很好地处理了这个问题,但我看不出自己如何处理未初始化的变量。但话又说回来,在汇编阶段,我想象该值的寄存器中只有随机数据。这样的假设准确吗?

级别1不确定这里有什么问题。这与语法无关,这是合法的语法。

但是,根据是否有任何单独的传递来对表达式类型等进行排序,解析器需要确保在类型为';int;的符号表中提供';x';,以便能够处理后面的x*42表达式。

您可能希望您的编译器注意到的唯一问题是,在赋值之前使用';x;的值。但在我尝试的六个编译器中,没有一个在使用默认选项运行时报告了这一点。

级别2:那么,了解消除左递归有什么用处呢?我以为这就是答案,但它看起来相当直截了当。?

级别1阅读您的链接时,我有点担心您的词法分析方法(也没有提到解析)。例如,当您看到";{";时,您谈到通过它是否跟在";==";后面来确定它的含义(对于复合语句或数据)。

通常情况下,当你遇到一个声明时,你就会知道自己是否处于声明之中。但我相信你列出的书里一定会提到这一点。

级别2,所以我认为这在很大程度上归因于我没有使用编译器的经验。我采用的方法是将我的程序分成多个单独的块(因此,单个块将类似于";char*str=";Hello world;;";而另一个块将类似于";int main(int argc,char**argv){";因为这些块是可以求值的块。

因此,这个问题源于这样一个事实:函数定义以";){";(就像上面的";main&34;定义一样)结尾,但数组以";{";,

因此,在我创建这些块的过程中,";{";导致歧义,这迫使我检查它周围的标记。

另外,语义分析不是解析过程的一部分吗?我有没有别的办法可以做到这一点?我想不出其他的办法了。

级别1有一种停止递归的通用技术(当然,假设您想这样做):历史跟踪或跟踪。基本上,您可以向所有参与函数添加一个辅助参数,该参数包含您已经处理过的所有案例的纯函数列表。即使是新的案例也会在执行任何操作之前被添加到列表中,除非它已经在列表中了,在这种情况下,您已经开始重复自己,并且可以停止递归。

如果您事先设计数据结构来处理这种情况,并且愿意使用突变,那么有一种更有效的方法来实现这一点:您只需在数据结构的节点上翻转一个标志,表明它已经被访问。事实上,这是标记清除垃圾收集器的基本工作方式。

在更特殊的情况下,可能存在更有效的解决方案。我在我的编译器中广泛使用跟踪。添加和检查踪迹的时机和地点非常关键,而且很难正确处理。

第一级,如果你在做一个静态类型的编译器,它应该编译失败,因为它应该使用在这条语句之前声明的x(没有)。

级别2根据C语言的规则,它不应该编译失败(也不应该使用现有的C编译器)。它应该编译良好(但理想情况下带有警告),然后在运行时做任何它想做的事情(因为行为是未定义的)。

请注意,即使在外部作用域中已经有了x的初始化定义,行为也是未定义的。Int x中的第二个x=x*42;总是指此行上定义的x,而不是其他地方定义的其他x。

级别2在C中,从声明结束的位置(即=号)可以看到声明。