之前有写过词法分析的原理，接下来是比较重要的文法分析(也称：语法分析)，这个步骤将词法分析产生的词语队列进行解析，提取出一个个语句单元，比如赋值语句，函数生命之类，最终会生成一个经常听到的词AST(抽象语法树)。

理论基础

文法的分类

相比我们日常说的汉语，英语，计算机科学中的编程语言有着明确的规范，虽然汉语英语也有语法，但很难描述所有的情况，这一点学过英语的人应该都有体会。 但计算机语言不一样，它有明确的格式，写错了就不能运行，因此产生了一门科学 形式语言理论，专门研究数学和计算机科学中所用语言的语法，而后由乔姆斯基提出了一套分层体系，用来描述形式语言的表达能力

乔姆斯基体系

http://s.idinr.com/post/2560px-Chomsky-hierarchy.svg.png

0型文法(无限制文法)

这种文法对最终产生的结果没有要求，因此它包含了所有类型的文法

1型文法(上下文相关语言)

故名思义，这种文法要求在生成句子时，必须是前后的内容满足了特定的条件

2型文法(上下文无关语言)

故名思义，这种文法在生成句子时，没有上下文的要求，但必须生成结果(包含一个确定的词)，不能生成空

3型文法(正则文法)

这种文法要求生成的句子的左侧必须是特定的单词

这么看比较抽象，可以拿汉语句举个不严谨的例子

定义一个文法 汉语 -> 任意汉字的集合 显然这个文法相当灵活，可以生成任何的句子，那么这是一个0型文法

定义一个文法 历史状态陈述句 -> 历史时间或者空+陈述句+其他内容或者空，这个文法可以生成这样的句子：

早上我吃了海鲜，早上是历史时间，我吃了海鲜是陈述句，后面跟的是空，这种文法要求前面必须带一个特定的时间，因此这是一个上下文相关文法

定义一个文法 陈述句 -> 主语+连系动词+表语，可以生成我吃了海鲜这样的句子，他的生成对前后内容没有要求，可以看出这是上一个文法的子集。

定义一个文法 主语 -> 人称代词，可以生成 我，你，他这样的词语，那么这是一个正则文法，它必须生成特定的单词，不能再继续生成。

上面四种文法从上到下，可以生成的内容依次减少，限制越来越多。 它们差别是抽象层次的区别，也可以说是所能描述的情况数量上的区别，比如 数字，它包含无符号数，有符号数，而有符号数 只能包含有符号的数字

虽然不太严谨，但可以按这个思路理解，实际上这四种文法有明确的公式定义以及运算规则，这里不赘述

编程语言的语法

那么在描述编程语言的语法时应该用什么文法？ 目前主流的是 上下文无关文法。

但这不意味着编程语言是上下文无关的语言。

一般来说编程语言的构成如下：

  • 字符 英文字符，数字，下划线等等
  • 单词 if，else，function，变量名等等
  • 文法 用来定义一段语句是否合乎形式上的规范
  • 语义 语句的含义或者说语句能否正确执行

文法在编译器中扮演的角色是描述语言的结构，但不能描述语言的语义 ****

举个例子：

一段rust代码

let a = &b;

从文法上来说，它肯定是合法的，这是一个赋值语句，并且产生了引用。但是它并不能正确执行，因为b没有定义，所以仅仅有文法并不能正确的解析代码还需要语义的检查。

继续上面的例子，看起来语义规则是上下文有关的，被引用的变量必须在它之前定义，为什么不用上下文有关文法呢？

最主要的原因还是过于复杂，被引用的变量可能在之前的几千行的代码中定义的，这当中的几千行代码相当于上下文，显然情况过于复杂。

更简单的方案是：如果要检查一个被引用的变量是否被定义，只需要在遇到引用语句的时候，再去搜索被引用的变量是否定义即可，不需要为这种规则建议一种文法上的约束。

因此编程语言的文法定义只要能描述正确的结构即可，即单词应该怎样组合才是一个合法的语句，至于语义以及上下文约束，交给专门的语义检查步骤去完成

上下文无关文法的特别之处在于，它可以不理会上下文并且能递归的展开

例如有这么一段文法定义：

A -> xB
B -> yC
C -> z

那么A最终可以递归的展开成：

A -> xB 
  -> xyC // 应用第二个规则，将B替换成yc
  -> xyz // 应用第三个规则

可以转换为如下的树状图

http://s.idinr.com/post/IMG_0921.jpg

即 语法树

语法树的构造方式

如果一段代码能按照某个文法递归的展开成一颗树，那么这段代码就是符合语法规则的。

所以文法分析阶段要做的事情就是：尝试根据源代码构造语法树

构造方式有两大类

自顶向下

这个过程叫推导

每次读取一个单词(由词法分析产生)，尝试从文法中选择一个产生式，这个产生式可能还可以继续展开，如此递归，直到不可展开，即从某个产生式的根节点出发向下递归构造语法树。

自底向上

这个过程叫规约

每次读取一个单词(由词法分析产生)，尝试从文法中选择一个产生式，并且这个产生式的结果的最右侧的和这单词个单词相同，重复此过程，直到产生式不能再继续规约，即从某个产生式的结果的最右侧出发，向上构造语法树。

文法的定义

文法的形式化定义包括如下几部分

  • 非终结符 用大写字母表示
  • 终结符 用小写字母表示 (包括空 用ε表示)
  • 产生式 定义推导过程
  • 起始符号

例如

S -> Xb | Yc
X -> a 
Y -> d

上例中有三个推导式，非终结符(S，X，Y)，终结符（a，b，c，d）。

此外还要引入另外三个概念，FIRST,FOLLOW,SELECT三种集合，

FIRST集

用来描述一个非终结符推导出来的结果中，首字符可能是哪些终结符。

对于上例：

  • X的FIRST集为a
  • Y的FIRST集为d
  • 由于S能推出两种结果，这两种结果最前面的是X和Y，所以X和Y的FIRST集就是S的FIRST集。

有些表达式可能推导出空，如果空出现在某个结果的最前面，此时计算FIRST集应该将空剔除，用紧跟在它后面的元素参与计算

FOLLOW集

用来描述一个非终结符推导出来的结果中，某个非终结符(X)后面可能紧跟的终结符的集合，如果X是某个产生式的开始符，那么结束符$也包含在X的FOLLOW集中

对于上例：

  • X可能出现在S推导的Xb中，此时紧跟在它后面的字符是b，故将b添加到X的FOLLOW集中
  • Y可能出现在S推导的Yc中，此时紧跟在它后面的字符是c，故将b添加到Y的FOLLOW集中

计算上面两种集合的意义在于：

为选择哪条产生式提供了依据

如果源代码中某个字符不在产生式的FIRST集中，那意味着此时不能使用这条产生式。

在某条产生式结尾处，如果此时输入的某个字符串不在FOLLOW集中，那意味着产生了错误

分析方法

自顶向下

基本思想：

每次从源代码中读取一个单词(来自于词法分析)，根据FIRST集找出一个匹配的产生式，若结果中包含非终结符，那么继续此过程，直到匹配完整个产生式。

例如，有如下语法:

S -> AB
A ->iC
C -> love
B -> you

假设输入的源代码序列为 i love you

那么构造过程如下所示：

http://s.idinr.com/post/IMG_8F2FDDD7306B-1.jpeg

这里存在两个潜在的问题 回溯和左递归

回溯

例如：

S -> aBd
B -> bc|b // 可推导出bc或者b

那么对于输入源代码 abcd，如果在替换B时，选择B→d 这个分支，将会报错

左递归

例如如下的文法

A -> Ab|b

如果选择 A→Ab ,A可以继续展开，最终的结果可以是一个无限长的b字符串

换句话说，上面两个问题的根源是：如果必须做出二选一的抉择，那么有概率会选错。

那么这种问题的解决方案是什么呢？

上文有提到FIRST集和FOLLOW集，它为选择产生式提供了依据，但这个依据是有前提的，前提就是文法必须是LL(1)文法

LL(1)文法

满足LL此文法必须满足以下条件：

  • 任何两个非终结符的FIRST集都不相交
  • 任何两个非终结符的FOLLOW集都不相交
  • 任意终结符的FIRST集与FOLLOW集不相交

如果满足了以上条件，那么该文法属于LL(1)型文法，它的最终目标是产生一个一一对应的分析表，每种情况都能选出正确的产生式。 通过构造该文法，可以实现表驱动的自下而上分析。

分析表

首先需要引入 SELECT集的概念 ，它表示如果一个字符在某产生式的SELECT集中，那么应该选择这个产生式。

规则如下：

对于某个产生式 A → α

  • 如果α 不含空， 那么A的SELECT集为A的FIRST集
  • 如果α 可以含空，那么A的SELECT集为A的FIRST集并上A的FOLLOW集

第二个规则的意思是，如果A产生了空，那么此时应该根据可以紧跟在A后面的字符来判断，即A的FOLLOW集。

假设有如下文法

E -> TE'
E' -> +TE'|ε
T -> FT'
T' -> *FT'|ε
F -> (E)|id

可得到如下SELECT集合

E -> TE'      => { (,id }
E' -> +TE'    => { + }
T -> FT'      => { $,) }
T' -> *FT'    => {* }
T' -> ε       => { +, ) , $ }
F -> (E)      => { ( }
F -> id       => {id}

从上面的SELECT集可以得出，当前终结符如果是E，并且当前输入为 (，那么可以选择 E → TE’这个产生式。

按照这个规律可以构造如下分析表：

非终结符/输入字符id+*()$
EE->TE'E->TE'
E'E’->+TE'E’ -> εE’ -> ε
TT->FT'T->FT'
T'T’ -> εT’ -> *FT'T’ -> εT’ -> ε
FF->idF -> (E)

表驱动的自顶向下分析

该方法的核心思想是：从文法开始符号出发，每读取一个字符，就在分析表中进行查找该选用哪个产生式。
继续上面的例子：
如果输入是 id+id ，从文法开始符E开始

  • 首先读入id，此时查表得到该选用 E->TE’，
  • 此时左子节点为T，查表得到该选择 T -> FT'
  • 此时左子节点为F，查表得到该选择 F -> id 这里完成了id的匹配
  • 读入下一个符号+
  • 此时回到上一个节点 T -> FT’的右节点T’，查表得到选用 T’-> ε，这里完成了ε匹配
  • 回到上一个节点E->TE’ 的右节点
  • 查表得选用E’-> +TE’，此时左节点+完成匹配
  • 读取下一个字符id，查表得选用T->FT’，左节点为F，该选用F->id，回到右节点T'
  • 此时输入为结束符$，故选用T’ -> ε,再回到上一个右节点，此时选用E’ -> ε。

整颗树构造完成

上面所述过程类似深度优先搜索，所以实际上有两种实现方法，一种是递归实现，一种是基于栈的下推自动机实现，这里不赘述其具体实现，核心都是上面的查表过程。

自底向上

核心思想：

根据输入的单词，尝试匹配一条产生式，其最右部能匹配这个单词，并用此产生式的开始符替换此单词，然后读取下一个单词，并检查其与上一步匹配出的开始符能否匹配某一个产生式的右部能否匹配，若能，执行类似上一步中的替换过程，若不能，继续读取下一个单词。

整个过程本质上是两大部分：移进与规约， 移进是读取下一个单词，规约是尝试现有单词串能否匹配产生式。由于需要记录上一步所规约出的非终结符，自底向上的分析一般用带栈的下推自动机实现。

下推自动机

其包含一个栈，用于记录规约出的非终结符。基本运行过程如下：

  1. 读取一个单词，并将其压入栈顶
  2. 检查栈内的单词串能否匹配一条产生式
  3. 若能，将这几个单词出栈，并将其所匹配的非终结符入栈
  4. 若不能，重复步骤1和2
  5. 若输入正确，最终栈内会留下一个开始符，整个文法匹配完成

设有文法：

S → E
E → T + E
E → T
T → int

则自动机解析过程如下

栈               输入                动作 
---------------------------------------------------------
                 int + int + int    移入
int              + int + int        规约 T -> int
T                + int + int        移入
T +              int + int          移入
T + int          + int              规约 T -> int
T + T            + int              移入
T + T +          int                移入
T + T + int                         规约 T -> int
T + T + T                           规约 E -> T
T + T + E                           规约 E -> T + E
T + E                               规约 E -> T + E
E                                   规约 S -> E
S                                   完成

与自顶向下的分析类似，自底向上也会遇到选择问题，在某一时刻，栈中的符号可能同时满足两个规约条件，为了解决此类问题，也引入了分析表的概念。

分析表

由于文法开始符可能出现在产生式的右部，此时将无法分清是规约到了文法开始位置，还是处于某个产生式右侧，为此引入增广文法：

S' -> S // S为文法开始符

此时将S‘作为文法开始符，这样保证了开始符永远只出现在开始位置。

第二步，引入状态标识：

S -> ·aB

用一个圆点· 表示紧跟在它后面的元素在等待规约，如上例，此时a在等待规约，如果当前输入了一个a，此时a规约完成，状态符后移，B处于待规约状态：

S -> a·B

第三步，生成项目集：

对于文法中的每条产生式，生成一个包含所有状态的集合，即生成了项目集，例如：

S' → S
S → E
E → T + E
E → T
T → int

生成项目集如下：

S' → S    =>  S' → ·S, S' → S· 
S → E     =>  S → ·E , S → E·
E → T + E =>  E → ·T + E , E → T ·+ E , E → T + ·E , E → T + E·
E → T     =>  E → ·T , E → T·
T → int   =>  T → ·int , T → int·

类似FOLLOW集的计算方式，这其中有些状态可以认为是等价的。

由于S可以生成E，那么在等待S的时候，可以认为在等待E，即

S' → ·S  等价于 S → ·E

类似的可以计算出所有的等价项目

E → ·T + E  等价于 T → ·int
E → T + ·E  等价于 E → ·T + E, E → ·T
E → ·T      等价于 T → ·int

某产生式的所有等价项目属于同一个状态

第四步，生成状态转换图

从文法开始符出发，写出每个待规约符遇到该符号后的状态转换路径，若该文法存在等价项目，将等价项目加入该状态。

http://s.idinr.com/post/hggh.png

最后一步，根据转换图生成分析表： 上文提到的下推自动机中包含了字符栈，而分析表中引入了状态的概念，所以需要增加一个状态栈。 字符栈包含两个动作，移入-shift和规约reduce
状态栈只有一个动作 goto，表示从当前状态进入到另一个状态。 构造分析表如下：

http://s.idinr.com/post/%E6%88%AA%E5%B1%8F2022-04-23%2010.52.12.png

Shift 4代表移入对应的非终结符，并进入到状态4。

Reduce代表规约成对应的产生式。

冲突

上例中标红的部分是一个冲突：

状态3的第二个产生式是一个规约状态，此时不管遇到什么符号都应该进行规约，但第一条产生式要求遇到+要进行移入，此时就产生了

移进规约冲突，此外还有规约规约冲突，这里不再赘述，为了解决这两种冲突，产生了更强大的SLR，LR(1),LALR 分析，本质上来说，这几种分析方式是考虑了上下文环境，通过观察下一个符号，来判断进行何种操作，这与自顶向下的解决方案从思路上来说是一致的。

SLR分析

SLR分析的思想是引入FOLLOW集来判读如何操作。 如果产生冲突的某条产生式处于规约状态，但下一个符号不在它的FOLLOW集中，那么显然此时不能进行该规约。 但上面的文法中，可以看到E的FOLLOW集中包含了+，此时依然无法判断该如何操作。 因为FOLLOW集只是该进行规约的必要条件，也就是说如果此时该进行规约那么下一个符号必然在它的FOLLOW集中，但不意味在FOLLOW集中就一定进行规约，为了解决此问题，产生了LR(1)分析

LR(1)分析

上述问题产生的根本原因是，某非终结符A的FOLLOW集可能来自不同产生式，这意味着在不同产生式中，A后面跟的符号是不一样的，所以只要确定A在不同产生式中的后继符就可以解决这个问题。 对于 S' -> S 只有后面是$符的时候才能规约，对于此产生式的等价项，他们的后继符也都是$，所以可以生成如下转换图：

此时就可以解决状态3的冲突问题，只有当下一个符号是$时才能进行规约。
但LR(1)分析法也存在状态过多的问题，因此又产生了LALR分析法
它的主要思想是合并同心集，同心集是指产生式内容相同但后继符不同的状态，这里不再赘述。由于LALR合并了部分同心集，所以它的状态会比LR(1)少，但比SLR多，所以它的分析能力介于SLR和LR(1)之间