c - 使用 Flex+Bison 识别尾递归函数并将代码转换为迭代形式

Question

我正在编写一个能够接受新函数定义的计算器。意识到新手需要尝试斐波那契等递归函数，我希望我的计算器能够使用 Flex + Bison 识别尾递归函数并将代码转换为迭代形式。我正在使用 Flex & Bison 来完成这项工作。如果您有任何提示或想法，我热烈欢迎。谢谢！

编辑：

我们不用担心 Flex & Bison 的 C 或 C++ 输出。主要是我想要一个想法或提示。谢谢。

Answer 1

正如我在评论中所建议的那样，这对于词法分析器来说根本不是问题，对于解析器来说可能只是轻微的问题。如果你有这样的功能：

func f( a ) 
    if ( a == 0 )  
       return a
    return f( a - 1 )

那么对于典型的 C 编译器，将由优化器/代码生成器将该递归调用转换为循环。当然，在解释性计算器中，您可以更加灵活，但我建议它仍然是应该执行尾调用删除的最后一个过程，而不是第一个。

Answer 2

我一直听到的建议是：如果可以实现尾调用检测，就不要实现尾递归检测。更多的方法以调用另一个方法结束，而不是调用它们自己。

如果您的调用堆栈对最终用户/开发人员并不重要（即，Java 中的尾调用消除会否定堆栈跟踪的大部分价值，除非处理得非常巧妙），那么您应该改用这条路线。

Answer 3

假设你有一个函数......

def func(args)
   #stuff
return func(otherargs)

然后请注意，AST 将具有类似 return -> func -> otherargs 的内容，并带有一些关于类型和其他内容的注释。当你走过它并注意到存在 return F 其中 F 是当前函数框架时，你可以将其转换为 PUSH ARGS、GOTO F，而不是完全形成堆栈框架等等。您必须自己摆弄返回值。

另请注意，如果您想要步行和执行，而不是拥有多通道系统，这将更加困难。我的直觉表明，“即走即走”需要先行一步。

而且，不，如果没有链接解析器，我认为野牛不会为你做这件事。您正在以上下文相关的方式分析语义。