如何在用C编写的类似FORTH的语言解释器中实现LOOP

Question

我正在用C编写一个简单的基于堆栈的语言,并且想知道我应该如何实现某种循环结构和/或前瞻符号.由于这个页面的代码有点长(超过200行),我把它放在GitHub存储库中.

编辑:主程序存档stack.c.

编辑:代码只是输入words,类似于FORTH.它使用scanf和从左到右工作.然后它使用一系列ifs和strcmps来决定做什么.真的是这样的.

Answer 1

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

5 0 DO I . LOOP

会打印

0 1 2 3 4

这种方式的工作原理是:

• DO 将索引(0)和控件(5)移动到循环堆栈.
• I 将循环堆栈的顶部复制到数据堆栈.
• LOOP递增索引(循环堆栈的顶部).如果索引小于控件(低于循环堆栈顶部的索引),则它会重新运行DO返回的命令LOOP.如果索引是> =,则它会从循环堆栈中弹出索引和控件,并且控制将恢复正常.

Answer 2

将控制结构添加到基于堆栈的语言的显而易见的方法是添加"控制堆栈".我将描述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>

该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}

解释器通过按下op栈来执行引用的过程.

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堆栈清除到循环运算符的"框架".对于双功能样式,这是一个null对象或类似的.对于单功能样式,这是循环运算符本身.