清华大学：《编译原理》课程教学资源_第三章 词法分析

第三章词法分析 本章将讨纶祠法分析程序的計原则,单 词的描述技术,别机制及词法分析程戽 的自动构造原理。 3.1词法分析程序 ●3.2正规表达式与正规集(正规语言) 3.3有穷自动机 34词法分析程序的自动构造

本章将讨论词法分析程序的设计原则，单 词的描述技术，识别机制及词法分析程序 的自动构造原理。 3.1 词法分析程序 3.2 正规表达式与正规集（正规语言） 3.3 有穷自动机 3.4 词法分析程序的自动构造 第三章 词法分析

本章重点 ●·单词的描述工具 ·单词的识别系统 ·设计和实现词法分析程序 首先需要描述和刻画程序设计语言中的原子 单位—单词,其次需要识别单词和执行某 些相关的动作 描述程序设计语言的词法的机制是正则表达 式,识别机制是有穷状态自动机

本章重点 • 单词的描述工具 • 单词的识别系统 • 设计和实现词法分析程序 – 首先需要描述和刻画程序设计语言中的原子 单位——单词，其次需要识别单词和执行某 些相关的动作。 – 描述程序设计语言的词法的机制是正则表达 式，识别机制是有穷状态自动机

回顺什麽是词法分析程序 实现词法分析( lexical analysis)的程序 逐个读入源程序字符并按照构词规则切分成 系列单词。单词是语言中具有独立意 义的最小单位,包括保留字、标识符、运算 符、标点符号和常量等。 词法分析是编译过程中的一个阶段,在语法 分析前进行。也可以和语法分析结合在一起 作为一遍,由语法分析程序调用词法分析程 序来获得当前单词供语法分析使用

回顾 什麽是词法分析程序 实现词法分析（lexical analysis）的程序 – 逐个读入源程序字符并按照构词规则切分成 一系列单词。 单词是语言中具有独立意 义的最小单位，包括保留字、标识符、运算 符、标点符号和常量等。 词法分析是编译过程中的一个阶段，在语法 分析前进行 。也可以和语法分析结合在一起 作为一遍，由语法分析程序调用词法分析程 序来获得当前单词供语法分析使用

词法分析程序和语法分析程序的关系 Token 源程序匚心词法分析程序二语法分析程序 ret tokeny

词法分析程序和语法分析程序的关系 源程序 词法分析程序 语法分析程序 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 g Const pi=3.14159;中的 p是 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语言的字母表 是由字母、数字、若干专用符号及 BEGIN、I之类的保 留字组成

正规表达式与正规集（正规语言） 程序设计语言中的单词是基本语法成分.单词符 号的语法可以用有效的工具加以描述，并且基 于这类描述工具，实现词法分析程序的自动构 造. 首先表述一些基本术语和概念. 符号 一个抽象实体,我们不再形式地定义它(就象几何中的” 点”一样).例如字母是符号,数字也是符号。 字母表 字母表是元素的非空有穷集合，我们把字母表中 的元素称为符号，因此字母表也称为符号集。 不同的语言可以有不同的字母表，例如汉语的字母表中 包括汉字、数字及标点符号等。PASCAL语言的字母表 是由字母、数字、若干专用符号及BEGIN、IF之类的保 留字组成

符号串由字母表中的符号组成的任何有穷序列称为符 号串,例如001110是字母表∑={0,1}上的符号串 字母表A={ab,c}上的一些符号串有:ab,c,ab,aca。 在符号串中,符号的顺序是很重要的,符号串ab就不 同于ba,abca和abc也不同 可以使用字母表示符号串,如x=STR表示“x是由符号 S、T和R,并按此顺序组成的符号串” 符号串的长度如果某符号串ⅹ中有m个符号,则称其长度 为m,表示为|x|=m,如001110的长度是6。 空符号串,即不包含任何符号的符号串,用E表示,其长 度为0,即|ε|=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