编译原理第二章词法分析.ppt

第一章 总结 语言与语言的翻译 编译器的基本组成 编译器的分析/综合模式(编译器基础架构) 扫描遍数 编译器的编写 第二章 词法分析 词法的双重含义 规定单词形成的规则，被称为构词规则或词法规则。相当于立法，规定语言所允许的合法单词。 根据构词规则识别输入序列，被称为词法分析。相当于执法，识别出合法的单词、指出非法的输入序列。 主要内容 词法分析中的若干问题 模式的形式化描述 记号的识别 从正规式到词法分析器 上机：函数绘图语言的词法分析器 2.1 词法分析中的若干问题 记号、模式与单词 单词的基本分类： 关键字 kw(key word, or reserved word) 标识符 id(identifier) 字面量 literal 特殊符号 ks(key symbol, or special symbol) [例2.1]语句 position := initial + rate * 60 记号 id ks id ks id ks number 注意：称识别出id而不是rate或initial 问题：根据什么识别这些词法的基本单位（词法元素）？ 2.1 词法分析中的若干问题 三个术语： 模式(pattern)：产生和识别元素的规则 记号(token)： 按照某个模式(或规则)识别出的元素(一组) 单词(lexeme)：被识别出的元素自身的值(一个)，也称为词值 2.1 词法分析中的若干问题 记号的属性 记号是按照某个模式识别出的元素。 赋值句position := initial + rate * 60 position、initial和rate均为标识符，种类均是id。 问题：当识别出一个id时，如何判定是哪个id ？ 当识别出一个relation时，究竟是 = 还是 ？ 记号＝记号的类别＋记号的属性 [例2.2]表达式 mycount 25 由三个记号组成 类别 82 81 83 属性 “mycount” 5 25 注意：5与25的区别 （根据记号的类别） 25与“25”的区别 （如何区别？） 2.1 词法分析中的若干问题 词法分析器的作用与工作方式 词法分析器是编译器中唯一与源程序打交道的部分。 滤掉源程序中的无用成分，如注释、空格、回车等； 处理与平台有关的输入，如文件结束符的不同表示等； 根据模式识别记号，并交给语法分析器； 调用符号表管理器或出错处理器，进行相关处理 。 工作方式：单独扫描，作为语法分析器的子程序，并行工作 2.2 模式的形式化描述 字符串与语言 从词法分析的角度看程序设计语言，它是由记号组成的集合。 定义2.1 语言L是有限字母表∑上有限长度字符串的集合 说明： 字母表是字符的集合，这些字符可以组成字符串。 两个有限（计算机的表达能力有限）： 字母表是有限的； 字符串的长度是有限的。 [例2.3]字母表∑={a, b, c}，则其上的语言L={ε, a, b, c, aa, ab, ac, ba, bb, bc, ...} 2.2 模式的形式化描述 字符串的基本概念 术语 示例 |S| |abc| = 3 ε |ε| = 0 S1S2 abc def = abcdef Sn (abc)3 = abcabcabc S的前缀X abc的前缀有：ε，a，ab, abc S的后缀X abc的后缀有：ε，c，bc, abc S的子串X abc的子串有： ε，a，b, c, … S的真前缀 abc的真前缀有：a，ab S的真后缀 ？ S的真子串 ？ S的子序列X abdf是abcdef的一个子序列 2.2 模式的形式化描述 若 L = {a, b}, M = {c, d}，则 LM = {ac, bc, ad, bd}，L∩M = Φ L* = {ε, a, b, aa, bb, ab, ba, aaa, ...} L+ = { a, b, aa, bb, ab, ba, aaa, ...} 2.2 模式的形式化描述 正规式与正规集 定义2.2 令Σ是一个有限字母表，则Σ上的正规式及其表示的集合递归定义如下: 1. ε是正规式，它表示集合L(ε)={ε} 2. 若a是Σ上的字符，则a是正规式，它表示集合L(a)={a} 3. 若正规式r和s分别表示集合L(r)和L(s)，则 （a） r|s是正规式，表示集合L(r)∪L(s)， （b） rs是正规式，表示集合L(r)L(s)