当前位置：文档之家 › 编译原理第三章

编译原理第三章

  • 格式：ppt
  • 大小：1.35 MB
  • 文档页数：77

下载文档原格式

  / 77

合集下载

编译原理第03章PPT课件

编译原理第03章PPT课件

65
-
procedure swap(var x:integer); begin x:=x+a; /*a是全局变量*/
a:=x-a; x:=x-a end; 调用swap(a);别名也影响编译器生成优化的代 a:=(x-y*z)+w ； b:=(x-y*z)+u ； 若a与x、y或z中任一个是别名
用标号控制循环体 DO 7 I=1，10 A(I)=0 B(I)=0
7 CONTINUE
19
-
②Pascal的for 语句
计数重复的值可在任何有序集上 for . . . to . . . for . . . down to . . .
20
-
2. 条件制导
①while：0次或多次重复 ②do-while，repeat-until:多次重复 ③ALGOL 68循环的一般形式：
Smalltalk 语言以对象方式来处理控 制结构。
40
-
可以认为上述语言是可扩充的，用 户可以通过定义新的（抽象）数据类型 和控制结构来扩充基本语言。
但基本的控制结构并没有发生改变。
41
-
第二节 单元级控制结构
规定程序单元之间控制流程的机制。 最简单的机制是 ALGOL60 的分程序
42
-
在程序顺序执行的过程中，遇到一 个分程序，就建立一个新的引用环境， 并执行这个分程序。
7
-
3. 多选一 嵌套 的 if then else
if语句包含if语句 ①ALGOL 60的选择结构引起二义性
if x>0 then if x<6 then x:=0 else x:=9 ②PASCAL的“最近匹配原则” ③ ALGOL 68中if语句的结束符号fi ④ ALGOL 68对else if 进行缩写

《编译原理》第3章

《编译原理》第3章

NFA到相应的DFA的构造的基本思路是： DFA的每 一个状态对应NFA的一组状态. DFA使用它的状 态去记录在NFA读入一个输入符号后可能达到的 所有状态.
NFA M所能接受的符号串的全体记为L(M)
结论：
上一个符号串集V是正规的，当且仅当存 在一个上的不确定的有穷自动机M，使得 V=L(M)。
DFA是NFA的特例.对每个NFA N一定存在一个DFA Ｍ，使得 L(M)=L(N)。对每个NFA N存在着与之 等价的DFA M。 有一种算法，将NFA转换成接受同样语言的DFA.这 种算法称为子集法. 与某一NFA等价的DFA不唯一.
0
1
S P
Z
{P} {}
{P}
{S,Z} {Z}
{P}
• δ为S * 到S的子集(2 S)的一种映射
• 从NFA的矩阵表示中可以看出，表项通常是一状态的集合， 而在DFA的矩阵表示中，表项是一个状态
∑*上的符号串t被NFA M接受:
• 对于Σ*中的任何一个串t，若存在一条从某一初态 结点到某一终态结点的道路，且这条道路上所有 弧的标记字依序连接成的串(不理采那些标记为ε 的弧)等于t，则称t可为NFA M所识别(读出或接 受)。 • 若M的某些结点既是初态结点又是终态结点；或 者存在一条从某个初态结点到某个终态结点的道 路,其上所有弧的标记均为ε，那么空字ε可为M所 接受。
其中： δ(S，0)={P}
δ(S，1)={S，Z} δ(Z，0)={P} δ(Z，1)={P} δ(P，1)={Z} • 状态图表示
1 1 S 0 0,1 Z
P
1
• 矩阵表示
状态 输入
δ(S，0)={P} δ(S，1)={S，Z} δ(Z，0)={P} δ(Z，1)={P} δ(P，1)={Z}

编译原理第三章_有穷自动机

编译原理第三章_有穷自动机
5
例 过河问题 分析（续）
初始状态：MWGC-φ；终止状态：φ-MWGC。 g
MWGC-φ
WC-MG
问题：
6
例 过河问题 状态转换图
起始 g
MWGC-φ g
g φ-MWGC
g
7
WC-MG
m
m MWC-G
w
w
c
C-MWG
c W-MGC
g
g
MGC-W c
MG-WC
w
m
c G-MWC
m
gg MWG-C
+dd. ddd;
输入符号串
数字 数字
SB
.
数字
+
A
H
-.
数字
.G
接收：若扫描完输入串， 且在一个终止状态上结 束。
数字 阻塞：若扫描结束但未 停止在终止状态上；或 者为能扫描完输入串 （如遇不合法符号）。
不完全描述：某些状态 对于某些输入符号不存 在转换。
练习：+34.567 .123 3.4.5
w
有穷自动机（FA）
数字系统：可以从一个状态移动到另一个状态；每次 状态转换，都上由当前状态及一组输入符号确定的；可以 输出某些离散的值集。
FA：一个状态集合；状态间的转换规则；通过读头来 扫描的一个输入符号串。
读头：从左到右扫描符号串。移动（扫描）是由状态 转换规则来决定的。
8
读头
一个FA的例子
(3)运行： 串f(，Q,且t1tt21)∈= Σf(，f(Qt1,t2t1∈), Σt2*)，其中Q∈K， t1t2为输入字符
17
例３
题：试证abba可为例1的DFA M所识别（所接受）。

编译原理_第3章课件

编译原理_第3章课件

编译原理_第3章课件第三章词法分析本章将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的⾃动构造原理。

教学要求１.掌握：正规式，DFA的概念，NFA的概念２.理解：将NFA转换为DFA ,正规式、正规⽂法与有穷⾃动机间的转换⽬录3.1 词法分析程序的设计3.2 单词的描述⼯具3.3 有穷⾃动机3.4 正规式与有穷⾃动机的等价性3.5 正规⽂法和有穷⾃动机的等价性3.6 词法分析程序的⾃动构造⼯具⼩结3.1.词法分析（lexical analysis）程序的设计回顾：1、词法分析的任务：逐个读⼊源程序字符并按照构词规则切分成⼀系列单词。

2、词法分析程序：实现词法分析的程序。

⼀.词法与语法分析程序的接⼝⽅式1、作为独⽴的⼀遍词法分析是编译过程中的⼀个阶段，在语法分析前进⾏，把字符流的源程序变为单词序列，输出在⼀个中间⽂件上。

2、与语法分析结合在⼀起作为⼀遍⼀般、把词法分析程序设计成⼀个⼦程序，由语法分析程序调⽤词法分析程序来获得当前单词，供语法分析使⽤。

….词法分析程序的主要任务：读源程序，产⽣单词符号词法分析程序的其他任务：滤掉空格，跳过注释、换⾏符追踪换⾏标志，复制出错源程序，宏展开，……⼆、词法分析程序的输出输出是单词符号。

单词是语⾔中具有独⽴意义的最⼩单位。

单词包括：保留字标识符常量运算符界符（标点符号）词法分析程序所输出的单词符号常常采⽤以下⼆元式表⽰：(单词种别，单词⾃⾝的值)。

单词的种别是语法分析需要的信息，⽽单词⾃⾝的值则是编译其它阶段需要的信息。

(标识符，指向该标识符所在符号表中位置的指针) 单词的种别可以⽤整数编码表⽰，假如标识符编码为1，常数为2，保留字为3，运算符为4，界符为5例如：程序段if i=5 then x∶=y；在经词法分析器扫描后输出的单词符号和它们的表⽰如下：- 保留字if(3，'if')- 标识符i(1，指向i的符号表⼊⼝)- 等号=(4，'=')- 常数5(2，'5')- 保留字then(3，'then')- 标识符x(1，指向x的符号表⼊⼝)- 赋值号∶=(4，'∶=')- 标识符y(1，指向y的符号表⼊⼝)- 分号；(5，'；')三、词法分析⼯作从语法分析⼯作独⽴出来的原因：简化设计改进编译效率增加编译系统的可移植性3.2 单词的描述⼯具程序设计语⾔中的单词是基本语法成分.单词符号的语法可以⽤有效的⼯具加以描述，并且基于这类描述⼯具，实现词法分析程序的⾃动构造.描述⼯具：正规⽂法和正规式识别⼯具：有穷⾃动机⼀．正规⽂法多数程序设计语⾔的单词的语法能⽤正规⽂法来描述。

编译原理 第三章

编译原理 第三章

• ε-Closure(q)： 从状态q出发，经过任意条标记为ε的矢线所能达到的状态集合。
• f^的递归定义： 1）f^(s,ε)=ε- Closure(s) 2）f^(s,wa)=ε- Closure(p) 其中：p=f(f^(s,w),a)=∪f(q,a), q∈f^(s,w) 3）f(R,a)=∪f(q,a), q∈R （将f的定义域推广到状态集合R） 4）f^(R,w)=∪f^(q,w), q∈R （将f^的定义域推广到状态集合R）
2）有限自动机所接受符号串的递归定义（将f的定义域推广到 k x ∑*） (1) f^(s,ε)=s; (2) f^(s,aw)=f^(f(s,a),w),a∈∑,w∈∑* 结论：f^与f效果一样。
3）一个DFA M所接受的字符串的全体称为M的接受集或语言，记为： L(M)={x|f(S0, x)∈Z, x∈∑*}。
最优 （优先顺序可用括号加以改变） 次之 最后
• 正规式：将文法的终结符号用以上三种运算符连接起来组成的正规文法的表 达式，是另一种用于描述正规文法的直观表示。 例如语法范畴<标识符>的正规表达式为：字母(字母|数字)* • 正规集：正规式所描述的字符串的集合。
1. 正规表达式和正规集定义：
设∑为一字母表，则∑上的正规式及其所表征的正规集可递归地定义为：
第三章
词法分析及词法分析程序
§3.1 设计扫描器时应注意的几个问题
1. 词法分析阶段的必要性
1）与语法分析比较，可采用简单有效的方法； 2）词法分析有时需要涉及上下文，与语法分析不同； 3）编译程序各部分的功能更加单一，结构清晰，编写、调试相对简单。 注：在逻辑功能上把词法分析和语法分析划分开； 在程序编制(执行流程)上可将词法分析作为语法分析程序的子程序

编译原理_chapter3概要

编译原理_chapter3概要

3.1.5 词法分析器的位置
符 号 表 源程序 词法分析器 语法分析器 语义分析与 代码生成 目标程序
目标代码整理 图3.1 以语法分析器为中心

以语法分析器为中心的优点：

简化编译器的设计。 提高编译器的效率。 增强编译器的可移植性。
16
2018/11/26
设计成一个独立程序，完成词法分析的 任务，结果以文件的形式组织，做为语 法分析的输入
单词名称 标识符 无符号常数(整) 无符号浮点数 布尔常数 字符串常数 FOR DO IF ELSE THEN INT CHAR FLOAT WHILE
2018/11/26
类别编码 单词值 1 内部字符串 标识符常数 : 2 整数值 一类一码 数值 3 4 0 或 1 5 内部字符串 6 7 8 9 关键字: 10 一字一码 11 12 13 14 7 …… ……
符号表
源程序
词法 分析
TOKEN字
错误信息
图3.2 设计成独立的程序
17
3.2 词法分析阶段的设计与实现
区别?
2018/11/26
8
例3.1 语句if count>7 then result := 100; 的单词符号序列
(9，0) (1，指向count 的符号表入口) (30，0) (11，7) (10，0) (1，指向result的符号表入口) (24，0) (11，100) (29，0)
2018/11/26
School of Computer Science & Technology Harbin Institute of Technology
第三章 词法分析
重点：词法分析器的输入、输出， 用于识别符号的状态转移图的构造 难点：根据状态转移图实现词法分析器的设计

程序设计语言编译原理(第三版)第3章

程序设计语言编译原理(第三版)第3章第3章词法分析任务：从左至右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号串。

§3.1§3.2§3.3§3.4对于词法分析器的要求词法分析器的设计正规表达式与有限自动机词法分析器的自动产生(LE某)—略1§3.1对于词法分析器的要求一.功能和输出形式二.接口设计§3.1对于词法分析器的要求一.功能和输出形式1.功能：输入源程序，输出单词符号2.单词符号的分类(1)关键字:由程序语言定义的具有固定意义的标识符，也称为保留字或基本字。

例如：Pacal语言中begin(2)标识符：用来表示各种名字。

endifwhile等。

如变量名、数组名、过程名等。

(3)常数：整型、实型、布尔型、文字型等例：100(5)界符：,;3.14159()true等ample(4)运算符：+、-、某、/3§3.1对于词法分析器的要求3.输出的单词符号形式二元式：(单词种别，单词符号的属性值)通常用“整数编码”“单词符号的特征或特性”单词符号的编码：标识符：一般统归为一种常数：常按整型、实型、布尔型等分类关键字：全体视为一种/一字一种运算符：一符一种界符：一符一种4§3.1对于词法分析器的要求例：考虑下述C++代码段：while(i>=j)i--;经词法分析器处理后，它将被转换为如下的单词符号序列：<while,-><(,-><id,指向i的符号表项的指针><>=,-><id,指向j的符号表项的指针><),-><id,指向i的符号表项的指针><--,-><;,->§3.1对于词法分析器的要求二.接口设计1.词法分析器作为独立的一遍词法分析字符流(源程序)单词序列(输出在一个中间文件上)2.词法分析器作为一个独立的子程序，但并不一定作为独立的一遍语法分析器单词(至少一个)调用(取下一个单词)词法分析器优点：使整个编译程序的结构更简洁、清晰和条理化.6§3.2词法分析器的设计一.输入和预处理二.单词符号的识别三.状态转换图及其实现§3.2词法分析器的设计一.输入、预处理1.预处理：剔掉空白符、跳格符、回车符、换行符、注解部分等.原因：编辑性字符除了出现在文字常数中之外，在别处的任何出现都无意义.#注解部分不是程序的必要组成部分，它的作用仅在于改善程序的易读性和易理解性.8§3.2词法分析器的设计2.预处理子程序：每当词法分析器调用时，就处理出一串确定长度(如120个字符)的输入字符，并将其装进词法分析器所确定的扫描缓冲区中。

编译原理课件第3章

ຫໍສະໝຸດ 04CATALOGUE
代码优化
代码优化的目的和分类
目的
提高程序运行效率，减少空间占用，提高可读 性。
局部优化
对单个程序块的优化，如基本块的优化。
全局优化
对整个程序的优化，如循环优化、死代码删除等。
代码优化的主要技术
常量折叠和替换
将常量表达式的结果在编译时计算出来，并 用结果替换掉表达式。
循环优化
编译原理课件第3章
contents
目录
• 词法分析 • 语法分析 • 中间代码生成 • 代码优化 • 目标代码生成
01
CATALOGUE
词法分析
词法分析器的任务
将源程序分解成一系列的记号（tokens） 去除源程序中的注释和空白符
识别出关键字、标识符、常量、操作符等记号 为语法分析器提供有序的记号流
通过改变循环的迭代顺序、减少循环中的计 算等方法来提高循环的效率。
死代码删除
删除永远不会被执行到的代码。
函数内联
将小的函数调用替换为函数体的直接执行， 以减少函数调用的开销。
代码优化的实现
编译器前端
负责将源代码转换成中间表示（IR），这一阶段主要 完成语义分析和语法分析。
编译器中端
对中间表示进行优化，如常量折叠、死代码删除等。
考虑文法的二义性
有些文法具有二义性，即一种语法结构可以有多种解析方 式。在设计语法分析器时需要考虑如何处理二义性问题， 避免产生错误的分析结果。
语法分析器的实现
编写词法分析器
词法分析器是将输入的字符串转 换成一个个的单词或符号，供语 法分析器使用。在实现语法分析 器之前，需要先编写词法分析器 。
实现递归下降分析
解析与语义分析

编译原理(清华)第三章文法和语言


例 文法G： S→0S1，S→01 有直接推导： 0S1 00S11 （ S→0S1 ） 00S11 000S111 （ S→0S1 ） 000S111 00001111 （ S→01 ） S 0S1 （ S→0S1 ）
推导和归约 若存在v=w0 w1 ... wn=w ,(n>0) 则称v推导出w，或w归约到v,记为v=+>w 若有v =+>w，或v=w，则记作v=*>w
2. 符号串 – 定义:由字母表中的符号组成的任何有穷序列 – 例： 0,00,10是字母表∑={0‚1}上的符号串 a,ab,aaca是Α={a‚b，c}上的符号串 – 在符号串中，符号是有顺序的，顺序不同,代 表不同的符号串，如:ab和ba不同 – 不含任何符号的符号串称为空串，用ε表示 注意:{ε}并不等于空集合{ } – 符号串长度: 符号串中含有符号的个数 如: |abc|=3 | ε|=0
3.3 文法和语言的形式定义
1．文法的定义 2．文法的简化表示法 3．推导与归约 4．句型、句子、语言的定义 5．文法的等价
1．文法的定义
产生式（规则） 产生式是一个有序对(α,β)，通常写作 α→β（或α::=β ） 文法定义: 文法G(Grammar)定义为四元组（VN，VT，P，S） VN (Nonternimal)：非终结符集 VT (Terminal)：终结符集 P (Production)： 产生式（规则）集合 S： 开始符号或识别符号
第三章
文法和语言
学习目标: 掌握：自上而下与自下而上的分析方法 理解：文法的形式定义，推导，归约，句 型，句子，语言，上下文无关文法，规范 句型，语法树，短语，直接短语，句柄 了解：文法的类型，文法使用中的限制， 文法的二义性

编译原理_课件_第三章_语法分析1

29
3.2 推导和语法树
推导、规范推导 短语、句柄、素短语 语法树 文法的二义性
30
【例】设有文法G[N]: N →D|ND
D→0|1|2|3|4|5|6|7|8|9 则句子 12可由三种不同的推导序列推导出来：
(1) N ? ND ? N2 ? D2 ? 12 (2) N ? ND ? DD ? 1D ? 12 (3) N ? ND ? DD ? D2 ? 12
u∈V* ；且 V=VN∪VT。
U称为规则（产生式）左部 ，u称为规则（产生式） 右部。 ? 非终结符号 ：需要进一步定义的符号，不会出现在 程序中。 ? 终结符号 ：不需要再定义，会出现在程序中。
10
注意：
1、VN∩VT=? ，即文法中的任意一个符号要么是非 终结符，要么是终结符。
2、只用一个产生式并不足以定义一个语法范畴， 一般都需要几个产生式，特别是需要含有 递归的 产生式。
6
3.1.1 文法概述
引例1：
<句子>::=<主语><谓语><状语> <主语>::=<名词> <谓语>::=<动词> <状语>::=<介词><名词> <名词>::=Peter | Berry | river <动词>::=swims <介词>::=in 注：<句子>为要定义的目标，称为识别符号或开始符号。
? 形式语言，只是从语法上研究语言。它是抽象的数学系统， 用于模拟程序设计语言的语法，或者是并不很成功地模拟 自然语言如英语的语法。
? 形式语言理论是编译理论的重要基础，它主要研究组成符 号语言的符号串的集合及它们的表示法、结构与特性。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

例3.4 Z→ A→ B→
有正规文法G： 0A 0A | 0B 1A | ε
例3.5 A→ B→ C→
有正规文法G： aB | bB aC | a | b aB
例3.6 Z→ U→ V→
有正规文法G： Z=0(0|01)*0 U0 | V1 A=(a|b)(aa)*(a|b) Z1 | 1 Z=(10|01)(10|01)* Z0 | 0
A
B
r2 ε
A C
A
B
ε
B
r1
④R为复合正规式？
例3.12 3.13 P41
教学进度
3.4.4 NFA确定化为DFA
方法（子集法） 1、改造M为M’： ①引进新的初态结点X、终态结点Y； ②对M的状态转换图实施分裂（替换）
计算机科学与工程系
2、将M’进一步变换为DFA :
①状态子集T的闭包_CLOSURE(T) ②定义状态集Ta = _CLOSURE(J) ③从DFA的初态_CLOSURE({X})开始计算状态转换矩阵；直到 不再产生新的状态子集为止。
第三章
• • • • • •
词法分析与有穷自动机
计算机科学与工程系
词法分析器的功能与输出 单词符号的两种定义方式 正规表达式与有穷自动机 正规文法与有穷自动机 词法分析器的设计 词法分析程序自动构造工具LEX简介
教学进度
3.1 词法分析器的功能

计算机科学与工程系
词法分析：对字符串表示的源程序进行从左到右的扫描和 分解，根据语言的词法规则识别出一个个具有独立意义的 单词符号。
教学进度
3.3 单词符号的两种定义方式
单词符号结构的描述方法：
计算机科学与工程系
正规文法（３型文法）(regular grammar)
正规式（正规表达式）(regular expression) 例：标识符的定义 id → let | id dig | id let let ( let | dig )*
1 a
2
a
3
a a
4
a
5
教学进度
3.4.2 非确定有穷自动机（NFA）
计算机科学与工程系
一个 NFA M是一个五元式 M=（Q， ，δ ，S，F） 它包括： • 状态集合Q • 输入符号集合 • 转换函数δ : Q ({}) P(Q) • S 是非空开始状态集 • F Q是接受状态集合 例3.11 P39 a 识别语言 (a|b)*ab 的NFA 开始 0 a 1 b 2
教学进度
b
• NFA的转换表
状 态 0 1 2 输 入 符 号 a {0, 1} a b {0} {2}
计算机科学与工程系
识别语言 (a|b)*ab 的NFA
开始
0 b
a
1
b
2
教学进度
注意： NFA M的状态转换图中可有标记为的边。
计算机科学与工程系
• 例 识别aa*|bb*的NFA
0 3 b 4 1
a
a
2
开始
b
教学进度
DFA是NFA的特例。
计算机科学与工程系
对于每一个NFA M存在一个DFA M″ ,
使得L(M) = L(M″ )。 也就是说，每一个NFA M都可以转换成等价的 DFA M″ 。
正规式 正规文法
NFA
DFA 最小化的DFA
实现
教学进度
3.4.3 由正规表达式R构造NFA
教学进度
例如：程序段 if (i＞j) i=20; 经词法分析器处理后， 计算机科学与工程系 输出单词符号系列： 〈if， 〈 — 2， 〉— 〉 〈(，〈 —29 〉 ，— 〉 〈id，指向 〈10，指向 i的符号表入口的指针〉 i的符号表入口的指针〉 〈 〉， 〈 23 —， 〉— 〉 〈id，指向 〈10，指向 j的符号表人口的指针〉 j的符号表人口的指针〉 〈）， 〈 — 30， 〉— 〉 〈id，指向 〈10，指向 i的符号表入口的指针〉 i的符号表入口的指针〉 〈=， 〈 — 17 〉 ，— 〉 〈con 〈 ，指向 11，指向 20的常量表入口的指针〉 20的常量表入口的指针〉 〈；， 〈 — 26， 〉— 〉

通常将词法分析程序设计为语法分析程序的子程序
词 法 分 析 器 单词符号
源程序
取下一个 单词符号
语 法 分 析 器
教学进度
(1)词法分析作为一个独立的阶段； (2)与语法分析组 计算机科学与工程系 织成一遍，作为语法分析的子程序
错误的诊查处理
语法分析
源 程 序 词法 分析 语义分析和
中间代码生成
教学进度
正规集对应的正规式练习：
1、以1开头以0结尾的二进制串；
={0,1} 计算机科学与工程系
2、倒数第三个符号是0的二进制串； 3、含有相继的三个0的二进制串；
4、含有相继的两个0或相继的两个1的二进制串； 5、含有奇数个1的二进制串； 6、二进制的奇数； 7、长度能被3整除的二进制串； 8、值能被3整除的二进制串； ……
教学进度
3.3.1 正规式与正规集
一、定义 正规表达式 1. ， 2. ai
设 ={a1,a2,…,an}是字母表 {}， {ai}
计算机科学与工程系
正规表达式表达的语言（正规集）
3.
若有 r, s
r|s
L( r ) , L(s)
L( r ) L(s)
则有 ( a )
(b)
(c)
教学进度
例 设ＤＦＡ Ｍ＝（｛０,１,２, ３｝， ｛ａ, ｂ｝ ，δ ， ０，｛３｝）
其中 δ（０，ａ）＝１，δ（１，ａ）＝3 δ（２，ａ）＝１，δ（３，ａ）＝３ δ（０，ｂ）＝２，δ（１，ｂ）＝２ δ（２，ｂ）＝３，δ（３，ｂ）＝３
计算机科学与工程系
教学进度
计算机科学与工程系
转换矩阵
a 0 1 2 3 1 3 1 3 b 2 2 3 3
b
2
b
教学进度
例：DFA，接受 0和1的个数都是偶数个的二进制串
1 0 0 0 1 1 0 1 0 偶 0奇 1
计算机科学与工程系
开始 偶 0偶 1
奇0偶1
2
1
3
奇 0奇 1
教学进度
计算机科学与工程系
解释下列有限自动机分别识别什么语言？ 1 0 1 2 3 4 5 1 0 1 0 0 6 7 0 8 0 9 1 1 1 0 1
教学进度
例
while (i!=j)
if (i＞j) i＝i-j; else j=j－i;
计算机科学与工程系
词法分析器
‘while’， ‘(’，‘i’，‘!=’，‘j’， ‘)’， ‘if’，‘(’，‘i’，‘＞’， ‘j’,‘)’, ‘i’, ‘=’ , ‘i’, ‘-’ , ‘j’, ‘;’, ‘ else’, ‘j’, ‘=’, ‘j’,
f(q0,a)=q1 f(q1,a)=q1 f(q2,a)=q2 f(q0,b)=q2 f(q1,b)=q1 f(q2,b)=q1
教学进度
一个DFA可用一个状态转换矩阵表示,
计算机科学与工程系
行表示状态，列表示输入字符，矩阵元素表示 δ(qi,a)的值。 一个DFA也可用一个状态转换图表示。
所以,一个ＤＦＡ有三种表示方法： （1）转换函数； （2）状态转换矩阵； （3）状态转换图。
{,a,b,aa,ab,ba,bb,aaa,……}
注意：{a,b}*的任一子集，不能也认为是一个正规集。 aa*bb*cc*
R1=R2 正规式R1与R2等价
教学进度
正规式的代数性质：
恒等式 rs=sr 说明
计算机科学与工程系
“”是可交换的
r(st)=(rs)t “”是可结合的 r(st)=(rs)t 连接是可结合的 r(st)=rs rt (st)r=srtr r=r r=r r*=(r)* r**=r* 分配律 对连接，是单位元素 “*”和之间的关系 “*”是幂等的
教学进度
3.4.1 确定有穷自动机（DFA） 计算机科学与工程系 • 一个 DFA M是一个五元式 • M=（Q， ，δ ，S，F） 其中，Q是有限状态集，是输入字符的字母表， • δ是Q×Σ到Q的单值部分映射（即状态转换） δ(qi,a)=qj， • S∈Q是唯一初态， F 是终态集（可空） 例3.10设DFA M=({q0,q1,q2},{a,b},f,q0，{q2}）
rs
( r )*
L( r ) L(s)
( L( r ))*
“*”，连接，“”运算左结合，优先级由高到低。
教学进度
例3.1 a a|b ab
Hale Waihona Puke 字母表={a,b}正规集 {a} {a,b} {ab} {b} b
计算机科学与工程系
正规式
(a|b)* 如：{anbn|n≥1}
例 3.2 ={a,b,c} 例 3.3
方法和步骤： ① R=Φ ② R=ε ③ R=a
X a Y X R Y
计算机科学与工程系
X
Y ε
X
Y
④R为复合正规式？
教学进度
3.4.3 由正规表达式R构造NFA
方法和步骤：
A X R Y
计算机科学与工程系
r1r2 r1| r2 r1*
r1
B A C
r2
B
r1
B
① R=Φ ② R=ε ③ R=a
A
教学进度
3.4 正规式与有穷自动机
计算机科学与工程系
有穷自动机（ finite automata）（FA）：具有离散输 入和输出系统的一种抽象数学模型。能够准确地识 别正规集。 DFA NFA 正规式R与FA M是等价的： • (1)对任何正规式R,都存在一个FA M 使得L(M)=L(R); • (2)对任何FA M,都存在一个正规式R, 使得L(R)=L(M)