跳至主要內容

编译原理

yyshino大约 10 分钟

编译原理

第二章 语法分析

闭包正闭包

image-20230530130426745
image-20230530130426745

文法与语言

文法：是描述语言的语法结构的形式规则

文法的概念

  1. 非终结符：

    • 出现在规则的左部、用一括起来、表示一定语法概念的词。

    • 非终结符集合用$V_N$表示。

  2. 终结符

    • 语言中不可再分割的字符串(包括单个字符组成的串)。注：终结符是组成句子的基本单位。
    • 终结符集合用$V_T$表示。

  3. 开始符号

    • 表示所定义的语法范畴的非终结符。
    • 注：开始符号又称为识别符号。

  4. 产生式

    • 是用来定义符号串之间关系的一组(语法)规则。
    • 形式：A→a （A产生α）

  5. 推导

    • 推导是从开始符号开始，通过使用产生式的右部取代左部,最终能产生语言的一个句子的过程。
    • 最左（右）推导：每次使用一个规则，以其右部取代符号串最左(右)非终结符。
    • 注:最左推导和最右推导称为规范推导。

  6. 归约

    • 归约是推导的逆过程，即，从给定的源语言的句子开始,通过规则的左部取代右部,最终达到开始符号的过程。
    • 最左(右)归约是最右(左)推导的逆过程。
    • 注：最左归约和最右归约称为规范归约。

  7. 句型、句子和语言

    image-20230530132449857image-20230530140452684

  8. 文法规则的扩充

    image-20230530145309031
    image-20230530145309031

  9. 元语言符号

    • 用来说明文法符号之间关系的符号,如, “→”和“|”称为元语言符号。

Chomsky对文法的分类

对产生式施加的限制不同可以分为

0型文法（α->β）（也被称短语文法，任何0型语言都是递归可枚举的，反之，递归可枚举集必定是0型语言）

1型文法（αAβ->αBβ）（上下文有关）

2型文法（A->α）（上下文无关文法）

3型文法（正规文法）

  • A->Bα|α
  • A->αB|α

包含关系：0 包含 1 包含 2 包含 3

正规文法

上下文无关

  • 产生式的左部一定是一个非终结符
  • 产生式的右部可以是任意的字符串组合

如果是正规文法那么一定是上下文无关文法

文法构造与文法简化

文法构造

  • 观察法（找规律）

文法简化

构造无ε产生式的上下无关文法

语法树(AST)与文法的二义性

语法树

  1. 先写出最左/右推导
  2. 由最左/右推导画出语法树

第三章 词法分析

正规文法和有限自动机

正规文法

正规文法：Chomsky 3型文法（左线型右线型）

正规集：

正规式：-设A是非空的有限字母表，A={a;l i=1,2,.....n},则

  1. $\epsilon$, $\empty$和$a_i(i=1,2,......n)$都是正规式。
  2. 若$\alpha$、β是正规式,则$\alpha | \beta$、$\alpha \cdot \beta$、$\alpha*$、$\beta*$也是正规式。
  3. 正规式只能通过有限次使用1, 2规则获得。

注： 1)“|”读作为“或”，也可写作为“+”或“," ；”$\cdot$”读作连接。

2)仅由字母表$A=a_i(i=1,2,......n)$上的正规式α所组成的语言称作正规集,记作$ L(\alpha) $。

3)利用正规集相同，可用来证明相应正规式等价。

定理1：

若$ \alpha、\beta、\gamma $是正规式则下述等价式成立

  1. 类式加法满足的性质：交换律结合律

  2. 类式乘法满足的性质：交换律结合律

  3. $ \epsilon \alpha = \alpha \epsilon = \alpha$

  4. $((\alpha)*)* = \alpha^*$

  5. $ \alpha^* = \alpha^+ + \epsilon $

  6. $ (\alpha + \beta)^* = (\alpha^* + \beta*)* = (\alpha^* \beta*)*$

定理2：

若$\alpha、\beta、\gamma)$是字母表A上的正规式,且$\epsilon \notin L(\gamma)$,

则$\alpha = \beta | \alpha \gamma$当且仅$\alpha = \beta \gamma^*$

则$\alpha = \beta | \gamma \alpha $当且仅$\alpha = \gamma^* \beta $

正规文法转换成相应正规式

  1. 由产生式写出对应的联立方程组（产生符号改为等号）
  2. 根据定理解方程组
  3. 进行代入工作，消除所要求的方程式中的非终结符，

有限自动机

有限自动机是一种识别装置，它能准确地识别正规集。它为词法分析程序的构造提供了方法和工具。

image-20230603104623548
image-20230603104623548

确定有限自动机DFA

image-20230603114811721
image-20230603114811721

注：这里确定的含义，就是状态转换关系f是一个函数，即对于给定的当前状态s和当前读入的符号a，有唯一确定的下一状态s’。

状态转换关系表示

  • 状态转换矩阵：DFA的映射关系由一个矩阵来完成

  • 状态转换图

注:

1)用矩阵表示转换便于计算机处理,但不直观,而用状态转换图表示比较直观。

2)在整个状态转换图中只有一个初始状态结点，用“→”射入的结点表示初始状态。可有若干终止状态(也可能没有),用双圆圈表示。若初始状态结点同时又是终止状态结点，则表示空串$\epsilon $可为相应DFA识别。

构造DFA

根据语言描述构造DFA

  1. 根据语言描述，画状态转换图
  2. 由状态转换图，写DFA

示例

image-20230603120905796image-20230603121020149

不确定有限自动机NFA

image-20230603121826937
image-20230603121826937

注：

1)非确定主要是指后继状态可有多个。

  1. DFA是NFA的特例。

与DFA的主要区别在于：NFA的初始态是一个集合而不是唯一的$s_0$

（2）两自动机等价：

  • 任何两个有限自动机M和M'，若它们识别的语言相同(L(M)=L(M'))，则称M和M'等价。
  • 注:存在判定任何两个有限自动机等价性的算法。
NFA确定化

(1)定理

对于每个NFA M,存在一个DFA M',使得L(M)=L(M')。即，设L是一NFA接受的正规集,则存在一个DFA接受L。

步骤：

  1. 先写转换表
    1. 由初态开始，对应字母表中每一个元素，取并集(∪)，得到相应的映射态
    2. 再对映射态进行第一步操作
    3. 重复1、2步，直到没有新的状态产生
  2. 由转换表得DFA
    1. DFA初态为NFA初态，DFA终态为包含NFA终态的所有态

确定有限自动机的化简

划分法
  1. 将DFA M中的状态划分为互不相交的子集，每个子集内部的状态都等价;而在不同子集间的状态均不等价。
  2. 从每个子集中任选一个状态作为代表，消去其它等价状态。
  3. 把那些原来射入其它等价状态的弧改为射入相应的代表状态。

正规表达式替换有限自动机的构造

正规 -> NFA 规则

image-20230604105144454
image-20230604105144454

自上而下语法分析

4、语法分析的方式

1）自上而下语法分析

  • 反复使用不同产生式进行推导以谋求与输入符号串相匹配。

2）自下而上语法分析

  • 对输入符号串寻找不同产生式进行归约直到文法开始符号。

注：这里所说的输入符号指词法分析所识别的单词。

FIRST集，FOLLOW集，SELECT集

FIRST集

  1. 看右侧第一个字符
    • 如果是终结符，等于当前终结符
    • 如果是非终结符，继续推导，
  2. 有|（或）链接或者有多个，取并集

FOLLOW集

Follow(A)为非终结符A后跟符号的集合,Follow(A)是所有句型中出现在紧接A之后的终结符或’#’

求解规则

（1）对于文法的开始符号S,置#于Follow（S）中；

（2）若A->αBβ是一个产生式，则把First(β) \ {ε} 加入到Follow（B）中

（3）若A->αB是一个产生式，或A->αBβ是一个产生式且β=>ε，则把Follow(A)加入到Follow(B)中

理解求解规则

（1）对于开始符号，首先将#放入Follow集中

（2）形如A->αBβ

（α可以是终结符或者非终结符或者直接为空，β可以是终结符或者非终结符，

注意β不能为空，B后面要有东西， 注意β不能为空，B后面要有东西， 注意β不能为空，B后面要有东西）

SELECT集

LL(1)文法

要证明此文法是不是LL(1)文法,就看各组左部相同的SELECT集的交集是否为空,若都为空,则是LL(1)文法

LL(1)分析表

  1. 写出SELECT集
  2. 根据文法写出分析表第一行、第一列
    1. 第一行为终结符，从上至下依次填入
    2. 第一列为非终结符，从上至下依次填入
  3. 根据SELECT集...

LR(0)

LR(0)项目集

相关概念

LR(0)项目：右部标有 $\cdot $ 的产生式 => 称为一个项目

  • 如果 $ \cdot $ 在非终结符前，则称为一个特殊的项目-移进项目。如$A \rightarrow \cdot aBD$
  • 如果 $ \cdot $ 在终结符前，则称为一个特殊的项目-待约项目。如$A \rightarrow a \cdot BD$
  • 如果 $ \cdot $ 在最右侧，则称为一个特殊的项目-归约项目。如$A \rightarrow aBD \cdot$

增广文法

如果G 是一个以S为开始符号的文法，则G的增广文法 G'就是在G中加上新开始符号S'和产生式S'→S而得到的文法

  • 引入这个新的开始产生式的目的是使得文法开始符号仅出现在一个产生式的左边，从而使得分析器只有一个接受状态

示例

G[S]
	S->aF|b
	F->Fbc|c

// 在最上方加入 S'->S即可
G'
	S'->S
	S->aF|b
	F->Fbc|c

LR(0)自动机 DFA

  1. 拓广文法（S'和分解）
  2. 由$I_0$开始

LR(0)分析表

  • 第一行I下填写下标数字、Action下填写终结符、Goto下填写非终结符
  • 根据LR(0)自动机图填写
    • $I_n$里含有归约项目，则在第n行填写归约项目对应的拓广文法序号$r_m$
    • $I_n$里移进项目或待归约项目指向$I_m$，看它识别的是终结符还是非终结符（也就是LR(0)自动机的箭头上对应的字符）
      • 终结符：在第n行，Action下的相应终结符列，填写$s_m$
      • 非终结符：在第n行，Goto下的相应非终结符列，填写$m$
    • 出现移进归约冲突时（），计算文法的Goto下非终结符FOLLOW集，看对应的终结符是否属于是否属于当前集合，不属于则删除

SLR(1)

  • SLR(1)遇到终结符属于FOLLOW集的才采取归约
  • LR(0)是所有终结符都采取归约

因此，只需要在LR(0)的基础上计算FOLLOW集，然后删除Action下不属于FOLLOW集（箭头右侧的非终结符的FOLLOW集）的归约项（r开头的）

s不受影响

LR(1)分析表

拓广文法—项目规范族（带向前搜索符）——LR(1)分析表

如何写向前搜索符？

  1. 文法开始符Follow集
  2. ”先看前再看后“
    1. $A \rightarrow \alpha \cdot \beta,a $
      1. $\beta$ 为空，照抄
      2. $\beta$ 不为空$First(\beta)$

LALR(1)

拓广文法—项目规范族（在带向前搜索符的基础上合并同心集）——LR(1)分析表

如何区别这四种文法

image-20230605203917556
image-20230605203917556

实践步骤：

根据DFA图判断

  1. 看是否存在冲突项目（移进归约|归约归约）
    • 不存在=>LR(0)文法
    • 存在（不是LR(0)文法）无法构表
  2. 存在冲突项目，根据FOLLOW集来判断
    • $= \empty $是SLR(1)文法
    • $\neq \empty$无法构表
  3. 存在冲突项目，根据向前搜索符来判断
    • $= \empty $是LR(1)文法
    • $\neq \empty$无法构表
  4. 如果构建的带向前搜索符的项目集规范族存在冲突项目（规约-规约），那就不是LR(1)，也不是LALR (1)。

根据分析表判断

  1. LR(0)的$R_n$占整行(Action行)
  2. SLR(1)根据FOLLOW集填写$R_n$
  3. LR(1)不同行可能出现相同的$R_n$状态

参考

https://blog.csdn.net/weixin_44445120/article/details/115681574
https://www.bilibili.com/video/BV1xr4y1m7Kg/?spm_id_from=333.788&vd_source=fb3505db9b87542728213f28843a6d74