将抽象语法树转换为字节码

Question

将抽象语法树转换为字节码

ccompiler-constructionabstract-syntax-treebytecodeinterpreter

4

我目前正在用C语言编写一个小解释器，用于执行我创建的一种语言（这种语言与Python非常相似）。我已经编写了词法分析器和语法分析器，并且现在我的程序可以输出AST。我正在尝试将此AST转换为字节码。目前，我的算法遍历AST（深度优先），并可以为简单的算术表达式生成字节码，而现在我正在尝试实现if语句。

由于我的代码量很大，所以我无法在这里复制所有的代码，但是目前该程序接收一个AST，该AST可能看起来像

ADD
|-- 1
|-- MUL
    |-- 2
    |-- 3

并将其转换为

LOAD 1 //the real code doesn't put the value here, but a number representing the position of this value in an array
LOAD 2
LOAD 3
MUL
ADD

对于简单表达式来说很容易，但是我真的不知道如何为if语句生成字节码。我知道如果比较结果为false，则必须跳转到else从句，并且还必须从每个if / else if块的末尾跳转，但是如果跳转超过256个字节的字节码怎么办？

- dangee1705

1

你的跳跃距离为什么被限制在256个单位内？ - Jongware

由于它是字节码，每个字节都是8位，允许256个字节跳过。 - dangee1705

@BasileStarynkevitch 不过再说，如果我少于256个指令，而我的确是这样的，如果我使用16位字节码，每条指令至少会浪费8位。 - dangee1705

3

@DanielGee：是的，你可以有可变长度的操作码或操作数。例如，相对距离为0显然是无用的，所以您可以有范围为-128..127（不包括0），并将0视为表示“读取两个字节以获取16位数字”的含义。如果这16位的第一个字节为零，则以这种方式编码毫无意义，因此您可以将其视为标志，表示“读取3或4个字节以获取24或32位数字”（取决于您是否认为24位数字好用），等等。或者，您可以只使用FARJUMP等指令。 - torek

你可以使用现有的字节码作为灵感... - Holger

显示剩余5条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Basile Starynkevitch · Accepted Answer

你应该阅读SICP、龙书和小步语法制导的编译器实现。

我希望你能重新设计你的字节码。然后你可以有一些FARJUMP字节码，它后面跟着四个字节a、b、c、d（被视为每个8位的uint8_t无符号整数），你将跳到偏移量(a<<24) + (b<<16) + (c<<8) +d。

你可能想要能够向前和向后跳转。要么有一个BACKFARJUMP来向后跳转，要么使用一些有符号偏移量...

使用这样的操作码，您将能够跳转到超过四十亿个字节码（确切地说是2的32次方）。这可能更容易。

如果四十亿个字节码偏移量不足够，您可以进行概括。

不要忘记，您的计算机不太可能拥有超过1TB的RAM（这样的计算机的价格比一辆汽车还贵）。