编译原理chapter2.ppt

第二章词法分析LexicalAnalysis 计算机科学与技术学院刘慧 对于编译器而言 其前端 frontend 执行分析 后端 backend 执行合成 词法分析 以字符流作为输入 生成一系列的名字 关键字和标点符号 punctuationmark 同时去掉单词之间的空白符 whitespace 和注释 comment 词法分析作为一个独立子程序的原因 描述单词的结构比描述源程序的其它语法结构要简单得多 这样就能采用比语法分析更为有效的方法或工具 如状态转换图 有限自动机 来识别单词和描述扫描器的结构 词法分析器的结构 1 输入缓冲区 为了提高读盘效率和便于扫描器进行工作 让操作系统直接将磁盘上的源程序字符串分批送入此缓冲区中 供扫描器进行处理 2 预处理子程序 当词法分析器调用它时 它就处理一串确定长度的输入字符 3 扫描缓冲区 存放经预处理子程序处理的字符 供扫描器使用 2 1词法单词符号 单词符号是由字符组成的序列 可是看成是程序设计语言的文法单位 可归类为有限的几组单词类型 对程序语言来说 关键字 标识符 各种常数 各种运算符及分隔符都是单词符号 举例 Floatmatch0 char s findazero if strncmp s 0 0 3 Return0 2 1词法单词符号 问题 如何描述程序设计语言的词法规则 用什么语言来编写词法分析器 答案 任何合理的程序设计语言都可以用来实现特定的词法分析器 我们学习使用正则表达式的形式语言来指明词法单词 用确定的有限自动机 DeterministicFiniteAutomata DFA 实现词法分析器 并用数学的方法将两者联系起来 2 2正则表达式 基本概念 语言 language 字符串 string 组成的集合字符串 符号 symbol 的有限序列符号 来自有限字母表 alphabet 以Pascal语言 素数语言 C语言保留字等这样的方式表示语言时 我们并没有给其中的字符串赋于任何含义 而只是要确定每个字符串是否属于其语言 例 所有能被5整除的数字字符串 为了用有限的描述表示这类语言 可能是infinite的 我们使用regularexpressions表示法 每个regularexpression代表一个字符串集合 符号 对于字母表 中的每个符号a 正则表达式a表示仅包含字符串a的语言可选 alternation 对于给定的两个正则表达式M和N 则M N表示一个字符串属于语言M或语言N 举例 a b0 1 2 3 4 5 6 7 8 9 联结 concatenation 对于给定的两个正则表达式M和N M N表示一个字符串是任意两个字符串 和 的联结 且 属于语言M 属于语言N epsilon 表示仅含一个空字符串的语言重复 repetition 对于给定的正则表达式M 它的克林 Kleene 闭包M 表示一个字符串是由M中的字符串经零至多次联结运算的结果 举例 a b a 0 1 2 3 4 5 6 7 8 9 举例 a b a 0 1 2 3 4 5 6 7 8 9 0 5 书写正则式时 一般会省略 omit 联结操作符 或符号 运算优先级 Kleenclosure高于concatenation concatenation高于alternation 2 2正则表达式 Regularexpressions举例 例1 令 a b 下面是 上的正则式和语言ba 上所有以b为首的后跟任意个a的字a a b 上所有以a为首的字 a b aa bb a b 上所有含有两个相继的a或两个相继的b的字例2 令 A B 0 1 A B A B 0 1 上 标识符 的全体 0 1 0 1 上 数 的全体 Someabbreviations 缩写形式 abcd means a b c d b g means bcdefg b gM Qkr means bcdefgMNOPQkr M means M M means M M 正闭包Figure2 1概括了所有这些操作符 period 除换行符之外的任意单个字符 a quotation 引号中的字符串表示字符串本身Figure2 2表示某些单词记号的正则表达式 词法规范 lexicalspecification 应当是完整的 complete 即应当总是能与输入中的某些初始子串 substring 相匹配 二义性 ambiguous 问题 消除二义性规则最长匹配 取可与正则表达式匹配的那个最长输入子串为下一个单词 规则优先 对于一个特定的最长初始子串 第一个与之匹配的正则表达式决定其单词类型 举例 IF 5 EQ M I 10IF 5 55 2 3有限自动机 FiniteAutomata 有限自动机 包括一个有限状态 state 集合和一些从一个状态通向另一个状态的边 edge 每条边上标有一个记号 symbol 其中一个状态是初态 startstate 某些状态是终态 finalstate 状态用圆圈 circle 表示 双圆圈 doublecircle 表示终态 圆圈中标有状态的名字或编号 Figure2 3表示部分构词规则的有限自动机 每个状态有一个编号 初态都是编号为1的状态 标有多个字符 severalcharacters 的边是多条平行边 manyparalleledges 的缩写形式 FiniteAutomata Informally finiteautomatonconsistof AfinitesetofstatesTransitionsbetweenstatesAninitialstate startstate Asetoffinalstates acceptingstate Twokindsoffiniteautomata Deterministicfiniteautomata DFA thetransitionfromeachstateisuniquelydeterminedbythecurrentinputcharacterNon deterministicfiniteautomata NFA theremaybemultiplepossiblechoicesorsometransitionsdonotdependontheinputcharacter 确定的有限自动机 DFA 在DFA中 不会出现同一状态出发的两条边标有相同的符号 DFA接受 accept 一个字符串 从初始状态出发 对于输入字符串中的每个字符 自动机都将沿着一条确定的边到达另一状态 这条边必须是标有输入字符的边 对n个字符的字符串进行了n次状态转换 transition 后 如果自动机到达了一个终态 则接受该字符串 a b aa bb a b 确定的有限自动机 DFA DFA拒绝 reject 一个字符串 若最终达到的不是终态 或者找不到与输入的字符相匹配的边 那么自动机将拒绝接受这个字符串 由一个自动机识别的语言是该自动机接受的字符串集合 a b aa bb a b Figure2 4为Figure2 3中六个独立的自动机合并后得到的一个可作为词法分析器的自动机 注意 DFA的映射关系可以由一个矩阵表示 矩阵的行表示状态 列表示输入字符 这个矩阵称为转换矩阵 transitionmatrix 存储形式为二维数组 two dimensionalarray a b b a b 2 4非确定的有限自动机 NFA NFA是一种需要对从一个状态出发的多条标有相同符号的边进行选择的自动机 也可能存在标有 的边 它可以在不接收输入字符的情况下进行状态转换 此NFA识别的语言是长度为2的倍数或3的倍数的所有由字母a组成的字符串的集合 设有限自动机M的状态转换图如下 显然M是一个NFA 猜测 M识别符号串ababb的过程为 1SababbA CA 2AbabbA BB 3BabbAA 4AbbA BB 5BbC接受 2 4 1RE NFA 转换算法 conversionalgorithm 将正则表达式转换为带有一个tail startedge 和一个head endingstate 的NFA 正则表达式a 正则表达式ab 归纳 一个正则表达式或者是原语primitive 单个符号或 或者是多个较小的表达式组合而成 类似地 NFA或者是基本元素 或者是多个较小NFA的组合 RulesfortranslatingREtoNFA M N M N M 例 将正规式a b aa b转换成等价的有限自动机 例 将四个RE转换为NFA if a z a z0 9 0 9 a z n n t NUM 2 4 2NFA DFA NFA具有 猜测 guessing 性质 举例 用下图识别字符串in 从状态1开始 有多种选择 替代猜测应采用哪个 转换 NUM closure的形式化定义 令edge s c 是从状态s出发沿着标有c的一条边可到达的所有NFA状态的集合 对于状态集合 closure S 是从S中的状态出发 无须接收任何字符 即只通过 边便可到达的状态组成的集合 即满足如下条件的最小集合T 迭代法 iteration 计算T T SRepeatT TT UntilT T 证明 算法是正确的 T只可能在迭代中扩大 所以最终的T一定包含S 如果在一次迭代之后有T T 则T也一定包含 s T edge s 因为在NFA中只有有限个不同的状态 所以算法一定会终止 DFAedge d c 当位于由NFA状态si sk sl组成的集合d si sk sl 时 从d中的状态出发 并输入符号c 所到达的NFA的一个新的状态集合 利用DFAedge d c 能够更形式化地写出NFA模拟算法 simulationalgorithm 设NFA的初态是s1 输入字符串的字符是c1 ck 则算法为 d closure s1 fori 1tokd DFAedge d ci NFA DFA的可行性 在实际的应用中 需要预先计算出所有的状态集合 即由NFA构造一个DFA 使得NFA的每一个状态集合都对应于DFA的一个状态 由于NFA的状态个数有限 n个 所以这个DFA的状态个数也是有限的 至多有2n个 DFAedge states 1 i 2 5 6 8 15 states 2 DFAedge states 1 a h j z 5 6 8 15 states 3 DFAedge states 1 0 9 10 11 13 15 states 4 DFAedge states 1 other 15 states 5 DFAedge states 2 f 3 6 7 8 states 6 DFAedge states 2 a e g z 0 9 6 7 8 states 7 DFAedge states 3 a z 0 9 6 7 8 states 7 DFAedge states 4 0 9 11 12 13 states 8 DFAedge states 6 a z 0 9 6 7 8 states 7 DFAedge states 7 a z 0 9 6 7 8 states 7 DFAedge states 8 0 9 11 12 13 states 8 一般只有约n个状态是从初态可到达的 避免了转换出现指数级的膨胀 exponentialblowup 只要states d 中有任何状态是其NFA中的终态 状态d就是DFA的终态 举例 正规式 a b aa bb a b 对应的NFA及状态转换矩阵如图所示 1 5 4 3 2 6 a a a a b b b b 1 5 1 1 3 5 2 1 4 5 3 1 3 5 2 1 2 3 5 6 4 1 4 5 1 4 5 3 1 3 5 1 2 4 5 6 5 1 2 3 5 6 4 1 2 3 5 6 1 4 5 6 6 1 4 5 6 6 1 3 5 6 1 4 5 2 6 1 2 4 5 6 5 1 3 5 6 7 1 2 4 5 6 1 4 5 6 1 3 5 2 6 1 3 5 6 7 对状态矩阵中的所有状态子集重新命名得到 转换后的DFA为 确定有限自动机的化简DFA的化简又称最少化 条件是接受的语言必须相同 化简算法原则 将DFAM中的状态划分为不相交的子集 在每个子集内部其状态都是等价的 而在不同子集间的状态均是可区别的 最后从每个子集中任选一状态作代表 消去其他的等价状态 将那些原来射入其他等价状态的弧改射入相应的代表状态 定义 设DFAM中有两个状态s和t 若 s s1 t t1 且s1 t1都属于终态 V T 则称s t为等价的 否则称可区别的 确定有限自动机的化简算法 1 首先把状态集S分成终态集和非终态集 因为终态集可接受 而非终态集则不能 所以他们是可区别的 这就是基本划分 0 I01 I02 2 假定经过k次划分后 已含有m个子集 k Ik1 Ik2 Ikm 这些子集到现在为止都是可区别的 然后继续考察这些子集是否还可以划分 3 重复步骤 2 直至所含的子集数不再增加为止 4 对每一个子集任取一个状态为代表 若该子集包含原有的初态 则此代表状态便为最少化后M的初态 若该子集包含原有的终态 则此代表状态便为最少化后M的终态 举例1 DFAM 1 2 3 4 5 6 7 a b 0 3 4 5 6 1