3

我编写了一个实验性的函数评估器，它允许我将简单的函数绑定在一起，这样当变量发生变化时，依赖于这些变量的所有函数（以及依赖于这些函数的函数等）都会同时更新。我这样做的方式不是在输入函数时立即评估函数，而是存储函数。仅当请求输出值时，我才评估函数，并且每次请求输出值时都对其进行评估。

例如：

pi = 3.14159
rad = 5
area = pi * rad * rad
perim = 2 * pi * rad

我将“pi”和“rad”定义为变量（嗯，返回常量的函数），将“area”和“perim”定义为函数。每当“pi”或“rad”发生变化时，我都希望“area”和“perim”的结果会发生变化。同样，如果有任何函数依赖于“区域”或“周边”，那么它们的结果也会发生变化。

这一切都按预期工作。这里的问题是当用户引入递归时——无论是偶然的还是有意的。我的语法中没有逻辑——它只是一个评估器——所以我不能为用户提供一种“突破”递归的方法。我想完全阻止它发生，这意味着我需要一种方法来检测它并将有问题的输入声明为无效。

例如：

a = b
b = c
c = a

现在评估最后一行会导致 StackOverflowException（而前两行评估为 '0' - 未声明的变量/函数等于 0）。我想做的是检测循环逻辑情况并禁止用户输入这样的语句。无论循环逻辑隐藏多深，我都想这样做，但我不知道如何去做。

顺便说一句，在幕后，输入字符串通过简单的扫描器转换为标记，然后通过手写递归下降解析器转换为抽象语法树，然后评估 AST。语言是 C#，但我不是在寻找代码解决方案 - 仅逻辑就可以了。

注意：这是我用来了解解析器和编译器如何工作的个人项目，因此它不是关键任务 - 但是我从中获得的知识我确实计划在某些时候投入到现实生活中。你们可以提供的任何帮助将不胜感激。=)

编辑：如果有人好奇，我博客上的这篇文章描述了我为什么要学习这个，以及我从中得到了什么。

4

3 回答 3

6

过去我也遇到过类似的问题。我的解决方案是在通过表达式递归检查语法时将变量名推送到堆栈上，并在退出递归级别时弹出它们。

在我将每个变量名压入堆栈之前，我会检查它是否已经存在。如果是，那么这是一个循环引用。我什至能够在循环引用链中显示变量的名称（因为它们会在堆栈上，并且可以按顺序弹出，直到我到达有问题的名称）。

编辑：当然，这是针对单个公式的...对于您的问题，变量赋值的循环图将是更好的方法。

于 2008-11-26T20:51:00.603 回答
2

一个解决方案（可能不是最好的）是创建一个依赖图。

每次添加或更改函数时，都会检查依赖关系图的循环。

这可以缩短。每次添加或更改功能时，都会对其进行标记。如果评估导致调用被标记的函数，则您有一个循环。

例子：

a = b

  • 标记一个
  • 评估 b（未找到）
  • 取消标记

b = c

  • 标志 b
  • 评估 c（未找到）
  • 取消标记 b

c = a

  • 标志 c
  • 评估一个
  • 评估 b
  • eval c（标记）-> 循环，放弃对 c 的更改！
  • 取消标记 c
于 2008-11-26T20:51:56.577 回答
0

回复对答案二的评论：

（抱歉，刚刚搞砸了我的 openid 创建，所以我必须稍后将旧的东西链接起来......）

如果您将“flag”切换为“push”，将“unflag”切换为“pop”，这几乎是一样的 :) 使用堆栈的唯一优点是您可以轻松地提供有关循环的详细信息，无论什么深度。（对错误消息有用:)）

安德鲁

于 2008-11-26T21:21:04.180 回答