编译原理笔记

第 03 讲 ~ 第 04 讲：词法分析、语法分析

第 03 讲 词法分析

正则文法和状态图

  • 左线性文法：字母代表状态，数字代表转移过程，可添加开始状态和终止状态的标志，形成一个状态转移图。文法中表示状态的字母在左，故称左线性文法
  • 左线性文法的状态图画法：
    • 每个左侧的非终结符都可以画为一个状态，，其与右侧的每一个可以推导的状态间都有一条单向的状态转移线，线上需要标记相邻的数字
    • 重复第一步，直到某个状态推导的文法中不包含状态字母，只包含数字，这时拟出一个初始状态，与线上标记该数字，最后标记终止状态即可

以下列文法为例，进行左线性文法的状态图绘制：
$$
Z::=U1|V1\
U::=Z1|1\
V::=Z0|0
$$

  • 这里从第一句 $Z$ 开始，绘出状态点 $Z$、$U$、$V$，并画出 $U\to Z$、$V\to Z$ 的两条状态转移线，分别标注 $1$ 和 $1$
  • 第二句针对状态点 $U$，画出 $Z\to U$ 的状态转移线，标注 $1$；注意到 $U$ 也可推导出 $1$，于是拟出一个初始状态 $S$ 加入状态图，并画出 $S\to U$ 的状态转移线，标注 $1$
  • 最后一句针对状态点 $V$，画出 $Z\to V$ 的状态转移线，标注 $0$；同理从初始状态画出一条 $S\to V$ 的状态转移线，标注为 $0$
  • 最终形成的状态转移图如下图所示：
image-20230913131716100
  • 对左线性文法的状态转移而言，处理问题的过程是自底向上的。

例如上图中输入字符串 $1001$ 进行识别，就会生成以下的推导过程：
$$
S=|=>V1=|=>Z01=|=>U001=|=>1001
$$
而显然，我们是从第一个 $1$ 输入后倒推回状态 U、$U+0$ 推出状态 $Z$、……、直至推回最初的初始状态 $S$

  • 在匹配字符串的过程中可以将推导得到的序列化成语法树，进行句柄的判断

词法分析程序

  • 词法分析程序的功能：识别、组合单词，进行词法检查；将数字常数从字符串转化为数值；删去空白符号和注释
  • 单词的种类：各个种类都有自己的状态图进行匹配，下图为简单示例
    • 保留字：begin、end、for等
    • 标识符：由用户定义的变量名
    • 常数：无符号数、布尔量、字符串常数
    • 分界符：运算符等
image-20230913133508874

正则表达式与有限状态机

  • 正则表达式的运算符定义：
    • $|$：选择其一
    • $·$：连接（可以省略）
    • ${}$ 或 $*$：重复（$0$ 或更多次）
    • 正则集合是由某一个正则表达式规则能够形成的所有句型的集合
  • 正则表达式的递归定义：
    • $\varepsilon$ 和 $\phi$ 都是 $\Sigma$ 上的正则表达式，正则集合是 ${\varepsilon}$ 和 $\phi$
    • 对任意 $a\in \Sigma$，其均为正则表达式，且正则集合为 ${a}$
    • 假定 $U$ 和 $V$ 都是正则表达式，正则集合分别记为 $L(U)$ 和 $L(V)$，那么 $U|V$、$U·V$ 和 $U^*$ 都是正则表达式，正则集合分别为 $L(U)\and L(V)$、$L(U)·L(V)$ 和 $L(U)^*$
    • 任何正则表达式和正则集合都由此递归定义
  • 正则表达式的性质：
    • 两个正则表达式相同则说明两者表示的语言相等
    • 交换律：$e1|e2=e2|e1$
    • 结合律：$e1|(e2|e3)=(e1|e2)|e3$
    • 分配律：$e1(e2|e3)=e1e2|e1e3$
    • 正则表达式与 $3$ 型文法等价
  • 特殊运算等式：
    • $r^*=(r|\varepsilon)^*$
    • $r^{**}=r^*$
    • $(r|s)^*=(rs)^*$

确定的有穷自动机（DFA）和状态图

  • 一个确定的有穷自动机可以表示为五元式：

$$
M=(S,\ \Sigma,\ \sigma,\ s_0,\ Z)
$$

其中，$S$ 是有穷状态集，$\Sigma$ 是输入字母表，$\sigma(s_x, a_i)=s_y$ 是状态转移函数，$s_0$ 是初始状态，$Z$ 是终止状态集

也可以根据状态转换矩阵画出状态转移图来表示：

image-20230919112726111

此时，这个 DFA 就可以表示为这样的状态转移图：

image-20230919112802369

  • DFA 可接受的符号串，若一个符号串 $\alpha=a_1a_2…a_n,\ \alpha\in\Sigma$，且 $\sigma(\sigma(…\sigma(s_0,\ a_1)…),\ a_n) = s_n,\ s_n\in Z$，那么 $\alpha$ 就可以被该 DFA 接受（也就是说如果输入能够将初始状态转移到某一个终止状态，字符串就可接受）
  • DFA 可接受的语言： $L(M)={\alpha\ |\ \sigma(s_0,\ \alpha)=s_n,\ s_n\in Z}$

不确定的有穷状态机（NFA）

若对于一个有穷状态机而言，输入可以为 $\varepsilon$，且 $\sigma$ 为多值函数，那么它就是不确定的（对于输入某个字符后可能存在多个后继状态）它也可以表示为五元式：
$$
M^{‘}=(S,\ \Sigma\cup{\varepsilon},\ \sigma,\ s_0,\ Z)
$$
其中，$S$ 是有穷状态集，$\Sigma\cup{\varepsilon}$ 是输入符号和 $\varepsilon$，$\sigma$ 是转换函数，$s_0$ 是初态，$Z$ 是终止状态集，如下例：

image-20230919114718288

对 NFA 的状态图而言，其特点是同一个状态有同一字符标记的多条边或以 $\varepsilon$ 标记的特殊边（不消耗字符）。

NFA 的确定化

NFA 需要猜测字符串可能途径的节点和路径，可能需要多次匹配才能确定某一符号串是否能被 DFA 接受。由于 NFA 的不确定性，我们可以将 NFA 构造成一个 DFA，即将 NFA 确定化，从而进行字符序列的匹配。

  • 集合 $I$ 的 $\varepsilon$-闭包（$\varepsilon-closure(I)$）
    • 若 $s\in I$，则 $s\in\varepsilon-closure(I)$
    • 若 $s\in I$，则从 $s$ 出发并经过任意条 $\varepsilon$ 边能到达的节点均属于 $\varepsilon-closure(I)$

换言之， $\varepsilon$-闭包就是所有 $I$ 中节点 + 走 $\varepsilon$ 能碰到的节点

  • 集合 $I$ 是 NFA 状态集的一个子集，$a\in\Sigma$，$I_a=\varepsilon-closure(J)$，其中 $J=\cup_{S\in I}\sigma(s,\ a)$

换言之， $I_a$ 是以 $I$ 所有节点经过 $a$ 边所到达的节点再做 $\varepsilon-$闭包操作得到的集合。这个集合里所有节点距离 $I$ 都只有一个 $a$

通过以上两个定义，可以将一个 NFA 确定化：

  • 以初始节点为集合 $I$，求出 $\varepsilon-closure(I)$
  • 求出所有 $I_x$，其中 $x$ 为图中存在的边
  • 将上两步中出现的所有集合都视作 $I$，重新执行 $1、2$ 两步，直至没有新集合出现
  • 将每个出现的集合编号，每个编号都对应一个新的状态，并且 $I$ 到 $I_x$ 的转换边为 $x$
  • 原初始状态的 $\varepsilon$ 子集是 DFA 的初态，包含原终止状态的状态为 DFA 的终态，最终画出 DFA 的状态图

以下图为例说明 DFA 的转换过程：

image-20230919144628565
  • 初始状态为 ${1}$，$I={1,\ 4}$，求出 $I_a、I_b、I_c$ 并画出表格；
image-20230919145023156
  • 表格中新出现了集合 ${2,\ 3}$，将其加入 $I$ 中，重新求出 $I_x$；
  • 过程中又出现了新的集合 ${2}、{4}、{3,\ 4}$，同样加入 ${I}$ 并循环
  • 求出所有已出现集合后，将集合编号，表头中的 $I_x$ 转化为 $x$，得到新的状态转换矩阵
image-20230919145030553
  • 原本初始状态的 $I={1,\ 4}$，转化为初始状态；包含原终止状态 $4$ 的所有状态（${1,\ 4}、{4}、{3,\ 4}$）都转化为终止状态

image-20230919145045871

正则表达式与 DFA 的等价性

  • 在 $\Sigma$ 上的一个子集 $V$ 是正则集合，当且仅当存在一个 DFA M，使得 $V=L(M)$
image-20230919150717616

对任何一个正则表达式，都可以构造出等价的 NFA，并能转化为 DFA

词法分析的自动生成器（LEX）

一个 LEX 源程序主要由三个部分组成（各部分之间用 $%%$ 隔开）：

  • 辅助定义式
  • 识别程序
  • 用户子程序

LEX 的功能是根据 LEX 源程序构造一个词法分析程序，生成对应的状态转移矩阵和控制程序，实际上是一个有穷自动机

LEX 的工作过程

  • 扫描每条识别规则 $P_i$，构造相应的有穷自动机 $M_i$
  • 将每条有穷自动机合成出新的 NFA
  • 确定化 NFA
  • 生成最终 DFA 的状态转换矩阵和控制执行程序

过程中需要遵守的两条原则（处理二义性）：

  • 最长匹配原则：在识别单词时会优先识别为匹配最长序列的单词
  • 优先匹配原则：若同时能有多条规则匹配，那么有限与靠前的规则进行匹配（优先权更高）

有穷自动机、正则文法、正则表达式间的转换

有穷自动机 → 正则文法

  • 对转换函数/连接弧 $\sigma(A,\ t)=B$ 或 $A\overset{t}{\to} B$，有一个产生式 $A\to tB$
  • 对终止状态 $Z$，有一个产生式 $Z\to\varepsilon$
  • 有穷自动机的初态对应于开始符号；字母表为终结符号集

正则文法 → 有穷自动机

  • 每个非终结符都对应一个状态，开始符号对应起始状态 $S$
  • 新添加一个状态 $Z$ 作为自动机的终止状态
  • 对 $A\to tB$ 的推导，构造一条弧 $A\overset{t}{\to} B$
  • 对 $A\to t$ 的推导，构造一条弧 $A\overset{t}{\to}Z$

正则式 → 有穷自动机

  • 对于 $\varphi、\varepsilon、a\in\Sigma$，构造自动机如下：
image-20230920082036951
  • 对正则式 $R=s|t$ 和 $R=st$，构造自动机如下：

image-20230920082211990

image-20230920082226665

  • 对正则式 $R=s^*$，构造自动机如下：

image-20230920082257819

有穷自动机 → 正则式

  • 在自动机上添加两个节点 $x、y$，前者通过 $\varepsilon$ 连接所有初态，后者同理连接所有终态
  • 逐渐消去过程中的所有节点直至保留 $x、y$ 两个节点
  • 消结规则如下：

image-20230920082657562

正则文法 → 正则式

  • 将文法进行转换，保留开始符号，最终剩余的产生式不包含非终结符
  • 消结规则如下：
image-20230920083538700

正则式 → 正则文法

  • 对正则式的每一部分，若形如 $xy、x*y、x|y$，则新创建一个非终结符

image-20230920083746183

DFA 的最小化

对于任意一个 DFA，存在一个唯一的等价 DFA，其状态最少，这个 DFA 被称为最简的（最小化的）DFA

  • 多余状态：对任何输入而言均为不可到达状态
  • 等价状态条件：
    • 一致性条件：状态 $s$ 和 状态 $t$ 必须同时可接受/不可接受
    • 蔓延性条件：对于所有输入，两个状态必须转化到等价的状态中
  • 找到所有等价类后，对图中所有节点重新编号

第 04 讲 语法分析

  • 本讲的内容较为零散，其中包括了原书第 4 章的语法分析（一）和第 12 章的语法分析（二）两部分内容。
  • 前一部分介绍了语法分析中自顶向下的递归子程序法，其手工实现方便、效率高，但难以自动实现
  • 后一部分从笔记中的 LL 语法分析法开始，介绍了包括几种自底向上分析法在内的多种自动生成文法的分析程序

自顶向下分析

  • 给定符号串 $S$，为其构造一棵语法树，若能匹配为某一语法成分则 $S\in L(G[Z])$

  • 主要分析过程是用起始符号进行推导，逐步匹配输入串；当出现无法匹配时逐级回溯，重新匹配其他的语法规则

  • 自顶向下分析法存在两个问题，需要进行手动规避

    • 自顶向下分析的过程是预测性的，要预测输入串的语法成分
    • 自顶向下的方法是自回溯的，在试探匹配的过程中无法避免回溯过程

下面我们对这两种问题进行分析和处理

左递归文法问题

  • 当语法中存在非终结符 $U$，且有形如 $U::=U……$ 的语法规则时，则称其为左递归的
  • 自顶向下分析的方法无法处理左递归文法问题。由于自顶向下会优先进入最左侧非终结符的解析过程，于是在处理左递归文法/间接左递归文法时会持续进入递归过程，无法结束
  • 若要使用自顶向下的方法则必须消除直接左递归和间接左递归

解决方法：

  1. 使用扩充 BNF 改写文法
  • 若 $U::=xy|xw|…|xz$，则改写为 $U::=x(y|w|…|z)$；
    • 当提取公因子后，存在某一项为 $\varepsilon$，则尽量将其放置在匹配项的最后一项，因为任何字符均能匹配 $\varepsilon$，会影响匹配的结果
  • 若有 $U::=x|y|…|Uv$，则改写为 $U::=(x|y|…){v}$
    • 当同时含有左递归 or 非左递归的规则时，说明非终结符由非左递归部分+任意个左递归后部分组合而来的

对于第二条规则，有下例：$U::=x|y|z|Ua|Ub$

  • 先分为递归部分和非递归部分：$x|y|z$、$U(a|b)$
  • 再进行连接：$U::=(x|y|z){a|b}$

  1. 将左递归转化为右递归：若 $U::=U\alpha|U\beta|\gamma|\theta$，则可转化为右递归 $U::=\gamma|\theta{U^{‘}};\ U^{‘}::=\alpha|\beta$

  2. 消除一般左递归：

  • 把所有非终结符整理成后续非终结符可推导前驱非终结符的顺序然后把所有前驱的非终结符带入到后续的非终结符，消除后续规则的左递归
  • 通常一般左递归包含了多余规则，需要进行语法压缩

回溯问题

当非终结符在解析规则时，右部有多个选择就需要做出挑选，当无法匹配完全时，就需要考虑回溯，选择其他的分支，回溯会导致语法分析工作的浪费，因此文法需要尽量避免回溯问题。回溯不发生时文法需要满足：
$$
FIRST(\alpha_i)\cap FIRST(\alpha_j)=\varphi(i\ne j)
$$
消除回溯可以通过以下几种方法实现：

  • 改写文法：对具有多个相同左部的规则提取公因子
    • 将 $U::=xV|xW$ 改写为 $U::=x|Z;\ Z::=V|W$
  • 超前扫描：当语法无法改写为公因子形式时，可以向前侦察输入符号串的后续字符进行匹配，但是不进行语义的处理工作（一般不采用）

非回溯自顶向下分析文法的两个条件

为了实现非回溯的自顶向下分析法，文法需要满足两个条件：

  • 文法是非左递归的
  • 当非终结符规则右侧有多个选择时，各个选择的首符号集合不相交

下面介绍两种常用的自顶向下分析法：递归子程序法和 LL(1) 分析法

递归子程序法

  • 对语法中每一个非终结符都编写一个分析程序，根据输入匹配时，逐个调用对应非终结符的分析程序
  • 不允许出现左递归，但是允许存在其他位置的递归
  • 在进行分析程序的调用时，需要先将语法成分的第一个字符读入程序再解析
  • 递归子程序法对应的是最左推导过程

LL(1) 语法分析法（未完成）

  • LL 分析法自左向右扫描+自顶向下推导、分析、匹配输入串，体现为最左推导

  • 由分析表、执行程序、符号栈三部分组成

  • 分析表：一个概括文法全部信息的矩阵，每一行都有一个非终结符，每一列都有一个终结符

  • 执行程序：按照分析表逻辑对符号栈和输入串进行操作的程序，程序逻辑在不同语言中是通用的

分析表的构造方法

为构造分析表，需要预定义两个和文法有关的集合 FIRST 和 FOLLOW

  • $FIRST(\alpha)={a|\alpha\overset{*}{\to} a…,\ a\in V_t}$，换言之，$FIRST$ 就是从 $\alpha$ 推导出所有可能的符号串中，第一个终结符、$\varepsilon$ 的集合
  • $FOLLOW(\alpha)={a|S\overset{*}{\to} …Aa…,\ a\in V_t}$，$FOLLOW$ 是所有从 $S$ 推出的句型中 $A$ 后终结符的集合

构造 $FIRST$ 集合（$\alpha\in{V_n,\ V_t}$）：

  • 若 $\alpha\in V_t$，则 $FIRST(\alpha)={\alpha}$
  • 若 $\alpha\in V_n$，且存在可推导 $\alpha\to aX$ 的产生式，则把 $a$ 加入集合
  • 若存在 $\alpha\to Y_1Y_2…Y_n$ 的产生式，如果 $Y_i$ 的 $FIRST$ 集合中有 $\varepsilon$，就能把 $Y_{i+1}$ 的 $FIRST$ 集合计入 $FIRST(\alpha)$ 中
  • 对于整个符号串，方式与第三条相同

构造 $FOLLOW$ 集合（$\alpha\in{V_n}$）：

  • 对于开始符号 $S$，令 #\in FOLLOW(S)$

  • 若存在 $A\to\alpha B\beta$ 的产生式（$\beta\ne \varepsilon$），则将 $FIRST(\beta)$ 中一切非 $\varepsilon$ 符号计入 $FOLLOW(B)$

  • 若存在 $A\to\alpha B\beta$ 的产生式，且 $\varepsilon\in FIRST(\beta)$，则 $FOLLOW(A)$ 中的所有元素都属于 $FOLLOW(B)$

  • 注意 $FOLLOW$ 集合中可能包含 $#$ 符号

为了构造文法 $G$ 的 LL 分析表，需要对 $G$ 中每一个规则 $A\to\alpha$ 按照以下规则确定

  • 若 $a\in FIRST(\alpha)$，则 $M[A,\ a]=A\to\alpha$
  • 若 $\varepsilon\in FIRST(\alpha)$，则将每个 $b\in FOLLOW(A)$ 置 $M[A,\ b]=A\to\varepsilon$
  • 其余位置均为 $error$，代表出错

自底向上分析

  • 从输入的符号串开始，重复规约当前句柄（把句柄合成为规则左侧的非终结符），若能规约为文法能识别的符号则说明输入串是合法的句子

移进—规约过程

  • 建立一个符号栈，自左向右地每次推入一个符号，在形成当前句型的句柄时进行规约，将栈中内容化为非终结符，向着初始符号 $S$ 靠近，如果化为初始符号则说明规约完成，输入串是合法句子
  • 规约的方式实际上存在一定的不确定性，如果句柄识别有误，可能合成的非终结符并不能继续合成，导致错判

算符优先分析

  • 算符优先分析法预先规定相邻终结符的优先关系，利用关系确定句柄，最终达到规约的目的，需要注意的是，若有 $a\gt b$ 的关系，并不一定有 $b \lt a$ 的关系
  • 在算符优先分析法中，每一步分析并不是严格地自左向右的，它每一步规约的都是当前句型的最左素短语

素短语与最左素短语

  • 素短语是至少包含一个终结符号地短语，并且其中不含有任何素短语（也就是最小的、语法树中最靠下的短语）
  • 素短语和句柄之间并没有直接联系

算符优先分析流程如下：

  • 确定终结符之间的优先关系：若 $a、b$ 都是终结符且可能相邻，那么 $a\gt/=/<b$ 说明 $a$ 的优先级大于/等于/小于 $b$

  • 将所有终结符画出一个矩阵，包含所有优先关系，矩阵空白处说明终结符不相邻；或选择构造算符优先函数，决定算符之间的关系

    • 这里的矩阵叫做优先关系矩阵，矩阵消耗空间更大，但使用优先关系函数可能会使得原本不存在优先关系的符号根据运算出现错误的比较关系

  • 重复比较、出入栈、规约的过程，直至符号串输入完毕

    • 入栈：当栈内终结符优先级 $\le$ 栈外优先级时则入栈，出栈则相反
    • 规约：当终结符未入栈、已出栈时要对输入的元素进行规约，合成为新的语法成分，在重新压入输入串栈

算符优先函数的确定方法：

  • 定义优先函数 $f$（栈内）、$g$（栈外），若两终结符存在优先关系，则 $f(a)>=<g(b)$
  • 对每个终结符，令 $f(a)=g(a)=1$
  • 若 $a>b$，而 $f(a)\le g(b)$，则 $f(a)=g(b)+1$
  • 若 $a=b$，而 $f(a)\ne g(b)$，则令 $f(a)、g(b)$ 的最小值和最大值相等

优先关系矩阵的构造方法在下一小节介绍

算符优先文法

  • 算符文法：文法中无 $U::=…VW…$ 的规则，则称 $G$ 为 OG 文法，即算符文法

    • 运算规则都是中缀形式
    • 规则中不会出现两个非终结符相邻

  • 算符优先文法：一个算符文法，且两个终结符之间（即 $a?b$、$b?a$ 中）最多只有一种优先关系成立，则称为算符优先文法

  • 优先关系的定义：$a=b$、$a<b$、$a>b$，指文法中包含以下三种类型的规则：

    • $U::=…ab…$ 或 $U::=…aVb…$

    • $U::=…aW…$，且 $W\overset{+}{\to}b…$ 或 $W\overset{+}{\to}Vb…$

    • $U::=…Wb…$，且 $W\overset{+}{\to}…a$ 或 $W\overset{+}{\to}…aV$

    • 换句话说，也就是相邻时谁后被推导出来（反过来就先被规约），谁的优先级就更高

优先关系矩阵的构造

构造优先关系矩阵的方法：

  • 先通过优先关系的定义求 $=$ 关系

  • 再求每个非终结符 $U$ 的 $FIRSTVT(U)$ 和 $LASTVT(U)$ 两个集合

    • $FIRSTVT(U)={b|U\overset{+}{\to}b… ||U\overset{+}{\to}Vb…}$

    • $LASTVT(U)={b|U\overset{+}{\to}…a||U\overset{+}{\to}…aV}$

  • 逐条分析文法规则，若某条规则出现 $…aU…$，那么对任意的 $b\in FIRSTVT(U)$，都有 $a\lt b$，类似地可以推出 $\gt$ 的优先关系

LR 语法分析法（未完成）

  • LR 分析法是自左向右扫描+自底向上规约的分析方法
  • 这种分析方法效率高，可自动生成规则、适用度高