# 语法分析

## 上下文无关文法

> 以计算器为例

1. 如何判定输入合法性？
   - 首先规定好合法的基本单元-词法分析
   - 其次理解算术表达式的构成(递归拆解)
   - 描述语言的语法结构可以使用上下文无关文法
   - 给定文法，判定输入串是否属于文法规定的语言，即语法分析

2. 上下文无关文法的形式化定义：
$$(V_T,V_N,S,P)$$
- $V_T$ 是终结符集合，基本符号，也叫token，不能再被分割
- $V_N$ 是非终结符集合，非空有限，表示*语法成分*的符号，存放中间结果，也叫语法变量，$V_T\cap V_N=\varnothing$
- $S$ 是开始符号，属于非终结符，是文法中*最大的语法成分*，分析开始的地方
- $P$ 是产生式集合，产生式描述了将终结符和非终结符组合成串的方法

3. 语法树、抽象语法树AST

4. 推导derivation：从文法推出文法所描述的语言中所包含的合法串集合的动作

5. 最左推导，最右推导

6. 上下文无关指的是在文法推导的每一步 $\alpha A \beta\Rightarrow\alpha\gamma\beta$ 符号串 $\gamma$ 仅依据 $A$ 的产生式推导，而无需依赖 $A$ 的上下文 $\alpha$ 和 $\beta$

7. 上下文无关语言
   - 上下文无关文法 $G$ 产生的**语言**：从开始符号 $S$ 出发，经 $\Rightarrow^+$ 推导所能到达的仅有终结符组成的串
   - 句型：$S\Rightarrow^*\alpha$，$\alpha$ 是由终结符和/或非终结符组成的串
   - 句子：仅由终结符组成的句型

8. 正则表达式存在局限，因为有限自动机无法记录访问同一状态的次数
   - 不能表示给定结构的**固定次数**的重复
   - 不能用于描述**配对或嵌套**
   - 能用正则表达式表示的语言都可以用上下文无关文法表示

9. 文法的二义性：文法的某些句子存在不止一种最左(最右)推导，或者不止一棵分析树
   - 消除二义性：定义运算优先级和结合律
   - 需要定义新的非终结符，优先级低的往上，优先级高的往下

## 自顶向下

### 递归下降

1. 两种分析
   - 自顶向下：从开始符号出发，尝试**推导**
   - 自底向上：尝试**归约**到开始符号

2. 自顶向下
   - 数据结构：输入缓冲区和向前看指针`lookahead`
   - 分析过程：从左向右扫描输入串，设计辅助过程`match()`，将`lookahead`指向的位置与产生式迭代生成的终结符进行匹配，若匹配则`lookahead`挪到下一个位置，为每一个非终结符写一个分析过程

3. 左递归：文法中一个非终结符的产生式的左侧也是该非终结符本身，会无限循环
   - **自顶向下分析方法无法处理左递归**
   
4. 直接左递归：$A \to A\alpha|\beta$，其中 $\alpha,\beta$ 不以 $A$ 开头，则有 $\beta\alpha\ldots\alpha$ 即直接左递归
   - 消除：考虑 $A\to\beta A',A'\to\alpha A'|\varepsilon$
   - 此处的 $\alpha,\beta$ 可以是一串符号

5. 处理任意多个数量的左递归：$A\to A\alpha_1|A\alpha_2|\cdots|A\alpha_m|\beta_1|\beta_2|\cdots|\beta_n$
   - 消除：考虑 $A\to\beta_1A'|\beta_2A'|\cdots|\beta_nA',A'\to\alpha_1A'|\alpha_2A'|\cdots|\alpha_mA'|\varepsilon$

6. 非直接左递归：$S\to Aa|b,A\to Sd|\varepsilon$
   - 代换得到 $S\to Aa|b,A\to Aad|bd|\varepsilon$
   - 消除：考虑 $S\to Aa|b,A\to bdA'|A',A'\to adA'|\varepsilon$

7. 有左公因子的文法，考虑提取公因子

### LL(1) 文法

1. LL(1) 文法是一种非递归的分析方法，而是一种查表式的预测分析方法

2. **预测分析法**与递归下降相似，但
   - 不会对若干产生式进行尝试
   - 没有回溯
   - 通过向前看一些记号预测需要用到的产生式

3. LL(k) 文法含义
   - L 从左到右的扫描
   - L 最左推导
   - k 向前看的符号个数

4. LL(1) 文法存在一些对文法的限制，首先定义如下函数
   - ${\rm FIRST}(\alpha)=\{a|\alpha\Rightarrow^*a\ldots,a\in V_T\}$，只包含终结符和 $\varepsilon$，其含义为可从 $\alpha$ 推导得到的串的首符号的集合
   - ${\rm FOLLOW}(A)=\{a|S\Rightarrow^*\ldots Aa\ldots,a\in V_T\}$，只包含终结符和输入串的结束符号 $\$$，其含义为可能在推导过程中紧跟在 $A$ 右边的终结符号的集合

5. LL(1) 文法定义：任何 $A\to\alpha|\beta$ 满足
   - ${\rm FIRST}(\alpha)\cap{\rm FIRST}(\beta)=\varnothing$
   - 若 $\beta\Rightarrow^*\varepsilon$，则 ${\rm FIRST}(\alpha)\cap{\rm FOLLOW}(A)=\varnothing$
以上条件保证没有公共左因子，无二义，且不含左递归

6. 预测分析表 $M$ 的构建，对每个 $A\to\alpha$
   - 对每个终结符 $a\in{\rm FIRST}(\alpha)$，将 $A\to\alpha$加入$M[A,a]$
   - 若 $\varepsilon\in{\rm FIRST}(\alpha)$，对包括 $\$$ 在内的每个 $b\in{\rm FOLLOW}(A)$，将 $A\to\alpha$ 加入 $M[A,b]$
   - 其他没有定义的条目均为 error

## 自底向上

自底向上相比自顶向下更加一般化，尝试根据产生式规则归约到文法的开始符号

### 移进归约

1. 归约 Reduce 是最右推导的**逆过程**
   - 每一步，**特定子串**被替换为相匹配的某个**产生式左部的非终结符**
   - 最终，输入串归约成文法的**开始符号**
   
2. 句柄 Handle 是可归约串
   - 在句型中和某产生式右部匹配的子串
   - 把它归约成该产生式左部的非终结符，代表了最右推导逆过程中的一步
   - 句柄的右端仅含终结符
   - 文法二义，则句柄不唯一

3. 移进-归约分析法
   - 用栈实现
   - 移进 shift：将下一个输入符号压入栈中，以形成句柄
   - 归约 reduce：将栈顶的句柄替换为相匹配产生式的左部非终结符
   - 接受 accept：分析成功
   - 报错 error：分析失败

4. 冲突
   - 移进-归约冲突
   - 归约-归约冲突

## LR 分析器的简单模型

1. LR(k) 文法
   - L 从左到右扫描
   - R 最右推导
   - k 向前看的符号个数

2. LR 分析器
   - 栈中存放**状态** $s_j$ 和**符号** $X_i$
   - 查表有**操作** ${\rm action}[s_m,a_i]$ (移进|归约|接受|出错) 和**跳转** ${\rm goto}[s_m,A_j]$ (归约后使用)

3. 关键在构建 LR 分析表
   - 计算所有可能的状态
   - 明确状态之间的**跳转关系**
   - 明确状态与输入间对应的**移进**或者**归约**操作

## 简单的 LR 方法 (SLR)

1. LR 语法分析的每一步都形成一个格局 configuration，包括栈内容 $s_0X_1s_1X_2s_2\ldots X_ms_m$ 和尚未处理的输入 $a_ia_{i+1}\ldots a_n\$$，其中 $X_1X_2\ldots X_m$ 是最右句型的一个前缀
   - 每一个前缀都对应一个状态，找出所有可能的前缀，就可以确定所有的状态
   - 状态间的转换就可以化为前缀间的转换
   - 栈顶为 $s$，下一个字符为 $a$ 的格局下，前缀为 $p$
     - 移进：在 $p$ 包含句柄一部分，且 $p'=pa$
     - 归约：在 $p$ 包含整个句柄

2. 活前缀或可行前缀 viable prefix:
   - 最右句型的前缀，前缀不超过最右句柄的右端
   - 出现在栈顶

3. LR(0) 项目 (简称项目)
   - 在右部的某个地方加点的产生式
   - 加点的目的是用来表示分析过程的状态
   - 点左边表示历史信息，点右边是展望信息

4. 拓广文法
   - 为文法增加一个新的开始符号 $S'$，并添加产生式 $S'\to S$
   - 为了方便，将 $S'$ 作为文法的开始符号
   - 当分析器归约到 $S'$ 时，分析成功

5. LR(0) 项目集规范族
   - 项目集规范族是若干可能前缀的集合，对应 DFA 的状态
   - 每个规范族包括核心项目与非核心项目，核心项目为初始项目/点不在最左边的项目，非核心项目为由核心项目求闭包而得
   - 求项目集 $I$ 的闭包 ${\rm closure}(I)$
     - $I$ 是项目集
     - ${\rm closure}(I)=I\cup\{B\to\cdot\gamma|A\to\alpha\cdot B\beta\in I,B\to\gamma\}$
   - 求项目集 $I$ 和文法符号 $X$ 的 $I'={\rm goto}(I,X)$
     - $I'=\varnothing$
     - $I'=I'\cup{\rm closure}(A\to\alpha X\cdot\beta)$，其中 $A\to\alpha\cdot X\beta\in I$
   - 首先是 $I_0$，其由核心项目 $S'\to S$ 得来
   - 然后是 $I'={\rm goto}(I,X)$

6. 从 $I_i$ 构造，得到如下 ${\rm action}$ 函数，以下约定 $a$ 为终结符
   - 如果 $A\to\alpha\cdot a\beta\in I_i$，且 ${\rm goto}(I_i,a)=I_j$，则 ${\rm action}[i,a]=sj$
   - 如果 $A\to\alpha\cdot\in I_i$，则对 $a\in{\rm FOLLOW}(A)$，则 ${\rm action}[i,a]=rj$，$j$ 为产生式 $A\to\alpha$ 的编号
   - 如果 $S'\to S\cdot\in I_i$，则 ${\rm action}[i,\$]=acc$
   - 而如果出现动作冲突，则文法不是 SLR(1) 文法

7. 一个上下文无关文法 $G$，通过上述4,5,6算法构造出 SLR 语法分析表，且表项中没有移进/归约或者归约/归约冲突，则为 SLR(1) 文法

8. LR(0) 自动机刻画了所有可能出现在栈中的所有串，但不是所有前缀都会出现在栈中

## 规范的 LR 方法

1. SLR(1) 文法的描述能力是有限的，当 ${\rm FOLLOW}$ 集合与移进的符号有重合时会出现移进/归约冲突，所以需要更强的 LR 方法

2. 规范的 LR 分析
   - 目标：在识别活前缀 DFA 的**状态**中，**增加信息**，**排除一些**不正确的**归约**操作
   - 方法：增加了前向搜索符号，将一个项目 $A\to\alpha\cdot\beta$ 中归约之后期望看到 $a$，则定义其前向搜索符为 $a$，且前向搜索符集合为 ${\rm FOLLOW}(A)$ 的子集
   - 与 SLR(1) 分析的区别：项目集的定义从 LR(0) 变为 LR(1)，之前的 ${\rm closure}(I)$ 和 ${\rm GOTO}$ 函数均有变化

3. LR(1) 项目：$[A\to\alpha\cdot\beta,a]$
   - LR(1) 中的1代表了搜索符 $a$ 的长度
   - 仅在 $\beta\to\varepsilon$ 时，$a$ 起作用，若下一个输入符号为 $a$，则按照 $A\to\alpha$ 归约

4. 构造 LR(1) 项目集规范族
   - ${\rm closure}(I)=I\cup\{[B\to\gamma,b]|[A\to\alpha\cdot B\beta,a]\in{\rm closure}(I),B\to\gamma,b\in{\rm FIRST}(\beta a)\}$
   - ${\rm goto}(I,X)={\rm closure}(\{[A\to\alpha X\cdot\beta,a]|[A\to\alpha\cdot X\beta,a]\in I\})$
   - 起始 $I_0={\rm closure}({[S\to S',\$]})$

5. 构造 LR 分析表，其中跳转不变，而动作函数变为
   - 如果 $[A\to\alpha\cdot a\beta,b]\in I_i$ 且 ${\rm goto}(I_i,a)=I_j$，则 ${\rm action}[i,a]=sj$
   - 如果 $[A\to\alpha\cdot,a]\in I_i$ 且 $A\neq S'$，则 ${\rm action}[i,a]=rj$
   - 如果 $[S'\to S,\$]\in I_i$ 则 ${\rm action}[i,\$]=acc$
   - 空白或冲突为 error

6. SLR(1) 文法都是 LR(1) 的