Brainfuck 以其极小的编译器而闻名。我有一个非常小的设备，它的数据可能甚至无法容纳最小的 Brainfuck 编译器。有没有一种深奥的编程语言，它的编译器比 Brainfuck 还要小，并且是一种图灵完备的语言？ 这已经过时了，但请随时提出您自己的答案，我会检查
问问题
2762 次
6 回答
6
我查看了 Brainfuck 编译器的大小（原始形式约为 240 字节），我怀疑你会变得更小，它旨在生成尽可能小的编译器（诚然，很多年前）。
虽然，来自维基百科：
除了两个 I/O 命令外，brainfuck 是 Corrado Böhm 在 1964 年创建的正式编程语言 P'' 的一个小变种。事实上，使用六个符号相当于各自的 Brainfuck 命令 +、-、<、>、[ , ], Böhm 为每个基本函数提供了一个明确的程序，这些基本函数共同用于计算任何可计算函数。因此，在非常真实的意义上，第一个“头脑风暴”程序出现在 Böhm 1964 年的论文中——它们是足以证明图灵完备性的程序。
从P'' 页面：
P'' 是第一个被证明是图灵完备的“无 GOTO”命令式结构化编程语言。
因此，P'' 的编译器或等效的 Brainfuck 的更改版本会更小，并且仍然可以完成。
但是，如果我不遵循问题的精神，那么设备本机指令集将是图灵完备的。汇编器可能太大，但您可以直接将操作码值写入可执行文件或“编译”为可执行文件的文本文件。那个“编译器”可能会更小。尽管它不是任何真正意义上的编译器，因此不遵循问题的精神。
这是一个现实世界的问题吗？如果你没有编译器的空间，那么你的源代码和二进制文件会去哪里？
于 2014-04-05T04:11:15.973 回答
1
MiniMAX
这是 MiniMAX 的完整 DOS .COM 可执行解释器：
MOV SI,010E # 3 bytes; 010E is the byte after the RET line
MOV DI,SI # 2 bytes
MainLoop: # assembler directive, 0 bytes
MOVSW # 1 byte
LODSW # 1 byte
ADD SI,AX # 2 bytes
XCHG SI,DI # 2 bytes
JNZ MainLoop # 2 bytes
RET # 1 byte
<append program to interpret here>
# Total: 14 bytes
您的设备可能没有完全相同的指令集，但我无法想象它会如此不同。可能还不到 20 个字节。
缺点是做任何有用的事情的 MiniMAX 程序都相当长，但如果你的唯一目标是在芯片上安装一个 TC 解释器，这将为你完成。
于 2021-04-02T18:12:30.070 回答
1
我发现使用 lambda 表达式以二进制形式 ( BLC ) 表示的最小 BF 编译器。
解释器正好是 112 个字节（这是 iirc。BF 本身中 Hello World 程序的确切字节数）。
于 2017-09-08T14:28:50.570 回答
0
TinyBF的指令数量是 BF 的一半，因此为它创建编译器应该更简单。
= Switch direction (- <-> +) (default: +)
+ Change data in selected direction. BF equivalents: - +
> Change cell in selected direction. BF equivalents: < >
| Jump in selected direction. BF equivalents: ] [
== Output. BF equivalent: .
|=| if switch is positive, =|=| if switch is negative. Input. BF equivalents: ,
还有许多其他类似于 BF的语言也可能是可行的选择。
于 2016-02-26T18:13:22.017 回答
0
另一个候选者是 J. Lambek (1961) 的无限算盘。具有条件跳转的 P" 机器的前身。
无限数量的计数器和两条指令：
n+: 在位置 n 处递增计数器。n- else p: 如果位置 n 的计数器为正减量，否则跳转到指令 p。
您可以轻松地n用 Böhm 的>and替换地址<，但我认为编译器需要更多字节（指令越少，情况越少）。
您也可以用直接寻址替换 P" 的>and<以减小编译器大小。
另一个候选者是H. Wang 的 B 机：具有不可擦除无限磁带的图灵机。
四指令：
- 向右移动磁带头并继续下一个指令
- 向左移动磁带头并继续下一条指令
- 标记当前磁带单元并继续下一条指令
- 如果当前点击单元被标记，则跳转，否则继续下一条指令
您当然可以使用条件循环而不是条件跳转来定义变体，而不会失去图灵完整性。
我不知道 C 中这些编译器的大小，但汇编中的解释器肯定更小。
缺点是内存大小，尤其是王的一次写入磁带。
于 2018-09-05T07:46:24.390 回答