第3章词法与有限自动机解决方案.ppt

编译原理编译原理第第3 3章章词法分析与有限自动机词法分析与有限自动机安庆师范学院计算机与信息学院安庆师范学院计算机与信息学院本章目标?解释词法分析器的工作原理及设计实现?介绍单词的描述工具:正规文法和正规式?定义 DFA 和 NFA 的概念?介绍“正规式→ NFA → DFA →最小化 DFA ”的转换方法?介绍有限自动机、正规文法和正规式的等价性?介绍词法分析器的自动构造工具-LEX 的原理与实现教学内容 词法分析器的设计思想 词法分析器的设计 单词的描述工具 有限自动机 正规式、正规文法和有限自动机的等价性 词法分析器的自动构造工具—— LEX 本章小结 词法分析器的设计思想词法分析器的任务和输出形式 1将词法分析工作分离的考虑 2 1、词法分析器的任务和输出形式(1)词法分析器的任务自左至右逐个字符地对源程序进行扫描,按语言的构词规则识别出一个个单词,把作为字符串的源程序改造为单词符号串的中间程序。字符串流单词流源语言程序单词符号 1、词法分析器的任务和输出形式(2)单词符号单词符号是程序设计语言的基本语法单位和最小语义单位。(3)单词符号的种类标识符标识符:标记常量、变量、函数等的名字,如 fun 、i 关键字关键字:具有固定意义的标识符,如 if、 while 、 for 常常数数:各种类型的常数,如实型 ,布尔型 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)将词法分析器设计为语法分析器的子程序在实现编译程序时,常将词法分析程序从语法分析中独立出来,将其设计为语法分析器的子程序,每当语法分析器需要一个单词符号时就调用词法分析器,每一次调用,词法分析器就从输入串中识别出一个单词符号,并将该单词类别和单词值返回给语法分析器。字符串形式的源程序字符词法分析器语法分析器符号表单词取下一单词