如何解析表达式

概述

佛法有云：“实相无相，即见如来”。笔者理解，实际上所谓“实相”就是事物的本质，也就是说我们理解事物的本质不能仅从外观或主观感受来臆测，而应该透过其外在表现而达到其本质，就是所谓的“即见如来”。

   那么简单而来说，如果我们想利用一点掌握的编译技术，自主开发一个脚本的解析或解释引擎，应从哪里下手？或则说脚本解释技术的“实相”是什么？

如想入门，个人理解应至少对“递归”的概念和实践有所了解或基本掌握。那么开启这扇大门的钥匙就是对于表达式的解析，毫不夸张地说，对于表达式完美地解析或解释是成功开发类似解释脚本的一半（可能至少是一半）。你在开发的过程中也可体会到运用“递归”的美妙之处。

   什么事表达式？我也曾经千百次地问自己，表达式的准确定义是什么？百度上给出的答案是：

由数字、算符、数字分组符号(括号)、自由变量和约束变量等以能求得数值的有意义排列方法所得的组合。约束变量在表达式中已被指定数值，而自由变量则可以在表达式之外另行指定数值。

个人认为上述的定义算是能基本上表达出了其含义。

   简而言之，表达式就是由算符、常量（可能还有字符串常量）、变量按一定法则进行组合，它最终会有一个值；那么这个法则是什么？很神秘！但其实也不太神秘，所有编译原理的书中都会提到所谓的“算符优先文法”——从直观上讲所谓算符优先文法就是算符可以连续出现在表达式中，而常量或变量不能连续出现，否则就不是合法的“算符优先文法”。就是这么简单！

简单表达式解析

   我们先来看一个简单的例子：

   10-(2+3)

   就是小学生也知道上例是如何计算的！答案是5而不是11，为什么？只要学习过一丁点数学知识的人都清楚括号的优先级是高于其他算符的；那么如果我们用计算机程序来处理应该是怎么样的步骤呢？

   好的，我们先模拟一个所谓叫“堆栈”的东西（有计算机常识的人都知道，堆栈的特点就是“先进后出”或者“后进先出”）；然后我们再构造一个所谓的算符优先表（不太严格），目前它只有几个符号，包括“+”，“-”，“(”，“)”和“#”，而且我们假定“#”默认的优先级最低，这时我们有如下表格（纵向表示算符在左，而横向算符在右）：

   现在我们构造这个堆栈如下：

   初始时，栈底只有算符“#”，为了方便起见我们在表达式10-(2+3)的尾部追加一个符号“#”，解析过程如下：

1.发现输入的不是算符，而是常数10，而且栈顶是“#”，将10入栈；

2.读入算符“-”，由于其优先级高于“#”，进栈；

3.读入“(”，经查表得知当其在右侧时，它比任何算符的优先级都高，故还是将其压入栈中；

4.同理，当程序读入2时也将其入栈；

5.读入“+”时，发现其优先级还是高于栈中的最近一个符号“(”，二话不说，进栈；

6.读入3，入栈；

7.当读到符号“)”时我们发现其优先级是低于栈中最近一个算符“+”，这时计算2+3的值，将得数5再入栈，去成对的括号；

8.读入符号“#”，发现其优先级是低于栈中离它最近的一个算符“-”，计算10-5的值，将结果“5”再入栈；

9.表达式解析完毕，检查栈中是否是仅包含两个元素，其一是得数，其二是原先压入栈中的算符“#”，如果是则解析正确，否则失败！

通过总结上述过程，我们就发现在解析表达式的时候，无非就是做如下几个动作：

1.如是操作数（变量或常量）则进栈；

2.如是算符，则和栈顶（略去操作数）的算符比较优先级；

3.高于则进栈（编译中的术语叫做“移进”）；

4.低于或等于则计算（编译中的术语叫做“规约”）。

四则运算表达式解析

那么上述算法对于更复杂一点的表达式也适用么？当然，现在我们构造一个完整的四则运算的算符优先表，如下：

综合表达式解析

好了，经过上述的分析和实践，我们发现解析一个表达式也不是那么复杂或者令人望而生畏的事！那么，在实际运用中，表达式中还可能出现如下情况：

1.不一定是数值常量，还可能是字符串常量（当然它们一般无法进行算数运算）或变量；

2.算符不仅仅是四则运算的算符，还有可能是关系运算、逻辑运算、赋值运算等等；

3.可能不是简单的变量，而是某个数组的元素；

4.可能不是简单的变量或某个数组的元素，而是函数调用！

好的，对于第一和第二种情况，本节会给出解决方法，而对于后两种情况，由于其状况较为复杂，我们将单独来解决它们。

我们约定字符串常量必须使用双引号括起，如字符串常量中出现双引号，请注意转意（加“\”），否则系统无法识别。

表达式中的变量

其实，其后续的章节中会介绍对于变量和常量处理的不同。可以认为，与常量不同，变量在脚本或程序运行是有“家”的，它的家就是运行时堆栈。

由于作者无意于将此脚本解释或解析系统做得像C/C++那样的强类型语言，而倾向于实现得像Perl那样的弱类型脚本语言即可，故系统内的变量类型只有标量和向量两种；而且在将源代码进行预编译时，系统会将变量的地址进行翻译，但前提是变量必须被定义，这在后续章节中会有描述（处理变量申明语句）。

如果变量未声明而是用的话，系统会在预编译时就给出无法继续的提示，这和一些不用声明就能使用的脚本语言系统不同，请读者务必注意（其实声明的目的也就是为了区分下这些变量是标量还是向量）。

对于变量的样式，一般约定其都是字符开头，可以混合英文字符及数字，长度在一定范围之内，这个可以根据实际需要进行约定。

值得注意的一点是，由于本系统打算支持正则匹配，故也支持类似像$1、$2等的临时正则变量（后续正则匹配临时变量会覆盖前期的正则匹配临时变量，这个同Perl是一样的）。

复杂算符的处理

那么复杂算符是如何处理的呢？

先来看看表达式中还需要处理哪些类型的算符。在上面的章节中，我们讨论了关于算术表达式（即算符只有数学上的四则运算）的处理方法以及遇到表达式中含有变量该如何处理（只是简单地涉及，并未深入），现在我们可以对各类算符进行分类：

1.括号：包括( )和[ ]（数组的下标运算）；

2.算数运算符号：加（+）、减（-）、乘（*）、除（/）、模运算（%），对于乘方、开方等运算，我们并不打算实用算符来解决，而是考虑使用函数，这在今后的章节中会有涉及；而且乘、除的优先级较之加、减更高；

3.关系运算符：包括等于（==）、不等于（!=）、大于（>）、大于等于（>=）、小于（<）、小于等于（<=）、匹配（^）、不匹配（!^）、正则匹配（~）、正则不匹配（!~）；它们之间的优先级是相同的；

4.逻辑运算符：或（||）、与（&&）；其中与的优先级要高于或；

5.赋值运算符：赋值（=）、自加赋值（+=）、自减赋值（-=）、自乘赋值（*=）、自除赋值（/=）、取模赋值（%=）；

6.其它符号：#，优先级最低。

需要说明的一点是，为了简便起见，我们并不打算实现位操作以及和位操作相关的赋值算符，有兴趣的读者可以翻看下C语言相关教材，可以看出位操作的优先级还是非常高的（但是一般要低于算数运算的算符优先级别，按位取反例外）；另外，我们也不打算实现类似“++”或“—”等算符的语法及其语义，因其在一个复杂的表达式中存在一定的二义性。

最后，需要申明的是我们也暂时不打算支持取结构，故取成员运算符“.”（优先级最高）也不会出现在下表中。

经过整理，我们可以得到上述算符的优先级别简表（完整的优先级表过大），此表基本上是按类别进行组织和比较的：

下面我们来看一个较为复杂的表达式解析结果，现假定表达式中出现的变量均已定义，且没有函数调用：

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

可以看出，上述表达式既有算数运算也有关系和逻辑运算，且包含了a、b、c三个变量；由于进行解析或解释时，我们并不知道这些变量的值，因为它们有可能预先定义也有可能是运行时输入的，故在此阶段我们只能把它们解析成更为简单的表达式（可称作中间代码），以便于他人利用其它的工具，如C/C++、Pascal、Basic等高级语言，或者是类似Perl的脚本语言在运行来进一步解释。

上述表达式的解析结果看起来是这样的：

tmp0=c+a

tmp1=b>tmp0

tmp2=tmp1<a

tmp3=b<3

tmp4=a==b

tmp5=tmp3&&tmp4

tmp6=tmp2||tmp5

可能读者会注意到，为什么会多出这么多以“tmp”开头的变量？这实际上是系统在进行规约时自动生成的临时变量；在实际系统中这些临时变量可能会有特殊的标识，以便于和其它普通变量进行区分。

另外，我们在前面提到过，在实际解释时系统会将用户定义变量a、b、c替换为这些变量在堆栈上的相对地址，这就是为什么我们在汇编语言中经常看到类似如下代码的原因：

.globl main

      .type   main, @function

main:  

.LFB1404:

      pushq   %rbp

.LCFI0:

      movq    %rsp, %rbp

.LCFI1:

      movl    $1, -8(%rbp)

      movl    $2, -4(%rbp)

      movl    -4(%rbp), %eax

      addl    %eax, -8(%rbp)

      movl    $0, %eax

       leave

       ret

（上述汇编代码是由gcc4.1.2 在Cent OS5 ，x86 64位平台上生成，与之对应的C源程序如下：

void main()

{

 int a = 1,b=2;

 a = a+b;

}

简单解释下，rbp是堆栈基指针，而-8(%rbp)和-4(%rbp)就是分别存放了变量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

其中，我们约定以“@@”开头的是临时变量，而%sstack[1]存储的是变量a、%sstack[2]存储的是变量b，而%sstack[3]存储的是变量c（我们称sstack为符号栈；当然，一般用户定义的变量是不太可能出现在符号栈sstack的底部附近，而应该是一些环境变量或命令行参数，而且对于一般的x86系统地编译程序而言，只会使用一个主要的堆栈，故临时变量也有可能是存储在其中，或者考虑到运行效率，它们可能就是某些寄存器）。

最终表达式的解析结果被存储在临时变量@@tmp6中（约定，临时变量是不和普通变量存储在一个堆栈中）。

看到这里可能有读者会问，怎么需要那么多临时变量，如果在解释过程中不够用怎么办？放心，对于不同的脚本作用域（scope），临时变量名是可以重用的，在后续章节中会专门阐述这个问题，只需要使用一点点小“技巧”。

另外，其实在解释过程或预编译过程中就将变量的名称用地址进行替换，是绝大多数编译系统或脚本解释系统都会做的，因为这样的好处就在于可以明确区分相同变量名但其作用域不同而出现的混乱——“最近作用域原则”；而且在运行时，可以利用其下标直接访问栈上存储的内容。

当然，上述表达式的解析也并非最优，而且许多编译系统可以对表达式进行优化（存在相同的子表达式），但这已经是所谓的“高级”技术，也不是本文讨论的范围。

最后，简单地说一下，在解析后的表达式中第一个被规约而生成的中间代码就是所谓的“最左素短语”（c+a），这样可以有助于大家理解编译原理中的相关概念。