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

缘起

RT

分析

上一节课讲到了编译原理的的工作分为

  1. 词法解析
  2. 语法解析

两部分，上一节简单讲解了词法解析. 这一集讲解语法解析.

1
语法解析就是通过设立一组规则，然后判断输入的文本是否符合给定规则的过程。

首先，我们来看看语法解析在日常生活中的例子

1
我看见刘德华唱歌

那么计算机是怎么对这句话做语法解析的呢? 我们假设计算机知道如下6条规则（先不管这些规则是如何得到的）

1
2
3
4
5
6
7
8
9
10
11
1.句子-->主语＋动词 ＋ 谓语从句

2.谓语从句 -> 宾语 ＋ 谓语动词

3.主语->名词

4.谓语动词->动词

5.动词-> “看见” ｜ “唱歌”

6.名词-> "我“  |  "刘德华".

那么语法解析的过程实际上是使用上面6条规则经过如下一系列的替换，还原回原先的”我看见刘德华唱歌”这句话. 从第一个规则（它是下面要讲的语法解析树的根节点）开始，用右边替换左边的token

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
1. 句子 通过规则 ：句子-->主语＋动词 ＋ 谓语从句 替换得到：

2. 主语＋动词 ＋ 谓语从句， 通过规则 主语->名词 替换得到：

3. 名词 ＋ 动词 ＋ 谓语从句， 通过规则 名词-> "我“  |  "刘德华" 替换得到

4. 我 ＋ 动词 ＋ 谓语从句， 通过规则 动词-> "看见" 替换得到：

5. 我 看见 ＋ 谓语从句， 通过规则 谓语从句 -> 宾语 ＋ 谓语动词 替换得到：

6. 我 看见 宾语＋谓语动词， 通过规则 宾语->名词 替换得到：

7. 我 看见 名词＋谓语动词， 通过规则 名词-> "我“  |  "刘德华" 替换得到：

8. 我 看见 刘德华 ＋ 谓语动词， 通过规则 谓语动词->动词 替换得到：

9. 我 看见 刘德华 动词。通过规则 动词-> “唱歌” 替换得到

10 我 看见 刘德华 唱歌

已经没有可以替换的地方了，并且最终得到的语句和原先的”我看见刘德华唱歌”一模一样. 由此可见，”我看见刘德华唱歌” 这句话是符合计算机的规则的. 则编译是通过的.

其次，让我们好好看看上面的语法解析的步骤——其实是在一棵树上进行dfs. 这棵树是编译原理中说的语法解析树. 本例中, 这棵语法解析树长下面的样子

如果我们的语句是 “我看见张学友唱歌” 那么这句话就无法通过编译. 因为按照 dfs 规则, 替换到最后得不到”我看见张学友唱歌”这句话的. 能通过编译的只有

1
2
3
4
我看见刘德华唱歌
刘德华看见我唱歌
刘德华看见刘德华唱歌
我看见我唱歌

所以如果想要”我看见张学友唱歌”能通过编译的话, 就要将上述第六条规则

1
名词->我|刘德华|张学友

则”我看见张学友唱歌” 就能通过编译了.

最后，我们来看看上述规则. 很明显，上面的6条规则分成两派

一派是抽象的. 即 1 2 3 4四条规则. 说白了，就是语法解析树的非叶子节点. 而另一派是具体的规则. 即5 和6 ，说白了，就是语法解析树的叶子节点.

好了，说完了生活中解析文本的例子，下篇文章我将分享对算术表达式的解析.

ps: 2019-7-19 补充

其实上面的例子的那一句话有误导之嫌——“最终 我看见刘德华唱歌 和原来的一模一样”， 其实语法解析的过程只是判断输入的语句（表达式statements）是否符合语法要求，并不是为了什么一模一样. 而是在拆解 我看见刘德华唱歌 这句话（表达式）的过程中发现每个步骤都合法, 所以 我看见刘德华唱歌 这句话就是编译通过的.