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

发布于 2024-08-28 23:43:41 字数 214 浏览 9 评论 0原文

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

编辑：

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

平定天下 2024-09-04 23:43:41

正如我在评论中所建议的，这对于词法分析器来说根本不是问题，对于解析器来说可能只是轻微的问题。如果您有一个类似这样的函数：

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

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

As I suggested in my comment, this is not an issue at all for the lexer, and possibly only slightly so for the parser. If you have a function something like this:

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

then for a typical C compiler it would be up to the optimiser/code generator to convert that recursive call to a loop. Of course, in an interpretive calculator, you can be much more flexible, but I'd suggest that it's still one of the last processes that should perform the tail call removal, not the first ones.

回复收藏 0 原文

反差帅 2024-09-04 23:43:41

假设你有一个函数...

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

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

另请注意，如果您想要边走边执行，而不是使用多通道系统，这将变得更加困难。我的直觉表明，步行并执行需要先行。

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

Suppose you have a function...

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

then note that the AST will have something like return -> func -> otherargs, with some annotations about types and whatevers. When you walk it and note that there exists return F where F is the current function frame, you can transform that into PUSH ARGS, GOTO F, instead of fully forming the stack frame and so forth. You'll have to fiddle the return values yourself.

Also note this will be substantially harder if you want to walk-and-execute, instead of having a multipass system. My instinct suggests that walk-and-execute will require a lookahead.

And, no, I don't think bison will do this for you without chaining parsers. You are analyzing semantics in a context-sensitive fashion.

回复收藏 0 原文