logo标签列表

如何在用C语言编写的类FORTH语言解释器中实现循环？

cloopsinterpreterregex-lookaroundsforth
6
我正在用C语言编写一个简单的基于栈的语言，想知道如何实现某种类型的循环结构和/或前瞻符号。由于代码有点长（超过200行），我将其放在GitHub仓库中。
编辑：主程序在stack.c文件中。
编辑：该代码只是使用scanf从左到右处理输入的word，类似于FORTH。然后使用一系列if和strcmp来决定要做什么。就是这样。
6
一句建议：如果代码太长无法在此处发布，那么它很可能对我们来说也过于庞大而难以帮助您。将问题分解为较小的部分并在此处发布。 - paxdiablo
有什么想法可以考虑我的现有代码，来表述这个较小的问题？ - tekknolagi
2
@paxdiablo：实际上，这只是一个简单的线程解释器。代码很长，但并不复杂 - 问题本身已经足够小了。 - Jeremy W. Sherman
4个回答
10
第四种方法是在数据栈旁边添加一个独立的循环栈。然后您定义可与此循环栈一起使用的操作。例如： 
5 0 DO I . LOOP

会打印出来

0 1 2 3 4
这是它的工作方式：
DO 将索引（0）和控制（5）移动到循环堆栈上。 I 将循环堆栈顶部复制到数据堆栈上。 LOOP 增加索引（循环堆栈顶部）。如果索引小于控制（循环堆栈顶部下面的一个值），则重新运行从 DO 到 LOOP 的命令。如果索引大于或等于控制，则将索引和控制从循环堆栈中弹出，并继续正常的控制流程。
1
你可以添加一个静态结构体 loop { double index; double control; size_t buffer_size; char buffer[]; } loopStack;。然后，eval 需要使用缓冲区来保存从 DO 到看到 LOOP 后的所有内容，以便根据 index 和 control 来重放它。 - Jeremy W. Sherman
1
static 表示将变量存储在静态存储区。 loop 是结构体标识符；它使得可以声明其他类型的变量，如 struct loop loop2;。 - Jeremy W. Sherman
2
在Forth中真的有“循环栈”吗？我一直认为它使用返回栈来进行循环。 - Andriy M
2
这是Forth中的I，有很好的惯用理由（并且还有嵌套循环的兄弟J和K），但再次强调：您不会实现任何类似于Forth的东西，因此您称呼循环索引的名称并不重要。 - Julian Fondren
1
没事了，我解决了（所以嵌套的DO-LOOP可以工作！）。只需要在遇到DO时将当前命令堆栈的引用推入循环堆栈即可。我想太多了。我主要是为了练习而在Elixir中编写Forth运行器，这种函数式语言真的很容易编写 :) https://github.com/pmarreck/elixir-snippets/blob/master/rpn_forth_thing.exs（当然还带有内联单元测试套件） - pmarreck
显示剩余10条评论
7

为栈式语言添加控制结构的明显方法是添加一个“控制堆栈”。我将描述Postscript机制，因为那是我所知道的，但Forth具有类似的行为（当然还有微妙的差异）。

最简单的受控循环是repeat循环。严格来说，无限loop更简单，但要使用它需要显式的exit命令，而解释这一点会使事情变得复杂。

repeat的语法如下：

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>
< p > 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！”然后找到一个整数，并将其推送到op堆栈上。
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实际上有一个可以设置cvx cvlit或测试xcheck的文字/可执行标志。执行堆栈上的可执行数组将被执行。因此，对于“引用”的过程体，它实际上是一个“字面量”过程体（即一个数组）。由于这个原因，在下一次迭代之前，repeat也必须推送一个调用cvx的指令。因此，Postscript实现repeat的更正确的伪代码是：
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@的东西。使用单独的继续函数，您就不必在堆栈上仔细处理各种顺序，并且不需要转换文字标志。相反，您可以在执行堆栈上的递归调用下方存储一些持久化数据；但是您也必须清理它。

因此，备选的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运算符与循环密切相关，它清除执行堆栈直到循环运算符的“帧”。对于2函数样式，这是一个null对象或类似对象。对于1函数样式，这是循环运算符本身。

1
将引用过程推送到执行堆栈上。我找不到关于引用过程的任何信息。为什么需要引用？ - juFo
“Quoted” 意味着该过程的字面版本。位于执行堆栈顶部的过程将被执行，但其中一个必须是字面量，以便在下一次迭代中将其推送到操作数堆栈中。 - luser droog
1
@juFo，我添加了更多的后续说明。对于造成的困扰，我很抱歉。 :) - luser droog
2
您的语言与 Forth 非常不相似，因此不要复制 Forth 的（仅编译 - 对于您的语言来说是毫无意义的区别）循环结构。
观察您的代码，将 until 添加为有条件的重新评估单词。也就是说，将其作为普通单词添加到您的 range 和 jump 中，将其弹出堆栈，并且如果堆栈顶部为 true，则设置 stack.c 的 cmd 回到开头。
0
dup . 1 + dup 5 > until
.

在您的语言中，将产生输出0 1 2 3 4 5 6，跨越三个评估，并多次重新评估第二行。这假定您在评估之间保留状态，并且评估是基于行的。您可以从LSE64获取更多类似这样的想法。

1
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接