《编译原理课件.ppt》由会员分享，可在线阅读，更多相关《编译原理课件.ppt（90页珍藏版）》请在第壹文秘上搜索。
1、编 译 原 理 词法分析理解词法分析器功能及形式；熟练掌理解词法分析器功能及形式；熟练掌握词法分析器设计的原理，单词的描述工具，掌握握词法分析器设计的原理，单词的描述工具，掌握正规文法、正规式、有穷自动机的相关概念及相互正规文法、正规式、有穷自动机的相关概念及相互转换转换; 掌握运用状态转换图进行词法分析器设计。掌握运用状态转换图进行词法分析器设计。 编 译 原 理 词法分析本章知识点本章知识点(内容内容)词法分析程序的设计词法分析程序的设计单词的描述工具单词的描述工具有穷自动机有穷自动机正规式和有穷自动机的等价性正规式和有穷自动机的等价性正规文法和有穷自动机的等价性正规文法和有穷自动机的等价
2、性词法分析程序的自动构造词法分析程序的自动构造编 译 原 理 词法分析编译程序首先是在单词级别上来分析和翻译源编译程序首先是在单词级别上来分析和翻译源程序的。程序的。词法分析的任务是词法分析的任务是：从左至右逐个字符地对源：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号，把作为程序进行扫描，产生一个个单词符号，把作为字符串的源程序改造成为单词符号串的中间程字符串的源程序改造成为单词符号串的中间程序。因此，词法分析是编译的基础。执行词法序。因此，词法分析是编译的基础。执行词法分析的程序称为分析的程序称为词法分析器词法分析器, ,词法分析程序亦词法分析程序亦称为扫描器。称为扫描器。词法分析
3、程序的设计词法分析程序的设计首页首页结束结束首页首页结束结束编 译 原 理 词法分析一、一、词法分析器功能和输出形式词法分析器功能和输出形式功能：输入源程序，输出单词符号。功能：输入源程序，输出单词符号。程序语言的单词符号一般分为五种：程序语言的单词符号一般分为五种：(1)关键字（保留字或基本字）关键字（保留字或基本字）(2)标识符标识符(3)常数（整型、实型、布尔型、文字型等）常数（整型、实型、布尔型、文字型等） (4)运算符。运算符。(5)界符界符(逗号、分号、括号、逗号、分号、括号、*，*等等)。词法分析器输出的单词符号常常表示为二元式：词法分析器输出的单词符号常常表示为二元式： （单词
4、种别，单词符号的属性值）（单词种别，单词符号的属性值）首页首页结束结束编 译 原 理 词法分析单词种别单词种别通常用整数编码。通常用整数编码。1 1、标识符一般统归为一种、标识符一般统归为一种2 2、常数则宜按类型（整、实、布尔等）分、常数则宜按类型（整、实、布尔等）分种种3 3、关键字可视其全体为一种，也可以一字、关键字可视其全体为一种，也可以一字一种。一种。4 4、运算符可采用一符一种的分法，但也可、运算符可采用一符一种的分法，但也可以把具有一定共性的运算符视为一种。以把具有一定共性的运算符视为一种。5 5、界符一般一符一种的分法。、界符一般一符一种的分法。首页首页结束结束编 译 原 理
5、词法分析 如果一个种别只含有一个单词符号，那么如果一个种别只含有一个单词符号，那么对于这个单词符号，种别编码就完全代表它自对于这个单词符号，种别编码就完全代表它自身了。若一个种别含有多个单词符号，那麽，身了。若一个种别含有多个单词符号，那麽，对于它的每个单词符号，除了给出种别编码之对于它的每个单词符号，除了给出种别编码之外，还应给出有关单词符号的外，还应给出有关单词符号的属性信息。属性信息。 单词符号的属性是指单词符号的特征或特单词符号的属性是指单词符号的特征或特性。属性值则是反映特性或特征的值。性。属性值则是反映特性或特征的值。【例如例如】对于某个标识符，常将存放它有关信对于某个标识符，常将
6、存放它有关信息的符号表项的指针作为其属性值；对于某个息的符号表项的指针作为其属性值；对于某个常数，则将存放它的常数表项的指针作为其属常数，则将存放它的常数表项的指针作为其属性值。性值。首页首页结束结束编 译 原 理 词法分析 作为例子考虑下述作为例子考虑下述C+C+代码段：代码段： while (i=j) i- -;while (i=j) i- -; 经词法分析器处理后，它将转换为如下的单经词法分析器处理后，它将转换为如下的单词符号序列：词符号序列： while, - ( , - 标识符编码标识符编码 , ,指向指向i i的符号表项的指针的符号表项的指针 = =的编码的编码 , - , - -
7、 - , - ; , - 首页首页结束结束编 译 原 理 词法分析【例如例如】单词符号单词符号 类别编号类别编号 标识符标识符 1 常数常数 2 if3 then 4 else5 program 6 begin7 end 8 + 9 - 10 * 11 单词符号单词符号 类别编号类别编号/ 12 ( 13 ) 14 15 = 16 17 = 18 19 :=20 ; 21 . 22 ,23 单词种别编码单词种别编码首页首页结束结束编 译 原 理 词法分析可使整个编译程序的结构更简沽、清晰和条理可使整个编译程序的结构更简沽、清晰和条理化。化。 也可以把词法分析器安排成一个子程序，每当也可以把词法
8、分析器安排成一个子程序，每当语法分析器需要一个单词符号时就调用这个子程语法分析器需要一个单词符号时就调用这个子程序。每一次调用，词法分析器就从输人串中识别序。每一次调用，词法分析器就从输人串中识别出一个单词符号，把它交给语法分析器。出一个单词符号，把它交给语法分析器。词法分析器作为独立子程序词法分析器作为独立子程序首页首页结束结束编 译 原 理 词法分析二、词法分析器的设计二、词法分析器的设计 1 1、输入、预处理、输入、预处理 词法分析器工作的第一步是输入源程序文本。输入串词法分析器工作的第一步是输入源程序文本。输入串一般放在一个缓冲区中，这个缓冲区称输入缓冲区。词一般放在一个缓冲区中，这个
9、缓冲区称输入缓冲区。词法分析器的工作可以直接在这个缓冲区中进行。但在许法分析器的工作可以直接在这个缓冲区中进行。但在许多情况下，把输入串预处理一下，对单词符号的识别工多情况下，把输入串预处理一下，对单词符号的识别工作将是比较方便的。作将是比较方便的。 预处理工作包括对空白符、跳格符、回车符和换行预处理工作包括对空白符、跳格符、回车符和换行符等编辑性字符的处理，及删除注解等。我们可以设想符等编辑性字符的处理，及删除注解等。我们可以设想构造一个预处理子程序，他完成上面的工作。每当词法构造一个预处理子程序，他完成上面的工作。每当词法分析器调用它时就处理出一串确定长度的输入字符，并分析器调用它时就处理
10、出一串确定长度的输入字符，并将其装入词法分析器所指定的缓冲区中（称为扫描缓冲将其装入词法分析器所指定的缓冲区中（称为扫描缓冲区）。这样分析器就可以在此缓冲区中直接进行单词符区）。这样分析器就可以在此缓冲区中直接进行单词符号的识别工作。号的识别工作。首页首页结束结束编 译 原 理 词法分析扫描缓冲区进行扫描时一般用两个指示扫描缓冲区进行扫描时一般用两个指示器，一个指向当前正在识别的单词的开始器，一个指向当前正在识别的单词的开始位置（指向新单词的首字符），另一个用位置（指向新单词的首字符），另一个用于向前搜索以寻找单词的终点。于向前搜索以寻找单词的终点。 首页首页结束结束编 译 原 理 词法分析
11、源程序串源程序串 输入缓冲区输入缓冲区 列表列表 预处理预处理 子程序子程序 扫描器扫描器 单词符号单词符号 扫描缓冲区扫描缓冲区 2、 单词符号的识别单词符号的识别词法分析器的结构图如图词法分析器的结构图如图1所示。所示。首页首页结束结束编 译 原 理 词法分析 当词法分析器调用预处理子程序处理出一当词法分析器调用预处理子程序处理出一串输入字符串放进扫描缓冲区之后，分析器就从串输入字符串放进扫描缓冲区之后，分析器就从此缓冲区中逐一识别单词符号。当缓冲区里的字此缓冲区中逐一识别单词符号。当缓冲区里的字符串被处理完之后，它又调用预处理程序装入新符串被处理完之后，它又调用预处理程序装入新串。串。
12、编 译 原 理 词法分析单词的描述工具单词的描述工具-正规表达式正规表达式 单词的识别系统单词的识别系统-有穷自动机有穷自动机首页首页结束结束首页首页结束结束编 译 原 理 词法分析 是程序设计语言中的基本语法符号，是程序设计语言中的基本语法符号，正规式正规式给出了字符串的简洁结构表示，因此通给出了字符串的简洁结构表示，因此通常用正规式来描述字符串的词法结构，再利用常用正规式来描述字符串的词法结构，再利用正规式与有穷自动机之间的等价性，构造出能正规式与有穷自动机之间的等价性，构造出能识别符合词法结构的字符串的有穷自动机，这识别符合词法结构的字符串的有穷自动机，这便是便是词法分析器的形式化构造方
13、法。词法分析器的形式化构造方法。编 译 原 理 词法分析3型文法，又称右线性文法或正规文法型文法，又称右线性文法或正规文法(Regular Grammars),其表达式形如：其表达式形如：AaB或或Aa。 绝大部份程序设计语言绝大部份程序设计语言的单词都能用正规文法来描述。的单词都能用正规文法来描述。单词的描述工具单词的描述工具1 1、正规文法、正规文法首页首页结束结束首页首页结束结束编 译 原 理 词法分析 所谓正规表达式就是用特定的运算符及运所谓正规表达式就是用特定的运算符及运算对象按某种规则构造的表达式，用于描述给算对象按某种规则构造的表达式，用于描述给定定3型语言的所有型语言的所有句子
14、。句子。2 2、正规式、正规式首页首页结束结束编 译 原 理 词法分析正规表达式与正规集正规表达式与正规集正规式和正规集的递归定义：正规式和正规集的递归定义：（1）和和都是都是上的正规式，它们所表示的正规集分别为上的正规式，它们所表示的正规集分别为和和(2)任何任何a，a是是上的一个正规式，它所表示的正规集为上的一个正规式，它所表示的正规集为a；(3)假定假定U和和V都是都是上的正规式，它们所表示的正规集分别记上的正规式，它们所表示的正规集分别记为为L(U)和和L(V)，那么，那么，(U|V)、(UV)和和(U)*也都是正规式，也都是正规式，它们所表示的正规集分别为它们所表示的正规集分别为L(
15、U) UL(V),L(U)L（V）（连接）（连接积）和（积）和（L（U）*（闭包）。（闭包）。仅由有限次使用上述三步骤而得到的表达式才是仅由有限次使用上述三步骤而得到的表达式才是上的正规上的正规式。仅由这些正规式所表示的字集才是式。仅由这些正规式所表示的字集才是上的正规集。上的正规集。首页首页结束结束编 译 原 理 词法分析1、正规式的运算符，、正规式的运算符，|读为读为“或或”，“”读为读为“连接连接”，“*”读为读为“闭包闭包”（即，（即，任意有限次的自重复连接）。任意有限次的自重复连接）。2、规定算符的优先顺序为：先、规定算符的优先顺序为：先“*”，次次“”最后最后”|”。连接符。连接符
16、 一般可省略一般可省略不写。不写。【说明说明】首页首页结束结束编 译 原 理 词法分析【例例】设设 =0，1，则有，则有正规式正规式正规集正规集000|10，101011*，1，11，111.(0|1)*,0,1,01,10.首页首页结束结束编 译 原 理 词法分析v设设r,s,t为正规式，则正规式服从如下的代数为正规式，则正规式服从如下的代数规则：规则： r|s=s|r (或或满足交换律满足交换律) r|(s|t)=(r|s)|t (或或满足结合律满足结合律) r(st)=(rs)t (连接连接满足结合律满足结合律) r(s|t)=rs | rt (分配律分配律) r=r=r (是连接的恒等元素是连接的恒等元素) 注意：注意： rs sr r|(st) rs | rt首页首页结束结束编 译 原 理 词法分析【例例】 令令=a, b其正规式和正规集如下其正规式和正规集如下： 正规式正规式 正规集正规集 ba* a(a|b)* (a|b)*(aa|bb)(a|b)*正规集是正规集是 所有两个相继的所有两个相继的a或相继的或相继的b 的字的字 上所有以上所有以a为首的字。为首的字。上所有以
