语法分析 (Parsing)

语法分析是编译的第二个阶段，它的主要任务是从词法分析器输出的 Token序列中 识别出各类短语，并构造语法分析树 （parse tree），语法分析树描述了句子的语法结构。

Example 1

先来看一个赋值语句的分析

position = initial + rate * 60;

经过词法扫描后会得到这样的一个 Token 序列:

<id,position> <=> <id,initial> <+> <id,rate> <*> <num,60> <;>

它对应的分析树应该就是这样的:

graph TD
	赋值语句---A["标识符 (position)"]
	赋值语句---B["="]
	赋值语句---C["表达式"]
	赋值语句---D[";"]
	C---E["表达式"]
	C---F["+"]
	C---G["表达式"]
	E---H["标识符 (rate)"]
	G---I["数字 (60) "]

从中我们可以看出，一个标识符，或者一个常数本身，都可以构成一个表达式，一个表达式加上另一个表达式，或者一个表达式乘上另一个表达式，都可以构成更大的表达式，一个标识符，连接上一个表达式，再连接一个表达式，最后跟上一个分号，可以构成一条赋值语句。

Example 2：变量声明语句的分析树

首先我们先来看变量声明语法分析树的文法：

<D> → <T> <IDS> ;
<T> → int | real | char | bool
<IDS> → id | <IDS> , id

这里的<D>是英文单词 declaration 的首字母，表示声明语句，<T> 是英文单词 type 的首字母，表示类型，<IDS>则是英文单词 Identifier sequence 的首字母，表示标识符序列。

从中我们可以看出，一个声明语句 <D> 是由一个类型 <T> 连接上一个标识符序列 <IDS> 和一个分号构成。

第二行则表示这里的 <T> 可以是 int，可以是 real，或者 char、bool，这里的竖线 | 表示的是或关系。

根据第三行规则可以看出，一个标识符 id 本身可以构成一个标识符序列 <IDS>，或者一个标识符序列 <IDS> 连接上一个 , 和一个标识符 id 可以构成一个更大的标识符序列 <IDS>。

根据这个文法，假如说我们输入了这样的一个声明语句:

int a,b,c;

那么它的语法分析树就是这样的

graph TD
	A["< D >"] ---  B["< T >"]
	B---int
	A---C["< IDS >"]
	C---D["< IDS >"]
	C---E[","]
	C---G["id (c)"]
	A---F[";"]
	D---H["< IDS >"]
	D---J[","]
	D---K["id (b)"]
	H---L["id (a)"]

从中我们可以发现，一个 id (a) 本身可以构成一个 <IDS>， 一个 <IDS> 连接上 , 和 id (b) 又可以构成一个更大的 <IDS>,一个类型 <T> 连接这个 <IDS> 和 ; 就构成了声明语句 <D>

graph TD
	Start-- 字符流 -->词法分析器
	词法分析器-- 词法字节流 -->语法分析器
	语法分析器-- 语法树 -->语义分析器
	语义分析器-- 语法树 -->中间代码生成器
	中间代码生成器-- 中间表示形式 -->机器无关代码优化器
	机器无关代码优化器-- 中间表示形式 -->目标代码生成器
	目标代码生成器-- 目标机器语言 -->机器相关代码优化器
	机器相关代码优化器-- 目标机器语言 -->Fin