编译原理—第3章 词法分析及词法分析程序.pptx

编译原理 第3章词法分析及词法分析程序 计算机与软件学院陆克kzlu 1 3 1设计扫描器时应考虑的几个问题 2 词法分析 3型 语法分析 2型 单词的 Class Value 二元组表示标识符的长度限制和按 尽可能长 的识别策略超前搜索与回退 程序3 1输入缓冲注释与空白的删除 3 2 1由正规文法构造状态转换图 3 正规文法标识符 字母 数字 字母无符号数见课本49页 3 2 1由正规文法构造状态转换图 4 状态转换图有向图结点表示状态一个初态 箭头指示若干个终态 双圆圈指示边表示转移边上的字符表示转移时应满足的条件字符串的识别 0 1 3 2 a b c d d 3 2 1由正规文法构造状态转换图 5 右线性文法 状态转换图设G VN VT P S 是一右线性文法 令 VN K 1 则所要构造的状态转换图共有K 1个状态 2 VN中的每个符号分别表示K个状态 G的开始符S为初态状态 3 终止状态用F VN 标记 3 2 1由正规文法构造状态转换图 6 右线性文法 状态转换图例S aAA bXX c eY图3 3文法G 的状态转换图 S A X F a b c Y e 3 2 1由正规文法构造状态转换图 7 状态转换图 右线性文法利用状态转换图识别符号串对应推导过程例addb的识别S aA adA addA addb 3 2 1由正规文法构造状态转换图 8 左线性文法 状态转换图设G VN VT P S 是一左线性文法 令 VN K 1 则所要构造的状态转换图共有K 1个状态 2 VN中的每个符号分别表示K个状态 G的开始符S为终止状态 3 起始状态 用R VN 标记 3 2 1由正规文法构造状态转换图 9 状态转换图 左线性文法利用状态转换图识别符号串对应归约过程例addb的识别addb Addb Adb Ab S 0 1 3 2 a b c d d 3 2 2状态转化图的一种实现 状态矩阵法 10 状态矩阵状态矩阵Bij B Si aj Sk 当前状态 扫视字符 语义动作 后续状态 程序3 2 3 2 2状态转化图的一种实现 状态矩阵法 11 识别无符号数的状态矩阵 3 2 2状态转化图的一种实现 状态矩阵法 12 识别无符号数的状态矩阵语义动作中的返回值ICON FCON分别为整型数 浮点型数的值 一般说来 无符号数具有形式 dmdm 1 d0 d 1 d nE d d即dmdm 1 d0d 1 d n 10 d d n程序3 3 3 3 1确定的有限自动机 13 DFA DeterministicFiniteAutomata 一个DFAM定义为M K f S0 Z 其中1 K 状态i 2 字母表 即 输入字符i 3 f K K f为函数 表示某状态接受某个字母所到达的状态 如 f p a q p q K a 4 S0 K S0为初态5 Z K 且Z Z为终态集合 3 3 1确定的有限自动机 14 DFA例子右侧的状态图 在数学上称作DFA 其形式化定义为M K f S0 Z K 0 1 2 3 a b c d S0 0Z 2 3 f 3 3 1确定的有限自动机 15 函数f的推广定义f f K K 表示某状态接受一个字母串 而不是一个字母 所到达的状态 f 的定义依赖于f的定义 f 递归定义如下 1 f p p ifp K 即任意一状态p接受 串长为0 的输入 状态不变 2 f p aw f f p a w ifp K a w 3 3 1确定的有限自动机 16 函数f的推广定义f 例对于x adb x 那么从状态0可以迁移到的状态p可以这样求出 P f 0 adb f f 0 a db f 1 db f f 1 d b f 1 b f f 1 b f 3 3 因为从初态0接受输入字母串adb后 迁移到f 0 adb 3 Z 所以adb为DFA所识别 3 3 1确定的有限自动机 17 DFA所识别的语言令M为一DFA 我们定义L M x f S0 x Z x L M 称为DFAM所识别的语言 定理 对于任给的正规文法G 都存在一个DFAM 使L M L G 反之亦然 3 3 1确定的有限自动机 18 DFA关键特征状态迁移映射f是入射函数f x f y 蕴含x y 对任意状态结点p 其出弧上的字母各不相同且不为 从状态图角度 如出现下述情况的状态结点 则不是DFA 而是NFA Why 3 3 2非确定的有限自动机 19 NFA的形式定义一个NFAM定义为M K f S0 Z 除f外其余成员与DFA相同 f定义为f K K 其中 K 为集合K的幂集合 即有 K 2 K f表示某状态接受某个字母所到达的状态集合 如f p a q m p q m K a 3 3 2非确定的有限自动机 20 映射f的推广定义f f K K 表示某状态集合接受一个字母串 而不是一个字母 所到达的状态集合 f 递归定义如下 依赖于f f p p f p a f p1 p2 aw f f p1 a f p2 a w 其中 p p1 p2 K a w 属于什么 3 3 2非确定的有限自动机 21 NFA所识别的语言令N为一NFA 我们定义L N x f S0 x Z x L N 称为NFAN所识别的语言 有定理 L N L M L G 其中N为一NFA M为一DFA G为一正规文法 3 3 2非确定的有限自动机 22 NFA例子 写状态迁移表f 为什么是NFA 对每状态结点 按出弧上的字母写出状态迁移表 C行可以不填 f K K 3 3 2非确定的有限自动机 23 NFA例子 接受串 f K K 当前状态余留输入后续状态选择状态 SababbA CAorC 注意 NFA识别输入符号串时有一个试探过程 为了能走到终态 往往要走许多弯路 带回溯 这影响了NFA的效率 解决办法 3 3 2非确定的有限自动机 24 课堂练习对于下图所示NFA 求f S ababb 3 3 2非确定的有限自动机 25 课堂练习对于下图所示NFA 求f S ababb S A B C a b a a a b b a S a A C A B b A C a A B b A B C b S a A C A B b A B C a b b a a b 3 3 3NFA与DFA的等价性 26 定理3 1对于字母表 上的任一NFAN 必存在与M等价的DFAM 使L N L M 有了该定理 为提高NFA识别字符串的效率提供了tips 将NFA转换为DFA 即NFA的确定化 基本idea DFA的f K KNFA的f K K 将其改造为f K K 并证明f 是入射函数 且f 接收的串与f 接收的串相同 3 3 3NFA与DFA的等价性 27 例子 DFA状态矩阵 3 3 4带有 动作的FA 28 例子 abc S0 S0 S1 S2 S1 S1 S3 S2 S2 S3 S3 3 3 4带有 动作的FA 29 闭包 closure q 从状态q出发 仅经过若干条标记为 的矢线所能达到的状态所组成的集合 约定q也在此集合之中 closure S0 S0 S1 S2 S3 closure S1 closure S2 closure S3 3 3 4带有 动作的FA 30 f 的定义f S closure S f S wa closure f f S w a f q 通常不等于f q f S0 f S0 f S0 f S0 a f S0 ac 带有 动作的NFA所识别的语言L M w f S0 w Z 图3 11识别某语言单词的NFAM 3 3 5带有 动作的NFA的确定化 子集法 31 1 令K closure S0 给出M 的初态q0 2 对于K 中任一尚未标记的状态qi Si1 Si2 Sim 作2 1 标记qi2 2 对于每个a 置T f Si1 Si2 Sim a qj closure T 2 3 若qj不在K 中 则将qj作为一个未加标记的状态添加到K 中 且把状态转移添加到M 3 重复进行步骤2 直到K 中不再含有未标记的状态为止 对于由此构造的K 我们把那些至少含有一个Z中的元素的qi作为M 的终态 3 3 5带有 动作的NFA的确定化 子集法 32 例 a S0 S1 S2 S3 c S2 S3 c S1 S3 b b 3 3 5带有 动作的NFA的确定化 子集法 33 课堂练习 3 3 5带有 动作的NFA的确定化 子集法 34 课堂练习 DFA状态矩阵 S0 S2 S3 c S2 S3 c S1 b a S3 3 3 6DFA状态数的最小化 35 可区分状态状态A B被某一输入串w a1a2 an所区分 指1 从其中一个状态出发读入w 到达终态2 而从另一个状态出发进入非终态 a1 a2 an a1 a2 3 3 6DFA状态数的最小化 36 可区分状态的递归定义在一个DFA中 状态A与状态B可区分 1 A是终止状态 B是非终止状态或B是终止状态 A是非终止状态2 对于字母a 有f A a C f B a D2 1 C与D可区分2 2 C NULL且D NULL且D可达终态或C NULL且C可达终态且D NULL 3 3 6DFA状态数的最小化 37 例 S0 S1 S3 S2 b a b b a a a b a b 3 3 6DFA状态数的最小化 38 例 1 划分为终态和非终态 S0 S1 S2 S3 q0 S4 q1 S0 S1 S2与S3可区分 2 划分为 S0 S1 S2 q0 S3 q1 S4 q2 S0 S2与S1可区分 3 3 6DFA状态数的最小化 39 例 3 划分为 S0 S2 q0 S1 q1 S3 q2 S4 q3 S0与S2不再可区分 4 合并状态S0和S2 可得 q0 q1 q2 a b a a b a b b 3 3有限自动机 40 小结一个DFAM K f S0 Z 函数f K K表示某状态Ki接受某字母a 后 到达状态Kj的转换 一个NFAM K f S0 Z 函数f K K 表示某状态Ki接受某字母a 后 到达状态集合 K1 Kj 的转换 一个带 动作的NFAM K f S0 Z 函数f K K 表示某状态Ki接受某字母a 或空串 后 到达状态集合 K1 Kj 的转换 3 4正规表达式与正规集 41 试描述下述文法所产生的语言的特点G S VN S VT A Z a z 0 9 P S 其中P S S S S S A z 0 9 上述正规文法产生的语言的特点是由字母开头 后接0个或多个字母和 或 数字的符号串 即标识符的定义 3 4 1正规表达式及正规集的定义 42 如果使用型如字母 字母 数字 的式子来表示上述符号串构成的集合 那么这样的式子就称为正规表达式 相应的符号串集合则称为该表达式对应的正规集 正规式正规集 空集 a a a r s Lr Ls r s Lr Ls r Lr r r r Lr 3 4 1正规表达式及正规集的定义 43 算符优先级与正规式化简算符优先级从高到低依次为 如 r s r 可化简为r s r 又因为连接符 通常可省略不写 再化简为rs r 3 4 1正规表达式及正规集的定义 44 正规式与正规集的例子 a b 3 4 1正规表达式及正规集的定义 45 正规式与正规集的多对一关系给定一个正规式 它唯一确定一个正规集 反之不然 即一个正规集可由多个不同的正规式表示 我们称两个正规式等价 当且仅当它们所描述的正规集相同 例如a b与b a a b 与 b a 等等 3 4 1正规表达式及正规集的定义 46 正规式的基本等价公理A1 r s s rA2 r r rA3 r rA4 r s t r s t A5 rs t r st A6 r s t rs rtA7 s t r sr trA8 r r A9 r r rA10 r r rr 3 4 1正规表达式及正规集的定义 47 例写出一个正规式 它能匹配C语言的标识符 a b z A B Z 0 1 9 a b z A B Z 3 4 1正规表达式及正规集的定义 48 课程练习写出一个正规式 它能匹配C语言的整数 例如 0X89aB 0123 45等等 3 4 1正规表达式及正规集的定义 49 课程练习写出一个正规式 它能匹配C语言的整数 例如 0X89aB 0123 45等等 0 x X 0 1 9 a b f A B F 0 0 1 7 1 9 0 1 9 3 4 2由正规文法构造相应的正规式 50 右线性文法使用正规式描述下述右线性文法产生的语言S aS bS aS bS c 或S a b S c S abS c总结出规律 S S 对应的正规式是 3 4 2由正规文法构造相应的正规式 51 左线性文法使用正规式描述下述左线性文法产生的语言S Sa bS Sa Sb c 或S S a b c S Sab c总结出规律 S S 对应的正规式是 3 4 2由正规文法构造相应的正规式 52 如果将 用 替换 用 替换 那么可以将产生式转换为方程的形式 于是对上述两个规律 我们得到论断 论断3 1方程X X 对应S S 有解X 论断3 2方程X X 对应S S 有解X 3 4 2由正规文法构造相应的正规式 53 文法G S S aS bA bA aS 我们可以将所有产生式的运算符 用 替换 用 替换 再以我们习掼的线性方程组求解方法来求解S对应的正规式 3 4 2由正规文法构造相应的正规式 54 例S aS bA bA aSS aS baS bS a ba S bS a ba b a ba bS aAA bA aB bB aAA bA aaA bA b aa A bA b aa bS a b aa ba b aa bS bS aAA aA bBB aA bC bC bS aAB aA bS bB S bA aA bS bbA S bbS bS aS abbS a b S abb a b abb 3 4 2由正规文法构造相应的正规式 55 课堂练习构造以下文法的正规式 1 S aS bA cA bS 2 S aAA aA bB cB cS 3 4 2由正规文法构造相应的正规式 56 课堂练习构造以下文法的正规式 1 S aS bA cA bSS aS bbS cS a bb S c a bb c 2 S aAA aA bB cB cSA aA bcS cA aA bcaA cA a bca A cA a bca cS a a bca ca a bca c 3 4 3由正规式构造FA Thompson法 57 根据正规式所含运算符个数n递归给出n 0r r r a 3 4 3由正规式构造FA Thompson法 58 根据正规式所含运算符个数n递归给出n 1r r1 r2 r1 S01 r2 S02 S0 Sf 不再是初态 不再是终态 Sf1 Sf2 3 4 3由正规式构造FA Thompson法 59h 根据正规式所含运算符个数n递归给出n 1r r1 r2 r1 S01 Sf1 r2 S02 Sf2 3 4 3由正规式构造FA Thompson法 60 根据正规式所含运算符个数n递归给出n 1r r1 r1 S01 Sf1 S0 Sf 3 4 3由正规式构造FA Thompson法 61 例 1 a b aa b 2 0 1 1 0 1 1 0 0 3 4 3由正规式构造FA Thompson法 62 课堂练习构造以下正规式的FA 1 ab c 2 b aa ac aaa aac 3 4 3由正规式构造FA Thompson法 63 课堂练习构造以下正规式的FA 1 ab c 2 b aa ac aaa aac b c c a a a a 3 5词法分析程序的实现 64 构造词法分析程序的两种途径根据对语言中各类单词的某种描述或定义 用手工的方式构造词法分析程序词法分析程序的自动生成 3 5 1词法分析程序的编写 65 表3 4一个语言的单词符号及其分类码图3 22识别表3 4所列语言单词的DFA及相关的主义过程程序3 4根据图3 22编写的扫描器 3 5 3词法分析程序的自动生成 66 LEX源文件结构定义部分 识别规则部分 辅助函数部分 3 5 3词法分析程序的自动生成 67 LEX源程序的定义部分宏digit 0 9 alpha a zA Z alnum alpha digit id alpha alnum 其中 0 9 0 1 2 9 3 5 3词法分析程序的自动生成 68 LEX源程序的定义部分宏 include includeexternintflag defineZhao1 defineQian2intERROR 1charc digit 0 9 alpha a zA Z alnum alpha digit 3 5 3词法分析程序的自动生成 69 LEX源程序的识别规则部分R1A1R2A2 RmAm 3 5 3词法分析程序的自动生成 70 LEX源程序的识别规则部分 defineFCON1 defineICON2 D 0 9 D returnICON D D D D D eE D returnFCON 3 5 3词法分析程序的自动生成 71 辅助函数部分一个语言扫描器的LEX源程序 include include include defineBEGIN1 defineEND2 defineIF3