lispscheme果壳_(Scheme(Lisp))解析表达式，就这么简单

什么是表达式&＃xff1f;

计算机如何表达和计算一个算术表达式&＃xff1f;

搞懂了这个问题&＃xff0c;我们也就弄清楚了如何去解析一个算术表达式。甚至再多学一点&＃xff0c;就可以写一个可以进行简单编程的计算器。

一个表达式就是一个顺序表list&＃xff0c;是一个由操作数(Operand, 算数)和操作符(Operator, 算符)按某种顺序组合起来的序列。

表示一个算术表达式的方法通常有三种&＃xff0c;前缀表达式&＃xff0c;也称为波兰表达式、中缀表达式&＃xff0c;也就是我们人类常用的这种&＃xff0c;后缀表达式&＃xff0c;也称为逆波兰表达式。前缀表达式&＃xff0c;顾名思义&＃xff0c;就是操作符置于其对应的操作数的前面的表达式&＃xff0c;而后缀表达式则是操作符置于对应的操作数之后的表达式&＃xff0c;中缀则不用说&＃xff0c;学过小学数学的人都知道。

解析表达式&＃xff0c;就是要将它的的各项和各个运算符逐个读入内存&＃xff0c;然后构造某种数据结构(通常是表达式树)将它们关联和表达出来。

表达式树的特点是&＃xff1a;叶节点上存放操作数&＃xff0c;而内部节点存放操作符&＃xff0c;一个操作符的子树是它的一个子表达式(求值之后便是它的操作数)。构建好表达式树之后&＃xff0c;通过不同的遍历算法即可生成不同的表达式。对表达式树执行前序遍历&＃xff0c;生成的是前缀表达式(操作符置于操作数之前)&＃xff1b;对表达式树执行中序遍历&＃xff0c;生成的是中缀表达式&＃xff1b;对表达式树执行后序遍历&＃xff0c;生成的是后缀表达式&＃xff1b;

下面是一些表达式树

和对应的中缀表达式

1 &＃43; 2

2 * (3 &＃43; (3 &＃43; 1))

(((1 / 2) * 3) - 4) &＃43; 5

等价的前缀表达式

&＃43; 1 2

* 2 &＃43; 3 &＃43; 3 1

&＃43; - * / 1 2 3 4 5

以及等价的后缀表达式

1 2 &＃43;

2 3 3 1 &＃43; &＃43; *

1 2 / 3 * 4 - 5 &＃43;

看上去前缀表达式和后缀表达式比较复杂&＃xff0c;而中缀表达式则较为简单。但事实上&＃xff0c;对前缀和后缀两种表达式的求值比对中缀表达式的求值简单得多。这是因为前置和后置的操作符保证了操作符与操作数结合的唯一性。总之&＃xff0c;前缀表达式和后缀表达式是没有歧义的表达式&＃xff0c;而中缀表达式则是一种有歧义的表达式&＃xff0c;所以需要借助括号和算符结合的优先级来消除歧义。正所谓抓住了树根&＃xff0c;你就抓住了一切&＃xff1b;

抓住了叶子&＃xff0c;你就得一片叶子。

在现代计算机中&＃xff0c;中缀表达式通常用于编写人类可读的源代码&＃xff0c;例如大多数的编程语言的表达式都是中缀表达式。不过&＃xff0c;也有使用前缀表达式进行编程的语言&＃xff0c;比如汇编语言。为什么是是这样呢&＃xff1f;因为前缀表达式就像是一条条的命令&＃xff0c;这样的命令适合机器一步步的执行&＃xff0c;而中缀表达式更适合人类的书写和阅读习惯。

表达式的求值

求值(evaluate)&＃xff0c;是常见于编译原理和编程语言相关领域的一个术语&＃xff0c;表示计算并返回一个表达式或一段程序的结果。

如果已经有了该表达式的表达式树&＃xff0c;我们可以直接对表达式树进行求值。由于树本身的自相似结构&＃xff0c;以及树的遍历通常要用到递归或栈&＃xff0c;使用递归函数对表达式树进行求值是最简单的方式。该递归函数的特点是对每一个节点&＃xff0c;判断它是操作数还是操作符。如果是操作数&＃xff0c;直接返回&＃xff1b;如果是操作符&＃xff0c;那么就递归地计算它的各个子项(操作数)&＃xff0c;再用该操作符把各个操作数计算出来并返回。

当然&＃xff0c;直接使用一个栈对表达式进行求值亦可&＃xff0c;就像借助栈来对树进行非递归的遍历一样。下面讲述如何对前缀、中缀和后缀三种的四则运算表达式进行求值。在之后的表达式树的生成一节中&＃xff0c;将会讲解如何解析一个表达式生成它的表达式树。

前缀和后缀表达式的求值算法比较简单&＃xff0c;中缀则较为困难。首先来看下后缀表达式的求值过程&＃xff0c;

;;; 判断 elem 是否在 elems 中

(define(in elem elems)

(if(atom? elems)

(eqv?elems elem)

(if(null?elems)

#f

(or(in elem (carelems))

(in elem (cdrelems))))))

(defineeval-suffix

(lambda(expr)

(defineoperator? (lambda(elem) (in elem &＃39;(&＃43; - * /))))

(letloop ([expr expr][stack &＃39;()])

(if(null?expr)

(carstack)

(let([elem (carexpr)]

[expr (cdrexpr)])

(if(operator? elem)

(let([op (evalelem)]

[first-operand (cadrstack)]

[second-operand (carstack)]

[stack (cddrstack)])

(loop expr (cons(op first-operand second-operand) stack)))

(loop expr (conselem stack))))))))

(printf "~a\n" (eval-suffix &＃39;(1 2 &＃43;))) ; 3

(printf "~a\n" (eval-suffix &＃39;(2 3 3 1 &＃43; &＃43; *))) ; 14

(printf "~a\n" (eval-suffix &＃39;(1 2 / 3 * 4 - 5 &＃43;))) ; 5/2

看起来很简单&＃xff0c;总结为一条规则就是&＃xff1a;从左往右顺序遍历每个操作数和操作符&＃xff0c;遇见操作数压栈&＃xff0c;遇到操作符弾栈执行对应计算&＃xff0c;并将结果压入栈中。最后&＃xff0c;返回栈顶的值。

前缀表达式的求值算法与此类似&＃xff0c;只不过遍历操作符和操作数的时候要从右往左地进行&＃xff0c;从栈中取操作数的顺序也与后缀表达式的相反。因此&＃xff0c;将对后缀表达式进行求值的函数稍微改一下&＃xff0c;就可以用来对前缀表达式进行求值了。

;;; 判断 elem 是否在 elems 中

(define(in elem elems)

(if(atom? elems)

(eqv?elems elem)

(if(null?elems)

#f

(or(in elem (carelems))

(in elem (cdrelems))))))

(defineoperator? (lambda(elem) (in elem &＃39;(&＃43; - * /))))

(define(gen-eval get-first-operand get-second-operand)

(lambda(expr)

(letloop ([expr expr][stack &＃39;()])

(if(null?expr)

(carstack)

(let([elem (carexpr)]

[expr (cdrexpr)])

(if(operator? elem)

(let([op (evalelem)]

[first-operand (get-first-operand stack)]

[second-operand (get-second-operand stack)]

[stack (cddrstack)])

(loop expr (cons(op first-operand second-operand) stack)))

(loop expr (conselem stack))))))))

(defineeval-suffix (gen-eval cadr car))

(defineeval-prefix (lambda(expr) ((gen-eval car cadr) (reverseexpr))))写到这里&＃xff0c;放张图片&＃xff0c;向用SublimeText的同学推荐一下我为SublimeText开发的括号高亮插件&＃xff1a;RainbowBrackets&＃xff0c;和Scheme语言的语法高亮、代码补全插件SublimeScheme. 功能不尽完善&＃xff0c;还望同学多多提意见。

中缀表达式的求值

(defineeval-infix

(lambda(expr)

(defineeval-help

(lambda(handled-value next-expr)

(if(null?next-expr)

handled-value

(let([op (carnext-expr)])

(caseop

[(&＃43;-) (eval(listop handled-value (eval-infix (cdrnext-expr))))]

[(*/) (eval-help (eval(listop handled-value (eval-infix (cadrnext-expr))))

(cddrnext-expr))])))))

(if(atom? expr)

(evalexpr)

(eval-help (eval-infix (carexpr)) (cdrexpr)))))

在中缀表达式的求值过程中&＃xff0c;基于处理算符优先级和对自相似性的考虑&＃xff0c;用到了递归函数。

S表达式

讲完了前缀中缀后缀三种表达式&＃xff0c;下面&＃xff0c;我们来讲一种更简单也更通用的表达式&＃xff0c;它叫S表达式。

其实S表达式也是一种前缀表达式&＃xff0c;只不过&＃xff0c;它的每一个表达式都被用括弧括起来&＃xff0c;而这括弧巧妙地隔离了优先级、参数个数(它的参数个数不限)等表达式自带的刺&＃xff0c;并提供了自相似性&＃xff0c;甚至提供了作用域&＃xff0c;使得尽管S表达式可以异常复杂&＃xff0c;但对S表达式的求值却极其简单。而它的操作符也因此可以更平凡因而更有表达力&＃xff0c;既可以是各种简单的算符&＃xff0c;也可以是一个复杂的函数。它的操作数可以是一个简单的原子类型(数值或符号)&＃xff0c;也可以是另一个嵌套的表达式。通过层层嵌套&＃xff0c;使得s表达式本身就具有一种强有力的表示数据的能力。可以说&＃xff0c;一个S表达式就是一个表达式树数据结构的字符化表示。

下面是一个简单的S表达式

(&＃43;1 (*2 (/3 4)))

它也是lisp编程语言和它的各种方言的一个程序片段。

lisp是一门强大的函数式编程语言&＃xff0c;但相较于C&＃xff0c;C&＃43;&＃43;&＃xff0c;Javascript&＃xff0c;Python等语言&＃xff0c;lisp语言并不怎么流行。这种处境在很大程度上是由充斥于lisp程序里的层层嵌套的括号导致的。对大部分人来说&＃xff0c;层层嵌套看上去很怪异&＃xff0c;就像某种魔咒&＃xff0c;令他们害怕而悄悄远离。我想&＃xff0c;这跟一个在别人看来比较怪异的同学在班上的待遇没有区别。确实&＃xff0c;

要比

简洁不少。可以说&＃xff0c;lisp的括号是屏障&＃xff0c;也是墙壁&＃xff0c;屏蔽掉了污染&＃xff0c;也挡住了很多人。

关于另外一些原因&＃xff0c;我会说&＃xff0c;我个人觉得成员运算符『.』和下标运算符『[]』是两个很重要的操作符&＃xff0c;它们表意明确而且可以使程序变得简洁&＃xff0c;而lisp的语法系统天然导致了在lisp语言中加入这两个运算符绝无可能。此外&＃xff0c;可移植的Unix操作系统的出现使另外一门同样优秀的语言——C语言——占尽了先机&＃xff0c;而此后流行的编程语言在某种程度上都有着C语言的影子。但尽管如此&＃xff0c;依然有很多人喜欢lisp&＃xff0c;因为它足够强大、足够优雅(尽管怪异)&＃xff0c;因为他们都喜欢孤独。

前面讲到&＃xff0c;如果一个表达式的表达式树已经给出&＃xff0c;那么直接对表达式树进行求值是最简单的求值方式。既然S表达式是表达式树的字符化表示&＃xff0c;那么下面就我们就来看看&＃xff0c;如何将前缀、中缀和后缀这三种表达式转化为可以存储为文本并且lisp语言可以直接进行计算的表达式树——S表达式。

表达式树的生成

表达式树的生成&＃xff0c;其过程是模拟表达式的求值过程。

前缀和后缀

(define(parse-expr get-first-operand get-second-operand)

(lambda(expr)

(letloop ([expr expr][stack &＃39;()])

(if(null?expr)

(carstack)

(let([elem (carexpr)]

[expr (cdrexpr)])

(if(operator? elem)

(let([op elem]

[first-operand (get-first-operand stack)]

[second-operand (get-second-operand stack)]

[stack (cddrstack)])

(loop expr (cons(listop first-operand second-operand) stack)))

(loop expr (conselem stack))))))))

(defineparse-suffix (parse-expr cadr car))

(defineparse-prefix (lambda(expr) ((parse-expr car cadr) (reverseexpr))))

验证一下结果的正确性

(defineassert-prefix

(lambda(expr)

(let([s-expr (parse-prefix expr)]

[value (eval-prefix expr)])

(let([s-value (evals-expr)])

(printf "prefix expr: ~a &＃61; ~a\n" expr value)

(printf " S expr: ~a &＃61; ~a\n" s-expr s-value)

(assert (&＃61;s-value value))))))

(defineassert-suffix

(lambda(expr)

(let([s-expr (parse-suffix expr)]

[value (eval-suffix expr)])

(let([s-value (evals-expr)])

(printf "suffix expr: ~a &＃61; ~a\n" expr value)

(printf " S expr: ~a &＃61; ~a\n" s-expr s-value)

(assert (&＃61;s-value value))))))

中缀

(defineparse-infix

(lambda(expr)

(definecompose

(lambda(handled-expr next-expr)

(if(null?next-expr)

handled-expr

(let([op (carnext-expr)])

(caseop

[(&＃43;-) (listop handled-expr (parse-infix (cdrnext-expr)))]

[(*/) (compose (listop handled-expr (parse-infix (cadrnext-expr)))

(cddrnext-expr))])))))

(if(atom? expr)

expr

(compose (parse-infix (carexpr)) (cdrexpr)))))

可以看到&＃xff0c;表达式树的生成过程与求值过程具有相同的递归结构和执行流。

再来看一个对支持幂运算的中缀表达式的解析

(definepaser-infix

(lambda(expr)

(definesplit-high-precedence-item

(lambda(expr ops)

(let([first (paser-infix (carexpr))]

[next-expr (cdrexpr)])

(if(null?next-expr)

(valuesfirst next-expr)

(let([op (carnext-expr)])

(if(in op ops)

(let-values (([next-item next-expr]

(split-high-precedence-item (cdrnext-expr) ops)))

(values(listop first next-item) next-expr))

(valuesfirst next-expr)))))))

(definecompose

(lambda(handled-expr next-expr)

(if(null?next-expr)

handled-expr

(let([op (carnext-expr)])

(caseop

[(&＃43;-) (listop handled-expr (paser-infix (cdrnext-expr)))]

[(*/ ^)

(let-values (([next-item next-expr]

(split-high-precedence-item (cdrnext-expr) &＃39;^)))

(compose (listop handled-expr next-item) next-expr))])))))

(if(atom? expr)

expr

(compose (paser-infix (carexpr)) (cdrexpr)))))

验证一下

既然可以借助栈直接对表达式进行求值&＃xff0c;那么将表达式转化为表达式树的意义何在呢&＃xff1f;这当然是非常有意义的事情&＃xff0c;将表达式转换为表达式树之后&＃xff0c;表达式树的可操作性和可计算性为表达式的优化(比如消除冗余的计算)提供了可能&＃xff0c;这对于编译优化是非常重要的。