文法和形式语言-Read.PPT

第三章 词法分析 《编译原理》课程组 计算机科学系网络教研室 第三章 词法分析 3.1 词法分析程序的设计 3.2 单词的描述工具 3.3 有穷自动机 3.4 正规式、正规文法和自动机的等价性 3.5 词法分析程序的自动构造 第3章 词法分析 本章将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。 【学习目标】 单词的描述工具 单词的识别系统 设计和实现词法分析程序 首先需要描述和刻画程序设计语言中的原子单位——单词，其次需要识别单词和执行某些相关的动作。 描述程序设计语言的词法的机制是正则表达式，识别机制是有穷状态自动机。 第3章 词法分析 本章重点 掌握正规式及正规式、正规文法之间的转换 掌握有穷自动机、NFA、DFA理论，以及NFA向DFA的转化和DFA的最小化 掌握正规式、正规文法和有穷自动机之间的等价转换 问题导入 词法分析的功能是什么？ 试结合你所学习过的或熟悉的程序设计语言，讨论其“单词”有哪几种？ 程序设计语言中对标识符的命名规则是如何描述的？编译程序能检查出非法的标识符吗？ 你认为词法分析程序应该如何设计和构造？ 3.1 词法分析程序的设计 3.1.1 词法 分析程序与语法分析程序的接口方式 1、实现词法分析（lexical analysis）的程序 逐个读入源程序字符并按照构词规则切分成一系列单词。单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符号和常量等。 词法分析是编译过程中的一个阶段，在语法分析前进行 。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。 2、词法分析程序的实现方案 3.1.2 词法分析程序的输出 1、词法分析程序的主要任务 读源程序，产生单词符号 2、词法分析程序的其他任务 滤掉空格，跳过注释、换行符 追踪换行标志，复制出错源程序， 宏展开，…… 3.1.2 词法分析程序的输出 3、单词的分类(通常可分为5类) 基本字(关键字、保留字)：具有特殊含义的标识符，不作他用，有分隔语法的作用； 标识符：表示各种名字； 常量：整型、实型、布尔型、字符型； 运算符：算术、逻辑、关系运算符； 界符：包括.，;，(，)，:，,等，有时也把运算符称作界符。 3.1.2 词法分析程序的输出 4、扫描器的输出格式 输出格式为二元式序列，每个单词对应一个二元式，形式为(类号，内码) 类号用整数表示，起了区分单词种类和方便程序处理的作用。类号考虑如下： (1)每个基本字占用一个类号； (2)各种标识符统一为一类； (3)常量按不同的类型分成相应的类号； (4)界符，包括运算符，通常一符一类号。 词法分析将会将一系列单词加入到符号表中。 3.1.2 词法分析程序的输出 扫描案例： if i=5 then x:=y; 3.1.3 将词法分析程序工作分离的考虑 词法结构的表示方法与识别方法 词法结构的表示方法：正则表达式 词法结构的识别方法：有穷自动机 词法分析工作从语法分析工作独立出来的原因： 简化设计，使编译程序的结构更加简洁、清晰 改进编译效率 增加编译系统的可移植性 3.2 单词的描述工具 程序设计语言中的单词是基本语法成分.单词符号的语法可以用有效的工具加以描述，并且基于这类描述工具，实现词法分析程序的自动构造. 3.2.1 正规文法 正规文法、正规集与正规式 正规文法是描述正规集的文法，它的产生式必须是： A?αB A?α , α ∈VT* (右线性文法) 或者 A?Bα A?α , α ∈VT*(左线性文法) 在一个正规文法中不允许既用右线性文法又用左线性文法。 由正规文法产生的语言称作正规集。 正规集是一个有穷或者无穷的集合，可用正规式(Regular Expression，Re)来描述。 3.2.1 正规文法 标识符的规则描述 标识符?l | l字母数字 字母数字? l | d | l 字母数字 | d 字母数字 无符号整数的规则描述 无符号整数? d | d无符号整数 3.2.2 正规式 正规式也称正则表达式，也是表示正规集的工具。 定义（正规式和它所表示的正规集）： 设字母表为?，辅助字母表?’={?，?，?，?，?，?，?}。 ?和?都是?上的正规式，它们所表示的正规集分别为{?}和{ }； 任何a? ?，a是?上的一个正规式，它所表示的正规集为{a}； 假定e1和e2都是?上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1), e1? e2, e1?e2, e1? , e2?也都是正规式,它们所表示的正规集分别为L(e1), L(e1)?L(e2)，L(e1)L(e2)， (L(e1))? 和(L(e2))? 。 仅由有限次使用上述三步骤而