运算符优先算法

Question

我目前正在为自定义编程语言编写一个编译器。编译器每单个操作员或呼叫转换为形式

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

例如的目的，表述3 + 4（= 3.+(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

一个常见的解决方案是有时称为“调车场”的算法，该算法使用操作员堆栈。在最低优先级

上堆

• 推标记得到一个主
• 获得操作者
• 如果优先级是低或没有更多的运营商，弹出堆栈和生成代码
• 推操作在栈上
• 循环，直到标记所有剩下的

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