第3章词法分析与有限自动机概要.ppt

编译原理 第3章 词法分析与有限自动机 本章目标 解释词法分析器的工作原理及设计实现 介绍单词的描述工具：正规文法和正规式 定义DFA和NFA的概念 介绍“正规式→NFA→DFA→最小化DFA”的转换方法 介绍有限自动机、正规文法和正规式的等价性 介绍词法分析器的自动构造工具-LEX的原理与实现 教学内容 3.1 词法分析器的设计思想 1、词法分析器的任务和输出形式 （1）词法分析器的任务 自左至右逐个字符地对源程序进行扫描，按语言的构词规则识别出一个个单词，把作为字符串的源程序改造为单词符号串的中间程序。 1、词法分析器的任务和输出形式 （2）单词符号 单词符号是程序设计语言的基本语法单位和最小语义单位。 （3）单词符号的种类 标识符：标记常量、变量、函数等的名字，如fun、i 关键字：具有固定意义的标识符，如if、while、for 常 数：各种类型的常数，如实型0.618，布尔型TRUE 运算符：如+、-、*、/、=、 、、 = 、== 界 符：如，、；、（、），{，} 1、词法分析器的任务和输出形式 （4）单词符号的输出形式 二元式： （ 单词种别， 单词符号的属性值） 1、词法分析器的任务和输出形式 （4）单词符号的输出形式 常用单词种别编码方案 标识符：一种 关键字：全体视为一种或一字一种 常 数：按类型分种，如整数、实数、布尔型 运算符：一符一种 界 符：一符一种 1、词法分析器的任务和输出形式 （5）举例 　　假定单词类别用整数编码，标识符、常数、关键字、运算符和界符的编码依次为1、2、3、4、5。C++语句 if(a=90) b=c；在经过词法分析器处理后输出的二元式及其单词表示如下： 　　二元式 单词 　　(3, ’if’) 关键字if 　　(5, ’(’) 界符( 　　(1,指向a的符号表项的指针) 标识符a 　　(4, ’=’) 运算符= 　　(2, 90) 常数90 　　(5, ’)’) 界符) 　　(1,指向b的符号表项的指针) 标识符b 　　(4, ’=’) 运算符= 　　(1,指向c的符号表项的指针) 标识符c 　　(5, ’；’) 界符； 2、将词法分析工作分离的考虑 （1）将词法分析器设计为语法分析器的子程序 在实现编译程序时，常将词法分析程序从语法分析中独立出来，将其设计为语法分析器的子程序，每当语法分析器需要一个单词符号时就调用词法分析器，每一次调用，词法分析器就从输入串中识别出一个单词符号，并将该单词类别和单词值返回给语法分析器。 　　 2、将词法分析工作分离的考虑 （2）好处 简化设计： 由词法分析器处理注解和空白字符，可简化语法分析器的设计。此外，在设计新语言时，分离词法和语法规则可以进行更全面的语言设计。 改进编译效率： 编译的大部分时间消耗在读源程序和分离一个个单词符号上，专用的经过精心设计的读源程序字符流和处理单词符号的词法分析器可以加快编译速度。 增强编译系统的可移植性：不同语言的字母表的特殊性，构词规则的差异和其它与设备有关的不规则