这两天大概写完了编译原理大作业。于是用一些博客来记下来里面用了哪些东西。其实里面根本没有用到什么高深的技巧，好像就是一路顺下来就写完了；唯一有些弯弯绕绕的地方就是解析数字的parser了。

这在之前也已经写过了，那是一个Lisp语言的解析数学表达式的东西，只是在Lisp中数学表达式的写法是自带语法树的，在对于普通的数学表达式的时候，由于有了优先级的限制，这个就显得很麻烦了。

数学表达式的文法

语法分析是在词法分析的基础上将单词的序列组合成表达式。里面会有定义好的一些文法的检查，类似于这样：

1
F = num | FF

说明F由两个F或一个num组成。那也就是说，F是一个由无穷多个num组成的文法。

如果用这样文法分析的做法来做的话，一个只有一个优先级符号(比如+)的可求值的数学表达式可以做成下面这样的形式：

1
2
numExpr = num symbol
symbol = + numExpr

为了使表达式的求值有优先级，我们需要对上面的式子做一点改写：

1
2
3
4
5
6
7
num0 = num1 symbol1
symbol1 = + num0 | - num0
num1 = num2 symbol2
symbol2 = * num1 | / num1
num2 = num3 symbol3
symbol3 = ^ num2
num3 = num

这个最重要的就是出现了一个求值的顺序，也即首先对优先级最低的做处理，然后处理两侧优先级更高的。

一些别的规则

比如说可能引入了括号，在括号内的东西需要优先计算，这在上面的文法表达式里面只要做稍微的改动就好了，也就是最后一句的处理：

1
num3 = num | (num0)

对于一个函数，他应该也是跟单纯数字是同一个级别的：

1
num3 = num | func(num0) | (num0)

另外我们需要明确的是，我们在这个函数中是有变量的，而且是个数不明的变量。因此这里我们应该返回的是一个函数，接受一定的参数并返回一定的结果。但是要返回一个函数的话其实还是很麻烦的，因为我们没有办法确定参数的数量和参数之间的关系。因此我们需要返回的其实是一个列表，列表里面包含了这个数字的解析式。因此对于一个表达式，我们不需要求它的结果，直接返回获得的解析树就好了。

Clojure实现

如果用C语言来做的话，可能很容易写出一系列的跟文法表达式一样的函数，但是我觉得那样实在是有些蠢。其实讲道理C语言也可以像这样写，而且很优雅，但是我看到的都是用各种一系列的switch-case，至少并不好看。

因为上面的是几乎一样的结构，我想可以用一个数字来表示这个0123，然后写出num3的情况就好了。这个数字也就是对应运算符的优先级。

这两个函数，因为首先要给后面的东西留下解析的结果，也就是剩下留给它们解析的部分；然后是解析得到的解析式。解析数字和解析符号的函数返回值都是这个，在明确了这一点之后写起来就会好写一点了。

下面是解析数字函数，中间对于数字、函数、括号的处理部分略。

1
2
3
4
5
6
7
8
(defn __parseNum
  [expr level]
  (if (= level 3)  ; 停止递归
    (...)
    (let [res (__parseNum expr (+ level 1))]
      (do (assert (not (nil? res)))
        (let [op_res (__parseOp (first res) (+ level 1) (second res))]
          (if (nil? op_res) res op_res))))))

解析符号的函数：

1
2
3
4
5
6
7
8
9
10
(defn __parseOp
  [expr env level last_res]
  (let [op (first expr)
        ex (rest expr)]
    (if (= level (third op))
      (let [next_num (_parseNum ex env (- level 1))
            next_res (list (second op) last_res (second next_num)))]
        (let [op_res (_parseOp (first next_num) env level next_res)] ; 继续匹配下一个 符号 数字
          (if (nil? op_res) `(~(first next_num) ~next_res) op_res)))
      nil)))

最后再做一个针对这两个函数解析的接口：

1
2
3
4
(defn parseNumExpr
  [numExpr]
  (let [res (__parseNum numExpr 0)]
    `(~(first res) ~(second res)))))

这就是一个解析数字的表达式的相应结构。

需要注意的是，由于这两个函数互相引用，所以在它们定义的前面应该首先说明一个__parseNum或者__parseOp才能避免报错。

整个的函数可以到这里看到。

另：只解析数字，不包含符号的版本可以在这里看到。

化简函数

对于这个函数的返回值的第二部分，可以看到，它是一个包含变量和数字的表达式。我们可以直接用它来计算，只要之后在环境中需要变量的值就可以，但是这样并不是最好的方案，因为有一些东西我们是可以提前算出来结果的，比如：

1
'(+ (- "8" "4") (* "5" "v"))

这个式子中(- 8 4)是可以提前得到结果的，在求完后化简一下这样的表达式可以避免重复计算。

化简的函数如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
(defn simplify
  [code]
  (if (list? code)
    (if (= (count code) 3)
      (let [arg1 (simplify (second code))
            arg2 (simplify (third code))]
        (if (and (number? arg1) (number? arg2))
          (eval (list (first code) arg1 arg2))
          `(~(first code) ~arg1 ~arg2)))
      (let [arg1 (simplify (second code))]
        (if (number? arg1)
          (eval (list (first code) arg1))
          `(~(first code) ~arg1))))
    (let [alpha (first code)]
      (if
        (alpha? alpha) code
        (if (digit? alpha) (Float/parseFloat code) nil)))))

也就是这样的一个逻辑：

  1. 如果式子是列表，返回式子参数化简结果和式子的符号，如果式子参数都是数字，计算这个式子，返回数字。
  2. 如果式子是符号，返回符号本身
  3. 如果式子是数字，返回解析后的数字。