Fork me on GitHub

在之前的介绍里面, 我讲了我们想要实现的Scheme语言的定义,并且用这个定义好的语言写了一些例子程序。 那么在这篇文章里面,我会讲讲大概的解析器是什么样子的。

前提:Lexer

在编译原理里面,介绍编译器的时候,一般都会介绍前端的一个重要的组成部分是Lexer的模块。 Lexer是词法分析器,也就是讲输入的字符流转换成语法定义的Token流。 一般的实现都是用状态机来实现,而在我们的解析器里面,为了简化实现的难度,我们利用Scheme 内置的read函数,它相当与Scheme的Lexer。它每次都从input-stream输入一个S表达式。

举个例子,看下面的代码:

1
2
3
4
(read (open-input-string "(define a 1)"))  ; read from stdin
;;; 上面的表达式返回(define a 1),
;;; 这个表达式也可以用下面的表达式来获得
(cons (quote define) (quote a) 1)

上面的代码也能看出一个Lisp的重要特性——代码即数据。在Lisp里面, Lisp代码可以很容易的看成是Lisp里面的数据,基本不用什么特别的处理。 这个特性让Lisp语言的拓展性相比起其他语言来有很大的优势。

接下来我们的解析器,都用read来进行输入的转换。基于read, 我们就能假设输入进来的Lisp代码,可以用相对于atom或者list的操作来进行处理, 而不用用字符操作来进行处理。

上面的说明是什么意思?用下面的代码来说明一下应该最好:

1
2
3
4
5
6
7
8
(define l (read (open-input-string "(define a 1)")))
(if (eq? (quote define) (car l))
    (display "It's definition!")
    (display "It's not definition!"))

(if (number? (car (car (car l))))
    (display "It's number!")
    (display "It's not number!"))

上面的代码里面,我将用read读进来的表达式用car取出第一个symbol, 然后用eq?来进行比对。eq?是一个用来判断两个symbol是否一样的函数。 而number?就是一个用来判断参数是不是Number类型的函数。 除了上面两个函数之外,还有string?函数, 它可以用来判断参数是不是String类型的。

看了上面的代码,估计你心中已经大概有了一点概念了吧?

解析器的基本结构

有了前面的说明,接下来我们就要想想怎么写解析器才可以实现之前说的语言了。

既然我们是写解析器,解析器实际上就是一个evaluate表达式的过程, 我就把这个解析器的函数命名为eval。

假设现在我们只需要解析最基本的atom,比如1, a, define的话, 那么eval要怎么写呢?首先在scheme里面,有一个函数是pair?, 是用来判断一个表达式是不是list的。

比如:

1
2
(pair? 1) ; false
(pair? (cons 1 2)) ; true

有了pair?之后,我们就可以很方便判断一个S表达式是不是atom了。 下面是一个只解析atom的解析器:

1
2
3
4
5
6
7
8
9
10
(define (eval exp)
  (if (not (pair? exp))
      (if (number? exp)
          exp
          (display "Unknown type"))
      (display "Unknown type")))

(eval 1) ; returns 1
(eval 10) ; returns 10
(eval "hello") ; display "Unknown type"

看到上面的代码中,实际上eval的定义可以简化成只用一个number?判断, 因为number?就是一个类型检查。如下:

1
2
3
4
(define (eval exp)
  (if (number? exp)
      exp
      (display "Unknown type")))

如果现在加入对字符类型的atom进行解析的话,要怎么写呢?还记得之前我们有string? 来对参数进行String的类型判断么?对,我们就用string?就可以了,如下:

1
2
3
4
5
6
7
8
9
10
(define (eval exp)
  (if (number? exp)
      exp
      (if (string? exp)
          exp
          (display "Unknown type"))))

(eval 11) ; returns 11
(eval "hello") ; returns "hello"
(eval (quote a)) ; display "Unknown type"

cond表达式

在上面的eval里面,我们用了两个if,而if越多,嵌套就越多, 那么想想我们如果要处理的表达式类型越多,那么我们嵌套不就…… 在C里面,可以用switch或者连续的if来避免深层的嵌套,比如:

1
2
3
4
5
6
7
8
9
10
11
12
if (i == 1)
{
    i++;
}
else if (i == 2)
{
    i--;
}
else
{
    i += 2;
}

其实在Scheme里面,有一个cond表达式,它的作用和上面C里面的if类似。

1
2
3
(cond ((= a 1) a)
      ((> a 1) (+ a 1))
      (else (- a 1)))

上面的表达式应该不难看懂吧?我们用C来表示一次,你应该就是明白了:

1
2
3
4
5
6
7
8
9
10
11
12
if (a == 1)
{
    a;
}
else if (a > 1)
{
    a + 1;
}
else
{
    a - 1;
}

有了cond表达式,那么我们用cond来“重构”一下我们的解析器吧。

1
2
3
4
(define (eval exp)
  (cond ((number? exp) exp)
        ((string? exp) exp)
        (else (display "Unknown type"))))

现在我们的解析器已经可以处理Number和String了,那么还有什么是atom呢? 还有Boolean我们没有处理。那我们现在来分析一下怎么处理Boolean吧。首先需要注意的是, 在mit-scheme里面,boolean的值是#t#f,而在我们要实现的解析器里面, boolean的值是truefalse。这里的关系,和用C来实现Scheme是类似的, 实现语言C里面的boolean是1和0,而被实现的语言里面的boolean是truefalse。 而这里truefalse从解析器的角度来说是symbol类型的,所以我们可以用eq? 来进行判断。

有了上面的说明之后,那么我们现在来加入对boolean的解析吧。

1
2
3
4
5
(define (eval exp)
  (cond ((number? exp) exp)
        ((string? exp) exp)
        ((or (eq? (quote true) exp) (eq? (quote false) exp)) exp)
        (else (display "Unknown type"))))

上面的or和C里面的||或者Python里面的or是一样的作用的。 OK,有了上面解析器,那么现在我们玩一玩吧!

1
2
3
4
(eval (read (open-input-string "1"))) ; 等同于(eval 1)
(eval "hello") ; returns "hello"
(eval (read (open-input-string "true"))) ; returns true
(eval (read (open-input-string "false"))) ; return false

好了,现在我们已经有了一个能用的解析器了,虽然它现在只能解析atom,但是在接下来的几节中, 我们还会继续的丰富这个解析器,它就能慢慢地解析更多的东西啦。


知识共享许可协议
作品airekans创作,采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。


blog comments powered by Disqus

Published

26 November 2012

Tags