编译原理 第一章 编译程序概述 第二章 PL/0编译程序的实现 第三章 文法和语言 第四章 词法分析 第五章 自顶向下语法分析方法

Slides:



Advertisements
Similar presentations
1 基北區 103 學年度免試入學志願選填、 超額比序項目、共同就學區規劃說明 臺北市政府教育局 新北市政府教育局 基隆市政府教育處.
Advertisements

一、模型与计算公式 二、基本的组合分析公式 三、概率直接计算的例子 第 1.3 节 古典概率 四、抽签与顺序无关 五、二项分布与超几何分布 六、概率的基本性质.
A A A.
林園高中適性入學 高雄區免試入學 及 特色招生介紹 1. 國中學生 國中教育會考 1 ( 每年五月 ) 特色招生 術科考試 五專 免試入學 ( 每年六月 ) 特色招生 甄選入學 高中高職 免試入學 擇一報到 林園高中適性入學  入學管道流程 2.
思維方法 課程網頁: 第十一週: 自然演繹法Ⅱ:蘊含規則.
实数与代数式是初中数学中重要的基础知识, 是中考的必考内容.这部分知识散布于多个章节之中, 知识点琐碎,但概念性强,在中考试卷中多以填空题、 选择题、化简、探索或求值的形式出现.在复习中, 一定要加强对各个概念、性质和公式的辨析和理 解.注重让学生在实际背景中理解基本的数量关系和 变化规律,注重使学生经历从实际问题中建立数学模.
中原工学院 理学院 任课教师 曾灏宪曾灏宪 中原工学院 理学院 任课教师 曾灏宪曾灏宪 2 牛顿定律.
第二節-諧聲修辭 一、生活中的音近諧聲 ( 1 )忌諱語及吉祥話 人們因著趨吉避凶的普遍心理,對於有 災厄的諧音,或有吉祥祈福的近音字, 在詞語的使用上,呈現了特殊的習慣和 文化。
說 劍 《莊子‧雜篇》─ 第 一 組 賴泊錞 謝孟儒 張維真 羅苡芸
德 国 鼓 励 生 育 的 宣 传 画.
第六课 遗传与变异 第六课时 性别决定和伴性遗传.
性质形容词 软、硬、甜、苦、好、坏、远、近、斜、直、伟大、勇敢、优秀、聪明、大方
參與除權(息)是否能獲利— 以台灣125家上市公司為例
温 度 定义: 表示物体冷热程度的物理量。 国际单位:开尔文(K) 单位 常用单位:摄氏度(℃) 原理: 根据液体热胀冷缩的性质制成的。
8 企业信息管理的定量分析 第八讲 企业信息管理的定量分析 8.1 企业信息化水平的测评 8.2 企业信息管理绩效的测评.
第十二章 小组评估 本章重点问题: 评估的设计 测量工具的选择和资料的收集 与分析.
新材料作文.
第二章 不等式與線性規劃 ‧2-1 一元二次不等式 ‧2-2 絕對不等式 ‧2-3 二元一次不等式的圖形 ‧2-4 線性規劃 總目錄.
现代汉语语法精讲.
现代汉语语法 2017/3/11 语法知识辅导.
习题与试题 认真复习,重点是掌握基本概念。基本概念掌握了,相当一部分试题的解就有了
巧用叠词,妙趣横生.
2017/3/16 上 (興) 櫃 公 司 僑外資持股情形申報作業.
成功教育研究的新进展 上海市闸北八中新校、闸北八中校长 上海市田家炳中学董事长 刘京海 2003年3月14日.
形式语言与自动机 第四章 正则表达式 南京航空航天大学 计算机科学与技术学院 关东海
104年振聲國中 志願選填個別序位 說明會 104年06月08日 輔導室關心您.
民法总论 北京师范大学珠海分校 法律与行政学院 白 非.
单元辅导(二)   词法分析与有穷自动机.
编 译 原 理 指导教师:杨建国 二零一零年三月.
第2章 LR分 析 法 LR分析法是一种自下而上进行规范归约的语法分析方法,LR指“自左向右扫描和自下而上进行归约”。LR分析法比递归下降分析法、LL(1)分析法和算符优先分析法对文法的限制要少得多,对大多数用无二义的上下文无关文法描述的语言都可以用LR分析器予以识别,而且速度快,并能准确、及时地指出输入串的任何语法错误及出错位置。LR分析法的一个主要缺点是,若用手工构造分析器则工作量相当大,因此必须求助于自动产生LR分析器的产生器。
大陸產業分析 課程說明會.
遗传规律类推断题及实验设计题解题策略初探
4.4流体微团运动分析 借助于流体微团的概念来分析流体运动的组成 流体运动不同于刚体的一个显著区别:
出入口Y27 往塔城街口/中興醫院 出入口Y25 往延平北路一段/中興醫院 出入口Y23往延平北路一段 出入口Y21往延平北路一段
调查统计 父母 子女 都是双眼皮 一方单眼皮一方双眼皮 都是单眼皮 有单眼皮 有双眼皮 有单眼皮 有双眼皮 加标题(调查) 单眼皮.
高考第二轮复习课件 东莞中学松山湖学校 丁文韬
第一节 孟德尔的豌豆杂交实验.
Part5语法分析 授课:胡静.
编译原理复习.
上次课主要内容 正规式的简化形式与辅助定义; 记号的识别:有限自动机 NFA的定义:M =(S,∑,move,s0,F)
编译原理与技术 词法分析(1) 2018/11/28 《编译原理与技术》讲义.
建國國小英語教學線上課程 字母拼讀篇(一) 製作者:秦翠虹老師、林玉川老師.
如何寫工程計畫書 臺北市童軍會考驗委員會 高級考驗營 版.
编译原理 第三章 词法分析.
LR(1)分析方法.
第四章 语法分析.
第三章 词法分析.
Part5语法分析 授课:胡静.
有穷自动机 本章介绍有关有穷自动机的基本概念和 理论以及正规文法、正规表达式与有穷 自动机之间的相互关系。
编译原理与技术 词法分析 (2) 2018/12/30 《编译原理与技术》讲义.
第五章 语法分析——自下而上分析 自上而下分析法(Top-down) 自下而上分析法(Bottom-up) 国防科技大学计算机系602教研室.
第三课时 匀变速直线运动的位移与时 间的关系
第三章 文法和语言 本章目的为语言的语法描述寻求工具,以便: 对源程序给出精确无二义的语法描述。(严谨、简洁、易读)
语法分析 本章内容 语法分析器:把词法分析生成的词法单元流翻译成语法分析树(parse tree)
§1.5 分块矩阵.
第二章 词法分析3 非确定有限自动机NFA 非确定有限自动机(NFA)的定义 NFA的确定化:NFA到DFA的转换(子集法)
107上五年級〈社會科〉學校日簡報 教師個人檔案 ★民國77年8月開始任職本校 ★在本校擔任自然科任1年、導師8年、
考前总结 背景 必要性 作用 新旧版交替面临一些问题 从教学目标和要求说起 知识梳理 可能有助于提高考试成绩 或者让知识掌握得更好.
第3 语言翻译问题 [学习目标]:学习和掌握语言的语法的基本概念和基本要素,理解翻译的步骤;学习和掌握BNF文法。
不等式與線性規劃 ‧一元二次不等式 ‧絕對不等式 ‧二元一次不等式的圖形 ‧線性規劃.
第三章 内压薄壁容器的应力分析 教学重点: 薄膜理论及其应用 教学难点: 对容器的基本感性认识.
Ch3-聲波 § 3-1 聲波的傳遞 § 3-2 聲波的駐波 § 3-3 聲音的共鳴 § 3-4 都卜勒效應 § 3-4 音爆.
§3 布尔格与布尔代数 一、布尔代数 定义16.10:有补分配格称为布尔(Boole)格, 习惯上写成(B;≤)。
§12-5 同方向同频率两个简谐振动的合成 一. 同方向同频率的简谐振动的合成 1. 分振动 : 2. 合振动 : 解析法
1.8 完全平方公式(一) 锦州市实验学校 数学组(3).
乘法公式 麗山國中王綉瑗製.
制作:黎卓强 等差数列.
乘法公式 麗山國中王綉瑗製.
编译原理 第一章 编译程序概述 第二章 PL/0编译程序的实现 第三章 文法和语言 第四章 词法分析 第五章 自顶向下语法分析方法
2.2.2双曲线的简单几何性质 海口市灵山中学 吴潇.
Presentation transcript:

编译原理 第一章 编译程序概述 第二章 PL/0编译程序的实现 第三章 文法和语言 第四章 词法分析 第五章 自顶向下语法分析方法 第一章 编译程序概述 第二章 PL/0编译程序的实现 第三章 文法和语言 第四章 词法分析 第五章 自顶向下语法分析方法 第六章 自底向上优先分析方法 第七章 LR分析方法 第八章 语法制导翻译和中间代码生成 第九章 符号表 第一○章 代码优化 第一一章 代码生成

词法分析 词法分析是编译过程的第一个阶段。 主要任务:从左到右逐个字符地对源程序进行扫描,产生一个个单词序列,用以语法分析。 词法分析的基本思路: 将单词符号的语法用有效的工具描述; 基于该描述建立单词的识别机制; 设计和实现词法分析程序

单词的描述技术 单词的识别机制 词法分析程序的自动构造原理 正规文法 正规式 确定有穷自动机 不确定有穷自动机 正规式和有穷自动机的等价性 词法分析程序的自动构造工具

单词的描述工具 某种程序设计语言中的所有单词构成一种语言。该语言的语法都能用正规文法表示。正规文法是描述单词的一种工具。 1、正规文法(回顾) 文法G=(VN,VT,P,S),P中每一规则有A→aB或A→a ,A,BVN,aVT*,称G(S)是正规文法。 <标识符> →l|l <字母数字> <字母数字> → l|d|l<字母数字>| d <字母数字> <无符号整数> → d|d<无符号整数> l表示a-z中的任何英文字母,d表示0-9中的任何数字 由正规文法产生的语言称为正规集 除单词外,程序中包括的表达式及语句的语法需要用上下文无关文法表示。

2、正规式(正则表达式) 是表示正规集的工具,也是用以描述单词符号的方便工具。 正规式与正规集的定义: 设字母表为Σ,辅助字母表Σ'={,,|,·,*,(,)} ; 和都是Σ上的正规式,表示的正规集分别为{}和; 任何aΣ,a是Σ上的一个正规式,表示的正规集为{a};

假定e1和e2都是Σ上的正规式,它们所表示的正规集分别为L(e1)和L(e2),则(e1),e1|e2,e1·e2和e1 假定e1和e2都是Σ上的正规式,它们所表示的正规集分别为L(e1)和L(e2),则(e1),e1|e2,e1·e2和e1*也都是正规式,所表示的正规集分别为L(e1),L(e1)∪L(e2), L(e1)L(e2)和(L(e1))*。 仅由有限次使用上述三步骤而定义的表达式才是Σ上的正规式,仅由这些正规式所表示的集合才是Σ上的正规集。 例: ={a,b}, 上的正规式和相应的正规集为:

(a|b)*(aa|bb) (a|b)*   a b ----------- (a) 一个正规式可以表示若干个符号串, ------------------- (a|b)* a*|b* aba* (a|b)*(aa|bb) (a|b)*

(a|b)*(aa|bb) (a|b)* *上所有含有两个相继的a或两个相继的b组成的串  {}   a {a} b {b} ----------- (a) {a} 一个正规式可以表示若干个符号串, (b) {b} 其正规集就是这些符号串的集合 a|b {a,b} ab {ab} a* {,a,aa,aaa,aaaa,….} b* {,b,bb,bbb,bbbb,….} ------------------- (a|b)* a和b组成的所有串 a*|b* {,a,aa,aaa,aaaa,….,b,bb,bbb,bbbb,….} aba* 以ab开头后接若干个(包括0个)a组成的串 (a|b)*(aa|bb) (a|b)* *上所有含有两个相继的a或两个相继的b组成的串

设r,s,t为正规式,正规式服从代数规律有: 例:令={d, ,e,+,-},则上的正规式d*(.dd*| )(e(+|-|)dd*|)表示的是所有无符号数。 其中d为0~9中的数字。 比如:2,12.59,3.6e2,471.88e-1等都是正规式表示集合中的元素。 设r,s,t为正规式,正规式服从代数规律有: 1、r|s=s|r 交换律 2、r|(s|t)=(r|s)|t 结合律 3、(rs)t=r(st) 结合律

4. r(s|t) = rs|rt 分配律 (s|t)r = sr|tr 分配律 5. r=r 零一律 r=r 零一律 程序设计语言中的单词既能用正规文法表示,又能用正规式来表示. 正规式? 正规文法: <标识符> →l|l <字母数字> <字母数字> → l|d|l<字母数字>| d <字母数字> <无符号整数> → d|d<无符号整数> l表示a-z中的任何英文字母,d表示0-9中的任何数字

4. r(s|t) = rs|rt 分配律 (s|t)r = sr|tr 分配律 5. r=r 零一律 r=r 零一律 程序设计语言中的单词既能用正规文法表示,又能用正规式来表示. 正规式: 标识符:e1=字母(字母|数字)* 无符号整数:e2=dd* 正规文法: <标识符> →l|l <字母数字> <字母数字> → l|d|l<字母数字>| d <字母数字> <无符号整数> → d|d<无符号整数> l表示a-z中的任何英文字母,d表示0-9中的任何数字

3、正规文法和正规式的等价性 一个正规语言可以由正规文法定义,也可以用正规式定义。 对于任意一个正规文法,存在一个定义同一语言的正规式。对每一个正规式,存在一个生成同一语言的正规文法。 即正规式正规文法

 正规式正规文法: (把正规式转换为正规文法所要求的规则形式) 将Σ上的一个正规式r转换为一个正规文法G=(VN,VT,P,S)的规则: 令VT=Σ, 对正规式r,选择一个非终结符S生成S→r,S为G的开始符号。不断拆分r直到符合正规文法要求的规则形式:  若x,y都是正规式,对形如A→xy的产生式,写成A→xB,B→y。其中B VN  对形如A→x*y的产生式,重写为: A→x A A→y B为新的非终结符,B VN 对形如A→x|y的产生式,重写为: A→x 不断利用上述规则进行变换即可。

例:将R=a(a|d)*变换成正规文法。令S是文法开始符号。

例:将R=a(a|d)*变换成正规文法。令S是文法开始符号。 解: S→aA A→(a|d)* A→(a|d) A A→  S→ a(a|d)* 

S→aA A→aA A→dA A→  最后得到:

转换为正规式 例:文法G[S]:  正规文法正规式:将一个正规文法转换为正规式的规则: 转换规则:   正规文法正规式:将一个正规文法转换为正规式的规则: 转换规则:  A→xB,B→y 正规式为: A=xy  A→xA|y 正规式为: A=x*y A→x,A→y 正规式为: A=x|y 不断收缩产生式规则,直到剩下一个开始符号定义的正规式 S→ aA S→ a A→ aA A→ dA A→ a A→ d 转换为正规式 例:文法G[S]: S→ aA|a A→ (a|d)A A→ a|d ------ S→ a(A| ) A→ (a|d)+ S→ a (a|d)*

A→x,A→y 推出A=x|y S→ aA S→ a A→ aA A→ dA A→ a A→ d S=aA|a A=aA|dA 根据上述规则3 A→x,A→y 推出A=x|y S→ aA S→ a A→ aA A→ dA A→ a A→ d S=aA|a A=aA|dA A=(aA|dA)|(a|d)  A=(a|d)A|(a|d)  A=(a|d)*(a|d) A=a|d 将它化为正规文法 变成A→ (a|d)A|(a|d) 再根据上述 规则2转换 x=y= (a|d) 将A代入S=aA|a得到如下:

=a((a|d)+|)= a(a|d)* S=a( (a|d)*(a|d)) |a =a(a|d)+|a =a((a|d)+|)= a(a|d)* 二、有穷自动机 有穷自动机:是一种自动识别装置,能正确识别正规集; 是词法分析程序的工具和方法,可自动识别(且是正确识别)正规集。 确定的有穷自动机(DFA) 不确定的有穷自动机(NFA) 分为

含义:当前状态为Ki,输入字符a,转换为Kj状态 (一) 确定的有穷自动机DFA 自动识别装置 一个确定的有穷自动机M是一个五元组: M=(K,Σ,f,S,Z),其中: ① K是一个有穷集,每个元素表示一个状态; ②Σ是一个有穷字母表,每个元素是一个输入字符; ③ f是转换函数,是在K×Σ→K上的映象,如: f(Ki ,a)= Kj (Ki, KjK); ④ S是初态,SK; ⑤ ZK,是终态集。 含义:当前状态为Ki,输入字符a,转换为Kj状态

例:DFA的M=({S,U,V,Q},{a,b},f,S,{Q}) 其中f为: 1、用状态图表示: 方法如下: 初始态用 “”或“-”表示; 终态点用 “+” 或“” 表示; 若f(Ki ,a)= Kj ,则从状态点Ki 到Kj画弧,标记为a。 例:DFA的M=({S,U,V,Q},{a,b},f,S,{Q}) 其中f为: f(S,a)=U, f(S,b)=V, f(U,a)=Q f(U,b)=V, f(V,a)=U, f(V,b)=Q f(Q,a)=Q, f(Q,b)=Q 画出状态图

 元素表示相应状态行和输入字符下的新状态。 - + a b S U V Q 状态图如下: a,b a,b 2、用矩阵表示DFA : 方法: 行表示状态  列表示输入字符  元素表示相应状态行和输入字符下的新状态。

“” 标明初态,默认第一行是初态。 终态行在表右端标1,非终态标0 上例矩阵表示如下: a b S U V Q 字符 状态 1

例: 表示:f(S,a)=Z f(S,b)=Z f(Z,a)=Z f(Z,b)=Z a b S Z 写成正规式是: (a|b)(a|b)* - + Z b 表示:f(S,a)=Z f(S,b)=Z f(Z,a)=Z f(Z,b)=Z a b S Z 1 写成正规式是: (a|b)(a|b)*

3、接受(识别)的概念: 自动识别单词 对于Σ*中的任何字符串t,若存在一条初态到某一终态的路,且这条路上所有弧的标记符连接成的字符串等于t,则称t可为DFA M所接受。 若M的初态同时又是终态,则空字可为M所接受。 4、接受(识别)的理解: ① 设QK,函数f(Q,)=Q,则输入字符串是空串,并停留在原状态上。 ② 输入字符串t(t表示成Tt1形式,TΣ,t1 Σ*),在DFA M上运行的定义为:f(Q,Tt1)=f(f(Q,T),t1),其中QK。

例如:baab字符串被DFA所接受,DFA见上例。 f(S,baab)=f(f(S,b),aab)=f(V,aab) =f(f(V,a),ab)=(f(U,ab)=f(f(U,a),b) =f(Q,b)=Q (Q是终态) ③DFA M所能接受的字符串的全体记为L(M)—称为语言 (也即句子的集合) 5、DFA的确定性: 当f:k×Σ→K是一个单值函数,即对任何状态KR,输入符号a  K,f(k,a)唯一确定下一状态。

DFA的行为很容易用程序来模拟. DFA M=(K,Σ,f,S,Z)的行为的模拟程序 K:=S; c:=getchar; while c<>eof do {K:=f(K,c); }; if K is in Z then return (‘yes’) else return (‘no’)

自动识别单词的方法: (1)把单词的结构用正规式描述; (2)把正规式转换为一个NFA; (3)把NFA转换为相应的DFA; (4)基于DFA构造词法分析程序。

(二) 不确定的有穷自动机NFA 一个不确定的有穷自动机NFA M是一个五元组::M=(K,Σ,f,S,Z),其中: ②Σ是一个有穷字母表,每个元素是一个输入字符; ③ f是一个从K×Σ*到K上的子集的映象; f:k×Σ* →2k ④ SK,是一个非空初态集; ⑤ Z K,是一个终态集。 与DFA区别:多值函数 f( Ki,a)=Kj f( Ki,a)=Kt;允许输入字符为

例:一个NFA, M=({0,1,2,3,4},{a,b},f,{0},{2,4}) 其中:f(0,a)={0,3} f(2,b)={2} f(0,b)={0,1} f(3,a)={4} f(1,b)={2} f(4,a)={4} f(2,a)={2} f(4,b)={4} 状态图表示如下:

对于每个NFA M,存在一个DFA M’,使得L(M)=L(M’)。 3 4 1 2  a b a,b 说明:一个初态,二个终态。 DFA是NFA的特例。 对于每个NFA M,存在一个DFA M’,使得L(M)=L(M’)。 对于任何两个有穷自动机M和M’,如果L(M)=L(M’),则称M与M’是等价的。

NFA 转换为等价的DFA 从NFA的矩阵表示中可以看出,表项通常是一状态的集合,而在DFA的矩阵表示中,表项是一个状态,NFA到相应的DFA的构造的基本思路是: DFA的每一个状态对应NFA的一组状态. DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态.

定义对状态集合I的几个有关运算: 1. 状态集合I的ε-闭包,表示为ε-closure(I),定义为一状态集,是状态集I中的任何状态S经任意条ε弧而能到达的状态的集合。 状态集合I的任何状态S都属于ε-closure(I)。 2. 状态集合I的a弧转换,表示为move(I,a)定义为状态集合J,其中J是所有那些可从I中的某一状态经过一条a弧而到达的状态的全体。

状态集合I的有关运算的例子 I={1}, -closure(I)=?; I={5}, -closure(I)=?; move({1,2},a)=? -closure({5,3,4})=?; 1 2 5 3 4 6 8 7 a 

状态集合I的有关运算的例子 I={1}, -closure(I)={1,2}; I={5}, -closure(I)={5,6,2}; move({1,2},a)={5,3,4} -closure({5,3,4})={2,3,4,5,6,7,8}; 1 2 5 3 4 6 8 7 a 

NFA确定化算法: 假设NFA N=(K, ,f,K0,Kt)按如下办法构造一个DFA M=(S, ,d,S0,St),使得L(M)=L(N): 1. 构造DFA M的状态,选择NFA N的状态的一些子集构成: M的状态集S由K的一些子集组成。用[S1 S2... Sj]表示S的元素,其中S1, S2,,... Sj是K的状态。并且约定,状态S1, S2,,... Sj是按某种规则排列的,即对于子集{S1, S2}={ S2, S1,}来说,S的状态就是[S1 S2];

2 M和N的输入字母表是相同的,即是; 构造DFA M的转换函数,根据新构造的状态和字母表中的字符构造: 转换函数是这样定义的: d([S1 S2,... Sj],a)= [R1R2... Rt] 其中 {R1,R2,... , Rt} = -closure(move({S1, S2,,... Sj},a)) 4 S0=-closure(K0)为M的开始状态; 5 St={[Si Sk... Se],其中[Si Sk... Se]S且{Si , Sk,,... Se}Kt}

构造NFA N的状态K的子集的算法: 把多值转换函数所转换到的多值(多状态)的集合作为一个子集,映射到DFA的一个新的状态 假定所构造的子集族为C,即C= (T1, T2,,... TI),其中T1, T2,,... TI为状态K的子集。 1 开始,令-closure(K0)为C中唯一成员,并且它是未被标记的。

2 while (C中存在尚未被标记的子集T)do. {. 标记T;. for 每个输入字母a do. { 2 while (C中存在尚未被标记的子集T)do { 标记T; for 每个输入字母a do { U:= -closure(move(T,a)); if U不在C中 then 将U作为未标记的子集加在C中 } }

NFA的确定化 例子 4 f 3 5 6 2 1 i  a b

4 f 3 5 6 2 1 i  a b

等价的DFA a C D B A E F S b a a b F

三、确定有穷自动机DFA的化简 (消除多余状态+合并等价状态): 将多余状态消除而形成一个最小的等价的DFA 1、多余状态的概念: 从该自动机的开始状态出发,任何输入串也不能到达的那个状态。 下图中的哪些状态是多余的?

化简后的结果: 1 S0 S1 S5 S2 S7 S3 S4 S6 S8 左右等价

化简后的结果: 1 S0 S1 S5 S2 S7 S3 S4 S6 S8 1 S0 S1 S5 S2 S7 S3 左右等价

合并等价状态:发现等价状态,并将这些等价状态合并成一个状态。 2、等价的条件(状态S和T)    一致性条件 —— 状态S和T必须同时为可接受状态或不可接受状态(终态还是非终态)。  蔓延性条件 —— 对于所有输入符号,状态S和状态T必须转换到等价的状态里。 3、合并等价状态的方法(分割法) 方法:将DFA的状态分割成一些互不相交的子集。不同子集的状态是可区别的,同一子集中的任何两个状态是等价的。

1 6 4 3 2 5 7  a b 例子:将图中的DFA M最小化。

 将M分成两个子集: 一个终态(可接受态)组成,一个非终态组成。 P0=({1,2,3,4},{5,6,7})  第1个子集{1,2,3,4}中: {1,2}中的状态和{3,4}中的任何状态在读入a后到达了不等价的状态,两个状态都是不可区别的。 P1=({1,2},{3,4},{5,6,7})  P1中的{3,4}对应输入符号a或b,将再分割: P2=({1,2},{3},{4},{5,6,7})  P2中的{5,6,7}可有输入符号a或b,分割为:

P3=({1,2},{3},{4},{5},{6,7}) {1,2},{6,7}不能再分割,也即等价的。 a a 4 6 b 1 6 4 3  a b a a b a  1 7 b b 5 a b a b 3 2 b

DFA的最小化算法 DFA M =(K,∑,f, k0,, kt),最小状态DFA M’ 1.构造状态的一初始划分: 终态kt 和非终态K- kt两组(group) 2.对∏施用过程PP 构造新划分∏new 3. 如∏new =∏,则令 ∏final=∏ 并继续步骤4,否则∏:=∏new重复2 . 4.为∏final中的每一组选一代表,这些代表构成M’的状态。若k是一代表且f(k,a)=t,令r是t组的代表,则M’中有一转换f’(k,a)=r

M’ 的开始状态是含有S0的那组的代表 M’ 的终态是含有F的那组的代表

过程PP : Construction of ∏new For each group G of ∏ do begin 1.Partiton G into subgroups such that two states s and t of G are in the same subgroups if and only if for all input symbols a, states s and t have transitions on a to states in the same group of ∏;/*at worst, a state will be in a subgroup by itself*/ 2.replace G in ∏new by the set of all subgroups formed end

自动识别单词的方法: (1)把单词的结构用正规式描述; (2)把正规式转换为一个NFA; (3)把NFA转换为相应的DFA; (4)基于DFA构造词法分析程序。

四、正规式和有穷自动机的等价性 正规式和有穷自动机的等价性由以下两点说明 : ※对于Σ上的NFA M,可以构造一个Σ上的正规式R,使得L(R)=L(M)。 ※对于Σ上的每个正规式R,可以构造一个Σ上的NFA M,使得L(M)=L(R)。 1、在NFA M上构造正规式R。即从L(M)  L(R) 方法:在每一条弧上用一个正规式作标记。 规则如下:

   1 2 3 R1 R2 R1R2 a. 1 3 1 2 R1 R2 2 1 R1|R2 b. R1+R2 或 1 2 R2 c. 给定有穷自动机,判断它识别的语言

例1: L(M)如下图: 求正规式R,使L(R)=L(M). 解: - + a b a,b

例1: L(M)如下图: 求正规式R,使L(R)=L(M). 解: - + a b a,b a b a,b   x y a|b  因此: L(R)= (a+b)(a+b)* x y

例2:M状态图如下: 求正规式R,是L(R)=L(M). 3 4 1 2  a b a,b

解:加x,y结点。 a,b  a a x a,b 3 4 b  1 b y 2  a,b

a,b  aa x a,b 4 bb  2  y a,b a,b  aa(a+b)* x y bb(a+b)*

所以 L(R) =(a+b)*(aa+bb)(a+b)* x y 所以 L(R) =(a+b)*(aa+bb)(a+b)*

2、L(R) NFA,从正规式R构造NFA 规则如下:  正规式,构造NFA为: 或:  对应正规式,构造NFA为:   对应正规式a,构造NFA为:   s,t是正规式,相应NFA为N(s),N(t),则正规式R=s|t,构造NFA(R) 为: x y  x y  x y a x y N(s) N(t)  

 s,t是正规式,相应NFA为N(s),N(t),则正规式R=st,构造NFA(R) 为:  x y  s,t是正规式,相应NFA为N(s),N(t),则正规式R=s*,构造NFA(R) 为:     x y N(s)

例1:L(R) =(a+b)*abb,构造NFA使L(N)=L(R) 解:

例1:L(R) =(a+b)*abb,构造NFA使L(N)=L(R) 解: x y  (a+b)* abb x  y abb  a,b  x  y abb  a b x  y  a b

例4: L(R) =(a+b)*(aa+bb)(a+b)* 构造L(N)使与L(R) 等价。 y  a 例4: L(R) =(a+b)*(aa+bb)(a+b)* 构造L(N)使与L(R) 等价。

(a+b)*(aa+bb)(a+b)*  x y x y  (a+b)* aa+bb x y  aa bb a,b 

x y  a b  - + a b

词法分析程序的自动构造 自动识别单词的方法: (1)把单词的结构用正规式描述; (2)把正规式转换为一个NFA;  自动识别单词的方法: (1)把单词的结构用正规式描述; (2)把正规式转换为一个NFA; (3)把NFA转换为相应的DFA; (4)基于DFA构造词法分析程序。

本章小结 词法分析程序是编译第一阶段的工作,它读入字符流的源程序,按照词法规则识别单词,交由语法分析程序接下去。 本章讲述了词法分析程序设计原则,并介绍了分别作为正规集的描述机制和识别机制的正规式和有穷动机。在此基础上给出了词法分析程序自动构造工具的原理。

课后作业 1。叙述正规式(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*描述的语言。 2。写出语言“由偶数个0和奇数个1构成的所有0和1的串”的正规式。 3。构造一个DFA,它接受∑={0,1}上0和1的个数都是偶数的字符串。 4。处于/* 和 */之间的串构成注解,注解中间没有*/。画出接受这种注解的DFA的状态转换图。