编 译 原 理 指导教师:杨建国 二零一零年三月.

Slides:



Advertisements
Similar presentations
实数与代数式是初中数学中重要的基础知识, 是中考的必考内容.这部分知识散布于多个章节之中, 知识点琐碎,但概念性强,在中考试卷中多以填空题、 选择题、化简、探索或求值的形式出现.在复习中, 一定要加强对各个概念、性质和公式的辨析和理 解.注重让学生在实际背景中理解基本的数量关系和 变化规律,注重使学生经历从实际问题中建立数学模.
Advertisements

电子商务专业人才培养方案 五年制高职. 一、招生对象、学制与办学层次  (一)招生对象:初中毕业生  (二)学制:五年  (三)办学层次:专科.
說 劍 《莊子‧雜篇》─ 第 一 組 賴泊錞 謝孟儒 張維真 羅苡芸
第一节 人口的数量变化.
德 国 鼓 励 生 育 的 宣 传 画.
温 度 定义: 表示物体冷热程度的物理量。 国际单位:开尔文(K) 单位 常用单位:摄氏度(℃) 原理: 根据液体热胀冷缩的性质制成的。
8 企业信息管理的定量分析 第八讲 企业信息管理的定量分析 8.1 企业信息化水平的测评 8.2 企业信息管理绩效的测评.
行政诉讼法.
第五章 心理应激与心身疾病 护理学院 王芳.
透過教學鷹架引導 三年級學生形成科學議題 高雄市復興國小 李素貞 102年3月20日
限时综合强化训练 限时综合强化训练.
2017/3/16 上 (興) 櫃 公 司 僑外資持股情形申報作業.
紧扣课程标准 关注社会热点 —苏教版教材新增内容复习建议 南京市南湖第一中学 马 峰.
第二部分 人文地理 第一单元 人口与城市 第5课 城市化过程和特点. 第二部分 人文地理 第一单元 人口与城市 第5课 城市化过程和特点.
104年振聲國中 志願選填個別序位 說明會 104年06月08日 輔導室關心您.
项目2-1 店铺的定位.
单元辅导(二)   词法分析与有穷自动机.
第2章 LR分 析 法 LR分析法是一种自下而上进行规范归约的语法分析方法,LR指“自左向右扫描和自下而上进行归约”。LR分析法比递归下降分析法、LL(1)分析法和算符优先分析法对文法的限制要少得多,对大多数用无二义的上下文无关文法描述的语言都可以用LR分析器予以识别,而且速度快,并能准确、及时地指出输入串的任何语法错误及出错位置。LR分析法的一个主要缺点是,若用手工构造分析器则工作量相当大,因此必须求助于自动产生LR分析器的产生器。
A.李时珍 B.司马迁 C.达尔文 D.袁隆平 D
了解太平天国运动的主要史实,认识农民起义在民主革命时期的作用与局限性。
第五章 电流和电路 制作人 魏海军
B F C D G E B E A 下图是沿20°经线所作的地形剖面示意图
4.4流体微团运动分析 借助于流体微团的概念来分析流体运动的组成 流体运动不同于刚体的一个显著区别:
出入口Y27 往塔城街口/中興醫院 出入口Y25 往延平北路一段/中興醫院 出入口Y23往延平北路一段 出入口Y21往延平北路一段
高考第二轮复习课件 东莞中学松山湖学校 丁文韬
电在我们日常生活、现代化社会中的应用: 电 是 什 么?.
第五章 透镜及其应用 物理·新课标(RJ).
台州市2011年科学学业考试试题的命制 台州初级中学 郭海平.
第二章 自然环境中的物质运动和能量交换.
江苏省2009年普通高校 招生录取办法 江苏省教育考试院
Part5语法分析 授课:胡静.
第七章 财务报告 主讲老师:王琼 上周知识回顾.
第 二 章 逻 辑 代 数 基 础.
编译原理与技术 词法分析(1) 2018/11/28 《编译原理与技术》讲义.
知识点7---矩阵初等变换的应用 1. 求矩阵的秩 2. 求矩阵的逆 3. 解矩阵方程.
建國國小英語教學線上課程 字母拼讀篇(一) 製作者:秦翠虹老師、林玉川老師.
如何寫工程計畫書 臺北市童軍會考驗委員會 高級考驗營 版.
编译原理 第三章 词法分析.
数字电子技术 Digital Electronics Technology
第四章 语法分析.
第三章 词法分析.
Part5语法分析 授课:胡静.
有穷自动机 本章介绍有关有穷自动机的基本概念和 理论以及正规文法、正规表达式与有穷 自动机之间的相互关系。
编译原理与技术 词法分析 (2) 2018/12/30 《编译原理与技术》讲义.
第五章 语法分析——自下而上分析 自上而下分析法(Top-down) 自下而上分析法(Bottom-up) 国防科技大学计算机系602教研室.
第三课时 匀变速直线运动的位移与时 间的关系
第三章 文法和语言 本章目的为语言的语法描述寻求工具,以便: 对源程序给出精确无二义的语法描述。(严谨、简洁、易读)
第2章 PL/0编译程序 2.1 PL/0语言和类pcode的描述 2.2 PL/0编译程序的结构 2.3 PL/0编译程序的语法语义分析
第二章 词法分析 (Lexical Analysis)
语法分析 本章内容 语法分析器:把词法分析生成的词法单元流翻译成语法分析树(parse tree)
比與比值 比例式 應用問題 自我評量.
第一节 相关概述 第二节 积差相关系数 第三节 其他相关系数
第1讲 C语言基础 要求: (1) C程序的组成 (2) C语言的标识符是如何定义的。 (3) C语言有哪些基本数据类型?各种基本数
第五章 相交线与平行线 三线八角.
電子白板百萬小學堂 本活動建議搭配電子白板 學生最多可分成2~6組(請按組別按鈕) 老師可以視時間多少,來進行活動 每一組要回答十個問題。
7.1 逻辑代数与门电路 逻辑代数初步 1. 数字电路中的数制和码制 (1) 数制及其转换
不動產估價.
铰链四杆机构 5 机械2组 郭广新.
会计实务(第七讲) ——固定资产 讲师:天天老师.
Ch3-聲波 § 3-1 聲波的傳遞 § 3-2 聲波的駐波 § 3-3 聲音的共鳴 § 3-4 都卜勒效應 § 3-4 音爆.
探索直线平行的条件 第一课时.
第二章 数据类型、运算符和表达式 §2.1 数据与数据类型 §2.2 常量、变量和标准函数 §2.3 基本运算符及其表达式 目 录 上一章
鏈球的力學分析 日本奧運鏈球冠軍(82米91) 室伏廣治因小腿肌肉受傷,退出杜哈亞運。 俄羅斯「鐵娘子」泰亞娜.李森科 九十五年八月八日在
知识点5---向量组的最大无关组 1. 最大线性无关组的定义 2. 向量组秩的定义及求法 向量组的秩和对应矩阵秩的关系 3.
第三章 植物的激素调节.
编译原理实践 7.PL/0的词法分析程序构造.
高雄市104學年度國民中學 童軍教育聯團露營 活動組簡報
编译原理 第一章 编译程序概述 第二章 PL/0编译程序的实现 第三章 文法和语言 第四章 词法分析 第五章 自顶向下语法分析方法
编译原理实践 --词法分析程序的自动生成器LEX
2.2.2双曲线的简单几何性质 海口市灵山中学 吴潇.
Presentation transcript:

编 译 原 理 指导教师:杨建国 二零一零年三月

第四章 词法分析 第一节 词法分析程序的设计 第二节 单词的描述工具 第三节 有穷自动机 第四节 正规式和有穷自动机的等价性 第四章 词法分析 第一节 词法分析程序的设计 第二节 单词的描述工具 第三节 有穷自动机 第四节 正规式和有穷自动机的等价性 第五节 正规文法和有穷自动机的等价性 第六节 词法分析程序的自动构造工具 第七节 典型例题及解答

知识结构

知识结构 ⑤ ③ 正规文法 有穷自动机(NFA DFA) ② 寻找特殊方法和工具 ④ 描述 正规式 识别 {正规集} ① ⑥ 词法分析 自动构造工具LEX

第四章 词法分析 4.1 词法分析程序的设计 源程序 词法分析程序 语法分析程序 Token get token …. 4.1 词法分析程序的设计 源程序 词法分析程序 语法分析程序 Token get token …. 主要任务:读源程序,产生单词符号 其他任务: 滤掉空格,跳过注释、换行符 追踪换行标志,复制出错源程序, 宏展开,……

一.词法分析程序与语法分析程序的接口方式 词法分析工作可以是独立的一遍,把字符流的源程序  变为单词序列,输出在一个中间文件上,这个文件作  为语法分析程序的输入而继续编译过程

更通常情况,常将词法分析程序设计成一个子程序,  每当语法分析程序需要一个单词时,则调用该子程序。  词法分析程序每得到一次调用,便从源程序文件中读  入一些字符,直到识别出一个单词,或说直到下一单  词的第一个字符为止

二.词法分析程序的输出 1.单词符号一般可分为下列五种: 基本字(关键字):begin、end、if、while、var 标识符:常量名、变量名、过程名 常数(量):25、3.1415、true、“ABC” 运算符:+、-、*、<= 界符:逗点、分号、括号

2.输出表示: (单词种别,单词自身的值) 单词种别:语法分析需要的信息 单词自身的值:编译其他阶段需要的信息 例如:const i=25,yes=1;

(标识符,指向该标识符所在符号表中位置的指针) const i=25,yes=1;对单词i和yes的表示为: (标识符,指向i的表项的指针) (标识符,指向yes的表项的指针) 单词的种别可以用整数编码表示,假如标识符编码为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, ‘; ’ )

三.将词法分析工作分离的考虑 1.使整个编译程序的结构更简洁、清晰和条理化: 2.编译程序的效率会改进: 3.增强编译程序的可移植性:

4.2 单词的描述工具 一.正规文法 什么是正规文法? 正规文法所描述的是VT上的正规集

程序设计语言中的几类单词可用下述规则描述: <标识符>  l|l<字母数字> <字母数字>  l|d|l<字母数字>|d<字母数字> <无符号整数>  d|d<无符号整数> <运算符>  +|-|*|/|=|<<等号|><等号>…… <等号>  = <界符>  ,|;|(|)| ……   其中l表示a~z中的任何一个英文字母,d表示0~9中 的任何一个数字

关键字也是一种单词,一般关键字都是由字母构成,它  的描述也极容易,实际上,关键字集合是标识符集合的  子集 最复杂的一类单词要属无符号实数,如25.55e+5和2.1,  它们可以由例4.1的规则描述

例4.1: <无符号数>  d<余留无符号数>|.<十进小数>e<指数部分> <余留无符号数>   d<余留无符号数>|.<十进小数>e<指数 部分>|  <十进小数>   d<余留十进小数> <余留十进小数>  e<指数部分>| d<余留十进小数> | <指数部分>   d<余留整指数> |s<整指数> <整指数>   d<余留整指数> <余留整指数>  d<余留整指数> |   其中,s表示正或负号(+,-)

二.正规式(正则表达式) 表示正规集的工具 描述单词符号的工具

正规式和它所表示的正规集的递归定义: 设字母表为,辅助字母表`={,,,,,,} (1)和都是上的正规式,它们所表示的正规集分别为   {}和{ } (2)任何a ,a是上的一个正规式,它所表示的正规集   为{a}

(3)假定e1和e2都是上的正规式,它们所表示的正规集分别   为L(e1)和L(e2),那么,(e1), e1 e2, e1e2, e1也都是正规   式,它们所表示的正规集分别为L(e1), L(e1)L(e2),   L(e1)L(e2)和(L(e1)) 仅由有限次使用上述三步骤而定义的表达式才是上的正规  式,仅由这些正规式所表示的字集才是上的正规集

其中的“”读为“或”(也有使用“+”代替 “” 的  );“ ”读为“连接”;“”读为“闭包”(即,任  意有限次的自重复连接)。在不致混淆时,括号可省去,  但规定算符的优先顺序为“”、“”、“”、“ ”、  “” 。连接符“ ”一般可省略不写。“”、“ ”和  “” 都是左结合的

例4.2 令={a,b}, 上的正规式和相应的正规集的例子有: 正规式 正规集 a {a} ab {a,b} ab {ab} (ab)(ab) {aa,ab,ba,bb} a  { ,a,a, ……任意个a的串} (ab) { ,a,b,aa,ab ……所有由a和b组成的串} (ab)(aabb)(ab)  {上所有含有两个相继的a或两个            相继的b组成的串}

例4.3 ={d,,e,+,-},则上的正规式  d(dd   )(e(+- )dd ) 其中d为0~9的数字  表示的是: 无符号数的集合

例题:词法分析器的输入是什么?(10分) 例题:令={a,b},则上所有以a开头,后跟0个或许多个的  ab的字的全体对应的正规式是什么?(5分) 例题:请写出表示标识符的正规式e1=(l|_)(l|d|_)*所对应的  正规集。(5分) 例题:有一台饮料自动售货机,接收1元或2元硬币,出售3  元钱一瓶的饮料。顾客每次向机器中投放等于或大于3元的  硬币,便可得到一瓶饮料(注意:多投不找钱)。写出对  应饮料自动售货机售货过程的正规式。画出与该正规式的  最小DFA。(10分)

答案:源程序(的字符流) 答案:a(ab)* 答案:{l,_,ll,ld,l_,_l,_ _,-d,……}或者{以1或_打头l,_,d组成     的字符串} 答案:设a=1,b=2,则a (b | a( a| b) ) | b (a |b) 或者:21|22|12|111|112

若两个正规式e1和e2所表示的正规集相同,则说e1和e2等价,写 例如: e1= (ab), e2 = ba 又如: e1= b(ab) , e2 =(ba)b  e1= (ab) , e2 =(ab)

设r,s,t为正规式,正规式服从的代数规律有: rs=sr “或”服从交换律 r(st)=(rs)t “或”的可结合律 (rs)t=r(st) “连接”的可结合律 r(st)=rsrt  (st)r=srtr 分配律 r=r  r=r 是“连接”的恒等元素(零一律) rr=r  r=rrr… “或”的抽取律

三.正规文法和正规式的等价性 1.将上的一个正规式r转换成文法G=(VN,VT,P,S):  令VT=∑,确定产生式和VN的元素用如下办法:

A→xB,A →y A →xA,B →y A →xA,A →y 选择一个非终结符S生成产生式S  r,并将S定为G的  识别符号。若x和y都是正规式 , BVN ,则: (R1) 对形如 A  xy的正规产生式,重写为: A  xB,B  y     (R2)对形如A  x*y的正规产生式,重写为:   A  xB,A  y,B  xB,B  y   (R3)对形如A  xy的正规产生式,重写为:   A  x,A  y 不断应用R做变换,直到每个产生式右端只含一个VN

例4.4 将 r=a(a|d)*转换成相应的正规文法 令S是文法的开始符号,形成S  a(a|d)*: R1  S  aA A  (a|d)* R2 S   aA    A  (a|d)B  A      B  (a|d)B  B   R3  S  aA A      A  aB A  dB   B  aB B  dB    B  

2.将正规文法转换成正规式:   基本上是上述过程的逆过程,最后只剩下一个开始符 号定义的正规式,其转换规则如表4.1所示:

例4.5 G[s]:  S  aA  S  a  A  aA  A  dA  A  a   A  d ①S  aA|a  A  aA|a|dA|d  (a|d)A|(a|d)        (a|d)*(a|d) ②s=a(a|d)*(a|d)|a=a((a|d)*(a|d)|ε)=a((a|d)*|ε) ③r=a(a|d)*

4.3 有穷自动机 一.确定的有穷自动机(DFA)(有限自动机) DFA:能准确地识别正规集 一个确定的DFA:M=(K,Σ,f,S,Z) 4.3 有穷自动机 一.确定的有穷自动机(DFA)(有限自动机) DFA:能准确地识别正规集 一个确定的DFA:M=(K,Σ,f,S,Z) K是一个有穷集,它的每个元素称为一个状态 Σ是一个有穷字母表,它的每个元素称为一个输入符  号,所以也称Σ为输入符号字母表

f是转换函数,是在K×Σ→K上的映射,即,如  f(ki,a)=kj,(ki∈K,kj∈K)就意味着,当前状  态为ki,输入符为a时,将转换为下一个状态kj,我们  把kj称作ki的一个后继状态 S∈K是唯一的一个初态 Z K是一个终态集,终态也称可接受状态或结束状态

例4.6:DFA M=({S,U,V,Q},{a,b},f,S,{Q}) f(S,a)=U   f(V,a)=U f(S,b)=V f(v,b)=Q f(U,a)=Q f(Q,a)=Q f(U,b)=V f(Q,b)=Q

一个DFA可以表示成一个状态图(状态转换图) 假定DFA M含有m个状态,n个输入符号,那么这个  状态图含有m个结点,每个结点最多有n个弧射出,整  个图含有唯一一个初态结点(  、-)和若干个终态结  点(双圈、+),若f(ki,a)=kj,则从状态结点ki到状态结点  kj画标记为a的弧

例4.6中的DFA的状态图表示如图4.1所示: 图4.1 状态图表示

一个DFA可以表示成一个矩阵表示,该矩阵的行表示状  态,列表示输入符号,矩阵元素表示相应状态和输入符  号将转换成的新状态,即k行a列为f(k,a)的值。用    标明初态;否则第一行即是初态,相应终态行在表的右  端标以1,非终态标以0

例4.5中的DFA的矩阵表示如图4.2所示: 图4.2 矩阵表示

若t ∑*,f(S,t)=P,其中S为 M的开始状态,P  Z,  Z为终态集,则称t为DFA M所接受(识别) 设Q∈K,函数f(Q,ε)=Q,一个输入符号串t(t1tx,t1  ∈∑,tx ∈∑*),在DFA M上运行的定义为:  f(Q,t1tx)=f(f(Q,t1),tx)

例如,证明t=baab被例4.6的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) 结论:上一个符号串集V是正规的,当且仅当存     在一个上的确定有穷自动机M,使得V=L(M) DFA的确定性表现在转换函数f:K×∑→K是一个单值  函数,也就是说,对任何状态k∈K和输入符号a ∈∑,  f(k,a)唯一地确定了下一个状态

提示:NFA与DFA的第三个区别是,前者可以空移:t(q, ε)={某些状态的集合} 一个NFA:M=(K,,f,S,Z) K是一个有穷集,它的每个元素称为一个状态 是一个有穷字母表,它的每个元素称为一个输入符号 f是一个从K * 到K的子集的映像,即:K* * →2 K  (多值映射) SK是一个非空初态集 ZK是一个终态集 提示:NFA与DFA的第三个区别是,前者可以空移:t(q, ε)={某些状态的集合}

例4.7:一个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} 它的状态图表示如图4.3所示:

一个NFA也可以用一个矩阵表示... ∑*上的符号串t在NFA N上运行... ∑*上的符号串t被NFA N识别(读出、接受)... DFA是NFA的特例 对每个NFA  N存在一个DFA M ,使得L(M)=L(N) 对于任何两个有穷自动机M和N,如果L(M)=L(N),则称  M与N是等价的

三.NFA转换为等价的DFA 定理:设L为一个由不确定的有穷自动机接受的集合,则  存在一个接受L的确定的有穷自动机 将NFA转换成接受同样语言的DFA,这种算法称为子集法

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

使用图4.4的NFA N的状态集合来理解上述两个运算: -closure(0)= {0,1,2,4,7}=I1 move(I1,a)= {3,8} move(I1,b) = {5} -closure({3,8})= {1,2,3,4,6,7,8}=I2 -closure({5})= {1,2,4,5,6,7}=I3

对于一个NFA N=(K,,f,K0,Kt)来说,若I是K  的一个子集,设I={s1,s2,…,sj},a是∑中的一个元素,则  move(I,a)=f(s1,a) ∪f(s2,a) ∪…∪f(sj,a)

假设NFA N=(K, ,f,K0,Kt)按如下办法构造一个DFA  M=(S, ,d,S0,St),使得L(M)=L(N): 1. M的状态集S由K的一些子集组成。用[S1 S2... Sj]表示S  的元素,其中S1, S2,,... Sj是K的状态。并且约定,状态S1,  S2,,... Sj是按某种规则排列的,即对于子集{S1, S2}={ S2,  S1,}来说,S的状态就是[S1 S2] 2.M和N的输入字母表是相同的,即是 3.转换函数是这样定义的:  D([S1 S2,... Sj],a)= [R1R2... Ri] 其中  {R1,R2,... , Ri} = -closure(move({S1, S2,,... Sj},a))

4.S0=-closure(K0)为M的开始状态 5.St={[Sj Sk... Se],其中[Sj Sk... Se]S且{Sj , Sk,,... Se} ∩KtØ}

构造NFA N的状态K的子集的算法,见图4.5: 假定所构造的子集族为C,即C= (T1, T2,,... Ti),其中T1,  T2,,... Ti为状态K的子集

例4.8 应用图4.5的算法对图4.4的NFA N构造子集 步骤如下: 1.首先计算-closure(0):令T0=-closure(0)={0,1,2,4,7},T0未  被标记,它现在是子集族C的唯一成员 2.标记T0:令T1=-closure(move(T0,a))={1,2,3,4,6,7,8},将T1  加入C中,T1未被标记。令T2=-closure(move(T0,b))   ={1,2,4,5,6,7},将T2加入C中,T2未被标记 3.标记T1:-closure(move(T1,a))={1,2,3,4,6,7,8},即T1,T1已  在C中。T3=-closure(move(T1,b))={1,2,4,5,6,7,9},将T3加  入C中,T3未被标记

4.标记T2:-closure(move(T2,a))={1,2,3,4,6,7,8},即T1,T1已  在C中。-closure(move(T2,b))={1,2,4,5,6,7},即T2,T2已在  C中 5.标记T3:-closure(move(T3,a))={1,2,3,4,6,7,8},即T1。-  closure(move(T3,b))={1,2,4,5,6,7,10},令其为T4,在入C中,  T4未被标记 6.标记T4:-closure(move(T4,a))={1,2,3,4,6,7,8},即T1。  -closure(move(T4,b))={1,2,4,5,6,7},即T2

 a b 01247 T0=01247 38 5 38 1234678 5 124567 T1=1234678 38 59 1245679 59 T2=124567 38 5 T3=1245679 38 5 10 5 10 12456710 T4=12456710 38 5

至此,算法终止共构造了5个子集: T0={0,1,2,4,7} T1={1,2,3,4,6,7,8} T2={1,2,4,5,6,7} T3={1,2,4,5,6,7,9} T4={1,2,4,5,6,7,10} 那么图4.4的NFA N构造的DFA M为: 1.S={ [T0], [T1], [T2], [T3], [T4] } 2. ∑={a,b}

3. D([T0],a)=[T1] D([T3],a)=[T1] D([T0],b)=[T2] D([T3],b)=[T4] D([T1],a)=[T1] D([T4],a)=[T1] D([T1],b)=[T3] D([T4],b)=[T2] D([T2],a)=[T1] D([T2],b)=[T2] 4.S0=[T0] 5.St=[T4] 为便于书写,将[T0]、 [T1]、 [T2]、 [T3]、 [T4]重新命名为  A、B、C、D、E或用0、1、2、3、4分别表示,若采用后  者,该DFA M的状态转换图如图4.6所示:

图4.6 DFA M

四. DFA的化简 最小状态DFA: 没有多余状态(死状态) 没有两个状态是互相等价(不可区别) 一个有穷自动机可以通过消除无用状态和合并等价状态  而转换成一个最小的与之等价的有穷自动机 有穷自动机的无用状态:从该自动机的开始状态出发,  任何输入串也不能到达的那个状态或者从这个状态没有  通路到达终态

例如图4.7的有穷自动机M: s4是不可到达,S6和S8不可到达 图4.7 消除多余状态

在有穷自动机中,两个状态s和t等价的条件是: 一致性条件——必须同是为可接受状态或不可接受状态 蔓延性条件——对于所有输入符号,必须转换到等价的  状态里 分割法:把一个DFA(不含多余状态)的状态分成一些  不相交的子集,使得任何不同的两子集的状态都是可区  别的,而同一子集中的任何两个状态都是等价的

DFA M最小化方法: 先分成终态集合和非终态集合 对每个集合中的符号分别用输出字母去查看它们到达状 态的集合是否在同一个集合中 如果不在同一个集合,将它们划分在不同的集合中 直到不能再划分为止

例4.9 将图4.8中的DFA M最小化 P0=({1,2,3,4},{5,6,7}) a P1=({1,2},{3,4},{5,6,7}) a P2=({1,2},{3},{4},{5,6,7}) a P3=({1,2},{3},{4},{5},{6,7}) b   令1代表{1,2}消去2,令6代表{6,7},消去7,得到图4.8(b) 的DFA M`,它是4.8(a)的DFA M的最小化

图4.8 DFA M和DFA M`

4.4 正规式和有穷自动机的等价性 对于∑上的一个NFA M,可以构造一个∑上的正规式 R,使得L(R)=L(M) 4.4 正规式和有穷自动机的等价性 对于∑上的一个NFA M,可以构造一个∑上的正规式  R,使得L(R)=L(M) 第一步,在M的状态转换图上加进两个结,一个为x结  点,一个为y结点。从x结点用弧连接到M的所有初始  结点,从M的所有终态结点用弧连接到y结点。形成  一个与M等价的M`, M`只有一个初态x和一个终态y 第二步,逐步消去M`中的所有结点,直至只剩下x和y  结点。在消结过程中,逐步用正规式来标记弧

其消结的规则如下: 最后x和y结点间的弧上的标记则为所求的正规式r

例4.10 以例4.7的NFA M为例,M的状态图在图4.3,求 正规式r,使L(r)=L(M)

对于∑上的一个正规式R,可以构造一个∑上的NFA  M,似的L(M)=L(R) 语法制导方法:按正规式的语法结构指引构造过程,首先  将正规式分解成一系列子表达式,然后使用下面规则为r  构造NFA,对r的各种语法结构的构造规则具体描述如下: 1. ①对于正规式Ø,所构造的NFA为:

例4.11 为r=(a|b)*abb构造NFA N,使得L(N)=L(r) 从左到右分解r,令r1=a,第1个a,则有    令r2=b,则有    令r3=r1|r2,则有 令r4=r3*,则有:

令r5=a, 令r6=b, 令r7=b, 令r8=r5r6, 令r9=r8r7,则有: 令r10=r4r9, 则最终得到的NFA N:

  其实,分解r的方式很多,用图4.10(a)(b)(c)(d)分别表明另一种分解方式和所构造的NFA。 图4.10 从正规式r构造NFA

思考:如果不用怎么分解 r=(a|b)*abb ? 1 2 3 a b 思考:如何把上面的NFA变成DFA? a b 01 02 03

1 2 3 a b

4.5 正规文法和有穷自动机的等价性 采用下面的规则可以从正规文法G直接构造一个有穷 自动机NFA M;使得L(M)=L(G): 4.5 正规文法和有穷自动机的等价性 采用下面的规则可以从正规文法G直接构造一个有穷  自动机NFA M;使得L(M)=L(G): M的字母表与G的终结符集相同 为G中的每个非终结符生成M的一个状态,G的开始符S  是开始状态S

增加一个新状态Z,作为NFA的终态 对G中的形如A  tB的规则(其中t为终结符或ℇ,A和B为  非终结符的产生式),构造M的一个转换函数f(A,t)=B 对G中形如A  t的产生式,构造M的一个转换函数  f(A,t)=Z

例4.12:与文法G[S]等价的NFA M如图4.11 G[S]: S  a A S  bB S  ε A  aB A  bA B  aS B  bA B   ε

有穷自动机转换成等价的正规文法: 对转换函数f(A,t)=B,可写一产生式:A  tB 对可接受状态Z,增加一产生式:Z  ε 有穷自动机的初态对应文法开始符 有穷自动机的字母表为文法的终结符集

例4.13:给出与图4.12的NFA等价的正规文法G G=({A,B,C,D},{a,b},P,A),其中P为: A  a B C   ε A  bD D  aB B  bC D  bD C  aA D   ε C  bD

4.6 词法分析程序的自动构造工具 以LEX为例介绍如何从正规式产生识别该正规式所描述的 单词的词法分析程序 4.6 词法分析程序的自动构造工具 以LEX为例介绍如何从正规式产生识别该正规式所描述的  单词的词法分析程序 LEX是一个广泛使用的工具,UNIX系统中使用lex命令调  用。它用于构造各种各样语言的词法分析程序 图 4.13LEX编译系统的作用

图 4.14 使用LEX生成词法分析器

LEX程序由三部分组成: 说明部分:变量说明、常量说明、正规定义 %% 转换规则:Pn {action  n} 辅助过程:容纳的是action所需要的辅助过程

图4.15给出一个识别PL/O单词的LEX程序片断: IDENT[a-zA-Z] [a-zA-Z0-9]*  NUMBER[0-9] [0-9]*  %(  #include 〈stdio.h〉  #include "code.h“  #include "symbol.h“  #include "y.tab.h“  extern int level;  int cc=0;  %)  %%  "" { cc++;}  "\t" { tablize(); } /*adjustcc to tabposition*/  "\n" { cc=0; line-copy(); } /*copy a line of input file*/  "<" { cc++; return LT;}  ">" { cc++; return GT;}  "=" { cc++; return EQ;}

 "#" { cc++; return NE;} "," { cc++; return colon; }  "." { cc++; return Period;}  "(" { cc++; return Lparen;}  ")" { cc++; return Rparen;} "<=" { cc++;cc++;return LE;} ">=" { cc++;cc++;return GE;} "∶=" { cc++; cc++;return ASGN;} ";" { cc++; return Semicolon;} {NUMBER} {       intn;       cc += yyleng;       sscanf(yytext,"%d", &n);       yylval.number=n;       return NUMBER;       }

图 4.15 LEX程序例子--识别PL/0单词的LEX程序   {IDENT} {       Symbol *s;       cc += yyleng;       if((s=lookup(yytext))==0) /*new identifier*/        s=install(yytext,VARIABLE,level,0); /* install symbol*/       if (s→type==C)        yylval.number=s-〉adr;       else /*it's a VARIABLE or PROC*/        yylval.sym=s;       return s-〉type;      }  %%  yywrap( ) {  }; 图 4.15 LEX程序例子--识别PL/0单词的LEX程序

4.7 典型例题及解答 1.构造正规式1(0|1)*101相应的DFA

2.将图4.18所示的DFA最小化

【本章小结】 词法分析程序是编译第一阶段的工作,它读入字符流的源程序,按照词法规则识别单词,交由语法分析程序接下去。   词法分析程序是编译第一阶段的工作,它读入字符流的源程序,按照词法规则识别单词,交由语法分析程序接下去。   本章讲述了词法分析程序设计原则,并介绍了正规式和有穷动机分别作为正规集描述和识别机制。在此基础上给出了词法分析程序自动构造工具如LEX的原理。   词法分析程序的设计技术可应用于其它领域,比如查询语言以及信息检索系统等,这种应用领域的程序设计特点是,通过字符串模式的匹配来引发动作,回想LEX,说明词法分析程序的语言,可以看成是一个模式动作语言。   词法分析程序的自动构造工具也广泛应用于许多方面,如用以生成一个程序,可识别印刷电路板中的缺陷,又如开关线路设计和文本编辑的自动生成等。

第4章 作业题 P72: 1.(2)(3) 2. 4. 6. 7. 9.