[资料] 表达式求值

jerryli · 发表于 2016-4-26 11:43

EDA365欢迎您！

您需要登录才可以下载或查看，没有帐号？注册

x

表达式求值是程序设计语言编译中的一个最基本问题。它的实现时栈应用的又一个典型例子。这里介绍一种简单直观、广为使用的算法，通常称为“算法优先法”。
要把一个表达式翻译成正确求值的一个机器指令序列，或者直接对表达式求值，首先要能够正确解释表达式。例如，要对下面的算术表达式求值：
4+2×3-10/5
首先要了解算术四则运算的规则。即：
（1）
先乘除，后加减；
（2）
从左算到右；
（3）
先括号内，后括号外。
由此，这个算术表达式的计算顺序应为
4+2×3-10/5=4+6-10/5=10-10/5=10-2=8
算符优先法就是根据这个运算优先关系的规定来实现对表达式的编译或解释执行的。
任何一个表达式都是由操作数、运算符和界限符组成的，我们称它们为单词。一般地，操作数既可以是常数也可以是被说明符为变量或常量的标识符；运算符可以分为算术运算符、关系运算符和逻辑运算符3类；基本界限符有左右括号和表达式结束符等。为了叙述的见解，我们仅讨论简单算术表达式的求职问题。这种表达式只含加、减、乘、除4种运算符。
我们把运算符和界限符统称为算符，它们构成的集合命名为OP。根据上述3条运算规则，在运算的每一步中，任何两个相继出现的算符θ1和θ2之间的有限关系至多是下面3种关系之一；
θ1<θ2  θ1的优先权低于θ2
θ1=θ2  θ1的优先权等于θ2
θ1>θ2  θ1的优先权高于θ2