Javac (J2SE) 编译器的词法分析介绍.pdf

第二章 词法分析 1 2.1 单词符号的定义 3 2.2 词法分析程序的基本数据结构 4 2.3 词法分析程序的初始化 7 2.4 扫描下一个字符 8 2.5 扫描下一个符号 9 2.6 滤除源程序中注释 14 2.7 读取一个标识符 15 2.8 读取一个数值常量 16 2.9 词法分析程序运行实例 17 3.0 词法分析程序小结 19 第二章第二章 词法分析词法分析 第二章第二章 词法分析词法分析 将高级语言翻译成较低级的、面向机器的汇编语言或者某种中间表示，是一件非常复杂 和困难的事情。自从IBM 的计算机科学家第一次实现Fortran 语言的编译器以来，全世界的 计算机科学家对编译的技术进行了长期的研究和探索，总结出了一套行之有效的、对一般的 高级程序设计语言普遍适用的翻译方法。这套方法的主要思想就是，把高级语言的翻译这个 大问题划分为若干个相对容易解决的小问题，然后采用分而治之的策略逐个给出解决的方 法。该划分一般是把编译器的主要任务分为：词法分析，语法分析和语义分析。其中词法分 析要解决的问题是：从输入文件中读取字符形式的高级语言源程序，并把输入转化为一个由 单词符号组成的流供语法分析部分进一步分析。这样使语法分析部分不必关心，例如单词符 号如何组成，这样的细节问题，从而简化了语法分析的设计。 词法分析程序要完成的工作有： 过滤掉源程序中空白字符和注释，因为这些信息仅仅增加了源程序的可读性便于程序员 阅读和维护程序，而对于语法分析是完全无用的。 识别各种常量，并且把字符形式的表示翻译成编译器的内部表示。 识别标识符和关键字 识别源程序中的各种符号 程序设计语言的单词符号可以用乔姆斯基 3 型文法，也即正则文法描述。所谓正则文法， 其产生式集合中仅含有如下形式的产生式： α→β α∈Vn, β=a 或者β=aB 其中 a∈Vt, B∈Vn 由这种文法所产生的语言被认为是正则的。由形式语言和自动机理论可知，正则文法与 正则表达式是等价的，并且正则文法所描述的语言可以用一种有穷自动机来识别。 下面是正则表达式的递归定义： （1） Φ是一个表示空集的正则表达式 （2 ） ε是一个正则表达式，它所表示的语言仅包含一个空符号串，即{ε} （3 ） a 是一个正则表达式，a∈Vt。它所表示的语言是由单个符号所组成的，即{a} （4 ） 如果 e1 和e2 是正则表达式，其表示的语言分别为L1 和 L2，则： （e1）|（e2）是一个表示语言L1∪L2 的正则表达式 （e1）（e2）是一个表示语言 L1L2 的正则表达式 * {e1}是一个表示语言 L1 的正则表达式 确定性有穷自动机，简称作DFA ，它的定义如下。 一个确定性有穷自动机 M 是一个五元式： M= （Q,Vt, δ,q0,F） 其中： Q ：有穷状态集合 Vt ：输入符号表 δ：状态转换函数，为 QⅹVt→Q 的映射 q0：初始状态，q0∈Q F:终止状态集，F⊆ Q 非确定性有穷自动机，简称NFA，它的定义如下。 一个非确定性有穷自动机 M’是一个五元式： M’= （Q,Vt ∪{ ε}, δ,q0,F） 其中： Q ：有穷状态集合 Vt ∪{ ε}：输入符号表与空符号串组成的集合 δ：状态转换函数，为 QⅹVt ∪{ ε}→2Q Q 的映射，2 表示 Q的幂集 q0：初始状态，q0∈Q F:终止状态集，F⊆ Q 词法分析程序一般来说比较简单，很容易手工编程实现。另一种方法就是利用lex 等自 动生成