编译原理学习笔记

alpha(α) beta(β) gamma(γ) delta(δ) epsilon(ε) sigma(∑)


集合乘积

{0,1}{a,b} = {0a,0b,1a,1b}


集合幂运算
{0,1}³ = {0,1}{0,1}{0,1} = {000,001,010,011,100,101,110,111}
{字母}³ = 即长度为3的字母串构成的集合
∑⁰ = {ε}

正闭包(positive closure)
∑⁺ = ∑ ∪ ∑² ∪ ∑³ ∪ ...
{a,b,c,d}⁺ = {a,b,c,d,aa,ab,ac,ad,ba,bb,bc,bd...}

克林闭包(kleene closure)
∑* = ∪ ∑⁺ = {ε,a,b,c,d,aa,ab,ac,ad,ba,bb,bc,bd...}

串(string)
假设∑是一个字母表,∀x ∈ ∑*,x称为∑上的一个串
串是字母表中符号的有穷序列

串长度
|s| 代表串s的长度即串s中符号的个数
长度为0的是空串 |ε| = 0

串连接
x = aa, y = bb 那么 xy = aabb
x = ε 那么 εx = xε = x

串幂运算
假设 s = 12
s⁰ = ε
s¹ = 12
s² = 1212



[文法]

文法的形式化定义
G = (Vₜ Vₙ P S)

Vₜ 终结符(terminal)是文法定义的基本符号也叫 token
Vₙ 非终结符(nonterminal)是用来表示语法成分的符号,有时也称为 语法变量

Vₜ ∩ Vₙ = ∅ 终结符集合和非终结符集合是不想交的
Vₜ ∪ Vₙ 表示 文法符号集

P 产生式的集合
产生式(production)描述了将终结符和非终结符组合成串的方法,就是用来产生串的

产生式的一般形式 α->β 读作 α 定义为 β
α 为产生式的头(head)或左部(left side),至少包含一个非终结符
β 为产生式的体(body)或右部(right side)

S 表示的是文法的开始符号(start symbol),是文法中最大的语法成分

例如 G = ({id + * ( )}, {E}, P, E)
P = {
E -> E + E,
E -> E * E,
E -> (E),
E->id
}

在不引起歧义的前提下,文法定义只需要写产生式即可比如
E -> E + E,
E -> E * E,
E -> (E),
E -> id

相同左部
α -> β¹
α -> β²
可以简记为
α -> β¹|β²
β¹ β² 称为 α 的候选式(candidate)


推导(Derivation)和归约(reduction)

如果 α₀=>α₁, α₁=>α₂......αₙ₋₁=>αₙ 则可以记作
α₀=>α₁=>α₂...=>αₙ 称为 α₀ 经过n步推导出 αₙ 间记为 α₀=>ⁿαₙ

α₀ =>⁰ αₙ 即 没有推导,还是 α₀
=>⁺ 指的是经过正数步推导
=>* 指的是经过任意步推导

自顶向下过程称为推导
自低向上过程称为归约

归约是推导的逆过程

句型(sentential form)既可以包含终结符,又可以包含非终结符,也可能是空串
句子(sentence)不包含非终结符的句型

语言的形式化定义
由文法G的开始符号S推导出的句子构成的集合称为文法G生成的语言,即为L(G)
L(G) = {w|S =>* w, w ∈ Vₜ*}

文法 E->E+E|E*E|(E)|id 可以包含无穷个句子
也就是说文法可以解决无穷语言的有穷表示




文法分类
0型文法(Type-0 Grammar)
无限制文法(unrestricted Grammar)/短语结构文法(Phrase Structure Grammar,PSG)
只要求文法的左部至少包含1个非终结符
由0型文法生成的语言称为0型语言


1型文法(Type-1 Grammar)
上下文有关文法(Context-Sensitive Grammar,CSG)
产生式左部符号的个数不能多于右部符号的个数

产生式的一般形式 α₁Aα₂ -> α₁Bα₂(B ≠ ε)
CSG中不包含 ε 产生式

由上下文有关的文法生成的语言称为上下文有关语言

2型文法(Type-2 Grammar)
上下文无关文法(Context-Free Grammar,CFG)
左部必须为一个非终结符
产生式的一般形式为 A -> β



3型文法(Type-3 Grammar)
正则文法(Regular Grammar,RG)
右线性(Right Linear)文法:A -> wB 或 A -> w
左线性(Left Linear)文法: A -> Bw 或 A -> w

右部都只能出现之多一个非终结符,左线性靠最左,右线性靠最右

由正则文法生成的语言称为正则语言
正则文法与正则表达式是等价的
正则文法可以用正则表达式来表示,反过来也可以


正则表达式
ε是一个RE,L(ε) = {ε}
r|s = L(r|s) = L(r) ∪ L(s)
rs = L(rs) = L(r)L(s)
r* = L(r*) = (L(r))*

优先级为 * 连接符 |

L(a|b) = {a} ∪ {b} = {a,b}
L((a|b)(a|b)) = {a,b}{a,b} = {aa,ab,ba,bb}
L(a*) = {a}* = {ε,a,aa,aaa,...}
L((a|b)*) = {a,b}* = {ε,a,b,aa,ab,ba,bb,...}
L(a|a*b) = {a,b,ab,aab,aaab,...}

十进制整数的RE
(1|2...|9)(0|1|...|9)*|0
八进制整数的RE
0(1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7)*
十六进制整数的RE
0x(1|...|9|a|...|f|A|...|F)(0|1|...|9|a|...|f|A|...|F)*

可以用RE定义的语言叫做正则语言(regular language)或正则集合(regular set)




有穷自动机 FA
系统只需要根据当前所处的状态和当前面临的输入信息来决定系统的后继行为,每当系统处理了当前输入后,系统的内部状态也将发生改变。

由一个有穷自动机M接收的所有串构成的集合称为是FA定义(或接收)的语言,记为L(M)

有穷自动机遵循最长子串匹配原则(Longest String Matching Principle)

NFA
非确定的有穷自动机 - NFA - 人类友好
可以带有空边(ε)

DFA
确定的有穷自动机 - 机器友好


他们是等价的也就是 DFA可以转化为NFA,NFA可以转化为DFA


正则文法 可以有等价的 正则表达式 可以有等价的 FA
正则文法 <=> 正则表达式 <=> FA


正则表达式到有穷自动机一般为
正则表达式 -> NFA -> DFA





自顶向下分析(top-down parsing)
从分析树的顶部(根节点)向底部(叶节点)方向构造分析树,可以看成是从文法符号S推导出词串w的过程

推导完之后输入串的各个符号恰好自左向右的在各个分析树的叶节点,因此该输入串为该语言的句子
每次推导都需要做两个选择
1.替换当前句型的哪个非终结符
2.用该非终结符的哪个候选式进行替换

最左推导(left-most derivation)
总是选择每个句型的最左非终结符进行替换

最右归约
最右归约是最左推导的逆过程

最右推导(right-most derivation)
最左归约
最左归约是最右推导的逆过程

因为在自低向上的分析中,总是采用最左规约和最右推导,所以称最左规约为规范归约,最右推导为规范推导

递归下降分析
由一组过程组成,每个过程对应一个非终结符

递归下降分析可能需要回溯

预测分析
预测分析是递归下降分析技术的一个特例,在输入中向前看固定个数(通常为1)符号来正确的确定产生式


文法的编写需要技巧,要不然可能会产生左递归
当同一非终结符的多个候选式存在共同前缀将导致回溯现象,比如
S -> aAd|aBe

含有 A -> Aα 形式产生式的文法称为直接左递归(immediate left recursive)
如果 A 经过若干部推导出A开头的比如 A =>⁺ Aα 称为左递归
经过2步或者以上的推导产生的左递归称为间接左递归

所以我们要重写文法来消除左递归,可能要新增新的产生式和空串



S 文法
每个产生式右部都以终结符开始
同一非终结符各个候选式的首终结符都不同
S 文法不包含空产生式

q 文法
每个产生式右部以终结符开始或为 ε
具有相同左部的产生式有不相交的可选集

LL(1)
当且仅当文法的任意两个具有相同左部的产生式 A -> α|β 满足下面条件
1.α β最大有一个能推导出 ε
2.如果α β 均不能推导出 ε 则他们的 first集 不相交
3.如果 β =>* ε 则FIRST(α) ∩ FOLLOW(A) = ∅
4.如果 α =>* ε 则FIRST(β) ∩ FOLLOW(A) = ∅

也就是要保证同一非终结符的各个产生式的可选集互不相交,这样我们才能通过输入串的符号来确定使用哪个产生式,也就是能构造预测分析器

第一个 L 从左向右扫描
第二个 L 最左推导
1 代表向前查看1个字符


递归预测分析法
需要为每个非终结符编写过程

非递归预测分析法
不需要为每个非终结符编写递归下降过程,而是根据预测分析表构造一个自动机,也叫表驱动的预测分析
这个自动机叫做下推自动机,需要基于分析表


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

递归预测分析比较直观,但是如果程序比较复杂,那么规模也会变大
非递归预测分析需要载入分析表
自动生成的程序一般都采用非递归预测分析法



非终结符的 FOLLOW集
FOLLOW集 是针对非终结符的,比如FOLLOW(A)是指所有可能跟在非终结符A后面的终结符的集合,包含 ε 空串

产生式的可选集 SELECT集
SELECT集 是针对产生式的,包含 ε 空串
是指该产生式第一个可能的终结符的集合

串首终结符集 FIRST集
串首终结符集 是针对文法符号的,可以是终结符或非终结符,包含 ε 空串
终结符的 FIRST集 是该终结符本身
非终结符的 FIRST集 是该非终结符所有可能出现在第一个的终结符集和




自底向上分析法
从分析树的底部(叶节点)向顶部(根节点)方向构造分析树,可以看成是将输入串w归为文法开始符号S的过程
采用的是最左规约方式
通用框架是移入-归约分析(shift-reduce parsing)

增广文法 - 使得文法的开始符号只出现在一个产生式的左边 - 使得分析器只有一个接受状态


LR0项目 - 右部某位置标有圆点的产生式为响应文法的一个项目,比如
S -> bBB 拥有4(符号数 + 1)个项目,
S -> .bBB 移进项目
S -> b.BB 待约项目
S -> bB.B 待约项目
S -> bBB. 规约项目

后继项目 - 同属于一个产生式的项目,但圆点的位置只相差一个符号,则称后者是前者的后继项目
比如 A -> α.Xβ 的后继项目是 A -> αX.β



LR 最难的是分析表的构造


很多项目是等价项目,我们可以把所有等价的项目组成一个项目集称为 项目集闭包,每个项目集闭包对应着自动机的一个状态


LR0 有些时候会产生冲突,比如

移进归约冲突
E -> T. 这是个规约项目,不管下一个输入符号是啥,都要规约
T -> T.*F 当输入符号为 * 时进行移入操作

归约归约冲突
B -> .
T -> .
到底是归约成 B 还是 T


如果 LR(0) 分析表中没有语法分析动作冲突,那么该文法称为 LR(0) 文法


SLR

SLR 即 SLR1 需要向前查看一个元素,并且借助于 FOLLOW集 来决定是移入还是归约动作
比如
E -> T.
T -> T.*F

比如上面如果 * 为 E 的FOLLOW集中的终结符才可以进行规约,否则就要进行移入操作

如果给定的文法的 SLR 分析表中不存在有冲突的动作,那么该文法称为 SLR 文法

有些复杂点的仅仅利用 FOLLOW集 来解决冲突是不够的,所以要引入功能更加强大的 LR1 分析法
比如
S -> L.=R
R -> L.

FOLLOW(R) = {=,$}

那么上面既可以移入,又可以规约为 R



LR1
LR1引进了 "展望符",对归约动作进行了限制,只有当下一个符号为 "展望符" 时才可以进行归约动作,展望符为 FOLLOW集的一个 子集,即把当前环境考虑进去了

如果除了展望符,两个 LR1 项目集是相同的,则称这两个 LR1 项目集是同心的

LR1 较于 LR0 状态数多了不少,因为 LR1 在 LR0 基础上分裂出了同心项目集




LALR
在 LR1 基础上把同心项目集合并,这样可以少很多状态,合并同心项目集后可能会推迟错误的发现。
LALR分析法可能会做多余的规约动作,但绝不会作错误的移进操作,因为合并动作只是对 展望符 进行合并,而移入操作跟展望符没有关系

大小上跟 LR0/SLR 是相当的,形式上跟 LR1 相同
分析能力 SLR < LALR < LR1

上一篇: 无
下一篇: LALR(1)实例
作者邮箱: 203328517@qq.com