当前位置：首页 > news >正文

编译原理第一到三章（知识点学习/期末复习/笔试/面试）

news 2025/7/16 8:15:19

第一章引言

1.1 程序设计语言

（1）机器语言(Machine Language)与汇编语言(Assemble Language)

0、1代码（机器语言）与助记符（汇编语言）：更接近于计算机硬件指令系统的工作。

（2）高级语言(High Level Language)

其表示方法更接近于待解问题的表示方法：定义数据、描述运算、控制流程、传输数据。
如：C、FORTRAN、PASCAL、C++、JAVA、SQL(数据定义、数据操作)。

（3）命令语言(Command Language)

控制系统的工作——以功能封装为特征。如UNIX上的shell。

程序设计语言的分类

（1）命令式语言(Imperative Language)

通过指明一系列可执行的运算及运算的次序来描述计算过程的语言；
FORTRAN(段结构)、BASIC、Pascal(嵌套结构)、C…… ；
程序的层次性和抽象性不高。

（2）面向对象语言(Object-Oriented Language)

以对象为核心，如Smalltalk、C++ 、Java、Ada(程序包)…… ；
具有识认性（对象）、类别性（类）、多态性和继承性。

（3）申述式语言(Declarative Language)

着重描述要处理什么，而非如何处理的非命令式语言；
函数(应用)式语言(Functional Language) -- 基本运算单位是函数，如LISP、ML……；
逻辑式(基于规则)语言(Logical Language) -- 基本运算单位是谓词，如Prolog，Yacc……；
并发式语言(Concurrent Language) -- 着重于如何描述潜在的并行机制，如ErLang，Fortran+MPI，Elixir……

1.2 程序设计语言的翻译

（1）翻译程序(Translator)

将某一种语言描述的程序(源程序——Source Program)翻译成等价的另一种语言描述的程序(目标程序——Object Program)的程序。

（2）解释程序(Interpreter)

一边解释一边执行的翻译程序；同声传译。

（3）编译程序(Compiler)

将源程序完整地转换成机器语言程序或汇编语言程序；高级语言程序→汇编/机器语言程序。

编译系统(Compiling System) -- 编译系统=编译程序+运行系统

1.3 编译程序的总体结构

（1）词法分析

词法分析由词法分析器(Lexical Analyzer)完成，词法分析器又称为扫描器(Scanner)。
词法分析器从左到右扫描组成源程序的字符串，并将其转换成单词(记号—token)串；同时要：查词法错误，进行标识符登记——符号表管理。
输入：字符流
输出：词法单元(token): (token-name，attribute-value)

例：sum=(10+20)*(num+square);

结果： (id，1) 、( = ) 、( ( )、 ( 10 )、 ( + ) 、( 20 )、 ( ) )、 ( * )、 ( ( )、 (id，2) 、( + ) 、(id，3)、 ( ) )、 ( ; )。

（2）语法分析

语法分析由语法分析器(Syntax Analyzer)完成，又叫Parser。
功能：【1】Parser实现“组词成句”，将词组成各类语法成分：表达式、因子、项，语句，子程序… 【2】构造分析树【3】指出语法错误【4】指导翻译
输入：词法单元/符号流
输出：语法单元(syntax tree)

例：sum=(10+20)*(num+square);

（3）语义分析

语义分析(semantic analysis)使用语法树和符号表信息来检查源程序的语义一致性
功能：分析由语法分析器识别出来的语法成分的语义。包括：【1】收集标识符的类型信息【2】语义检查：类型检查、自动类型转换、运算的合法性等。

（4）中间代码生成

中间代码 (intermediate Code) 。例:sum=(10+20)*(num+square);

中间代码的特点：简单规范；与机器无关；易于优化与转换
三地址码的另一种表示形式： T1=10+20；T2=num+square ；T3=T1*T2 ；sum=T3

（5）代码优化

代码优化(optimization)是指对中间代码进行优化处理，降低存储空间，提升运行效率。

与机器无关的优化

【1】局部优化

常量合并：常数运算在编译期间完成，如8+9*4
公共子表达式的提取:在基本块内进行的

【2】循环优化

代码外提：将循环不变计算移出循环
强度削减：用较快的操作代替较慢的操作: X^2 →X*X

与机器有关的优化

【1】寄存器的利用：将常用量放入寄存器，以减少访问内存的次数

【2】体系结构：MIMD、SIMD、SPMD、向量机、流水机

【3】存储策略：根据算法访存的要求安排：Cache、并行存储体系——减少访问冲突

【4】任务划分：按运行的算法及体系结构，划分子任务(MPMD)

（6）目标代码生成

【1】将中间代码转换成目标机上的机器指令代码或汇编代码

确定源语言的各种语法成分的目标代码结构（机器指令组/汇编语句组）
制定从中间代码到目标代码的翻译策略或算法

【2】目标代码的形式

具有绝对地址的机器指令
汇编语言形式的目标程序
模块结构的机器指令（需要链接程序）

（7）表格管理

管理各种符号表(常数、标号、变量、过程、结构……)，查、填（登记、查找）源程序中出现的符号和编译程序生成的符号，为编译的各个阶段提供信息。辅助语法检查、语义检查；完成静态绑定、管理编译过程
Hash表、链表等各种表的查、填技术

（8）错误处理

进行各种错误的检查、报告、纠正，以及相应的续编译处理

词法：拼写……
语法：语句结构、表达式结构……
语义：类型不匹配、参数不匹配……

模块分类

分析：词法分析、语法分析、语义分析
综合：中间代码生成、代码优化、目标代码生成
辅助：符号表管理、出错处理
8项功能对应8个模块

1.4 编译程序的组织

（1）根据系统资源的状况、运行目标的要求……等，可以将一个编译程序设计成多遍（Pass）扫描的形式，在每一遍扫描中，完成不同的任务。 如：首遍构造语法树，第二遍处理中间表示、增加信息等。

（2）遍可以和阶段相对应，也可以和阶段无关。

（3）编译程序的设计目标

规模小、速度快、诊断能力强、可靠性高、可移植性好、可扩充性好
目标程序也要规模小、执行速度快

（4）编译系统规模较大，因此可移植性很重要。为了提高可移植性，将编译程序划分为前端和后端。

【1】前端

与源语言有关、与目标机无关的部分
词法分析、语法分析、语义分析与中间代码生成、与机器无关的代码优化

【2】后端

与机器有关的代码优化
目标代码生成

1.5 T形图

表示语言翻译的Ｔ形图

本机编译器的利用

问题一： A机上有一个C语言编译器，现要实现一个新语言NEW的编译器？需要直接用A机器语言编写吗？

用C编写NEW的编译，并用C编译器编译它

交叉编译(Cross Compiling)/移植

问题二：A机上有一个C语言编译器，是否可利用此编译器实现B机上的C语言编译器？

条件：Ａ机有Ｃ语言的编译程序（P1)

目的：实现Ｂ机的Ｃ语言的编译(P3)

1. (人)用Ｃ语言编制B机的Ｃ编译程序P0(C→B)

2. (Ａ机的C编译P1)编译P0，得到在A机上可运行的P2(C→B)

第二章语言及其文法

字母表

字母表∑是一个有穷符号集合。
符号：字母、数字、标点符号、…
例：二进制字母表：{ 0,1 } ；ASCII字符集；Unicode字符集

字母表上的运算

（1）字母表∑1和∑2的乘积( product)，∑1∑2 ={ab|a ∈ ∑1, b ∈ ∑2}

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

（2）字母表∑的n次幂( power)

例： {0,1}^3 ={0,1} {0,1} {0,1} ={000,001,010,011,100,101,110,111}\

字母表的n次幂：长度为n的符号串构成的集合

（3）字母表∑的正闭包( positive closure)

∑+ = ∑ ∪ ∑2 ∪ ∑3 ∪ …

例：{a, b, c, d }+ = {a, b, c, d, aa, ab, ac, ad, ba, bb, bc, bd, …, aaa, aab, aac, aad, aba, abb, abc, …}

字母表的正闭包：长度正数的符号串构成的集合

（4）字母表∑的克林闭包(Kleene closure)

∑* = ∑0 ∪ ∑+ = ∑0 ∪ ∑ ∪ ∑2 ∪ ∑3 ∪ …

例：{a, b, c, d }* = {ε, a, b, c, d, aa, ab, ac, ad, ba, bb, bc, bd, …, aaa, aab, aac, aad, aba, abb, abc, …}

字母表的克林闭包：任意符号串（长度可以为零）构成的集合

串(String)

（1）设∑是一个字母表，任意x∈∑*，x称为是∑上的一个串。串是字母表中符号的一个有穷序列。

（2）串s的长度，通常记作|s|，是指s中符号的个数。例: |aab|=3

（3）空串是长度为0的串，用 ε（epsilon）表示。 |ε|= 0

串上的运算——连接

如果 x和y是串，那么x和y的连接(concatenation) 是把y附加到x后面而形成的串，记作xy

例如，如果x=dog且y=house，那么xy=doghouse
空串是连接运算的单位元( identity)，即，对于任何串s都有，εs = sε = s
设x,y,z是三个字符串，如果 x=yz，则称y是x的前缀，z是x的后缀

串上的运算——幂

串s的幂运算：

例：如果 s =ba，那么s^1= ba，s^2=baba，s^3=bababa，…

串s的n次幂：将n个s连接起来

文法的定义

自然语言的例子——句子的构成规则

未用尖括号括起来部分表示语言的基本符号，尖括号括起来部分称为语法成分。

文法的形式化定义

G = (VT , VN , P , S )

VT ：终结符集合

终结符（terminal symbol）是文法所定义的语言的基本符号，有时也称为token（词法单元）

例: VT = { apple, boy, eat, little }

VN：非终结符集合

非终结符(nonterminal) 是用来表示语法成分的符号，有时也称为“ 语法变量”

例: VN = { <句子>, <名词短语>, <动词短语>, <名词>, … }

VT ∩VN = Φ
VT∪VN ：文法符号集

P ：产生式集合

产生式( production)描述了将终结符和非终结符组合成串的方法

产生式的一般形式：α→β，读作：α定义为β

α∈(VT∪VN)+，且α中至少包含VN中的一个元素：称为产生式的头(head)或左部(left side)
β∈(VT∪VN)* ：称为产生式的体(body)或右部(right side)

S ：开始符号

S∈VN 开始符号(start symbol)表示的是该文法中最大的语法成分，例：S = <句子>

约定：不引起歧义的前提下，可以只写产生式

产生式的简写

对一组有相同左部的α产生式 α→β1 , α→β2 , … , α→βn

可以简记为： α→β1 | β2 | … | βn

读作：α定义为β1，或者β2，…，或者βn 。

β1，β2，…，βn称为α的候选式(Candidate)

例子：E → E + E，E → E * E ，E → ( E ) ，E → id -----》 E → E + E | E * E | ( E ) | id

符号约定

下述符号是终结符

(a) 字母表中排在前面的小写字母，如 a、b、c
(b) 运算符，如 +、*等
(c) 标点符号，如括号、逗号等
(d) 数字0、1、. . . 、9
(e) 粗体字符串，如id、if等

下述符号是非终结符

(a) 字母表中排在前面的大写字母，如A、B、 C
(b) 字母S。通常表示开始符号
(c) 小写、斜体的名字，如 expr、stmt等
(d) 代表程序构造的大写字母。如E(表达式)、T(项)和F(因子)

字母表中排在后面的大写字母（如X、Y、Z）表示文法符号（即终结符或非终结符）

字母表中排在后面的小写字母（主要是u、v、. . . 、z）表示终结符号串（包括空串）

小写希腊字母，如α、β、γ，表示文法符号串（包括空串）

除非特别说明，第一个产生式的左部就是开始符号

语言的定义

推导 (Derivations)和归约(Reductions)

给定文法G=(VT , VN , P , S )，如果 α→β ∈ P，那么可以将符号串γαδ中的α替换为β，也就是说，将γαδ 重写(rewrite)为γβδ，记作 γαδ → γβδ。此时，称文法中的符号串 γαδ 直接推导(directly derive)出 γβδ 。简而言之，就是用产生式的右部替换产生式的左部。

如果α0→α1，α1→α2，α2→α3，…，αn-1→αn，则可以记作α0→α1→α2→α3→ …→αn-1→αn，称符号串 α0经过n步推导出αn，可简记为α0 →n αn

α →0 α
→+表示“经过正数步推导”
→*表示“经过若干（可以是0）步推导”

句子的推导（派生）-从生成语言的角度

句子的归约 -从识别语言的角度

句型和句子

如果 S →* α，α∈(VT∪VN)*，则称α是G的一个句型(sentential form)

一个句型中既可以包含终结符，又可以包含非终结符，也可能是空串

如果 S →* w，w ∈VT*，则称w是G的一个句子(sentence)

句子是不包含非终结符的句型

语言的形式化定义

由文法G的开始符号S推导出的所有句子构成的集合称为文法G生成的语言，记为L(G )。即

L(G )= {w | S →* w, w∈ VT* }

例子：

文法G

① S → L | LT

② T → L | D | TL | TD

③ L → a | b | c | … | z

④ D → 0 | 1 | 2 | 3 |…| 9

该文法生成的语言是：标识符

T →TL →TDL →TDDL →TLDDL … → TD…LDDL → DD…LDDL

T为字母数字串

语言上的运算

例：令L={A，B，…，Z，a，b，…，z}，D={0，1，…，9}。则L(L∪D)*表示的语言是标识符。

文法的分类

Chomsky 文法分类体系

0型文法 (Type-0 Grammar)
1型文法 (Type-1 Grammar)
2型文法 (Type-2 Grammar)
3型文法 (Type-3 Grammar)

0型文法 (Type-0 Grammar)

α → β

无限制文法(Unrestricted Grammar) /短语结构文法 (Phrase Structure Grammar, PSG )

∀α → β∈P， α中至少包含1个非终结符

0型语言：由0型文法G生成的语言L(G )

1型文法 (Type-1 Grammar)

α → β

上下文有关文法(Context-Sensitive Grammar , CSG )

α1Aα2 → α1β α2 (β ≠ε ) or S → ε

上下文有关语言（1型语言）：由上下文有关文法 (1型文法) G生成的语言L(G )

2型文法 (Type-2 Grammar)

α → β

上下文无关文法 (Context-Free Grammar, CFG )

∀α → β∈P，α ∈ VN

产生式的一般形式：A→β

文法G（上下文无关文法）
① S → L | LT
② T → L | D | TL | TD
③ L → a | b | c | d
④ D → 0 | 1 | 2 | 3 | 4 | 5

上下文无关语言（2型语言） 由上下文无关文法 (2型文法) G生成的语言L(G )

3型文法 (Type-3 Grammar)

α → β

正则文法 (Regular Grammar, RG )

右线性(Right Linear)文法： A→wB 或 A→w

左线性(Left Linear) 文法： A→Bw 或 A→w

左线性文法和右线性文法都称为正则文法

例（右线性文法）
① S → a | b | c | d
② S → aT | bT | cT | dT
③ T → a | b | c | d | 0 | 1 | 2 | 3 | 4 | 5
④ T → aT | bT | cT | dT | 0T | 1T | 2T | 3T | 4T | 5T

正则语言（3型语言）:由正则文法 (3型文法) G生成的语言L(G )

正则文法能描述程序设计语言的多数单词

四种文法之间的关系

逐级限制

0型文法：α中至少包含1个非终结符
1型文法（CSG）：S → ε or｜α｜≤｜β｜
2型文法（CFG）：α ∈ VN
3型文法（RG）：A→wB 或 A→w (A→Bw 或A→w)

逐级包含

CFG的分析树

根节点的标号为文法开始符号
内部结点表示对一个产生式A→β的应用，该结点的标号是此产生式左部A 。该结点的子结点的标号从左到右构成了产生式的右部β
叶结点的标号既可以是非终结符，也可以是终结符。从左到右排列叶节点得到的符号串称为是这棵树的产出(yield )或边缘(frontier)

分析树是推导的图形化表示

给定一个推导 S→ α1→ α2→…→ αn ，对于推导过程中得到的每一个句型αi，都可以构造出一个边缘为αi的分析树

(句型的）短语

给定一个句型，其分析树中的每一棵子树的边缘称为该句型的一个短语(phrase)
如果子树只有父子两代结点，那么这棵子树的边缘称为该句型的一个直接短语(immediate phrase)

二义性文法

如果一个文法可以为某个句子生成多棵分析树，则称这个文法是二义性的。

例子

文法：

S→ if E then S
→ if E then S else S
→ other

句型： if E1 then if E2 then S1 else S2

消歧规则：每个else和最近的尚未匹配的if匹配

二义性文法的判定

对于任意一个上下文无关文法，不存在一个算法，判定它是无二义性的；但能给出一组充分条件，满足这组充分条件的文法是无二义性的

满足，肯定无二义性
不满足，也未必就是有二义性的

第三章词法分析

正则表达式

语言L={a}{a,b}*({ε}∪({.,_}{a,b}{a,b}*))

正则表达式(Regular Expression，RE)是一种用来描述正则语言的更紧凑的表示方法

例：r = a(a|b)*( ε | (.| _)(a|b)(a|b)* )

正则表达式可以由较小的正则表达式按照特定规则递归地构建。每个正则表达式 r定义（表示）一个语言，记为L(r )。

正则表达式的定义

ε是一个RE，L(ε) = {ε}

如果 a∈∑，则a是一个RE，L(a) = {a}

假设 r和 s都是 RE，表示的语言分别是 L(r)和L(s)，则

r|s 是一个RE，L( r|s ) = L(r)∪L(s)
rs 是一个RE，L( rs ) = L(r) L(s)
r* 是一个RE，L( r* )= (L(r))*
(r) 是一个RE，L( (r) ) = L(r)

运算的优先级：*、连接、|

例子1

令 ∑ = {a, b}，则

L(a|b) = L(a)∪L(b) ={a}∪{b} = {a, b}

L((a|b)(a|b)) = L(a|b) L(a|b)={a, b}{a, b}= { aa, ab, ba, bb }

L(a*) = (L(a))*= {a}*= { ε, a, aa, aaa, . . . }

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

L(a|a*b) = { a, b, ab, aab, aaab, . . .}

例子2

C语言无符号整数的RE

十进制整数的RE：(1|...|9)(0|...|9)*|0

八进制整数的RE：0(0|1|2|3|4|5|6|7)(0|1|2|3|4|5|6|7)*

十六进制整数的RE：0x(0|1|...|9|a|...| f |A|…|F)(0|...|9|a|...| f |A|…|F )*

正则语言

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

RE的代数定律

r|s = s|r ----- | 是可以交换的
r|(s|t) = (r|s)|t ----- | 是可结合的
r(st) = (rs)t ----- 连接是可结合的
r(s|t) = rs|rt ; (s|t)r = sr|tr ----- 连接对 | 是可分配的
εr = rε = r ----- ε 是连接的单位元
r * = （ r｜ε ）* ----- 闭包中一定包含 ε
r **= r * ----- * 具有幂等性

正则文法与正则表达式等价

对任何正则文法 G，存在定义同一语言的正则表达式 r
对任何正则表达式 r，存在生成同一语言的正则文法 G

正则定义（ Regular Definition）

正则定义是具有如下形式的定义序列：d1→r1，d2→r2，…，dn→rn

其中：每个di都是一个新符号，它们都不在字母表 Σ中，而且各不相同；每个ri是字母表 Σ∪{d1 ,d2 , … ,di-1}上的正则表达式。

（给一些RE命名，并在之后的RE中像使用字母表中的符号一样使用这些名字）

例子

C语言中标识符的正则定义（字母开头，不能数字开头）：

digit → 0|1|2|…|9

letter_ → A|B|…|Z|a|b|…|z|_

id → letter_(letter_|digit)*

（整型或浮点型）无符号数的正则定义：

digit → 0|1|2|…|9

digits → digit digit*

optionalFraction → .digits|ε

optionalExponent → ( E(+|-|ε)digits )|ε

number → digits optionalFraction optionalExponent

2 2.15 2.15E+3 2.15E-3 2.15E3 2E-3

有穷自动机

有穷自动机 ( Finite Automata，FA )由两位神经物理学家MeCuloch和Pitts于1948年首先提出，是对一类处理系统建立的数学模型

这类系统具有一系列离散的输入输出信息和有穷数目的内部状态（状态：概括了对过去输入信息处理的状况）

系统只需要根据当前所处的状态和当前面临的输入信息就可以决定系统的后继行为。每当系统处理了当前的输入后，系统的内部状态也将发生改变。

FA模型

输入带(input tape)：用来存放输入符号串

读头(head )：从左向右逐个读取输入符号，不能修改（只读）、不能往返移动

有穷控制器( finite control )：具有有穷个状态数，根据当前的状态和当前输入符号控制转入下一状态

FA的表示

转换图 (Transition Graph)

结点：FA的状态

初始状态（开始状态）：只有一个，由start箭头指向
终止状态（接收状态）：可以有多个，用双圈表示

带标记的有向边：如果对于输入a，存在一个从状态p到状态q的转换，就在p、q之间画一条有向边，并标记上a

FA定义（接收）的语言

给定输入串x，如果存在一个对应于串x的从初始状态到某个终止状态的转换序列，则称串x被该FA接收

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

例子：abbaabb（同上图）

L(M) =所有以abb结尾的字母表{a, b}上的串的集合

最长子串匹配原则(Longest String Matching Principle)

当输入串的多个前缀与一个或多个模式匹配时，总是选择最长的前缀进行匹配。

在到达某个终态之后，只要输入带上还有符号，DFA就继续前进，以便寻找尽可能长的匹配。

有穷自动机的分类

FA的分类

确定的FA (Deterministic finite automata, DFA)
非确定的FA (Nondeterministic finite automata, NFA)

确定的有穷自动机 (DFA)

M = ( S，Σ ，δ，s0，F )

S：有穷状态集
Σ：输入字母表，即输入符号集合。假设ε不是 Σ中的元素。
δ：将S×Σ映射到S的转换函数。任意s∈S, a∈Σ, δ(s,a)表示从状态s出发，沿着标记为a的边所能到达的状态。
s0：开始状态 (或初始状态)，s0∈ S
F：接收状态（或终止状态）集合，F⊆ S

例子：一个DFA

M = ( S，Σ ，δ，s0，F )

可以用转换表表示DFA

非确定的有穷自动机(NFA)

M = ( S，Σ ，δ，s0，F )

S：有穷状态集
Σ：输入符号集合，即输入字母表。假设ε 不是Σ中的元素
δ：将S×Σ映射到2^S的转换函数。任意s∈S, a∈Σ, δ(s,a)表示从状态s出发，沿着标记为a的边所能到达的状态集合
s0：开始状态 (或初始状态)，s0∈ S
F：接收状态（或终止状态）集合，F⊆ S

例子：一个NFA

M = ( S，Σ ，δ，s0，F )

如果转换函数没有给出对应于某个状态-输入对的信息，就把Ø放入相应的表项中。

DFA和NFA的等价性

对任何非确定的有穷自动机N ，存在定义同一语言的确定的有穷自动机D
对任何确定的有穷自动机D ，存在定义同一语言的非确定的有穷自动机N
DFA和NFA可以识别相同的语言
正则文法 ⇔正则表达式 ⇔FA

例子：r = (a|b)*abb

状态1：串以a结尾；状态2：串以ab结尾；状态3：串以abb结尾

带有“ε-边”的 NFA

M = ( S，Σ ，δ，s0，F )

S：有穷状态集

Σ：输入符号集合，即输入字母表。假设ε不是Σ中的元素

δ：将S×(Σ∪{ε})映射到2^S的转换函数。任意s∈S, a∈Σ∪{ε}, δ(s,a)表示从状态s出发，沿着标记为a的边所能到达的状态集合

s0：开始状态 (或初始状态)，s0∈ S

F：接收状态（或终止状态）集合，F⊆ S

例子：r = 0*1*2*

带有和不带有“ε-边”的 NFA 的等价性

例子：r = 0*1*2*（如上图）

状态A：0*；状态B：0*1*；状态C：0*1*2*

DFA的算法实现

输入：以文件结束符eof结尾的字符串x。DFA D 的开始状态s0，接收状态集 F，转换函数move。

输出：如果 D接收 x，则回答“yes”，否则回答“no”。

方法：将下述算法应用于输入串 x。

s = s0 ;
c = nextChar（）;
while（ c! = eof ）｛
s = move ( s , c ) ;
c = nextChar ( ) ;
｝
if (s在F中) return“yes” ;
else return “no” ;
函数nextChar( )返回输入串x的下一个符号
函数move(s, c)表示从状态s出发，沿着标记为c的边所能到达的状态

从正则表达式到有穷自动机

RE：r = (a|b)*abb

NFA：

DFA：

根据RE 构造NFA

ε对应的NFA

字母表Σ中符号a对应的NFA

r = r1r2对应的NFA

r = r1|r2对应的NFA

r = (r1)*对应的NFA

例子： r=(a|b)*abb 对应的NFA

从NFA到DFA的转换

从普通NFA到DFA的转换

例子1

r =aa*bb*cc*

DFA的每个状态都是一个由NFA中的状态构成的集合,即NFA状态集合的一个子集

	a	b	c
A	{A,B}	Ø	Ø
B	Ø	{B,C}	Ø
C	Ø	Ø	{C,D}
D	Ø	Ø	Ø

由转换表

从带有ε-边的NFA到DFA的转换

例子2

r=0*1*2*

转换表如下：

	0	1	2
A	{*A,B,C*}	{*B,C*}	{C}
B	Ø	{*B,C*}	{C}
C	Ø	Ø	{C}

DFA：

ε-closure ( s )：能够从NFA的状态s开始只通过ε转换到达的NFA状态集合

ε-closure ( T )：能够从T 中的某个NFA状态 s开始只通过ε转换到达的NFA状态集合,即Us∈T ε-closure ( s )（T是集合即合并！）

计算 ε-closure (T )

将T的所有状态压入stack中；
将ε-closure（T ）初始化为 T ；
while（stack非空）｛
将栈顶元素 t 给弹出栈中；
for（每个满足如下条件的u ：从t出发有一个标号为ε的转换到达状态u)
if ( u不在ε-closure （T ）中）｛
将u加入到ε-closure （T ）中；
将u压入栈中;
}
}

子集构造法（ subset construction）

输入：NFA N

输出：接收同样语言的DFA D

方法：一开始，ε-closure （ s0 ）是Dstates 中的唯一状态，且它未加标记；