第三章词法分析 本章将对论词法分析程序的没针原则，单 词的描述技术，温别机制及词法分析程序 的百动构造原理。 3.1词法分析程序 3.2正规表达式与正规集（正规语言） 3.3有穷自动机 3.4词法分析程序的自动构造
本章将讨论词法分析程序的设计原则，单 词的描述技术，识别机制及词法分析程序 的自动构造原理。 3.1 词法分析程序 3.2 正规表达式与正规集（正规语言） 3.3 有穷自动机 3.4 词法分析程序的自动构造 第三章 词法分析
本章重点 单词的描述工具 单词的识别系统 设计和实现词法分析程序 首先需要描述和刻画程序设计语言中的原子 单位一单词，其次需要识别单词和执行某 些相关的动作。 描述程序设计语言的词法的机制是正则表达 式，识别机制是有穷状态自动机
本章重点 • 单词的描述工具 • 单词的识别系统 • 设计和实现词法分析程序 – 首先需要描述和刻画程序设计语言中的原子 单位——单词，其次需要识别单词和执行某 些相关的动作。 – 描述程序设计语言的词法的机制是正则表达 式，识别机制是有穷状态自动机
颜什麽是词法分析程序 实现词法分析(lexical analysis)的程序 逐个读入源程序字符并按照构词规则切分成 一系列单词。 单词是语言中具有独立意 义的最小单位，包括保留字、标识符、运算 符、标点符号和常量等。 词法分析是编译过程中的一个阶段，在语法 分析前进行。也可以和语法分析结合在一起 作为一遍，由语法分析程序调用词法分析程 序来获得当前单词供语法分析使用
回顾 什麽是词法分析程序 实现词法分析（lexical analysis）的程序 – 逐个读入源程序字符并按照构词规则切分成 一系列单词。 单词是语言中具有独立意 义的最小单位，包括保留字、标识符、运算 符、标点符号和常量等。 词法分析是编译过程中的一个阶段，在语法 分析前进行 。也可以和语法分析结合在一起 作为一遍，由语法分析程序调用词法分析程 序来获得当前单词供语法分析使用
词法分析程序和语法分析程序的关系 Token 源程序 词法分析程序 语法分析程序 get token
词法分析程序和语法分析程序的关系 源程序 词法分析程序 语法分析程序 Token get token …
词法分析程序的主要任务： 读源程序，产生单词符号 词法分析程序的其他任务： 滤掉空格，跳过注释、换行符 追踪换行标志，复制出错源程序， 宏展开，……
词法分析程序的主要任务： – 读源程序，产生单词符号 词法分析程序的其他任务： – 滤掉空格，跳过注释、换行符 – 追踪换行标志，复制出错源程序， – 宏展开，……
常常遇到的术语 Token 单词，词标，符号 lexeme 词素，词位 pattern 模式，式样
常常遇到的术语 Token 单词,词标，符号 lexeme 词素，词位 pattern 模式，式样
帮助理解术语 In general,there is a set of strings in the input for which the same token is produced as output.This set of strings is described by a rule called a pattern associated with the token.The pattern is said to match each string in the set.A lexeme is a sequence of characters in the source program that is matched by the pattern for a token. e.g. Const pi=3.14159;中的pi是token "identifier” 的lexeme,其pattern为letter followed by letters and/or digit
帮助理解术语 In general，there is a set of strings in the input for which the same token is produced as output. This set of strings is described by a rule called a pattern associated with the token. The pattern is said to match each string in the set. A lexeme is a sequence of characters in the source program that is matched by the pattern for a token. e.g. – Const pi=3.14159；中的pi是token “identifier” 的lexeme，其pattern为letter followed by letters and/or digit
词法分析工作从语法分析工作独立出来的 原因： 简化设计 改进编译效率 增加编译系统的可移植性 网
词法分析工作从语法分析工作独立出来的 原因： – 简化设计 – 改进编译效率 – 增加编译系统的可移植性
正规表达式与正规集（正规语言） 程序设计语言中的单词是基本语法成分.单词衔 号的语法可以用有效的三具加以描述，并且基 于这类描述工具，实现词法分析程序的自动构 造 首先表述一些基本术语和概念 符号一个抽象实体，我们不再形式地定义它（就象几何中的” 点”一样).例如字母是符号，数字也是符号 母表字母表是元素的非空有穷集合，我们把字母表中 的元素称为符号，因此字母表也称为符号集。 不同的语言可以有不同的字母表，例如汉语的字母表中 包括汉字、数字及标点符号等。PASCAL语言的字母表 是由字母、数字、若干专用符号及BEGN、IF之类的保 留字组成
正规表达式与正规集（正规语言） 程序设计语言中的单词是基本语法成分.单词符 号的语法可以用有效的工具加以描述，并且基 于这类描述工具，实现词法分析程序的自动构 造. 首先表述一些基本术语和概念. 符号 一个抽象实体,我们不再形式地定义它(就象几何中的” 点”一样).例如字母是符号,数字也是符号。 字母表 字母表是元素的非空有穷集合，我们把字母表中 的元素称为符号，因此字母表也称为符号集。 不同的语言可以有不同的字母表，例如汉语的字母表中 包括汉字、数字及标点符号等。PASCAL语言的字母表 是由字母、数字、若干专用符号及BEGIN、IF之类的保 留字组成
符号串由字母表中的符号组成的任何有穷序列称为符 号串，例如001110是字母表Σ={0,1}上的符号串 字母表A={a,b,c}上的一些符号串有：a,b,c,ab,aaca。 在符号串中，符号的顺序是很重要的，符号串ab就不 同于ba,abca和aabc也不同。 可以使用字母表示符号串，如x=STR表示“x是由符号 S、T和R,并按此顺序组成的符号串”。 符号串的长度如果某符号串x中有m个符号，则称其长度 为m,表示为|x|=m,如001110的长度是6。 空符号串，即不包含任何符号的符号串，用ε表示，其长 度为0，即|e|=0
– 符号串 由字母表中的符号组成的任何有穷序列称为符 号串，例如00 11 10 是字母表 =｛0，1｝上的符号串. 字母表A=｛a,b,c｝上的一些符号串有：a,b,c,ab,aaca。 在符号串中，符号的顺序是很重要的，符号串ab就不 同于ba,abca和aabc也不同。 可以使用字母表示符号串，如x=STR表示“ x是由符号 S、T和R，并按此顺序组成的符号串” 。 符号串的长度如果某符号串x中有m个符号，则称其长度 为m，表示为｜x｜=m，如001110的长度是6。 空符号串，即不包含任何符号的符号串，用ε表示，其长 度为0，即｜ε｜=0
