6

我正在用 C 编写一种简单的基于堆栈的语言，并且想知道我应该如何实现某种循环结构和/或前瞻符号。由于此页面的代码有点长（超过 200 行），我将其放在GitHub 存储库中。

编辑：主程序在文件中stack.c。

编辑：代码只接受输入words，有点像 FORTH。它scanf从左到右使用和工作。然后它使用一系列ifs 和strcmps 来决定要做什么。就是这样。

4

4 回答 4

10

Forth 方法是在数据堆栈旁边添加一个单独的循环堆栈。然后，您定义使用此循环堆栈的操作。例如：

5 0 DO I . LOOP

将打印

0 1 2 3 4

它的工作方式是：

  • DO将索引 (0) 和控制 (5) 移动到循环堆栈。
  • I将循环堆栈的顶部复制到数据堆栈。
  • LOOP增加索引（循环堆栈的顶部）。如果索引小于控件（循环堆栈顶部下方的一个），则它重新运行从DO返回到的命令LOOP。如果索引>=，则从循环堆栈中弹出索引和控制，控制恢复正常。
于 2011-08-04T22:44:22.837 回答
7

将控制结构添加到基于堆栈的语言的明显方法是添加“控制堆栈”。我将描述 Postscript 机制，因为这是我所知道的，但是 Forth 有一些类似的行为（当然，有细微的差别）。

最简单的受控循环是repeat循环。从技术上讲，无限loop更简单，但要使用它需要明确的exit命令，并且解释会使事情复杂化。

重复的语法是：

int proc  **repeat**  -

因此，当repeat命令开始时，它希望在操作数堆栈的顶部找到一个过程（这是要执行的循环体），并在该过程的正下方找到一个整数（执行该过程的次数）。

由于还有一个执行堆栈（我认为 Forth 将其称为“返回”堆栈），一个命令可以通过将其他命令压入执行堆栈来“执行”其他命令，从而调度其他命令在当前命令完成后立即执行，但在恢复当前命令的调用者之前。这是一个很长的句子，但关键的想法就在那里。

作为一个具体的例子，假设解释器是从输入流中执行的。堆栈看起来像这样：

operand: -empty-
execute: <stdin>

用户类型2 {(Hello World!\n) print} repeat。

整数 2 被压入堆栈。

operand: 2
execute: <stdin>

引用的（*）过程主体被压入堆栈。

operand: 2 {(Hello World!\n) print}
execute: <stdin>

repeat命令被执行。

operand: 2 {(Hello World!\n) print}
execute: <stdin> repeat

Repeat: expects operands: int proc
    if int<0 Error
    if int==0 return //do nothing
    push `repeat` itself on exec stack
    push quoted proc on exec stack
    push int-1 on exec stack
    push "executable" proc on exec stack

执行重复过程（一次）会留下这样的堆栈：

operand: -empty-
execute: <stdin> repeat {(Hello World!\n) print} 1 **{(Hello World!\n) print}**

解释器在 exec 堆栈顶部执行过程，打印“Hello World！”，然后找到一个整数，并将其压入操作堆栈。

operand: 1
execute: <stdin> repeat {(Hello World!\n) print}

解释器通过压入操作堆栈来执行引用的过程。

operand: 1 {(Hello World!\n) print}
execute: <stdin> repeat

而我们又回到了起点！准备好进行下一次迭代（如果整数下降到零，则终止）。

希望这可以帮助。

编辑;

在实际查看您的代码之后，我有一个不同的建议，也许是我上面描述的事情的跳板。我认为您应该暂时忘记代码并专注于数据结构。您有一个很好的变量表，但是所有命令都是分散在代码中的嵌入文字！

如果您让表保存可变记录类型，则可以对两者使用相同的查找机制（甚至向上移动到散列或三元搜索树（我目前最喜欢的））。我想到了这样的事情：

struct object {
    int type;
    union {
        int i;
        void (*command)(context *);
    } u;
};

struct dict {
    int sz;
    struct rec {
        char *key;
        object val;
    }  data[]; //think resizable!
};

这样每个命令都有自己的功能。好处是：小功能。您应该尝试使您的功能足够小，以便您可以同时在屏幕上看到整个内容。一次扫描整个事情可以让你的右脑做一些检测问题区域的工作。

然后你需要另一种类型来保存命令序列。数组或列表应该可以工作。当您可以定义序列时，您可以更轻松地重复序列。

这里的好处是你离图灵完备只有一个构造。序列、迭代、决策（或选择）：这就是编写任何可计算函数所需的全部内容！

*。正如评论员所发现的，Postscript 实际上与我在描述中使用的引用概念并不相同。在这里，我从 Lisp 术语中借用了这个概念。Postscript 有一个可以设置或测试的文字/可执行标志。将执行执行堆栈上的可执行数组。所以对于“引用”的过程体，它实际上是一个文字过程体（即一个数组）。因此，还必须在下一次迭代之前推送要执行的调用。所以，一个更正确的 postscript 实现的伪代码是：cvx cvlitxcheckrepeatcvxrepeat

Repeat: expects operands: int proc
    if int<0 Error
    if int==0 return //do nothing
    push `repeat` itself on exec stack
    push 'cvx' on the exec stack
    push cvlit(proc) on exec stack
    push int-1 on exec stack
    push "executable" proc on exec stack

这将执行必要的标志操作，以将过程作为数据传递到执行堆栈上。

我看到实现此控制结构的另一种方法是使用两个函数，repeat相同的入口点和一个理论上不需要名称的内部延续运算符。我认为ghostscript 将其称为@repeat-continue@。使用单独的 continue 函数，您不必对堆栈上的内容顺序非常小心，也不需要旋转文字标志。相反，您可以在 exec 堆栈上的递归调用下方存储一些持久性数据；但你也必须清理它。

所以一个替代方案repeat是：

int proc  **repeat**  -
    if int<0 Error
    if int==0 return //do nothing
    push null on exec stack   <--- this marks our "frame"
    push int-1 on exec stack
    push proc on exec stack
    push '@repeat-continue' on exec stack
    push executable proc on exec stack

延续也有一个更简单的工作。

@repeat-continue
    peek proc from exec stack
    peek int from exec stack
    if int==0 clear-to-null and return
    push '@repeat-continue' on exec stack
    push executable proc on exec stack

最后，exit运算符与循环密切相关，它将 exec 堆栈清除到循环运算符的“帧”。对于 2-function 样式，这是一个null对象或类似的。对于 1-function 风格，这是循环运算符本身。

于 2011-08-05T05:31:41.580 回答
2

你的语言根本不像 Forth，所以不要复制 Forth 的（仅编译 - 对你的语言来说没有意义的区别）循环结构。

查看您的代码，添加until为条件重启评估词。也就是说，将它作为一个普通单词添加到你的rangeand旁边jump，让它弹出堆栈，如果堆栈顶部为真，则将 stack.c 设置cmd回开头。

0
dup . 1 + dup 5 > until
.

，用您的语言，将产生输出0 1 2 3 4 5 6，跨越三个评估，并重新评估第二行几次。这假设您在评估中保留状态，并且评估是面向行的。你可能会挖掘LSE64以获得更多这样的想法。

于 2011-08-05T02:32:38.750 回答
1

这是一篇博客文章，其中 DO/LOOP、BEGIN/UNTIL、WHILE/REPEAT 等在我的小 TransForth 项目中被隐含：http: //blogs.msdn.com/b/ashleyf/archive/2011/02/06/ loopty-do-i-loop.aspx

然而，我后来改变了主意，完全依赖递归，没有这样的循环词。

希望有帮助，玩得开心！

于 2012-08-09T21:34:51.863 回答