第二章 词法分析——单词
[例2.1]语句 position := initial + rate * 60 记号 id ks id ks id ks number 问题：一个单词究竟是标识符、关键字、字面量还是特殊 符号？ 根据构词规则来产生和识别
将产生和识别单词的规则称为模式，按照某个模式识别 出的元素称为记号(token)，而单词指被识别出元素自身 的值。
言，正则表达式
[例2.3]字母表∑={a, b, c} 字符串： ε, a, b, c, aa, ab, ac, ba, bb, bc,… ∑上所有字符串构成的语言L： L={ε, a, b, c, aa, ab, ac, ba, bb, bc, ...} ∑上所有字符串（模式非形式化的表达） 形式化的表达： ∑* (正则表达式) 正则表达式表达的语言L(∑*)= {ε, a, b, c, aa, ab, ac, ba, bb, bc, ...} 11
主要内容
词法分析中的若干问题 模式的形式化描述 记号的识别 从正规式到词法分析器

4
第二章 词法分析——单词
单词（组成程序的元素）
public class TestOfDeclared { public static void main(String[] args) { try{ ListOfNumbersDeclared list = new ListOfNumbersDeclared(); list.writeList(); }catch(Exception e){}; System.out.println("A list of numbers is created and stored in OutFile.txt"); } }
单词举例
const
模式的非形式化描述
const
if(03)
relation(81) id(82) num(83) literal(84)
if
<, <=, =, <>, >, >= pi, count, D2 3.1416, 0, 6.02E23 “core dumped”

<, <=, =, <>, >, >= 字母打头的字母数字串 任何数值常数 双引号间的任意字符串
Comment
{x is an integer}
括号间的任意字符串
8
第二章 词法分析——记号
记号 记号是按照某个模式识别出的元素。 赋值句position := initial + rate * 60 position、initial和rate均为标识符，种类均是id。
问题：当识别出一个id时，如何判定是哪个id ？ 当识别出一个relation时，究竟是 = 还是 < ？
5
第二章 词法分析——单词
单词的基本分类： 关键字（保留字）， kw (key word, or reserved word) 在程序设计语言中有着固定的意义 while, if, else, for, class 不允许用它们再表示其它的意思 标识符 id (identifier) 程序设计语言中最大的一个类别 为实体起个名字，便于之后的称呼和使用 可以用标识符命名的实体包括：类型名、变量名、过程名、常量名、类 名、对象名、程序包名等 字面量 literal，num 直接以其字面所表示的常量 25，true，“This is an apple” 注意：字面量和常量的区别（常量可以是字面量，也可以是常量名，pi） 特殊符号 ks (key symbol, or special symbol) 类似于自然语言中的标点符号，每个符号都有各自的特殊用途 6 +，-，*等
第二章 词法分析——正则表达式
字符串：字母表上的字符构成的串 相关术语 示例
长度：|S| ε 连接：S1S2 多次连接：Sn S的前缀X S的后缀X S的子串X S的真前缀 S的真后缀 S的真子串 S的子序列X |abc| = 3 |ε| = 0 abc def = abcdef (abc)3 = abcabcabc abc的前缀有：ε，a，ab, abc abc的后缀有：ε，c，bc, abc abc的子串有： ε，a，b, c, … abc的真前缀有：a，ab ？ ？ abdf是abcdef的一个子序列
12
第二章 词法分析——正则表达式
字符串的集合 及其运算 Φ 空集合 意义
{ε}
X=L∪M X=L∩M
空串是唯一元素
并: X={s| s∈L or s∈M } 交: X={s|s∈L and s∈M}
X=LM
X=L* X=L+
连接: X={st|s∈L and t∈M }
(星)闭包: X=L0∪L1∪L2∪... 正闭包: X=L1∪L2∪L3∪...
7
第二章 词法分析——单词
三个术语：
模式(pattern)：产生和识别元素的规则 记号(token)： 按照某个模式(或规则)识别出的元素(一组) （记号的类别可以用整型编码表示，例01表示const） 单词(lexeme)：被识别出的元素自身的值(一个)，也称为词值

记号的类别
const(01)
id, 1 = id, 2 + id, 3 60 记号流 词法分析：扫描构成源程序的字符流，按词法 规则把它们组成记号流
2
第二章 词法分析——简介
词法分析器的作用与工作方式 词法分析器是编译器中唯一与源程序打交道的部分。 滤掉源程序中的无用成分，如注释、空格、回车等； 处理与平台有关的输入，如文件结束符的不同表示等； 识别记号，并交给语法分析器； 调用符号表管理器或出错处理器，进行相关处理 。 工作方式: (1)单独扫描，(2)作为语法分析器的子程序，(3)并行 工作
源程序 词法分析器
源程序
记号流
词法分析器 调用 返回记号 语法树
记号流 源程序 词法分析器 语法分析器
语法分析器
语法树
3
第二章 词法分析——简介
x := y + z * 60.0 ; <id,1> := <id,2> + <id,3> * <60.0> ; 字符流到记号流
两个概念：

词法规则（构词规则）：规定单词形成的规则 相当于立法，规定语言所允许的合法单词 词法分析：根据词法规则识别输入序列 相当于执法，识别出合法的单词、指出非法的输入序列
若 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, ...} 13
记号＝记号的类别＋记号的属性 [例2.2]表达式
类别 属性 注意：5？
mycount
>
25 由三个记号组成
83 25
记号的类别
relation(81) id(82) num(83)
9
82 81 “mycount” 5
第二章 词法分析——模式
正规式 正则表达式
Regular Expression
记号的类别 const(01) if(03) relation(81) id(82) 单词举例 const if <, <=, =, <>, >, >= pi, count, D2 模式的非形式化描述 const if <, <=, =, <>, >, >= 字母打头的字母数字串
num(83)
literal(84) Comment
3.1416, 0, 6.02E23
“core dumped” {x is an integer}
任何数值常数
双引号间的任意字符串 括号间的任意字符串
10
第二章 词法分析——正则表达式
编译原理课所涉及到的第一个形式化的概念 正则表达式涉及到的概念有：字母表、字符串、语
第一章内容回顾
源程序 词法分析
语言与语言的翻译 编译器的基本组成 编译器的分析/综合模 式(编译器基础架构) 扫描遍数 编译器的编写

语法分析 符 号 表 管 理 语义分析 中间代码生成 代码优化 目标代码生成 目标代码
出 错 处 理
1
第二章 词法分析——简介
C语言赋值语句： 字符流 符 号 表 position = initial + rate 60 1 position . . . ... 2 initial 词法分析器 3 rate ...