如何解析表达式之二

  关于赋值算符在表达式中的使用

  其实,大家一般不会在一个表达式中使用多个赋值算符,除非不太正常,但其实很多语言的编译或解释系统都允许这样做,关键是如何使用。赋值算符和其它算符明显不同的一点还在于:其它算符均是自左至右进行解析,而赋值算符则恰恰相反!

  我们来看如下一个简单的例子,请你给出判断:这个表达式到底是合法的还是非法的:

  a=3+a*2+b=5

  看到上面这个表达式,我们的第一反应就是书写这个表达式的人可能脑子有问题,怎么能这些用呢?事实上这个表达式也是错误的(大家可以试试,一般系统都会报告类似“无法给常量赋值”等的错误),如果我们改一下:

  a=3+a*2+(b=5)

  这样,这个表达式就是合法的了!为什么?

  因为按算符的优先程度,上式中a*2最先被规约,然后是3+a*2,最后是先对变量b进行赋值,最后规约的效果实际上就相当于:

  a=3+a*2+5

  临时变量的约简

  在上一章的最后部分,提到了一个比较复杂的表达式的解析,即:

  b > c+a < a || a < 3 && a == b

  最终,经过处理的中间代码如下所示:

  @@tmp0=%sstack[3]+%sstack[1]

  @@tmp1=%sstack[2]>@@tmp0

  @@tmp2=@@tmp1<%sstack[1]

  @@tmp3=%sstack[1]<3

  @@tmp4=%sstack[1]==%sstack[2]

  @@tmp5=@@tmp3&&@@tmp4

  @@tmp6=@@tmp2||@@tmp5

  在上一章也提到,这样生成的中间代码并不是十分优雅、简约,虽然我们不需要研究到底如何对代码进行优化,甚至直接使用寄存器来替代临时变量(那是真正编译器干的事,不是脚本翻译研究的对象,时刻记住我们只研究脚本的解析或解释,至于如何使用累加寄存器、边界对齐、机器代码的翻译、运行时内存优化等“高深”课题至少现在不是我们所关心的),但还是有十分简单又比较有效的方法来减少临时变量的数量:如果被规约的表达式中包含了临时变量,那么就使用序号最大的临时变量作为规约的目标。

  经过一点点优化,上述的中间代码就被变换为如下形式:

  @@tmp0=%sstack[3]+%sstack[1]

  @@tmp0=%sstack[2]>@@tmp0

  @@tmp0=@@tmp0<%sstack[1]

  @@tmp1=%sstack[1]<3

  @@tmp2=%sstack[1]==%sstack[2]

  @@tmp2=@@tmp1&&@@tmp2

  @@tmp2=@@tmp0||@@tmp2

  通过上面的例子可以看出,我们仅用了三个临时变量(@@tmp0-@@tmp2)就替代了原来需要七个临时变量(@@tmp0-@@tmp6)的方案,而且效果相同。

  好了,其实本章的主要目的并不是对表达式解析的优化进行深入地探讨,而是主要解决如下两个问题:

  1.表达式中包含了数组元素的操作;

  2.表达式中包含了函数的调用。

  如需要解决上述两个问题,我们就要使用计算机界最为恐怖和逆天的方法,也是计算机科学中无处不在的核心内容之一——递归(Recursive)。

  关于递归,当然有许多非常高级的议题来讨论或研究它,比如令人无法捉摸的而又十分高深的理论课程——《递归论》,或者在《数据结构》中无所不在的基于递归的数据结果或递归算法(如二叉树的遍历、B树的删除等等),抑或是在《编译原理》中的什么左右递归文法!

  好了,本文的目的不是来探讨这些理论问题的,我们还是看看如何使用递归来解决表达式解析的。

  为什么需要在表达式的解析中专门提到数组的处理?在上一章中提到关于算符优先级时,关于符号“[]”就是实际上和数组相关的。

  几乎所有语言的,无论是一般高级语言还是一些通用的脚本语言都会将“[]”作为数组下标来使用。“[]”中不仅可以使用整数常量来存取数组中的元素,而且其中可以使用表达式,表达式即可以是常量表达式也可以是带变量的表达式甚至其中再嵌套其它数组的调用或者函数调用,对于这种复杂的情况我们只有也只能求助于递归。

  需要说明的一点是,我们实现的解释系统中,支持一维数组,而不支持多维数组,其原因很简单——一维数组已经够用了!其实,在C语言中实际上也是如此,Perl也是类似的,即使你想定义一个多维数组也不可得。

  言归正传,下面看一个含有数组的简单表达式的解析情况:

  array[0]+a+b

  它生成的中间代码如下:

  @@tmp0=%sstack[9][0]+%sstack[1]

  @@tmp0=@@tmp0+%sstack[2]

  可以看出,这里数组array中的第一个元素是从下标0开始的,这也是我们的以及大多数语言约定的,而且这个数组变量是其所在函数符号栈的第十个元素(我们约定栈中即可以保存普通的标量,也能够保存向量)。这个例子比较简单,因数组下标是常量,完全没有使用到递归,故其生成的中间代码和普通表达式几乎没有区别,唯有小小的不同点就在于符号%sstack[9][0]表明了这是一个数组,可以理解%sstack[9]存放的不是一般变量的值,而仅仅是数组变量array的首地址而已(第一个元素的地址),其元素的值是存放在其它地方的,这里还不能说明(佛曰:说不得!),得以后在解释脚本是如何运行时再讲。

  以下,再给出一个稍微复杂点的例子:

  array[12+a+b]+a+b

  在这个例子中,我们可以看到其数组下标中含有一个子表达式“12+a+b”,我们知道其实“[]”中所包含的表达式应该是优先被规约的,因为其优先级高,所以如遇到此类数组下标应递归调用表达式解析例程,这样上述表达式的解析结果大致如下所示:

  @@tmp0=12+%sstack[1]

  @@tmp0=@@tmp0+%sstack[2]

  @@tmp1=%sstack[9][@@tmp0]+%sstack[1]

  @@tmp1=@@tmp1+%sstack[2]

  通过上面生成的中间代码可以看出,系统首先是对表达式“12+a+b”进行了规约,并将结果保存在临时变量@@tmp0中,至于后续的解析就不用过多分析了,读者一看就知道大概了。

  表达式中的函数调用

  其实,表达式中包含了函数调用是非常正常的用法,我们在处理这种情况时和处理数组中的表达式其实比较类似,但存在如下几点不同:

  1.函数调用的合法性检查与数组处理存在一定差异;

  2.在处理函数调用时,需要注意处理堆栈中的输入参数、返回值以及返回地址;

  3.在处理函数调用时,需注意处理到底是传值还是传引用。

  下面我们就上述三个需要注意的方面分别介绍。

  函数调用的合法性检查

  在系统遇到函数调用时,需要进行合法性检查,其主要检查的方面无非是:

  1.函数是否定义?

  2.函数参数的类型是否匹配?

  对于第一个方面,函数是否定义的问题,我们可以这样的顺序查找一个函数是否定义:

  1.该函数是否是系统内置函数?

  2.该函数是否是本脚本或程序文件定义函数?

  3.该函数是否在其它库文件中被定义?(脚本中需要使用相关的语句进行引用,例如“use xxx”)

  如果根据上述查找顺序仍不能查到,则报错,否则将查到的函数地址(这个地址实际上是中间代码的行号,后面在阐述多文件解析时会给出如何翻译)。

  对于参数类型的检查,幸好我们所做的不是强类型语言,故在这方面我们只要把握好参数是标量还是向量即可,其它的可以推迟到运行阶段(例如如果某个函数的参数要求必须是数值,但你却传递的是字符串,那么在解释或编译时倒是不一定非要进行检查,待到运行时给出异常或者像Perl一样给出“undef”也可)。

  函数调用与堆栈使用

  一般而言,系统都是利用堆栈来传递输入参数、返回值并且保存返回地址的,但也不排除在一定情况下,直接使用寄存器来保存上述这些内容,但在我们的实现中,只考虑模拟堆栈来解决函数的调用和返回。

  在很多高级语言中,在将参数压入堆栈时,只有两种做法(也只能有两种),一种是将参数自左至右压入堆栈,而另外一种则正相反,即将参数自右至左压入堆栈;在高级语言中,Pascal是采用前者,而采用后者的则更多,利于C/C++(当然也可以使用第一种参数入栈方式,但需要特殊声明)。

  需要说明的一点是,我们打算单独使用堆栈来处理函数的调用,这和一般的高级语言的处理方式还是存在一定的出入。

  传值还是引用

  我们知道,在Java的函数调用中,一般都是传递的对于变量的引用,这样做的好处就是可以获得多个返回值,而且可以节省堆栈空间。

  所以,在本文所提到的函数调用中,一般参数也都是引用方式(当然,如果参数只是变量就可以使用引用,但如果它是普通表达式或者常量就没法使用引用了)。

  那么,下面就给出例子来说明如何来处理是传值还是传递引用。

  函数调用解析

  好了,经过上面的一串说明,我们终于可以处理函数调用了,下面给出一个例子来说明函数调用在表达式中的处理以及如何翻译成中间代码:

  a    +(22+array[12+a+b])+25.2+fun(f(a+b),sin(a),b,c,log(d))+(x+(y+z))

  上面是一个较为复杂的表达式,它既含有普通的算符,又包含了数组和函数调用,而且数组下标中也是表达式,而函数调用的参数中既包括普通的变量,也包括了表达式以及嵌套的函数调用。

  我们假定fun、f是用户自定义函数,而sin、log是系统内置函数,a、b、c、d、x、y和z都是用户定义的变量,25.2是个浮点类型的常数,最终得到的中间代码可能是这样的:

  @@tmp0=12+%sstack[1]

  @@tmp0=@@tmp0+%sstack[2]

  @@tmp1=22+%sstack[9][@@tmp0]

  @@tmp1=%sstack[1]+@@tmp1

  @@tmp1=@@tmp1+25.2

  @@tmp2=%sstack[1]+%sstack[2]

  call,f,@@tmp3,@@tmp2

  call,sin,@@tmp4,%sstack[1]

  call,log,@@tmp5,%sstack[4]

  call,fun,@@tmp6,@@tmp3,@@tmp4,%sstack[2],%sstack[3],@@tmp5

  @@tmp6=@@tmp1+@@tmp6

  @@tmp7=%sstack[6]+%sstack[7]

  @@tmp7=%sstack[5]+@@tmp7

  @@tmp7=@@tmp6+@@tmp7

  在上述生成的中间代码中,我们可以但到,如果数组下标或者函数参数中包含了表达式,则首先回递归调用表达式解析过程进行处理;我们将函数调用翻译成如下的中间代码形式:

  call,function name,returnedvalue,argument0,…,argumentn

  当然,我们可以将function name替换成所需要的函数地址,如下:

  call,function address,returnedvalue,argument0,…,argumentn

  其中,如果函数是系统内置、其它库函数或者用户自定义函数,则其地址可以增加一个前缀来表示,例如“###System::”;使用“###”就是告诉脚本解析器这个函数需要从其它库中来寻找,而不是本脚本文件定义的函数;另外,与其它脚本语言或者高级语言类似,用户也需要注意库的搜索路径,这个问题会在脚本的运行阶段来解释。

  如果不过考虑的中间代码的兼容性,其实只使用名字来查找也是不错的,至少这样看来更加直观(这个理念更加接近于动态库的概念,即无论库的版本如何修改,只要这个函数仍然存在我就可以使用),只不过这样做的话会略微降低一点脚本在运行时的效率(需要根据库文件的函数名与函数地址表进行查找)。

  另外,需要说明的是通过观察生成的中间代码,我们也可以轻易地区分出,哪些参数需要传值,哪些需要传递引用,如上述中间代码中的一行:

  最后,如果函数的参数是可变的(类似C语言中的printf函数),那么我们也需要小心处理这种样式。

  表达式解析的完整算法

  以下是表达式解析完整算法的伪代码;其中AnalysisStack就是在表达式分析时所使用的堆栈,expression是待分析的表达式串,GetNextToken是从输入串中获取算符或者操作数(变量、常量或者是函数调用):

  Initializethe AnalysisStack;

  Push ‘#’into the AnalysisStack;

  Add ‘#’to the end of expression;

  While(NotEof(expression) )

  {

  Token = GetNextToken();

  If ( Token is a common operand )

  {

  Checkvalidation of operand(if it is a valid constant or defined variable);

  Push Token into the AnalysisStack;

  }

  Else

  If ( Token isa function call )

  {

  Check thevalidation of function call;

  Resolve thearguments;

  Result = Recursivecalling the expression parser according to each argument;

  Push Result into the AnalysisStack;

  }

  Else

  If ( Tokencontains array )

  {

  Check validation of array;

  Result = Recursivecalling the expression parser according to its index;

  PushResult into the AnalysisStack;

  }

  Else

  {

  #The tokenis an operator

  PreOperator= Get the operator at the top of the AnalysisStack;

  If ( GetPriority(Token)<= GetPriority(PreOperator) )

  {

  Right =Pop from the AnalysisStack;

  PreOperator = Pop from the AnalysisStack;

  Left = Popfrom the AnalysisStack;

  Generatethe intermediate code, like tmpvar = Left PreOperator Right;

  Push tmpvar into the AnalysisStack;

  }

  Push Tokeninto the AnalysisStack;

  }

  }

  If (SizeOf(AnalysisStack) != 2 )

  {

  Error;

  }

  Else

  {

  Return (Pop from the AnalysisStack);

  }

  关于上述算法,有几点值得注意:

  1.关于字符串的处理:需要将字符串作为整体的Token来处理;由于字符串中可能包含任何字符,故需小心处理,包括对于字符串中也包含双引号(本文约定双引号是字符常量的界符)的情况;

  2.关于注释的处理:本节暂不做讨论,在后续章节中讨论复合语句解析时再进行;但值得注意的一点是注释可以出现在任何的算符之间或者算符和操作数之间,而不能横亘在操作数内,否则会认为注释是常量或变量的一部分,从而导致错误;

  3.关于回车换行的处理:回车换行不会作为脚本解析的分隔符号;其它与注释类似,即回车换行可以出现在任何的算符之间或者算符和操作数之间;

  4.关于临时变量的生成和存储:本节暂不作讨论(既可以存放在符号栈上也可以单独存储),待后续章节再继续阐述这个话题。

  小结

  通过上述章节的讲解和示例,我们基本上掌握了如何解析或解释一个较为复杂的表达式,其实其核心也无非如下两点:第一需要搞清楚各种算符的优先级别,当然也可以自己发明算符;第二善于使用递归的方法将复杂的问题简单化、重复化。

  关于递归,在后续的章节还需要经常出场,包括对于复合语句的解析等等,故希望能熟练掌握并多加练习(当然不要搞得老是堆栈溢出),大家可以尽量考虑用递归来改写一些循环语句做的工作。

  另外,值得注意的一点是在有些语言中,可以在表达式中直接声明变量,但我们并不打算这样做。

  最后,对于逗号运算符(在一般高级语言或脚本语言中,与它的优先级实际上是低于赋值运算符的),我们也并不打算支持,但读者应该知道在这种情况下,逗号运算符是可以将多个子表达式分隔开,整个表达式的值就是最后一个表达式的值,如下:

  假定:b=2,c=7,d=5,

  a1=(++b,c–,d+3);

  a2=++b,c–,d+3;

  那么,a1等于8,而a2却等于3。

 

发表评论

邮箱地址不会被公开。 必填项已用*标注