关于后缀到中缀解析器的建议

Question

我遇到过一种专有的基于堆栈的脚本语言，它看起来像是 x86 ASM 的简化版本。

我用 C++ 为这种语言构建了一个基于堆栈的线性解析器，我希望它能生成伪 C 代码，使该语言更容易阅读。

我至少遇到了一个严重的问题，我觉得这与我的解析器的线性性质有关......例如，假设我们有以下代码：

push const int
push const str
call some_method
pop const str
pop const int
return last return val

使用我当前的实现，我可以很容易地生成以下代码：

retval = some_method(str, int)
return retval

但是以下将是一个主要的痛苦：

return some_method(some_str, some_int)

当我遇到指令/操作码时，我会意识到 -variables- 被推送到堆栈上，但仅此而已......

它归结为我可以从 postfix 转到中缀用于类似指令的组合（例如推送+调用），但不适用于多个指令。

我在语言解析器方面非常缺乏经验，所以对我宽容点！您的建议是什么？

Answer 1

您想要的是符号执行。安排表达式的 C++ 表示形式，例如

class Expression{...};
class StringConstant:public Expression{...};
class FunctionCall:public Expression{...};

然后，使符号堆栈包含 Expression*。然后，当您将

return foo

其编译为

cout<<"return "; foo_expr->print();

每个表达式都有适当的（可能是递归的）打印方法时。

编辑：如果没有return语句，则需要迭代值堆栈，并对所有尚未被消耗的值执行->print。