数学表达式通常用中缀表示法表示。出于评估目的,我们可以将其更改为后缀(反向抛光)表示法(使用Shutting Yard等算法),然后使用堆栈评估后缀表示法。
我发现计算器使用这种技术,但今天的现代编译器是否使用这种技术来评估算术表达式?它是否足够有效或正在使用其他技术(或算法)?
要回答这个问题,让我们关注您提到的概念infix notation
、Shunting-Yard
和evaluation
,然后将它们与编译联系起来。
首先,我们需要了解通常计算机是如何处理表达式的。表达式被转换为抽象语法树(AST),然后用于创建代码。将树转换为代码的过程各不相同,但AST的遍历与表达式的求值相同。
1+2:的AST
+
/
1 2
Postfix:1 2 +
这是通过访问左分支1
、
访问右分支2
、
然后将运算符+
应用于两个操作数来评估的。
1*2+3^4:的AST
+
/
^ *
/ /
3 4 1 2
Postfix:3 4 ^ 1 2 * +
评估者访问左分支3^4
,
然后访问其左分支3
,
-然后访问其右分支4
,
1-然后访问运营商^
,以及评估3^4
并将其作为"+"的新左分支,即81
然后访问右分支1*2
,
然后访问其左分支1
,
-然后访问其右分支2
,
1-然后访问运营商*
,并评估1*2
,并将其作为"+"的新右分支,即2
则访问运营商CCD_,并评估CCD_ 20并将其作为结果返回CCD_
现在中缀表示法是语法糖,使人类更容易阅读使用表达式。为了帮助将中缀表示法转换为AST,转换算法需要知道运算符的优先级和关联性。该算法还使用堆栈,该堆栈是调车场算法的主要密钥之一。我所知道的将中缀转换为求值策略的每一种方法都以某种方式使用堆栈。
虽然编译器不会像计算器应用程序那样显式地计算表达式,但编译器会将用于计算的树的遍历转换为预执行计算的代码。
注意:由于我不知道每种语言的每一个编译器,我只能根据一般概念给你一个答案。没有规则要求遵循这些,如果一些编译器跳过AST,从输入代码转到编译代码,而不使用AST,我也不会感到惊讶。
此外,由于您提到了编译器,我只讨论了编译后的代码,而没有涉及脚本语言。
现在回到您的问题:
今天的现代编译器是否将其用于算术表达式评价
我不会特别使用调车场算法,而是使用堆栈的概念,这是我将使用的算法的关键概念之一。如果使用算法的概念与使用算法相同,您可以自己选择。
它是否足够高效或其他技术(或算法)正在习惯于
希望你现在已经知道这个问题的答案了。重要的不是Shutting Yard算法,而是使用堆栈来翻译中缀表示法的概念,这也是编译器所使用的。请记住,编译后的语言通常不仅仅是计算表达式,它们处理类型、处理条件表达式、存储值,并创建更高的类型,如方法/函数、类和模块。