第二讲词法分析-1.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * 有穷自动机和正则表达式之间的关系 例如 标识符的正则表达式是 让 letter=a|b|…|z digit=0|1|…|9 identifier=letter(letter|digit)* 识别这样的标识符过程可以被描述为有穷自动机 状态: 表示其中记录已被发现的模式的数量在识别过程中的位置 转换: 记录一个状态向另一个状态的转换 初始状态: 识别过程的开始 接受状态: 代表识别过程结束的状态 1 2 letter letter digit 将真实字符串识别为标识符的过程可通过列出在识别过程中所用到的状态和转换的序列来表示 例如: 识别 “xtemp”为标识符的过程: 1 2 letter letter digit 1 2 2 2 2 2 x t e m p 2.3.1 DFA的定义 2.3.2 NFA的定义 2.3.3 有穷自动机的代码实现 2.3.1 DFA的定义 DFA的定义 一个DFA M=（S，Σ，T，S0，A） S 是状态集合 Σ是字母表 T是转换函数T: S X ∑-S, T(Si,a)=Sj 表示当前状态时Si ,当前输入字符是a时，将转换到下一个状态 Sj S0∈S 是初始状态 A ? S 是接受状态的集合 例如 DFA M=({S，U，V，Q},{a，b},f,S,{Q}) f 定义为： f（S，a）=U f（S，b）=V f（V，a）=U f（V，b）=Q f（U，a）=Q f（U，b）=V f（Q，a）=Q f（Q，b）=Q 确定性 给定当前的状态和当前的输入符号,能唯一地确定下一个状态 DFA的转换图 每个状态是图的一个结点 单箭头线表示初态 接受状态由双线结点表示 若T(Si,a)=Sj, 从结点Si 到结点Sj 画标记为a的弧 例如: DFA M=（{S，U，V，Q},{a，b},f,S,{Q}） f（S,a）=U f（S,b）=V f（V,a）=U f（V,b）=Q f（U,a）=Q f（U,b）=V f（Q,a）=Q f（Q,b）=Q 状态转换图为: b S U V Q a a a b a,b b 转换图的几点说明 定义的扩展: 转换也可以表示为字符集合的名字 1 2 letter letter digit 惯例 出错转换在图中没有画出来 带有出错转换的标识符的有穷自动机 error other any 1 2 letter letter digit other DFA的状态转换表 状态和输入字符 转换函数T的值 第一个状态为初始状态 用一列表示是否为接受状态 … … 是/否 T(S,C) S 接受状态 C 字符 状态 例如: DFA M=（{S，U，V，Q},{a，b},f,S,{Q}） f（S,a）=U f（S,b）=V f（V,a）=U f（V,b）=Q f（U,a）=Q f（U,b）=V f（Q,a）=Q f（Q,b）=Q DFA的状态转换表为 : 是 否 否 否 接受状态 Q Q Q Q U V V Q U V U S b a 字符 状态 L(M): 能被 DFA M识别的语言 DFA识别(接受)的字符串 对于Σ*中的任何字符串t，若存在一条从初态结到某一终态结的通路，且该通路上所有弧的标记符连接成的字符串等于t，则称t可以为 DFA M所识别 若DFA M的初态结同时又是终态结，则ε可为M所识别。 串“baab” 可由 DFA M识别（接受） b S U V Q a a a b a，b b DFA的例子 1 ∑={a,b,c} ,至少有1个b的符号串集合可由下面的DFA识别（或接受） 1 2 b a,c a,c 2 最多只有一个b的符号串集合可由下面的DFA识别（或接受） 2 b a,c a,c 1 * * * * * * * * * * * * * * * * * 第二章 词法分析 学习目标: 掌握 编写正则表达式, 正则表达式到DFA的转换，词法分析程序的构建 理解 正则表达式，NFA，DFA的概念 2.1 扫描处理 2.2 正则表达式 2.3 有穷自动机 2.4 从正则表达式到DFA 2.1 扫描处理 回顾 扫描程序的任务 从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个有意义的单元，称为记号或单词(Token) 记号（单词） 单词有若源程序中逻辑上紧密相连的一组字符，这些字符具有集体含义。 若干种类型，保留字、标识符、特殊符号 1 单词的种别 种别 保留字 语言中具有特殊意义的符号串 ，如：“if” and “then” 特殊符号 包括+, -, :