运算符优先算法

Question

我目前正在为自定义编程语言编写编译器。编译器将每一个操作符或调用转换为一个对象形式

Call : Value
{
  Value instance
  String name
  Value[] arguments
}

例如，表达式3 + 4(= 3.+(4)) 变为

Call : Value
{
  instance = Value(3)
  name = "+"
  arguments = [ Value(4) ]
}

该表达式3 + 4 * 5将由解析器评估为3.+(4).*(5)。

Call : Value
{
  instance = Call
             {
               instance = Value(3)
               name = "+"
               arguments = Value(4)
             }
  name = "*"
  arguments = [ Value(5) ]
}

我知道有一个函数可以在此结构中创建调用列表并按运算符优先级对它们进行排序，结果如下所示：

[ 3.+(4).*(5), 3.+(4) ] （以上表格）

我现在需要的是一种对它们进行排序的算法，以便第一个表达式是3.+(4.*(5)). 关于这个的问题是上面的结果可以有任何长度。我当前的实现（依赖于它是 2 个或更少的中缀运算符）是这样的：

(go through all elements)
{
  current.arguments = [ prev ]
  prev.instance = current.arguments[0]
}

我知道运算符优先级通常是通过 BNF 文件中用于解析器生成的特殊构造来实现的，但是由于我使用的是始终从左到右计算的自定义解析器，因此我无法使用此类解决方案。

Answer 1

一种常见的解决方案是有时称为“调车场”的算法，它使用运算符堆栈。

• 以最低优先级在堆栈上压入标记
• 获得初级
• 找一个操作员
• 如果优先级较低或没有更多运算符，则弹出堆栈并生成代码
• 将运算符压入堆栈
• 循环直到标记是剩下的

我相信你会找到更好的解释，但我就是这样做的。