一个完整的编译程序还必须包括“表格管理”和“出错处理”两部分。一个编译程序在编译过程中应尽量找出源程序中的错误，向用户提供更多更准确的与错误有关的信
图3 编译程序结构框图
息，以便用户查找和纠正。一个典型的编译程序结构框图如图1.3所示。词法分析是实现编译器的基础，语法分析是实现编译器的关键。本书将按照这个顺序来讲述编译程序各个阶段涉及到的基本理论、实现方法和技术。
4 编译器的构造及编译技术的应用
1 如何构造一个编译程序
要在一台机器上为某种语言构造一个编译程序，必须从下述三方面入手： (1) 源语言：是编译程序处理的对象。对被编译的源语言要深刻理解其结构和含义，即该语言的词法、语法和语义规则，以及有关的约束和特点；
(2) 目标语言与目标机：是编译程序处理的结果和运行环境。目标语言是汇编语言或机器语言，必须对硬件系统结构，操作系统的功能，指令系统等很清楚；
(3) 编译方法与工具：是生成编译程序的关键。必须准确掌握把一种语言的程序翻译为另一种语言的程序的方法之一。同时应考虑所使用的方法与既定的源语言、目标语言是否相符合、构造是否方便，从时间、空间上考虑是否高效、实现的可能性和代价等诸多因素，并尽可能考虑使用先进、方便的生成工具。
2 编译程序的实现方式
编译程序本身也是一个程序，那怎样实现它呢？从理论上讲，基本上可以用任意语言来实现。早期人们用机器语言或汇编语言手工编写；为了充分发挥硬件资源的效率，满足各种不同的要求，许多人目前仍然采用低级语言编写；但由于
编译器本身是一个十分复杂的系统，用低级语言编写效率很低，现在越来越多的人使用高级语言来编写，这样可以节省大量的程序设计时间，且程序易读、易修改和移植；为了进一步提高开发效率和质量，可以使用一些自动生成工具来支持编译器某些部分的自动生成，如词法分析生成器LEX和语法分析生成器YACC等。
概括起来，生成编译程序的方法有：
1．直接用机器语言或汇编语言编写（编译程序核心部分常用汇编语言编写）； 2．用高级语言编写编译程序（这是普遍采用的方法）； 3．自编译；
4．用编译工具自动生成部分程序：LEX（词法分析）与YACC（用LALR分析
方法自动生成语法分析器）；
5.移植（同种语言的编译程序在不同类型的机器之间移植）。
用高级语言编写编译程序当然离不开高级语言的程序开发环境。目前常用的高级语言集成开发环境环境有Basic开发环境VB、C和C++开发环境VC++、C#开发环境VC#等。
3 编译技术的应用
为了提高软件开发效率、保证质量，在软件工程中除了遵循软件开发过程的规范或标准外，还尽量使用先进的软件开发技术和相应的软件工具。而大部分软件工具的开发，常常要用到编译技术和方法，实际上编译程序本身也是一种软件开发工具。为了提高编程效率，缩短调试时间，软件工作人员研制了不少对源程序处理的工具，这些工具的开发不同程度地用到了编译程序各个部分的技术和方法。下面是常用的软件工具：
语言的结构化编辑器 结构化编辑器不仅具有通常的正文编辑器的正文编辑和修改功能，而且还能像编译程序那样对源程序正文进行分析。这类产品有Turbo-Edit、editplus和Ultraedit等。
语言程序的调试工具 结构化编辑器只能解决语法错误的问题，而对一个已通过编译的程序来说，需进一步了解的是程序执行的结果与编程人员的意图是否一致、程序的执行是否实现了预期的算法和功能。对算法错误或程序不能反应算法的功能的检查就需要调试工具来完成。调试功能越强，实现就越复杂，它主要涉及源程序的语法分析和语义处理技术。
语言程序的测试工具 语言程序的测试工具有两种：静态分析器和动态测试器。静态分析器是对源程序进行静态的分析，它对源程序进行语法分析并制定相应表格，检查变量定值与引用关系，如检查某变量未被赋值就引用，或定值后未被引用，或多余的源代码等一些编译程序的语法分析发现不了的错误；动态测试
工具是在源程序的适当位置插入某些信息，并用测试用例记录程序运行时的实际路径，将运行结果与期望的结果进行比较分析，帮助编程人员查找问题。这种测试工具在国内已有开发，如FORTRAN和C语言的测试工具。
高级语言之间的转换工具 由于计算机硬件的不断更新换代，更新更好的程序设计语言的推出为提高计算机的使用效率提供了良好的条件。然而一些已有的非常成熟的软件如何在新机器新语言情况下使用呢？为了减少重新编制程序所耗费的人力和时间，就要解决如何把一种高级语言程序转换成另一种高级语言程序，乃至汇编语言程序如何转换成高级语言程序的问题。这种转换工作要对被转换的语言进行词法和语法分析，只不过生成的目标语言是另一种高级语言而已。这比实现一个完整的高级语言编译程序相比工作量要少些。目前已有成熟的转换系统。
交叉编译程序 随着嵌入式技术的发展和广泛应用，嵌入式软件开发环境所涉及的关键技术是多目标交叉编译和调试工具。这些工具希望在宿主机上为源语言交叉编译生成多个目标板上的目标程序，并能对目标机上运行的程序进行调试。
第2章 词法分析
主要内容：
1 词法分析器设计方法
2 一个简单的词法分析器示例 3 正规表达式与有限自动机简介 4 正规表达式到有限自动机的构造 5 词法分析器的自动生成
词法分析是编译的第一个阶段，其任务是从左至右逐个字符的对源程序进行扫描，产生一个个单词符号，把字符串形式的源程序改造成单词符号串形式的中间程序。
词法分析的工作主要依据语言的构词规则，描述构词规则的有效工具是正规式和有限自动机。
状态转换图
状态转换图是有限的有向图，结点代表状态，用圆圈表示；结点之间可由有
向边连接，有向边上可标记字符。
正规表达式和有限自动机
字母表?, 定义在? 上的正规式和正规集递归定义如下:
1. ?和?都是? 上的正规式, 它们所表示的正规集分别为:{?}和?; 2. 任何a? ? , a是? 上的正规式,它所表示的正规集为:{a}; 3. 假定U和V ? 上的正规式, 它们所表示的正规集分别记为L(e1) 和L(e2), 那么e1|e2, e1?e2和e1*也都是? 上的正规式, 它们所表示的
正规集分别为L(e1) ?L(e2)、 L(e1) ? L(e2)和(L(e1))* 4. 任何? 上的正规式和正规集均由1、2和3产生。 1.确定的有限自动机（DFA）
M=(Σ, Q, f,?S, Z)
Σ：有穷字母表，它的每个元素称为一个输入符号 Q：有穷集，它的每个元素称为一个状态 S∈K，是唯一的初态
Z ? K是一个终态集，终态也称可接受状态或结束状态 f是转换函数，是Q×Σ→Q上的单值映射： f（q1，a）=q2
2.不确定的有限自动机（NFA）
M=(Σ, Q, f,?S, Z)
f是一个多值函数，是从Q×Σ*到Q的子集的映射： f：Q×Σ→2Q
其中2Q是Q的幂集，即Q中所有子集组成的集合。 3.状态转换图与状态转换矩阵
DFA和NFA都可以用状态转换图表示。假定DFA有m个状态n个输入字符，则这个状态转换图含有m个状态，每个状态最多有n条输出边与其他状态相连接。 DFA和NFA可以用状态转换矩阵表示。 正规表达式到有限自动机的构造
（1）对于字母表Σ上的NFA M，可以构造一个Σ上的正规式R，使得L(R)=L(M)； （2）对于字母表Σ上的每个正规式R，可以构造一个Σ上的NFA M，使得L(M)=L(R)。 正规式R?NFA M
（1）对NFA M构造一个广义的状态图，其中只有一个初态S和终态Z，连接S
和Z的有向弧标记为正规式。
（2）对正规式依次进行分解，分解的过程是一个不断加入结点和弧的过程，直到转换图上的所有弧标记上都是字母表Σ上的元素或?为止。 词法分析器的自动生成： LEX的源程序
一个LEX源程序主要由三个部分组成 说明部分 －－可选 %% －－必须有
识别规则 －－必须有（LEX的核心） %% －－可选 辅助过程 －－可选
1、说明部分:变量、常量说明和正规式定义
正规式定义格式如下： D1 R1 D2 R2 ∶ ∶ Dn Rn
2、识别规则：是一串如下形式的LEX语句：
R1 {A1} R2 {A2} ∶ ∶ Rm {Am} Ri ：正规式
{Ai}：Ai为语句序列，在识别出单词Ri以后，词法分析器所应作的动作。 其基本动作是返回单词的类别编码和单词值。 3、辅助过程:用户定义的子程序
下面是识别C语言部分单词符号的LEX源程序： /*说明部分*/
digit [0-9] letter [A-Za-z]
id ({letter}|[_])({letter}|{digit}|[_])*