第4章 词法分析(lly)4.ppt_第1页
第4章 词法分析(lly)4.ppt_第2页
第4章 词法分析(lly)4.ppt_第3页
第4章 词法分析(lly)4.ppt_第4页
第4章 词法分析(lly)4.ppt_第5页
已阅读5页,还剩58页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

第四章词法分析 考查重点基本概念 正规式 正规集 有穷自动机 DFA与NFA 基本方法 由正规文法或自然语言描述求正规式由正规式构造有穷自动机 FA 确定化 NFA DFA DFA最小化正规文法与有穷自动机转换 4 1词法分析程序的设计 1 词法分析 lexicalanalysis 逐个读入源程序字符并按照构词规则切分成一系列单词 词法分析是编译过程中的一个阶段 在语法分析前进行 也可以和语法分析结合在一起作为一遍 由语法分析程序调用词法分析程序来获得当前单词供语法分析使用 单词是语言中具有独立意义的最小单位 包括保留字 标识符 运算符 标点符号和常量等 2 词法分析程序 主要任务 读源程序 产生单词符号其他任务 滤掉空格 跳过注释 换行符追踪换行标志 标志出错源程序 宏展开 单词符号一般可分为下列五种 1 基本字 关键字 if while 等2 标识符 如常量名 变量名 过程名等3 常数 量 25 3 1415 TRUE ABC 等4 运算符 如 等5 界符 逗号 分号 括号等 输出表示 单词类别 单词自身的值 例 A B 2 2 指向A的符号表的入口指针 4 2 指向B的符号表的入口指针 4 3 2 词法分析工作独立的原因 简化设计 词法分析比语法分析简单 如果与语法分析一起 会导致程序结构复杂 改进编译效率 编译的大部分时间花在扫描字符区分单词上 专门的词法分析可加快编译速度 增加编译系统的可移植性 4 2单词的描述工具 词法 单词符号的文法 用来描述高级语言中的 标识符 常数 运算符 分界符 关键字单词的描述工具 正规文法正规式一 正规文法与单词描述1 正规文法G VN VT P S P中每一产生式的形式都为 右线性 A aBA a左线性 A BaA a其中A VN B VN a VT注 正规文法中可能既右线性文法又左线性文法 2 程序设计语言几类单词的描述 如 程序设计语言 l表示a z中的任一英文字母 d表示0 9中的任一数字 l l l d l d d d if while else 无符号实数 其中s表示正或负号 无符号实数 d 余留无符号数 十进小数 e 指数部分 余留无符号数 d 余留无符号数 十进小数 e 指数部分 十进小数 d 余留十进小数 余留十进小数 e 指数部分 d 余留十进小数 指数部分 d 余留整指数 s 整指数 整指数 d 余留整指数 余留整指数 d 余留整指数 如25 55e 5和2 1思考 以上文法为几型文法 二 正规式和正规集 1 正规式和正规集递归定义 字母表 辅助表 和 都是 上的正规式 它们所表示的正规集分别为 和 任何a a是 上的一个正规式 它所表示的正规集为 a 假定e1和e2都是 上的正规式 它们所表示的正规集分别为L e1 和L e2 那么 e1 e1 e2 e1 e2 e1 也都是正规式 它们所表示的正规集分别为L e1 L e1 L e2 L e1 L e2 和 L e1 仅由有限次使用上述三步骤而定义的表达式才是 上的正规式 仅由这些正规式所表示的字集才是 上的正规集 相关说明 其中 读 或 也可用 代替 的 读 连接 读 闭包 任意有限次的自重复连接 连接符 一般可省略不写 并非正规式的运算符 规定算符的优先顺序为 和 都是左结合的 在不致混淆时 括号可省去 如 r s r r s rr s r 圆括号不可略去 例4 2令 a b 上的正规式和相应的正规集的例子有 正规式正规集 特点 a a a b a b ab ab a a a 任意个a的串 a b a b aa ab 所有由a和b组成的串 a b a b aa ab ba bb a b aa bb a b 上所有含有两个相继的a或两个相继的b组成的串 思考 表示 上所有以a开始 以b结尾串的正规式 程序设计语言中的单词都可由正规式来定义 例 l d r l l d 定义的正规集 l ll ld ldd 标识符 例4 3 d e 则 上的正规式dd dd e dd 表示的是无符号数的集合 其中d为0 9的数字 如 2 12 59 3 6e2 4 71e 1 参考P49 2 若两个正规式e1和e2所表示的正规集相同 则说e1和e2等价 写作e1 e2 例如 e1 a b e2 b a又如 e1 b a b e2 b b a 3 正规式的运算律 设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 是 连接 的恒等元素6 r r rr r rr 或 的抽取律 4 正规文法正规语言正规式正规集 由正规文法产生的语言称正规集 正规语言 正规集是一个有穷或者无穷的集合 可用正规式 RegularExpression Re 来描述 正规式也称正则表达式 正规表达式是说明单词的模式 pattern 的一种重要的表示法 记号 是定义正规集的数学工具 正规式描述的集合称作正规集 正规文法与正规式具有等价性 单词更适合用正规式 直观 来定义 对 上的正规式r 存在一个G VN VT P S 使得L G L r 反之亦然 三 正规文法与正规式的等价性 1 正规文法转换成正规式方法 由正规文法G的各个产生式写出对应的正规方程式 联立方程组 引进S作为识别符号 利用以下规则做变换文法产生式正规式规则1A xBB yA xy规则2A xA yA x yA Ax yA yx 规则3A xA yA x y变元是非终结符 求解正规方程式组 最后开始符号S的解 S VT 即为正规式 例 文法G S S aAS aA aAA dAA aA d转换过程如下 S aA a a A A aA dA a d a d A a d A a d a d S a a d a d S a a d S a a d 求 文法G S S Sc BcB Bb AbA Aa a得正规式 S Sc Bc Sc aa bb c aa bb cc 思考 什么条件下需要正规文法转换成正规式 2 将正规式转换成正规文法引进S作为识别符号 VT VN与P利用以下规则做变换产生 正规式rS r正规式xyA xBB yB新引进VN 正规式x yA xA y正规式x yA xA y直到每个产生式最多含有一个终结符为止 注意 正规式的字母表与正规文法的字母表 例 将r a a d 转换成相应的正规文法 S a a d S aAA a d A a d AA G S S aAA aAA dAA 思考 正规式对应的正规文法唯一 语言 G S S S a d a 思考 什么条件下需要正规式转换成正规文法 4 3有穷自动机 确定的有穷自动机 DeterministicFiniteAutomata 不确定的有穷自动机 NondeterministicFiniteAutomata NFA DFA的转换DFA的化简 自动机相关概念 1 如果语言是无穷的 找出语言的有穷表示 途经 生成方式 文法 语言中的每个句子可以用严格定义的规则来构造 识别方式 自动机 用一个过程 当输入的一任意串属于语言时 该过程经有限次计算后就会停止并回答 是 若不属于 要么能停止并回答 不是 要么永远继续下去 2 为了构造词法分析程序 要研究构词法 每种词类的结构模式以及识别它的数学模型 有穷自动机 有穷自动机作为一种识别装置 它能准确地识别正规集 即正规文法所定义的语言或正规式所表示的集合 引入有穷自动机这个理论 正是为词法分析程序的自动构造寻找特殊的方法和工具 有穷自动机分为两类 DFA和NFA 1 DFA定义 一个确定的有穷自动机 DFA M是一个五元组 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是一个终态集 终态也称可接受状态或结束状态 一 确定的有穷自动机 DFA例 M S U V Q a b f S Q f为 f S a Uf V a Uf S b Vf V b Qf U a Qf Q a Qf U b Vf Q b Q 2 的表示 状态转换图 设有m个状态和n个输入字符 图含有m个状态结点 每个结点最多只能有n条弧从结点射出并与别的结点相连结 每条弧上的标记是字母表 上的一个字符 图只有一个初态结点 用 双箭头 射入的节点表示初态 终态可由若干个 用双圆圈表示 状态转换矩阵 行表示状态 列表示输入字符 矩阵元素表示f s a 的值 2 1 DFA的状态图表示 f S a Uf V a Uf S b Vf V b Qf U a Qf Q a Qf U b Vf Q b Q 2 2 DFA的矩阵表示 f S a Uf V a Uf S b Vf V b Qf U a Qf Q a Qf U b Vf Q b Q 0 1 0 0 3 DFA 接受的字符串为了说明DFA如何作为一种识别机制 我们还要理解下面的定义3 1 上的符号串t在M上运行一个输入符号串t 我们将它表示成at1的形式 其中a t1 在DFAM上运行的定义为 f A at1 f f A a t1 其中A K扩充转换函数f 是K K上的映射 且 f A A 3 2 上的符号串t被M接受 对于 中的任何字符串t 若存在一条从初态结到某一终态结的道路 且这条路上所有弧的的标记符连接成的字符串等于t 则称t可为DFAM所接受 若M的初态结同时又是终态结 则空字可为M所接受 识别 若t f S t P 其中S为DFAM的开始状态 P Z Z为终态集 则称t为DFAM所接受 识别 4 例 证明t baab被如下的DFA所接受 DFAM S U V Q a b f S Q f定义为 f S a Uf V a Uf S b Vf V b Qf U a Qf Q a Qf U b Vf Q b Q 证明 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 QQ属于终态 得证 5 从状态转换图看 5 1 能被接受的字符串 存在一条从初态到某一终态的道路 且这条路上所有弧的标记符连成的字符串为t 则t被DFA接受 若初态同时也是终态 则空串可被接受 5 2 不能被接受的字符串 读完输入串 状态不停在终态 在读过程中出现不存在映射 使自动机无法继续动作 6 DFAM接受的语言DFAM接受的全体字符串为M接受的语言 记为 结论 上的一个字符串集V 是正规的 当且仅当存在一个 上的确定有穷自动机M使得V L M 二 不确定的有穷自动机NFA 1 定义 M K f S Z 其中K为状态的有穷非空集 为有穷输入字母表 f为K 到K的子集的映像 多值函数 S K是初始状态集 初始态可多个 Z K为终止状态集 例NFAM S P Z 0 1 f S P Z 其中f S 0 P f S 1 S Z f P 1 Z f Z 0 P f Z 1 P 2 1 状态图表示 思考 DFA与NFA的主要区别 2 2表格表示 较少采用 简化 NFAM S P Z 0 1 f S P Z 其中f S 0 P f S 1 S Z f P 1 Z f Z 0 P f Z 1 P 3 相关说明 上的符号串t在NFAM上运行 上符号串t被NFAM接受 识别 DFA是NFA的特例 4 有穷自动机M K f S Z 行为模拟程序 用一个过程 当输入的一任意串属于语言时 该过程经有限次计算后就会停止并回答 是 若不属于 要么能停止并回答 不是 K S c getchar whileceofdo K f K c c getchar ifKisinZthenreturn yes elsereturn no 以文件存串baab为例 三 NFA的确定化 1 定理 对任何一个NFAN 都存在一个DFAM 使L M L N 证明思想 子集构造法从NFA的矩阵表示中可以看出 表项通常是一状态集合 而在DFA的矩阵表示中 表项是一个状态 NFA到相应的DFA的构造的基本思路是 DFA的每一个状态对应NFA的一组状态 DFA使用它的状态去记录在NFA读入一个输入符号后可能达到的所有状态 注 与某一NFA等价的DFA不唯一 2 定义对状态集合I的几个有关运算 状态集合I的 闭包 closure I 定义为一状态集 是状态集I中的任何状态S经任意条 弧而能到达的状态的集合 约定状态集合I的任何状态都属于 closure I 状态集合I的a弧转换 move I a 定义为状态集合J 其中J是所有那些可从I的某一状态经过一条a弧而到达的状态的全体 例 I 1 closure I 1 2 move 1 a 5 4 move 1 2 a closure 5 3 4 closure move 1 2 a 3 NFA DFA NFAN K f K0 Kt DFAM S D S0 St M的状态集S由K的一些子集组成 用 S1S2 Sj 表示S的元素 其中S1 S2 Sj是K的状态 约定 状态S1 S2 Sj是按某种规则排列的 即对于子集 S1 S2 S2 S1 来说 S的状态是 S1S2 M和N的输入字母表是相同的 即是 转换函数是这样定义的 D S1 S2 Sj a R1 R2 Rt 其中 R1 R2 Rt closure move S1 S2 Sj a S0 closure K0 为M的开始状态 St Si Sk Se 其中 Si Sk Se S且 Si Sk Se Kt 4 构造NFAN的状态K的子集的算法 假定所构造的子集族为C 即C T0 T1 TI 其中T0 T1 TI为状态K的子集 开始 令 closure K0 为C中唯一成员 并且它是未被标记的 while C中存在尚未被标记的子集Ti do 标记T for每个输入字母ado Ti closure move T a ifTi不在C中then将Ti作为未标记的子集加在C中 5 例将下图的 NFAN转换成DFAM NFAN 思考 如何鉴别上图为NFA而非DFA closure 0 0 1 2 4 7 初态 终态 DFAM 思考 若NFAN无 运算有何不同 四 DFA的最小化 化简 1 有穷自动机最小状态DFA要求 没有多余状态 死状态 多余状态 从自动机的开始状态出发 任何输入串也不能到达的那个状态 或者从这个状态没有通路到达终态 没有两个状态是互相等价 不可区别 两个状态s和t等价 满足一致性 s与t同是终态或同是非终态蔓延性 对于任意a f s a p f t a q p和q必须等价 2 消除多余状态 思考 状态图中如何鉴别多余状态 状态0和4是可区别的 状态2和3是可区别的 why思考 有多余状态的吗 此图中四种状态都是可区别的吗 判定两个状态s和t不等价 只要找到一个w 使f s w F且f t w F 或者相反 DFAM 3 状态不等价 4 DFA最小化对于一个DFAM K f k0 kt 存在一个最小状态DFAM K f k0 kt 使L M L M 算法的核心 把一个DFA的状态分成一些不相交的子集 使得任何不同的两子集的状态都是可区别的 而同一子集中的任何两个状态都是等价的 结论 接受L的最小状态有穷自动机不计同构是唯一的 5 将下图中的DFAM最小化 4 4正规式和有穷自动机的等价性 对于 上的NFAM 可以构造一个 上的正规式R 使得L R L M 对于 上的一个正规式R 可以构造一个 上的NFAM 使得L M L R 1 自动机NFAM 正规式R在M的状态转换图上加进两个结点 x与y结点 从x结点用 弧连接到M的所有初态结点 从所有终态结点用 弧连接到y结点 形成一个与M等价的M M 只有一个初态x和一个终态y 利用消去规则消去M 中所有结点 直至剩下x和y x和y结点间弧上的标记则为所求正规式R 例 求该NFA所对应的正规式R 0 3 1 a b a a a b a b b b x 0 a b aa a b a b bb x 加进x与y结点 利用消去规则消去所有结点 0 a b aa a b bb a b x 0 a b x aa a b bb a b x a b aa bb a b aa bb a b R a b aa bb a b x和y结点间弧上的标记为正规式R 熟练可直接写 2 正规式R 自动机NFAM首先将正规式分解为一系列子表达式 然后使用以下规则为R构造自动机 简单 未含运算符 正规式对应NFA R R R a 设s t为正规式 对应的NFA为N s 与N t R s tR st R s 例 为R a b abb构造NFAN R a b abb R a b abb R a b abb 求解方法一 R a b abb R

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论