最简单的解析器

什么样的解析器是【最简单的解析器】呢?我认为,【最简单的解析器】是【递归向下解析器】。 无论你使用的解析方法是回退还是LL,递归向下总能使得解析器轻量化、简单、能够快速构造。

但是,这种解析器有几个问题:

  • 不能处理左递归文法
  • 文法不一定是LL(1)的,效率上和实现上都有些问题
  • 用过程式编程语言时,不能很好地进行抽象,导致重复代码

这篇文章通过介绍三个变换,解决了第一个问题,在某种程度上解决了第二个问题。至于第三个问题,这是一个纯粹的工程问题,我们就不在这里研究了。

第0变换

所谓的【第0变换】是我在研究lisp表达式的解析的时候总结出来的。我们知道,lisp的语法类似于

(id id id ...)

但是,它有几种不同的情况:

(+ 1 1) ;函数调用
(lambda (x) (+ x 1)) ;lambda定义

这两种情况应该生成两种不同的语法树:

(apply-node '+ 1 1)
(lambda-node 'x (apply-node '+ 'x 1))

如何在写解析器的时候能够简单地、正确地处理这两种情况呢?

这里真正的问题是,这个文法本身就不是LL(1)的。因为这两个非终结符的第一个终结符是相等的,所以当解析器读到一个(的时候,它无法区分下一步是进入apply-node的解析函数还是lambda-node的解析函数。

那么,我们究竟应该怎么办呢?

答案是,在解析时不区分这两种节点,而是解析为一个统一的形式,之后遍历这颗语法树,把正确的形式映射出来

比如说,对于这个问题,我们把这两种形式都解析为:

(s-expr '+ 1 1)
(s-expr 'lambda (s-expr 'x) (s-expr '+ 1 1))

然后,我们通过第0变换,把它们变成:

(apply-node '+ 1 1)
(lambda-node 'x (apply-node '+ 'x 1))

至于第0变换是如何做的,我们写一段scheme代码来示意:

(define (mapping x)
  (if (= (car x) 'lambda)
      (lambda-node (mapping (cadr x))
      			  (mapping (caddr x)))
      (apply-node ...))))

可以看到,这个变换是对语法树的直接映射,它没有什么复杂的东西。

第1变换

第一变换,简单地说就是交换语法树次序,比如说:

(+ 1 2 3 4)

变为

(+ 1 3 4 2)

对于具有可交换性的语法树节点,都可以做这个第一变换。

第2变换

第二变换是本文的重头戏。因为它可以解决最麻烦的问题-左递归问题

我们知道,一个左递归文法可以变成右递归的,这个变换有形式化的算法,这里就不多赘述了。

那个算法的实质和下面介绍的操作没有区别,也就是说,对于这样的句子:

1 - 2 - 3 - 4 - 5

如果你基于这样的文法进行解析:

A := A - number
   | number

那么,它的语法树就会是:

'(-(- (- (- 1 2) 3) 4) 5)

我们把文法修改一下:

A := number - A
   | number

那么,它的语法树就是:

'(- 1 (- 2 (- 3 (- 4 5))))

我们可以看到,那个算法并不能得到正确的、左递归的语法树。

实际上,一切递归向下解析器都无法正确解析左递归文法。但是,如果我们可以把被解析为右递归形式的语法树变成左递归的形式,岂不就解决了这个问题?

这就是我所谓的第2变换,这个变换会将【被解析为右递归形式的语法树】变成正确的左递归形式。

变换的算法其实也不复杂,这里把我写的一段简单的变换代码写出来:

#lang racket

(define (make-node root left right)
  (cons root (list left right)))

(define (node-root ast)
  (car ast))

(define (node-left ast)
  (cadr ast))

(define (node-right ast)
  (caddr ast))

(define (tree? ast)
  (pair? ast))

(define (trans-root? ast)
  (or
   (equal? (node-root ast) '-)
   (equal? (node-root ast) '/)))

(define (rec-right? ast)
  (equal?
   (node-root ast)
   (node-root (node-right ast))))

(define (trans? ast)
  (and (trans-root? ast)
       (tree? (node-right ast))
       (rec-right? ast)))

(define (type2-trans ast)
  (define (trans-cons this-root queue-list)
    (if (null? (cdr queue-list))
        (car queue-list)
        (make-node this-root
                   (trans-cons this-root (cdr queue-list))
                   (car queue-list))))
  (define (trans-func ast queue)
    (if (tree? ast)
        (if (trans? ast)
            (trans-func (node-right ast)
                        (cons (trans-func (node-left ast) '()) queue))
            (let ([left (trans-func (node-left ast) '())]
                  [right (trans-func (node-right ast) '())])
              (if (null? queue)
                  (make-node (node-root ast) left right)
                  (trans-cons (node-root ast) (cons right (cons left queue))))))
        ast))
  (trans-func ast '())) 

;; test
(type2-trans '(+ 1 (+ 1 2)))
(type2-trans '(- 5 (- 3 (- 2 4))))
(type2-trans '(/ 3 (/ 4 5)))
(type2-trans '(- (/
                  (* 3 4)
                  (/ 5 6))
                 (- 2 3)))
  

以其中的一个测试为例,它会将

'(- 5 (- 3 (- 2 4)))) ;5 - 3 - 2 - 4的错误形式

变为:

'(- (- (- 5 3) 2) 4) ;5 - 3 - 2 - 4的正确形式