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

在过去的几个月里，我一直在用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中，从声明结束的位置(即=号)可以看到声明。