Lib.rs

想法

这是一个具有2个栈（主栈和辅助栈）的堆栈自动机模拟。辅助栈不能直接读取或写入。有两个指令与辅助栈交互：aux('a') 和 main('m')。辅助指令将主栈的顶部元素移动到辅助栈的顶部。主指令则相反，将辅助栈的顶部元素移动到主栈。

名称

名称是对“地下室”和字符的恶作剧。

该语言的每条指令都是一个字符，且该语言基于栈。德语中堆栈自动机（具有栈的自动机）的名字是“Kellerautomat”，可以翻译为“地下室自动机”，因此是char和basement。

为什么这应该是图灵完备的“证据”

具有两个栈的PDA（或至少应该是）图灵完备的。通常可以将读/写头视为位于主栈的顶部。主栈的其他部分是从读/写头留下的所有内容，辅助栈是读/写头右侧的所有内容。这意味着aux指令等同于图灵机中的左移，而main指令等同于右移。

特性

目前这只是一个上述描述的自动机的模拟。也许会添加一些特性，如算术或逻辑指令，使其成为愚蠢的编译目标。然后会有一个命令行标志来关闭“额外”指令。

有一些“不必要的”指令本可以用其他指令实现。例如，w指令可以用aamm实现。目前所有存在的指令（除了+指令）应该是具有访问两个栈的正常PDA能够执行的操作。

示例

在 示例 目录中有一些示例。例如，check_anbncn.chase 文件可以检查输入是否为以下形式：a^nb^nc^n，这是一个上下文相关文法，因此自动机肯定可以做得比普通的PDA更多。如果这个自动机可以检查所有的上下文相关文法显然是无法测试的，但可以检查所有形式为 a^nb^nc^n，a^nb^nc^nd^n... 的文法。

说明

待办：添加所有指令的文档

许可

本项目采用MIT许可，更多信息请见LICENSE。

除非您明确声明，否则您有意提交以供包含的贡献也将采用MIT许可。