自己动手用java写编译器 课时2 用java实现一个简易编译器2-语法解析 笔记 后篇

缘起

RT

分析

本集我们我们在课时1（【1】）中写的词法分析器基础上继续添加语法分析器. 目的是能将一条或者一组含有+ * 的算术表达式编译成类似汇编的伪代码. 例如

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
1+2*3+4, 经过编译后转换成：

t0 = 1

t1 = 2

t2 = 3

t1 *= t2

t0 += t1

t1 = 4

t0 += t1

t0, t1 是对寄存器的模拟，上述语句基本上就类似计算机能执行的汇编语句了。

我们把一组带有分号的算术表达式称为statements, 例如下面就是一个statements

1
2
3
4
5
1+2*3+4;

2+3*4+5;

3+4*5+6;

而statements中的每一条;结尾的表达式称为expression. 也就是说 statements由一个或多个expression组成的

根据上一篇文章（【2】）说的语法解析就是设定一组规则，然后判断输入的文本是否符合给定规则的过程

我们在【1】中已经进行了词法分析, 这里要给出语法解析——看看合不合规. 于是我们要考虑设立一组规则.

受【2】的启发，其实我们要给出的就是一棵语法解析树嘛~ 所以可以给出如下规则

1
2
3
4
5
6
7
8
9
10
11
# statements的解析规则  | 表示 或 的意思
statements -> expression; | expression; statements

# expression的解析规则
expression ->expression + term | term;

# term的解析规则
term -> term* factor | factor

# factor的解析规则
factor -> NUMBER | (expression)

其中上面四条规则中, 除了第四条，其他三条和【2】中给出的6条规则很不一样. 它有点像 GNU 的定义

1
GNU是“GNU is Not Unix”的递归缩写

没错, 前三条规则和【2】中6条规则最大的不同就是”递归的”——即自己解释自己. 这种情况在编译原理里面叫左循环(LR left recursive)， 其实我更喜欢叫 左递归.

大家先不要着急问: “你是怎么想出这套规则的? 这套规则凭什么能解析算术表达式?” 后面会慢慢知道的.

但是有两个问题是不得不现在问的

1
2
3
4
1. 上面的规则中有 |, 涉及两组解析方式，我们用哪种? 也就是解析statements的时候，到底是使
用"expression;" 还是 "expression;statements" ? 这两种方式选哪一种?

2. 左递归会死循环吗?

先来解决第一个问题

  1. 在我们程序中，读取到第一个;的时候，再继续读取下一个字符，如果继续读取下一个字符返回的是EOF的话, 则就使用”expression;”, 如果不是的话, 说明分号右边还有需要解析的东西，那就使用 “expression;statements”这种替换规则. 这种技巧在编译原理中叫做lookAhead.

  2. 左递归会不会死循环，因为我们可以把规则改成下面的（具体为什么这么改，以后再说）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    1. statements -> '空' | expression; statements

    2. expression-> term expression'

    3. expression'-> +term expression' | '空'   ## 如果不以+开头的话, 就解释为空

    4. term -> factor  term'

    5. term' -> * factor  term' | '空'   ## 如果不以 * 开头的话, 就解释为 '空'

    6. factor -> number | (expression)   ## number是数字

    上面的 | 表示或者，即二择一

    这组规则可以保证不会出现死循环. 其中 ‘空’ 表示结束——do nothing. 在程序中相当于是return. 以 1+2 为例，看看上面的规则形成的语法解析树长什么样子.( 注意，单条expression不带分号的, statements才带分号)

上图中，statements是 1+2; expression是 1+2, term 是 1, expression’ 是 +2, factor是 1, term’是 空.

term是2, 这里term’是空, 因为它不以 * 开头

最后，我们使用上述规则

下面是本节代码, 参考 demo【1】

参考

【1】https://yfsyfs.github.io/2019/07/17/%E8%87%AA%E5%B7%B1%E5%8A%A8%E6%89%8B%E7%94%A8java%E5%86%99%E7%BC%96%E8%AF%91%E5%99%A8-%E8%AF%BE%E6%97%B61-%E7%94%A8java%E5%AE%9E%E7%8E%B0%E4%B8%80%E4%B8%AA%E7%AE%80%E6%98%93%E7%BC%96%E8%AF%91%E5%99%A81-%E8%AF%8D%E6%B3%95%E8%A7%A3%E6%9E%90%E5%85%A5%E9%97%A8-%E7%AC%94%E8%AE%B0/

【2】https://yfsyfs.github.io/2019/07/17/%E8%87%AA%E5%B7%B1%E5%8A%A8%E6%89%8B%E7%94%A8java%E5%86%99%E7%BC%96%E8%AF%91%E5%99%A8-%E8%AF%BE%E6%97%B62-%E7%94%A8java%E5%AE%9E%E7%8E%B0%E4%B8%80%E4%B8%AA%E7%AE%80%E6%98%93%E7%BC%96%E8%AF%91%E5%99%A82-%E8%AF%AD%E6%B3%95%E8%A7%A3%E6%9E%90-%E7%AC%94%E8%AE%B0/

DEMO

【1】https://github.com/yfsyfs/backend/tree/master/compiler%20%E8%AF%AD%E6%B3%95%E8%A7%A3%E6%9E%90/src