5

数学表达式通常用中缀符号表示。出于评估目的，我们可以将其更改为后缀（反向抛光）表示法（使用Shutting-Yard等算法），然后使用堆栈评估后缀表示法。

我发现计算器使用了这种技术，但是今天的现代编译器是否使用它来进行算术表达式评估？它是否足够有效或正在使用其他技术（或算法）？

4

1 回答 1

8

要回答这个问题，让我们关注您提到的概念，infix notation然后Shunting-Yard将evaluation它们与编译联系起来。

首先，我们通常需要了解计算机如何处理表达式。表达式被转换为抽象语法树(AST)，然后用于创建代码。将树转换为代码的过程各不相同，但遍历 AST 与评估表达式相同。

1+2 的 AST：

   + 
  / \ 
 1   2

后缀：1 2 +

这是通过访问左分支 、1访问
右分支 、2然后
将运算符 、+应用于两个操作数来评估的。

1*2+3^4 的 AST：

     + 
   /   \
  ^     *
 / \   / \
3   4 1   2

后缀：3 4 ^ 1 2 * +

这是通过访问左分支3^4，
然后访问它的左分支3，
然后访问它的右分支4，
然后访问运算符来评估的^，然后评估3^4并将其作为“+”的新左分支，即 81

然后访问右分支1*2，
然后访问它的左分支1，
然后访问它的右分支2，
然后访问运算符，*并评估1*2并保持它作为'+'的新右分支，即 2

然后访问运算符 ,+并评估81+2并返回结果83

现在，中缀符号是语法糖，使人类更容易阅读使用表达式。为了帮助将中缀表示法转换为 AST，转换算法需要知道运算符的优先级和关联性。该算法还使用一个堆栈，这是 Shunting-Yard 算法的主要关键之一。我所知道的将中缀转换为评估策略的每种方法都以某种方式使用堆栈。

虽然编译器不会像计算器应用程序那样显式地评估表达式，但编译器确实会将用于评估的树的遍历转换为将执行评估的代码。

注意：由于我不了解每种语言的每种编译器，因此我只能根据一般概念给您一个答案。没有要求遵循这些规则，如果某些编译器跳过 AST 并在不使用 AST 的情况下从输入代码转到编译代码，我不会感到惊讶。

另外，由于您提到了编译器，因此我只讨论了编译后的代码，而没有涉及脚本语言。

现在回到你的问题：

今天的现代编译器是否将其用于算术表达式评估？

我不会专门使用 Shunting-Yard 算法，而是使用堆栈的概念，这是我将使用的算法的关键概念之一。如果使用算法的概念与使用算法相同，您可以自己选择。

它是否足够有效或正在使用其他技术（或算法）？

希望现在你已经知道这个问题的答案了。重要的不是 Shunting-Yard 算法，而是使用堆栈转换中缀符号的概念很重要，这也是编译器所使用的。请记住，编译语言通常不仅仅计算表达式，它们处理类型、处理条件表达式、存储值并创建更高的类型，例如方法/函数、类和模块。

于 2013-12-26T13:31:21.567 回答