编译技术笔记

# 引论

# 什么是编译程序

# 编译程序

编译程序是翻译程序的一种，它将高级语言程序翻译成等价的目标程序。编译程序的输入是高级语言程序，输出是目标程序。编译程序的主要任务是将源程序翻译成目标程序，使得目标程序能够在计算机上正确运行。

# 解释程序

以源程序为输入，直接执行源程序，不生成目标程序。解释程序的主要任务是解释源程序，使得源程序能够在计算机上正确运行。

# 编译程序与解释程序的区别

根本区别：是否生成目标程序。

# 编译系统的组成

• 编译程序
• 运行系统
  • 支持环境
  • 运行库

# 编译过程与编译程序的组织结构

# 编译过程

# 词法分析

输入源程序；扫描、分解字符串，识别出单词；输出单词流。

词法分析由词法分析器完成，词法分析器又叫扫描器。

词法分析器从左到右扫描源程序，并将其转换成单词（Token）串；并检查词法错误，进行标识符的登记 —— 符号表管理。

输入：字符串
输出：（种别码，属性值）

# 语法分析

语法分析由语法分析器完成，语法分析器又叫解析器。

功能：

• 实现组词成句
• 构造分析树
• 检查语法错误
• 指导翻译

输入：Token 序列
输出：语法成分

# 语义分析

语义分析一般和语法分析一起进行，称为语法制导翻译。

功能：

• 获取标识符的属性
• 语义检查
• 子程序静态绑定
• 变量的静态绑定

# 中间代码生成

生成四元式、三地址码、P - 代码等。

# 目标代码生成

任务：将中间代码变换成特定机器上的低级语言代码

目标代码形式：绝对指令、可重定位指令、汇编指令

# 表格与表格管理

• 符号名表
• 常数表
• 标号表
• 入口名表
• 过程引用表
• 循环表
• 等价名表
• 公用链表
• 格式表
• 中间代码表

# 出错处理

• 语法错误：不符合语法（或词法）规则
• 语义错误：不符合语义规则

# 遍

遍：编译程序对源程序的从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。

# 前端与后端

• 前端：词法分析、语法分析、语义分析、中间代码生成，与源语言有关
• 后端：目标代码生成、优化，与目标机器有关

# 自举技术

编译程序的编译程序完全是由这个语言本身编写的，而且能够编译这门语言的任何代码。

# 自展技术

先对语言的核心部分构造一个小小的编译程序，然后用这个编译程序编译语言的其他部分。

# 移植技术

编译程序的移植性是指编译程序能够在不同的计算机上运行。

# 形式语言与自动机

# 形式语言

# 语言

• 语言（Language）：满足一定条件的句子的集合
• 句子（Sentence）：满足一定规则的单词的序列
• 单词（Token）：满足一定规则的字符串

语言就是字和组合字的规则所产生的字的序列。

# 文法、语言、自动机

• 0 型文法：递归可枚举语言，图灵机
• 1 型文法：上下文相关语言，线性有界自动机

  $$S A \rightarrow S S \\ S \rightarrow a \\ A \rightarrow a$$

• 2 型文法：上下文无关语言，下推自动机，例如$A\to \beta$
• 3 型文法：正规语言，有限自动机，例如$A\to \alpha B$

# 程序语言

程序语言是一个记号系统

# 语法

• 任何程序语言都可以看成一定字符集上的字符串
• 语法保障了这串字符的合法性
• 语法 = 词法规则 + 语法规则

# 词法

• 单词符号：语言中具有意义的最基本结构
• 词法规则
  • 规定了字母表中的字符如何组成单词符号
  • 程序语言的单词符号包括：常数、标识符、关键字、运算符、分节符等
  • 使用正规式和有限自动机理论描述词法结构和词法分析

# 语法规则

• 语法单位：表达式、子句、语句、函数、过程、程序
• 语法规则
  • 规定了如何从单词符号构成语法单位
  • 使用上下文无关文法描述语法结构和语法分析
  • 语言的词法规则和语法规则共同定义了程序的形式结构，是判断输入字符串是否都成一个形式上正确的程序的依据

# 语义

• 程序中单词符号和语法单位的含义
• 不同语言形式上语法单位相似，但含义可能不同
• 对于某种语言，可以定义一个程序的意义的一组规则，称为语义规则
• 目前大多数编译程序使用基于属性文法的语法制导翻译来分析语义

# 字母表

字母表是符号的非空有限集合，通常用 $\Sigma$ 表示。

# 字母表的运算

字母表$\Sigma, \Sigma_1, \Sigma_2$ 的运算：

• 连接 / 乘积：$\Sigma_1\Sigma_2 = \{xy | x \in \Sigma_1, y \in \Sigma_2\}$
• 幂：$\Sigma^n = \{x_1x_2\cdots x_n | x_i \in \Sigma\}$，其中$n=0$ 时，$\Sigma^0 = \{\varepsilon\}$
• 正闭包，记作$\Sigma^+$：$\Sigma^+ = \Sigma^1\cup\Sigma^2\cup\cdots$
• Kleene 闭包，记作$\Sigma^*$：$\Sigma^* = \Sigma^0\cup\Sigma^+=\Sigma^0\cup\Sigma^1\cup\Sigma^2\cup\cdots$

# 符号串

由字母表中的符号所组成的任何有穷序列称为符号串。也叫做字母表上的句子。

# 符号串的形式定义

• 字母表$\Sigma$ 上的字符是$\Sigma$ 上的符号串
• 若$x$ 是$\Sigma$ 上的符号串，$a$ 是$\Sigma$ 上的字符，则$x\cdot a$ 是$\Sigma$ 上的符号串
• $y$ 是$\Sigma$ 上的符号串，当且仅当它是由上述规则生成的

# 符号串的术语

• 前缀：移走$s$ 尾部的零个或多个字符得到的串称为$s$ 的前缀
• 后缀：移走$s$ 头部的零个或多个字符得到的串称为$s$ 的后缀
• 子串：从$s$ 中删去一个前缀和一个后缀得到的串称为$s$ 的子串
• 真前缀、真后缀、真子串：不等于$s$ 和$\varepsilon$ 的前缀、后缀、子串
• 子序列：从$s$ 中任意删除零个或多个字符得到的串称为$s$ 的子序列
• 长度：符号串的字符个数称为该串的长度，记作$|s|$

# 句子和语言

• 句子：字母表上符合某种规则构成的符号串
• 语言：确定字母表上字符串的集合，即句子的集合，即$\forall L\subseteq\Sigma^*$

# 符号串的运算

• 连接：设$x,y$ 是$\Sigma$ 上的符号串，它们的连接$xy$ 是$x$ 后接$y$ 的符号串
• 方幂：设$x$ 是$\Sigma$ 上的符号串，$n$ 是非负整数，$x^n$ 是$x$ 的$n$ 次方幂，即$x$ 连接自身$n$ 次

# 语言的运算

• 并：$L\cup M = \{x|x\in L or x\in M\}$
• 连接：$LM = \{xy|x\in L and y\in M\}$
• 方幂：$L^n = \{x^n|x\in L\}$
• Kleene 闭包：$L^* = L^0\cup L^1\cup L^2\cup\cdots$
• 正闭包：$L^+ = L^1\cup L^2\cup\cdots$

# 文法

字和组合的字规则，是描述语言的语法结构的形式化规则。

# BNF 范式

巴科斯 - 诺尔范式（Backus-Naur Form，BNF）是一种用于表示上下文无关文法的语言。

用 ::= 或 -> 表示 “定义为”，用 | 表示 “或”， | 两边的成分叫做候选式，用 <> 表示非终结符。

# 语法规则的推导

由规则推导句子：从一个要识别的符号开始，用相应规则的右部替换左部，直到推导出句子，每次仅用一个规则。推导一直进行到句子中不再有非终结符为止。

# 文法的形式定义

• 文法$G$ 是一个四元组$G=(V_T,V_N,P,S)$
  • $V_T$：非空有穷终结符集合
  • $V_N$：非空有穷非终结符集合且$V_T\cap V_N=\varnothing$
  • $S$：开始符号，$S\in V_N$
  • $P$：产生式的非空有穷集合，每个产生式是一个形如$A\to\alpha$ 的规则，其中$A\in V_N,\alpha\in(V_T\cup V_N)^*$，开始符号$S$ 必须至少出现在一个产生式的左部

# 直接推导和推导

令$G=(V_T, V_N, S, P), S\Rightarrow\alpha A\beta$，

• 若$A\rightarrow\gamma\in P$，则称$\alpha A\beta$ 直接推导出$\alpha\gamma\beta$，记作$\alpha A\beta\Rightarrow\alpha\gamma\beta$，同时称$\alpha\gamma\beta$ 直接由$\alpha A\beta$ 推导出，或称$\alpha\gamma\beta$ 直接规约为$\alpha A\beta$
• 如果存在一个直接推导的有限序列$\alpha_0\Rightarrow\alpha_1\Rightarrow\alpha_2\Rightarrow\cdots\Rightarrow\alpha_n$，表示成$\alpha_1\xRightarrow{+}\alpha_n$，则称从$\alpha_0$ 到$\alpha_n$ 的长度为$n$ 的推导。$\alpha_0\xRightarrow{*}\alpha_n$ 表示从$\alpha_0$ 的经 0 步或多步推导得到$\alpha_n$

# 最左推导和最右推导

• 最左推导：$\alpha A\beta\Rightarrow\alpha\gamma\beta(A\rightarrow\gamma),\alpha\in V_T^*$，每次推导都是用最左边的非终结符推导
• 最右推导：$\alpha A\beta\Rightarrow\alpha\gamma\beta(A\rightarrow\gamma),\beta\in V_T^*$，每次推导都是用最右边的非终结符推导，也称为规范推导

# 语言的形式定义

设文法$G=(V_T,V_N,P,S)$，如果$S\xRightarrow{*}\alpha$，则称$\alpha$ 是一个句型。仅含终结符的句型称为句子。

语言$L(G)$ 是文法$G$ 的所有句子的集合：$L(G)=\{\alpha|S\xRightarrow{+}\alpha\text{且}\alpha\in V_T^*\}$

# 短语、直接短语和句柄

令$G$ 是一个文法，如果有$S\xRightarrow{*}\alpha A\gamma\text{且}A\xRightarrow{+}\beta$，则称$\beta$ 是句型$\alpha\beta\gamma$ 的相对于非终结符$A$ 的短语

特别是，如果有$A\rightarrow\beta$，则称$\beta$ 是句型$\alpha\beta\gamma$ 的相对于$A\rightarrow\beta$ 的直接短语，一个句型的最左直接短语称为句型的句柄

# 分析树

设$G=(V_T,V_N,P,S)$ 是一个上下文无关文法，$G$ 的一个分析树是一个有根树，满足以下条件：

• 每个节点有个标记，是$V_T\cup V_N\cup\{\varepsilon\}$ 的元素
• 根节点标记为$S$
• 如果节点是内部节点，则其标记$A$ 必在$V_N$ 中
• 如果编号为$n$ 的节点标记为$A_{n_1,n_2,\cdots,n_k}$ 是节点$n$ 从左到右的儿子，并分别标有$X_1,X_2,\cdots,X_k$，则$A\rightarrow X_1X_2\cdots X_k$ 必须是$P$ 中的一个产生式
• 如果节点$n$ 有标记$\varepsilon$，则$n$ 必须是叶节点，且是他父亲的唯一儿子，其他叶子节点是$V_T$ 中的元素（终结符）

# 子树

一棵分析树中一个特有节点连同他的全部后裔，连接这些节点的边和边上的标记称为这个节点的子树。

# 从语法树看短语、直接短语和句柄

• 短语：一棵子树的所有叶子从左至右排列起来形成一个相对于该子树根节点的串。
• 直接短语：如果一棵子树只有两代，它的叶子从左至右排列起来形成的串。
• 句柄：一个句型的分析树中，最左那棵两代子树的叶子从左至右的排列。

找到句型的短语：找分析树的所有子树

1. 最左推导和最右推导的语法树是否相同？

尽管推导顺序不同，两者生成的语法树是一样的，因为语法树表示的是推导过程中应用的规则和它们的结构关系，而不是推导的具体顺序。因此，不管是最左推导还是最右推导，最终语法树的形状和结构都相同，表示句子中的层次关系。

# 二义性

如果一个文法存在两个不同的分析树，那么这个文法是二义的。如果一个文法包含二义性句子，那么这个文法是二义的。

# 自动机

# 有限自动机

# 有限自动机基本组成

• 有限自动机（FA）是一种识别装置，能准确识别正规文法，为词法分析程序提供了方法和工具。
• 离散输入输出系统，具有有限数目的内部状态
• 根据当前所处的状态和面临的输入字符决定系统的后继行为。

# 有限自动机工作原理

• 状态为初始状态、中间状态和终止状态。
• 可以有若干个终止状态。
• 只能有一个初始状态。

# 状态转换图

状态用节点表示，输入符号用边表示，两个圈表示终止状态。

# 确定的有限自动机（DFA）

# DFA 的定义

• 一个确定的有限自动机是一个五元组$M=(\Sigma, S, S_0, Z, f)$
  • $\Sigma$：输入字母表
  • $S$：有限状态集合
  • $S_0$：初始状态
  • $Z$：终止状态集合
  • $f$：状态转移函数，从$S\times\Sigma$ 到$S$ 的映射，$f(q,a)=q'$ 表示从状态$q$ 经过输入$a$ 转移到状态$q'$，$q'$ 称为状态$q$ 的后继状态

# DFA M 接受的语言

• 如果对所有的输入字符串$w\in\Sigma^*$，以下述方式递归地对 DFA M 扩充$f$ 的定义：
  • $f(q,\varepsilon)=q$
  • $f(q,wa)=f(f(q,w),a)$

# DFA M 所识别的语言

从状态转换图看，从初态出发，沿任一条路径到达终结状态，这条路径上的弧上的标记符号连接起来构成的符号串是 DFA M 所识别的语言。

DFA M 所识别的符号串的全体记作$L(M)$，即$L(M)=\{w|w\in\Sigma^*,\text{若存在}q\in Z\text{使得}f(q_0,w)=q\}$

# 非确定的有限自动机（NFA）

# NFA 的定义

• 一个非确定的有限自动机是一个五元组$M=(\Sigma, S, S_0, Z, f)$
  • $\Sigma$：输入字母表
  • $S$：有限状态集合
  • $S_0$：初始状态
  • $Z$：终止状态集合
  • $f$：状态转移函数，从$S\times(\Sigma\cup\{\varepsilon\})$ 到$2^S$ 的映射，其中$2^S$ 表示$S$ 的幂集，即$S$ 的所有子集的集合。

# NFA M 接受的语言

如果$f(q,a)=\{q_1,q_2,\cdots,q_k\}$，则从状态$q$ 经过输入$a$ 可以转移到状态$q_1,q_2,\cdots,q_k$ 中的任意一个。

# NFA M 所识别的语言

$L(M')=\{\alpha|f(q_0,\alpha)=q,q\in Z\}$

# FA 的等价定理

对于任何 NFA M，都存在一个 DFA M'，使得$L(M)=L(M')$。

NFA 和 DFA 的区别：

# 具有$\varepsilon$ - 转移的 NFA 构造 DFA 的方法

集合$I$ 的$\varepsilon$ - 闭包定义:

• 令$I$ 是一个状态集的子集，定义$I$ 的$\varepsilon\text{-closure}(I)$
  • 若$s\in I$，则$s\in \varepsilon\text{-closure}(I)$
  • 若$s\in I$，则从$s$ 出发的所有$\varepsilon$ - 转移的状态都在$\varepsilon\text{-closure}(I)$ 中

设$a$ 是$\Sigma$ 中的一个符号，定义$I_a = \varepsilon\text{-closure}(J)$，其中$J=f(I,a)$

# 构造方法

确定化：不失一般性，设字母表$\Sigma$ 中的符号是$a,b$，

• 首先，置第一行第一列为$\varepsilon\text{-closure}(\{X\})$，求出这一列的$I_a$ 和$I_b$，
• 然后，检查这两个$I_a$ 和$I_b$ 是否在第一列中，如果不在，就加入到第一列中，然后求出这两个$I_a$ 和$I_b$ 的$I_a$ 和$I_b$，如此循环下去，直到没有新的$I$ 加入为止。

# 等价分析

• 把表看成状态转移矩阵，子集视为状态
• 转换表唯一刻画了一个 DFA M
  • 初态是$\varepsilon\text{-closure}(\{X\})$
  • 终态是包含原终态$Y$ 的子集

# DFA 的最小化

# DFA 的最小化定义

DFA M=$(\Sigma, S, S_0, Z, f)$ 的化简是指寻找一个状态数比较少的 DFA M'，使$L(M) = L(M')$

一个 DFA M 的最小化是指他没有多余状态并且没有相互等价的状态。

# DFA 的多余状态（无关状态）

1. 从开始状态出发，任何输入串也不能到达的那个状态
2. 从该状态出发没有通向终态的道路

# DFA 的等价状态

设$p,q \in S$，如果对于任何输入符号$w\in\Sigma^*$，$f(p,w)$ 和$f(q,w)$ 同时到达终态或同时不到达终态，则称状态$p$ 和$q$ 是等价的。

判断$p$ 和$q$ 不等价：只要存在一个输入符号$w\in\Sigma^*$，使得$f(p,w)\in Z$ 而$f(q,w)\notin Z$，或者$f(p,w)\notin Z$ 而$f(q,w)\in Z$。

若$S_i$ 为自动机$M$ 的一个状态集，我们把从$S_i$ 出发能导出的所有符号串集合记为$L(S_i)$，若有$L(S_i)=L(S_j)$，则称$S_i$ 和$S_j$ 等价。

# 可区别状态

自动机的两个状态$S_i$ 和$S_j$，如果他们不等价，则称他们是可区别的。

# 分割法

把一个 DFA（不含多余状态）的状态分割成一些不相关的子集，使得任何不同的两个子集状态都是可区别的，而同一个子集中的任何状态都是等价的。在各个子集中任取一个状态做代表，删去子集的其余状态。

1. 首先将终态和非终态分开，分为$\Pi = \{Z, S-Z\}$
2. 对$\Pi$ 中的每个集合$G$，$G$ 中任意两个状态$S_i$ 和$S_j$ 在同一组中，当且仅当对于$\forall a\in\Sigma$，$f(S_i,a)$ 和$f(S_j,a)$ 在同一组中，否则将$S_i$ 和$S_j$ 分开，用$G$ 替换原来的集合
3. 重复第 2 步，直到不能再分为止
4. 合并等价状态，在每个$G$ 中任取一个状态作为代表，删去$G$ 中其余状态
5. 删去多余状态，从其他状态到无关状态到转换都成为无定义

# NFA 的最小化

NFA 化为 DFA，然后再对 DFA 进行最小化。

# 词法分析

# 词法分析的功能

对源程序进行从左到右的顺序扫描，按照词法规则从中识别出一个个具有独立意义的单词符号并把源程序转换为等价的内部表示形式（属性字流）。

• 识别单词符号
• 过滤掉源程序中的注释和空白符
• 对数字字符串转换为二进制数
• 记录读入字符的行号和列号，以便编译程序输出错误信息时能够准确指出错误位置
• 进行预编译
• 符号表操作和错误处理

# 实现词法分析的方案

1. 词法分析单独作为一遍（优点：结构清晰，各遍功能单一；缺点：生成中间文件，效率低）
   
2. 词法分析程序作为单独的子程序
   

# 预处理 —— 扫描缓冲区

• 两个半区互补使用：搜索指针从单词起点开始搜索，如果遇到半区域的边界，但尚未到达单词的终点时，则可将后续的输入字符装入该缓冲区的另一半
  

If f at end of first half {

  reload second half;

  F++;

} Else if F at end of second half {

  reload first half;

  move F to beginning of first half;

} Else {

  F++;

}

# 单词的描述和识别

# 单词的种类

• 保留字
• 标识符
• 常数
• 运算符
• 界限符

# 词法分析程序的输出形式

常用的单词内部表示形式：

• 按单词种类分类
• 保留字和分界符一符一类
• 标识符和长处的单词属性值作为符号表入口指针（标识符、常数相关属性很多）

# 出错处理

• 非法字符检查
• 关键字拼写错误检查
• 不封闭错误检查
• 重复说明错误检查
• 错误恢复与续编译

# 正规式（Regular Expression）

正则表达式是一种描述字符串特征的表达式，是一种用来描述字符串的方法。

正则表达式可以有较小的正则表达式递归地构建，每个正则表达式$r$ 都可以用来描述一个语言$L(r)$。

# 正规集

1. $\varnothing$ 和$\varepsilon$ 都是$\Sigma$ 上的正规表达式，他们所表示的语言分别为$\{\}$ 和$\{\varepsilon\}$
2. 对于$\forall a\in\Sigma$，$a$ 是$\Sigma$ 上的正规表达式，他所表示的语言为$\{a\}$
3. 如果$r$ 和$s$ 是$\Sigma$ 上的正规表达式，那么$r|s$，$rs$，$r^*$ 都是$\Sigma$ 上的正规表达式，他们所表示的语言分别为$L(r)\cup L(s)$，$L(r)L(s)$，$L(r)^*$

一个由正规表达式定义的语言称为正规集或正规语言。

# 正规式的代数性质

• 交换律：$r|s=s|r$
• 结合律：$(r|s)|t=r|(s|t)$
• 分配律：$r(s|t)=rs|rt$
• 幂等律：$r|r=r$，$r^*=(r|r)^*=r^*r^*$，$(r^*)^*=r^*$

# 正则定义

• 正则定义：正规表达式是由正规集上的运算符和正规集中的元素组成的表达式

$$\begin{aligned} d_1 &\to r_1\\ d_2 &\to r_2\\ &\cdots\\ d_n &\to r_n \end{aligned}$$

• 其中$d_1,d_2,\cdots,d_n$ 是新符号，都不在$\Sigma$ 中，$r_1,r_2,\cdots,r_n$ 是$\Sigma\cup\{d_1,d_2,\cdots,d_n\}$ 上的正规表达式

# 正规文法$\Rightarrow$ 正规式

# 正规式$\Rightarrow$ 正规文法

1. 对任何正规表达式$r$，选择一个非终结符$S$ 作为识别符号。并构建正规定义式$S\to r$
2. 若$x,y$ 是正规表达式，$A\to xy$ 重写为$A\to xB,B\to y$，$A\to x*y$ 重写为$A\to xA,A\to y$，其中$B$ 是新的非终结符

# 正规式与有限自动机

定理：设$r$ 是$\Sigma$ 上一个正规表达式，则存在一个 FA $M$ 接受$L(r)$。反之亦然。

正规文法，正规表达式和有限自动机三者之间在表示语言的意义下是等价的。

字母表$\Sigma$ 上的一个正规语言，既可以由某一个正规文法产生，也可以由某一个正规表达式所表示，还可以由某一个有限自动机识别。

# 转换法实现正规式与有限自动机的转换

# 从正规式到 NFA 的转换规则

对于$\Sigma$ 上任一正规表达式$r$，一定能构造一个 NFA $M$，使得$L(r)=L(M)$。

• 首先把转换图的概念拓广，每条弧上可以用一个正规式标记，对 NFA $M$ 构造一个广义的转换图。其中只有开始状态$S$ 和终止状态$Z$，连接$S$ 和$Z$ 的有向弧上是正规式$r$。
• 然后按照下面的替换规则对正规式不断进行分解，不断加入状态结点和箭弧，直到转换图上的所有弧标记都是$\Sigma$ 上的元素或$\varepsilon$ 为止。

# 从 NFA 到正规式的替换规则

对于$\Sigma$ 上任一 NFA $M$，能构造$\Sigma$ 上一个正规表达式 $r$，使得$L(r) = L(M)$。

• 首先，在$M$ 的转换图上加进$S$，$Z$ 两个节点。从$S$ 用$\varepsilon$ 弧连接到$M$ 的所有初态结点，从$M$ 的所有终结（接受）结点用$\varepsilon$ 弧连接到$Z$，从而构成一个新的 NFA $M'$，$L(M) = L(M')$。
• 反复使用下面的替换规则逐步消去 NFA $M'$ 中的状态结点和弧，直至剩下$S$，$Z$ 为止。在消去结点的过程中，逐步用正规式标记弧。

# 正规文法与 FA 的等价性

如果对于某个正规文法$G$ 和某个有限自动机$M$，有$L(G) = L(M)$（正规文法$G$ 所产生的语言和某个有限自动机所识别的语言相同），则称$G$ 和$M$ 是等价的。

定理 对每一个右线性正规文法或左线性正规文法 $G$，都存在一个 FA $M$，使 $L(M) = L(G)$

定理 对于每一个 FA $M$，都存在一个右线性正规文法 $G$ 和一个左线性正规文法 $G'$，使 $L(M) = L(G) = L(G')$.

# 有限自动机$\Rightarrow$ 正规文法（右线性正规文法）

1. 对转换函数$f(A, t) = B$，可写成一个产生式：$A \rightarrow tB$

2. 对可接受状态$Z$，增加一个产生式：$Z \rightarrow \varepsilon$

3. 有限自动机的初态对应于文法的开始符号，有限自动机的字母表文法的终结符号集.

# 正规文法（右线性）$\Rightarrow$ 有限自动机

1. 字母表与 $G$ 的终结符号相同。
2. 为 $G$ 中的每个非终结符生成 $M$ 的一个状态，$G$ 的开始符号 $S$ 是开始状态 $S$；
3. 增加一个新状态 $Z$，作为 NFA 的终态。
4. 对 $G$ 中的形如 $A \rightarrow tB$，其中 $t$ 为终结符或 $\epsilon$，$A$ 和 $B$ 为非终结符的产生式，构造 $M$ 的一个转换函数 $f(A, t) = B$。
5. 对 $G$ 中的形如 $A \rightarrow t$ 的产生式，构造 $M$ 的一个转换函数$f(A, t) = Z$

# 词法分析程序的实现

• 构造识别单词的状态转换图
  • 对程序语言的单词按种类分别构造对应的状态转换图.
  • 对各类转换图合并，构成一个能识别语言所有单词的状态转换图.
• 编程实现状态转换图

# 限制条件

• 所有基本字都是保留字；用户不能用它们作自己的标识
  符
• 基本字作为特殊的标识符来处理，使用保留字表如果基本字、标识符和常数（或标号）之间没有确定的运算符或界符作间隔，则必须使用一个空白符作间隔

# 状态转换图的代码实现

每个状态节点对应一小段程序

# 不含回路的分叉节点

GetChar();

if (IsLetter()) {

  // 状态 j

} else if (IsDigit()) {

  // 状态 k

} else if (ch == '\\') {

  // 状态 m

} else {

  // 错误处理

}

# 含回路的状态节点

GetChar();

while (IsLetter() || IsDigit()) {

  GetChar();

}

// 状态 j

# 终态节点

直接返回单词符号

return (C, VAL);

C 是单词种别， VAL 是单词的属性值

# 全局变量与过程

• ch 字符变量，存放最新读入的源程序字符
• strToken 字符数组，存放构成单词符号的字符串
• GetChar 子程序过程，把下一个字符读入到 ch 中
• GetBC 子程序过程，跳过空白符，直至 ch 中读入一非空白符
• Concat 子程序，把 ch 中的字符连接到 strToken
• IsLetter 和 IsDisgital 布尔函数，判断 ch 中字符是否为字母和数字
• Reserve 整型函数，对于 strToken 中的字符串查找保留字表，若它是保留字则给出它的编码，否则回送 0
• Retract 子程序，把搜索指针回调一个字符位置
• Insertld 整型函数，将 strToken 中的标识符插入符号表，返回符号表指针
• InsertConst 整型函数过程，将 strToken 中的常数插入常数表，返回常数表指针

# 状态图代码一般化

curState = 初态;

GetChar();

while (stateTrans[curState][ch] 有定义) {

  // 存在后继状态，读入，拼接

  Concat();

  // 转换入下一个状态，读入下一个字符

  curState = stateTrans[curState][ch];

  if (curState == 终态) {

    // 返回单词符号

    return (C, VAL);

  }

  GetChar();

}

# 词法分析程序的设计过程

词法规则 -> 正规式 -> 状态转换图 -> 合并状态转换图 -> 编程实现

# 词法分析阶段的错误处理

# 可检测的错误类型

• 单词拼写错误
• 非法字符

# 词法错误检测

如果当前状态与当前输入符号在转换表对应项中的信息为空，而当前状态又不是终止状态，则调用错误处理程序

# 词法错误处理的方法

查找已扫描字符串中最后一个对应于某终态字符

• 如果找到了，将该字符与其前面的字符识别成一个单词。然后将输入指针退回到该字符，扫描器重新回到初始状态，继续识别下一个单词
• 如果没找到，则确定出错，采用错误恢复策略

# 错误恢复策略

最简单的错误恢复策略！恐慌模式（panic mode）恢复
从剩余的输入中不断删除字符，直到词法分析器能够在剩余输入的开头发现一个正确的字符为止

# 自顶向下语法分析

# 词法、语法的关系

• 源语言的文法可以分解词法和语法

  • 词法：描述语言单词符号构成的文法
  • 语法：描述语言结构的文法

• 用正规文法或正规表达式描述单词符号的结构

• 用上下文无关文法描述语言的结构

• 词法产生式的终结符号是单个字符

• 语法产生式的终结符号是单词符号

# 语法分析器的作用

• 语法分析任务：按照语言规定的语法规则，对词法分析形成的记号（单词）串进行语法检查，识别出相应的语法成分，采用语法树的形式输出，如果不符合语法要求则给出出错的原因。
• 语法分析程序：执行语法分析的程序，也称语法分析器.
• 语法分析的关键：句型的识别

# 书写格式约定

• 终结符号
  • 次序靠前的小写字母，如$a$, $b$, $c$
  • 标点符号
  • 黑体的字串 $\textbf{if}, \textbf{for}$
• 非终结符号
  • 次序靠前的大写字母和$S$
  • 小写的斜体的名字 $\textit{expr}$
• 文法符号：次序靠后的大写字母 $X$, $Y$, $Z$
• 终结符号串：次序靠后的小写字母，$U$, $V$, ...
• 文法符号串：小写的希腊字母，$\alpha$, $\beta$, $\gamma$

# 推导

推导：就是用产生式的右部的串来代替左部的非终结符，事实上推导给出了自顶向下构成分析树过程的精确描述。

# 消除二义性

• 引入新的语法成分，使得原来的文法成为无二义的文法。
• 增加就近原则，使得文法成为无二义的文法。

# 下推自动机

# 消除左递归

一个文法$G$，若存在推导$A\xRightarrow{+}A\alpha$，则称$G$ 是左递归的。

消除直接左递归的方法：

若：$A\rightarrow A\alpha_1|A\alpha_2|\cdots|A\alpha_n|\beta_1|\beta_2|\cdots|\beta_m$，其中$\beta_i$ 不以$A$ 开头，$i=1,2,\cdots,m$，则可将$A$ 的产生式分为两部分：

$$\begin{aligned} A &\rightarrow \beta_1A'|\beta_2A'|\cdots|\beta_mA'\\ A' &\rightarrow \alpha_1A'|\alpha_2A'|\cdots|\alpha_nA'|\varepsilon \end{aligned}$$

消除间接左递归的方法：

• 非终结符号按照某种次序排列

• 消除算法

  	for i = 1 to n
  	for j = 1 to i-1
  	用A_i的产生式替换A_j的产生式中的A_i
  	end for
  	消除A_i的直接左递归
  	end for

• 去除开始符号无法到达的非终结符号的产生式

# 提取左因子

文法$G$ 的产生式$A\rightarrow\alpha|\beta$，若$\alpha\xRightarrow{*}\alpha_1$，$\beta\xRightarrow{*}\beta_1$，$\alpha_1$ 和$\beta_1$ 有一个最长的公共左因子$\gamma$

若$A\rightarrow\alpha\beta_1|\alpha\beta_2$，则可将$A$ 的产生式分为两部分：

$$\begin{aligned} A &\rightarrow \alpha A'\\ A' &\rightarrow \beta_1|\beta_2 \end{aligned}$$

# 递归下降分析法

# 包含回溯的递归下降分析法

思想：从语法的开始符号出发，试探使用不同产生式，寻找匹配于输入符号串的推导。或者说，从对应文法开始符号的根结点出发，自顶向下为输入符号串建立一棵分析树。

这种分析方法实质上是一种试探过程，是因为文法中，对于某个非终结符号的规则其右部有多个选择，并根据所面临的输入符号不能准确的确定所要选择时，就可能出现回溯。

上述分析称为带回溯的自顶向下分析。对于 w，从文法的开始符号出发，反复使用不同的产生式谋求匹配输入串。当用某个非终结符号的候选式进行匹配失败时，删除这个失败分析建立的分析树分支并回头查输入符号，以便与其它候选式匹配。

这种带回溯的自顶向下分析技术，效率很低，代价极高，因此，它只有理论上的意义。

# 不包含回溯的递归下降分析法

在不含左递归和每个非终结符的所有候选式的终结首符集都两两不相交（不含左因子）条件下，构造一个不带回溯的自上而下分析程序，该分析程序由一组递归过程组成，每个过程对应文法的一个非终结符。这样的一个分析程序称为递归预测分析器。

在推导过程中，根据当前的向前看符号，决定选择哪个产生式往下推导，因此，分析过程是完全确定的。这种分析称为自顶向下的预测分析。

# 终结首符集辅助确定候选式

若当前符号 =$a$，对$A$ 展开，而$A\rightarrow \alpha_1|\alpha_2|\dots|\alpha_m$，那么，要知道哪一个$\alpha_i$ 是获得以$a$ 开头的串的唯一替换式。
即：选择哪一个$\alpha_i$，亦即通过查看第一个（当前）符号来发现合适的替换式$\alpha_i$。

怎样选择$\alpha_i$？

• 以$a$ 为头的$\alpha_i$；
• 如有多个$\alpha_i$ 以$a$ 为头的，这是文法的问题

定义$\text{First}(\alpha)$ 为串$\alpha$ 的首符号集合；

$$\textrm{First}(\alpha) = \{a|\alpha\xRightarrow{*}a\dots,a\in V_T\}$$

若$\alpha\xRightarrow{*}\varepsilon$，则$\varepsilon\in\text{First}(\alpha)$
若有产生式$A\rightarrow\alpha$，且$\alpha\xRightarrow{+}a\dots$，当遇到输入字符$a$ 时，选择$A\rightarrow\alpha$ 进行推导。

若一个$A\in V_N$ 有许多$\textrm{First}(\alpha_i)$，如果$A$ 当任何两个候选式$\alpha_i$ 和$\alpha_j$ 均有

$$\textrm{First}(\alpha_i)\cap\textrm{First}(\alpha_j)=\varnothing$$

意味着$A$ 每一候选式$\alpha$ 推导后所得的串的第一个$V_T$ 符号都不相同。
于是对输入符号$a$，如果$a\in\textrm{First}(\alpha_i)$，则$a \notin \textrm{First}(\alpha_j)$，因此对于输入符号$a$，可以唯一确定$A$ 的候选式$\alpha_i$。

# 递归的预测分析法

递归的预测分析法是指：在递归下降分析中，对文法中的每个非终结符编写一个函数或子程序，其功能是识别由该非终结符所表示的语法成分，由于语言的文法常常是递归定义的，因此这组函数或子程序必须以递归方式调用。

void A() {

  选择一个A的产生式，A->X1X2...Xn

  for i = 1 to n

    if (Xi是终结符号)

      调用过程Xi()

    else if (Xi等于当前输入符号)

      GetChar()

    else

      出错处理

}

# 递归预测分析器的构造

• 向前看符号决定了选择哪个产生式右部的文法符号串与输入符号串匹配，在程序中由向前看符号可以确定一段程序完成与某一产生式右部的匹配。
• 每一个非终结符号对应一个函数，函数的功能是根据向前看符号扩展分析树，同时用该非终结符号的儿子结点匹配输入符号串。

# 非递归预测分析法

# 预测分析表

递归分析表是矩阵$M[A,a]$，其中行标$A$ 是文法的非终结符号，列标$a$ 是文法的终结符号或串终结符$\#$，$M[A,a]$ 是$A$ 的一个候选式，指出当前栈顶符号是$A$，输入符号是$a$ 时，应该用$A\rightarrow a$ 进行推导，或者存放一个错误标记，指出$A$ 不该面临输入符号$a$。

# 符号栈

把 $\#$ 和文法开始符号 $S$ 推进栈，并读入输入串的第一个单词 $a$，重复下述过程直到正常结束或出错。

根据栈顶文法符号 $X$ 和当前单词符号 $a$ 的关系进行不同的处理：

• 若 $X = a = \#$，分析成功，停止。匹配输入串成功。
• 若 $X = a \ne \#$，把 $X$ 从栈顶弹出，再读入下一个符号。
• 若 $X \in V_n$，查分析表 $M$。

# 预测分析控制程序

置ip指向输入串w#的第一个符号

REPEAT

令X为栈顶符号，a为ip所指符号

IF X in VT | X == #

  IF X == a

    POP

    ip++

  ELSE

    ERROR

  ENDIF

ELSE

  IF M[X, a] == X -> Y1Y2...Yk

    POP

    PUSH YkYk-1...Y1

  ELSE

    ERROR

  ENDIF

ENDIF

UNTIL X == #

• 输出的产生式对应了最左推导
• 栈中： 残缺规范句型<未被匹配的句型>
• $M[X,a]$：指出$V_N$ 按哪一条产生式扩展，依赖于$M$ 表指出$(\text{栈顶}，a)$ 时，如何扩充语法树，出错了可以立即发现。

# 预测分析表的构造

# 什么时候使用$\varepsilon$ 产生式

如果当前某非终结符 $A$ 与当前输入符 $a$ 不匹配时，若存在 $A\rightarrow\varepsilon$，可以通过检查 $a$ 是否可以出现在 $A$ 的后面，来决定是否使用产生式 $A\rightarrow\varepsilon$。若文法中无 $A\rightarrow\varepsilon$，则应报错。

# FIRST 集

令 $G[S] = \{ V_T, V_N, S, P \}$ 是一个文法，则对任意文法串 $\alpha, \alpha \in (V_T \cup V_N)^*$，定义

$$\textrm{FIRST}(\alpha) = \{ a | \alpha \xRightarrow{*} a\dots , a \in V_T \}$$

若 $\alpha \xRightarrow{*} \varepsilon$，则规定 $\varepsilon \in \textrm{FIRST}(\alpha)$。

$\textrm{FIRST}(\alpha)$ 是$\alpha$ 所有可能推导出的开头终结符号的集合或可能为空串$\varepsilon$ 所组成的集合。

# FIRST 集的构造

# 单个符号的 FIRST 集

当 $\alpha \in (V_T \cup V_N)$ 时，连续使用下面的规则，直至每个 $\textrm{FIRST}$ 集不再增大为止：

• 若 $\alpha \in V_T$，则 $\textrm{FIRST}(\alpha) = \{ \alpha \}$
• 若 $\alpha \in V_N$，且有产生式 $\alpha \xRightarrow{*} a\dots, a \in V_T$，则将 $a$ 加入到 $\textrm{FIRST}(\alpha)$ 中， 若 $\alpha \rightarrow \varepsilon$，则将 $\varepsilon$ 加入到 $\textrm{FIRST}(\alpha)$ 中。

# 多个符号的 FIRST 集

当$\alpha = X_1X_2\dots X_n$ 时，把$\text{FIRST}(X_1)$ 的所有非$\varepsilon$ 元素加入到$\text{FIRST}(\alpha)$，若$\varepsilon$ 在$\text{FIRST}(X_1)$ 中，把$\text{FIRST}(X_2)$ 的所有非$\varepsilon$ 元素也加入到$\text{FIRST}(\alpha)$，若$\varepsilon$ 既在$\text{FIRST}(X_1)$ 中也在$\text{FIRST}(X_2)$ 中，把$\text{FIRST}(X_3)$ 的所有非$\varepsilon$ 元素也加入到$\text{FIRST}(\alpha)$，...，若对所有的$\text{FIRST}(X_i)$，$i=1,\dots,n$，都含有$\varepsilon$，把$\varepsilon$ 加入到$\text{FIRST}(\alpha)$。

# FOLLOW 集

令 $G[S] = \{ V_T, V_N, S, P \}$ 是一个文法，则

$$\textrm{FOLLOW}(A) = \{ a | S \xRightarrow{*} \dots Aa \dots, a \in V_T, A \in V_N \}$$

若$S \xRightarrow{*} \dots A$，则规定$\# \in \textrm{FOLLOW}(A)$，$\#$作为输入串的右结束符号。

$\textrm{FOLLOW}(A)$ 是所有句型中$A$ 后面可能出现的终结符号的集合或串终结符号$\#$所组成的集合。

# FOLLOW 集的构造

对于文法 $G$ 的每个非终结符号 $A$，构造 $\text{FOLLOW}(A)$ 的办法是，连续使用下面的规则，直至每个 $\text{FOLLOW}$ 集不再增大为止：

• 对于文法的开始符号 $S$，将符号 $\#$ 放入 $\text{FOLLOW}(S)$ 中；

• 若 $A \rightarrow \alpha B \beta$ 是一个产生式，则将 $\text{FIRST}(\beta) - \{\varepsilon\}$ 加入到 $\text{FOLLOW}(B)$ 中；

• 若 $A \rightarrow \alpha B$ 是一个产生式，或 $A \rightarrow \alpha B \beta$ 是一个产生式且 $\varepsilon \in \text{FIRST}(\beta)$（即$\beta \xRightarrow{*} \varepsilon$），则将 $\text{FOLLOW}(A)$ 加入到 $\text{FOLLOW}(B)$ 中。

# 预测分析表的构造方法

在对文法$G$ 的每个非终结符号$A$ 及其任意候选$\alpha$ 都构造出$\text{FIRST}(\alpha)$ 和$\text{FOLLOW}(A)$ 之后，可以构造$G$ 的分析表$M[A,a]$。

算法：非递归预测分析表的构造

1. 对文法$G$ 的每个产生式$A\rightarrow\alpha$ 执行第 2 步和第 3 步；
2. 对每个终结符号$a\in\text{FIRST}(\alpha)$，把$A\rightarrow\alpha$ 加至$M[A,a]$ 中；
3. 若$\alpha \xRightarrow{*} \varepsilon$，则对任何$b\in\text{FOLLOW}(A)$，把$A\rightarrow\alpha$ 加至$M[A,b]$ 中；
4. 把所有无定义的$M[A,a]$ 标上错误标记。

# LL (1) 文法

一个文法$G$，若他的分析表$M$ 不含多重定义入口，则称$G$ 是 LL (1) 文法。

• L：从左向右扫描输入串
• L：用最左推导
• 1：在栈顶符号和输入符号的组合下，只有一个产生式可以被选择

一个文法$G$ 是 LL (1) 的，当且仅当对于$G$ 的每一个非终结符号$A$ 的任何两个不同的产生式$A\rightarrow\alpha$ 和$A\rightarrow\beta$，满足：

• $\text{FIRST}(\alpha)\cap\text{FIRST}(\beta)=\varnothing$
• 若$\beta \xRightarrow{*} \varepsilon$，则$\text{FIRST}(\alpha)\cap\text{FOLLOW}(A)=\varnothing$

# 预测分析法实现步骤

1. 构造文法
2. 改造文法：消除二义性、消除左递归、消除回溯
3. 求每个变量的 FIRST 集和 FOLLOW 集，从而求得每个候选式的 SELECT 集
4. 检查是不是 LL (1) 文法。若是，构造预测分析表对于递归的预测分析，根据预测分析表为每一个非终结符编写一个过程；对于非递归的预测分析，实现表驱动的预测分析算法。

# 递归的预测分析法 vs. 非递归的预测分析法

# 预测分析的错误检测

• 栈顶的终结符和当前输入符号不匹配
• 栈顶非终结符与当前输入符号在预测分析表对应项中的信息为空

# 预测分析中的错误恢复

恐慌模式

• 忽略输入中的一些符号，直到输入中出现由设计者选定的同步词法单元（synchronizing token）集合中的某个词法单元
  • 其效果依赖于同步集合的选取。集合的选取应该使得语法分析器能从实际遇到的错误中快速恢复，例如可以把 FOLLOW（A）中的所有终结符放入非终结符的同步记号集合
• 如果终结符在栈顶而不能匹配，一个简单的办法就是弹出此终结符

synch 表示根据相应非终结符的 FOLLOW 集得到的同步词法单元

• 如果 M[A,a] 是空，表示检测到错误，根据恐慌模式，忽略输入符号 a
• 如果 M[A,a] 是 synch ，报错，弹出栈顶的非终结符 A ，试图继续分析后面的语法成分
• 如果栈顶的终结符和输入符号不匹配，则弹出栈顶的终结符

# 自底向上语法分析

• 从分析树的底部（叶节点）向顶部（根节点）方向构造分析树
• 可以看成是将输入串$w$ 归约为文法开始符号$S$ 的过程
• 自顶向下的语法分析采用最左推导方式
• 自底向上的语法分析采用最左归约方式（反向构造最右推导）
• 自底向上语法分析的通用框架：移入 - 归约分析（Shift-Reduce Parsing）

# 规约

# 最右推导和最左归约

• 由最右推导得到的句型称为右句型， 最右推导也称为规范推导。
• 最左规约是最右推导的逆过程，即由最右推导的句型的某个右部规约到左部的过程，也称为规范规约。

# 规范规约

假定 $a$ 是文法 $G$ 的一个句子。称句型序列 $a_n, a_{n-1}, \ldots, a_1, a_0$ 是 $a$ 的一个规范归约，如果此序列满足

1. $a_n = a, a_0 = S$;
2. $\forall i (0 < i \leq n)$，$a_{i-1}$ 是把 $a_{i}$ 中的句柄替换为相应产生式的左部符号得到的。

如果文法 $G$ 是无二义的，那么，规范推导（最右推导）的逆过程必是规范归约（最左归约）。

# 移入 - 归约分析

把一个输入符号串逐步归约到文法的开始符号。

实现这种方法的大致过程是，用一个栈，把输入符号一个一个地移进到栈里，反复查看栈顶符号串，当栈顶形成某个产生式的右部（句柄）时，把栈顶的这一部分替换成（归约为）它的左部符号。直到移进所有的输入符号串时，若栈内是开始符号，则符合语法，否则不是文法的句子，这种分析称作 “移进一归约” 分析。

# 移入 - 归约分析的栈实现

“移进一归约” 分析器使用一个栈和一个存放输入符号串$w$ 的缓冲器。分析器的初始状态为：

工作过程：自左至右把串$w$ 的符号一一移进栈里，一旦栈顶形成句柄时，就进行归约。这种归约可能持续多次，直至栈顶不再呈现句柄为止。然后，继续向栈里移进符号，重复这个过程，直至最终形成如下格局：

# 移入 - 归约分析的动作

• 移入：将下一个输入符号移到栈的顶端
• 归约：被归约的符号串的右端必然处于栈顶。语法分析器在栈中确定这个串的左端，并决定用哪个非终结符来替换这个串
• 接收：宣布语法分析过程成功完成
• 报错：发现一个语法错误，并调用错误恢复子例
  程

# 规范句型的活前缀

设有文法$G[S]$，若$S\xRightarrow{*}\alpha Aw\xRightarrow{*}\alpha\beta w$ 是文法$G$ 的一个规范推导，其中$\alpha,\beta\in V^+$，$w \in V_T^*$，$A \in V_N$，若存在$\gamma$ 是$\alpha\beta$ 的一个前缀，则称$\gamma$ 是文法的一个活前缀，如果$\gamma$ 是含句柄的活前缀，则称$\gamma$ 是文法的可归前缀（特殊活前缀）。

# 规范句型的活前缀的识别

对于一个文法$G$，可以构造一个 DFA，它能够识别$G$ 的所有活前缀。如果将经过此 DFA 的弧上的文法符号依次入栈，那么栈内就一定是活前缀。

# 规范句型的可归活前缀的识别算法

产生式的右部加上一个圆点指示位置，用于标识产生式右部有多少成分被识别了，并且找到该右部正好被识别的时刻，才能保证此时被识别的部分仅仅包含一个句柄。
如果将产生式右部圆点不同的位置表示上述 DFA 的不同状态，那么就可以确定，经过某个弧后，是否在栈顶正好形成句柄。如果当前状态下圆点在产生式右部的末端，此时栈顶必然出现了句柄，此时的活前缀可以规约操作。

# LR 分析法

LR 分析法是一种有效的自底向上的语法分析技术，一般叫 LR（k）分析技术，其中的 “L” 是指从左至右扫描输入符号串，“R” 是指构造一个最右推导的逆过程，“k” 是指为了作出分析决定而向前看的输入符号的个数。

LR 分析方法是当前最广义的无回溯的 “移进 - 归约” 方法。根据栈中的符号串和向右查看输入串的 k（k≥0）个符号，就能唯一确定分析器的动作是移进还是归约，以及用哪个产生式进行归约。

# LR 分析法的优缺点

1. 适合文法类足够大，适用于绝大多数上下文无关文法
2. 分析效率高
3. 报错及时
4. 可以自动生成
5. 手工实现工作量大

# LR 分析法的本质 —— 状态法

由于句柄是逐步形成的，用状态来描述形成句柄到达什么程度。

采用此方法，语法分析程序根据当前分析状态就可以确定句柄的头和尾，从而进行正确的归约。

LR 分析方法的关键就是根据上述状态，设计状态转换规则，从而实现识别活前缀的 NFA，进而实现识别活前缀的 DFA。

# 项目与状态

定义：对于文法 G，其产生式的右部添加一个特殊符号 · 就构成文法的一个项目。后面也称为 LR（0）项目。

书写文法中所有产生式的项目，而每个项目都为识别活前缀的 NFA 的一个状态。

# 项目的分类

• 移进项目：$A\rightarrow\alpha\cdot a\beta, a\in V_T$，这类 LR（0）项目表示$a$ 出现在符号栈中，活前缀包含句柄的部分符号，为构成可归前缀，需继续将圆点后的终结符号$a$ 移进符号栈。因此这种形式的 LR（0）项目称为移进项目，它对应的状态为移进状态。
• 待约项目：$A\rightarrow\alpha\cdot B \beta, B\in V_N$，这类 LR（0）项目表示$a$ 出现在符号栈中，活前缀包含句柄的部分符号，为构成可归前缀，期待着把当前输入字符串中的相应内容先归约到$B$。因此这种形式的 LR（0）项目称为待约项目，它对应的状态为待约状态。
• 归约项目：$A\rightarrow\alpha\cdot$，这类 LR（0）项日表示句柄 a 刚好出现在符号栈栈顶，活前缀刚好包含句柄，即当前符号栈中的符号串正好为可归前缀，应按$A\rightarrow \alpha$ 进行归约。因此这种形式的 LR（0）项目称归约项目，它对应的状态为归约状态。
• 接受项目：对于拓广文法 $G[S']$，有项目 $S' \rightarrow S \cdot$，它是一个特殊的归约项目，我们称它为接受项目，它对应的状态为接受状态。

# 状态的转移规则

• 若文法中有项目$i: X\rightarrow x_1 x_2 \dots x_{i-1} \cdot x_i x_{i+1} \dots x_n$，项目$j: X\rightarrow x_1 x_2 \dots x_{i-1} x_i \cdot x_{i+1} \dots x_n$，那么从状态$i$ 到状态$j$ 连接一条有向弧，标记为$x_i$。

• 若项目$i: X\rightarrow \gamma \cdot A \delta, A\in V_N$，项目$K: A\rightarrow \cdot \beta$，那么从状态$i$ 到状态$k$ 连接一条有向弧，标记为$\varepsilon$。

# 拓广文法

对任何文法 $G$，在 $G$ 中加进一个新的符号 $S'$ 和一个产生式 $S' \rightarrow S$，并以 $S'$ 代替 $S$ 作为文法的开始符号，这样得到的一个与 $G$ 等价的文法 $G'$ 称为 $G$ 的拓广文法。

# 构造识别活前缀 NFA 的原则