Man*_*iAm 4 compiler-construction infix-notation expression-evaluation shunting-yard
数学表达式通常用中缀表示法表示.出于评估目的,我们可以将其更改为postfix(反向抛光)表示法(使用Shunting-Yard等算法),然后使用堆栈评估后缀表示法.
我发现计算器使用这种技术,但今天的现代编译器是否使用它进行算术表达式评估？它是否足够有效或正在使用其他技术(或算法)？
要回答这个问题,让我们专注于你所提到的概念infix notation,Shunting-Yard并且evaluation然后将它们涉及到编制.
首先我们需要了解典型的计算机如何处理的表达式.表达式转换为抽象语法树(AST),然后用于创建代码.将树转换为代码的过程各不相同,但AST的行走与评估表达式相同.
AST为1 + 2:
+
/ \
1 2
后缀: 1 2 +
这是通过访问左前分支评估1,
客队右支,2,
然后应用操作,+以两个操作数.
AST为1*2 + 3 ^ 4:
+
/ \
^ *
/ \ / \
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
现在,中缀符号是语法糖,使得使用表达式更容易为人类阅读.为了帮助将infix-notation转换为AST,转换算法需要知道运算符的优先级和关联性.该算法还使用堆栈,该堆栈是Shunting-Yard算法的主要关键之一.我所知道的将中缀转换为评估策略的所有方法都以某种方式使用堆栈.
虽然编译器没有像计算器应用程序那样显式地计算表达式,但编译器确实将树的行走转换为将执行评估的代码.
注意:由于我不了解每种语言的每个编译器,因此我只能根据一般概念给出答案.没有规则要求遵循这些规则,如果某些编译器跳过AST并从输入代码转到编译代码而不使用AST,我就不会感到惊讶.
此外,既然你提到了一个编译器,我只讨论了编译代码,而没有触及脚本语言.
现在回到你的问题:
今天的现代编译器是否使用它进行算术表达式评估？
我不会特别使用Shunting-Yard算法,而是使用堆栈的概念,这是我将要使用的算法的关键概念之一.如果使用算法的概念与使用算法相同,您可以自己选择.
它是否足够有效或正在使用其他技术(或算法)？
希望到现在为止你知道这个问题的答案.并非Shunting-Yard算法很重要,但是使用堆栈来转换重要的中缀符号的概念是编译器使用的概念.请记住,编译语言通常不只是计算表达式,它们使用类型,处理条件表达式,存储值,以及创建更高类型,如方法/函数,类和模块.