第四章 词法分析_new.ppt

计算机编译原理 计算机编译原理 第四章 词法分析 词法分析的基本概念 正规式自动机和状态图 词法分析程序的设计 学习目标: 掌握：词法分析程序的构造，正规式和正规文法到有穷自动机的转换，NFA到DFA的转换、DFA的化简 理解：正规文法、正规式、DFA的概念、NFA的概念 了解：词法分析程序的自动构造工具 词法分析程序 词法分析是编译过程中的一个阶段，在语法分析前进行 ，也可以和语法分析结合在一起作为一遍。 输入：源程序字符串 输出：单词符号（最基本的语法单位） 词法分析程序的功能 词法分析程序主要执行以下功能： 读入源程序字符串，识别开具有独立含义的最小语法单位——单词（符号）； 把单词变换成长度统一的且为定长的属性字； 其他功能： 滤掉空格，跳过注释、换行符 某些预加工处理 词法分析程序的实现方式 相对独立方式：把词法分析程序作为语法分析程序的一个独立子程序。语法分析程序需要新符号时调用这个子程序。 完全独立方式：词法分析程序作为单独一趟来实现。词法分析程序读入整个源程序，它的输出作为语法分析程序的输入。 相对独立方式 当采用递归下降分析等技术实现一趟编译程序时常采用这种方式。 完全独立方式 采用词法分析工作完全独立的原因： 简化设计，降低语法分析的复杂性 提高编译效率 增加编译系统的可移植性 源程序的输入 在内存开辟缓冲区，将程序文本放进该缓冲区 预处理：删除无用字符等 词法分析程序对缓冲区扫描时，设置两个指示器，一个指向当前正在识别的单词的开始位置，称为起始指针；另一个用于向前搜索，以寻找单词的终点，称为扫描指针。 扫描缓冲区的大小 应当保证单词符号不被缓冲区的边界打断 使用循环链表实现 规定单词符号的大小不超过整个链表的容量 超前搜索 词法分析程序在读取单词时，为了判断是否已读入整个单词的全部字符，常采取向前多读取字符并通过读取的字符来判别，即所谓超前搜索技术。 单词符号的构成规则——标识符 词法分析程序输出单词的形式 词法分析程序输出的单词符号通常用二元式表示：（单词类别，单词自身的值） 单词类别：表示单词种类，常用整数编码，它是语法分析需要的 单词自身的值：是编译中其他阶段所需要的信息 如果一个种别只含一个单词符号，那么该单词符号的类别编码就完全代表它自身的值。 把单词符号存储在符号表中。不同种类的单词符号可能具有不同类型的属性。可以用不同种类的符号表实现。 如果一个种别含有多个单词符号，那么还应给出该单词符号的自身值：标识符自身值是标识符自身的字符串；常数自身值是常数的二进制数值。 语言的单词符号 单词符号是程序语言的基本语法单位，一般分为下面5种： 关键字（基本字）：（个数确定，可全体编为一类，也可一字一类) 标识符：（个数不确定，作为一类） 常数：各种类型的常数 。(个数不确定，按类型分类) 运算符：如+、-、*、/、等。(个数确定，一符一类) 界符：如，、；、（、）、: 等。(个数确定,一符一类) 注意：一种语言的单词如何分类、怎样编码，主要取决于技术上的方便。 举例 例如：程序段 if(a1) b=10; 假定基本字、运算符、界符都是一符一种。 正规式和有限自动机 正规表达式和有限自动机——学习目的和内容 用正则表达式描述词法规则 构造正则表达式等价的NFA 构造NFA等价的DFA 化简DFA 根据DFA编写程序，实现词法分析器 提示：本部分内容占学习内容的25%， 考核内容的1/2与本部分相关 单词的描述工具 作用: 描述单词的构成规则,基于这类描述工具建立词法分析技术,进而实现词法分析程序的自动构造. 工具有: 正规文法 正规式(Regular Expression) 正规文法 多数程序设计语言单词的语法都能用正规文法(3型文法)描述 正规文法回顾 文法的任一产生式α→β的形式都为A→aB或A→a，其中A ，B∈VN ，a∈ VT 。 正规文法描述的是VT*上的正规集 例如 : 用l表示a~z中的任一英文字母，d表示0~9中任一数字 描述标识符的正规文法为 标识符→l｜l字母数字 字母数字→l｜d｜l字母数字｜d字母数字 描述无符号整数的正规文法 无符号整数→d｜d无符号整数 为什么要引进正则表达式？ 对于字母表∑，我们感兴趣的是它的一些特殊字集－正规集。 正规集是字母表Σ上的符合一定规则的符号串构成的集合 正则表达式是一种适合描述符号的表示法，可由它定义正规集。 正规式(regular expression) 定义（正规式和它所表示的正规集）： 设字母标为? 1 ?和?都是?上的正规式，它们所表示的正规集分别为{?}和?； 2 任何a? ?，a是?上的一个正规式，它所表示的正规集为{a}； 3 假定e1和e2都是