目    录
摘    要 1
ABSTRACT 2
第一章 概述 3
1.1研究背景与意义 3
1.2主要工作 4
第二章 设计开发使用的主要技术 5
2．1正则语言 5
2.1.1有穷自动机 5
2.1.2有穷自动机的形式化定义 6
2.1.3计算的形式化定义 6
2.1.4设计有穷自动机 6
2.1.5正则运算 7
2.2 非确定性 7
2.2.1   非确定型有穷自动机 8
2.2.2   非确定型有穷自动机的非形式化观点 8
2.2.3   非确定型有穷自动机的定义 8
2.2.4   确定型有穷自动机与非确定型有穷自动机的等价性 9
2.3上下文无关文法（Content-Free Grammar, CFG） 9
2.3.1形式定义 10
第三章 系统结构与建模 12
3．1 设计实现的策略---PL/0语言描述 12
3．2 PL/0编译程序的结构 14
第四章 系统实现技术 17
4.1词法分析 17
4.2语法语义分析 19
4.3目标代码结构和代码生成 22
4.4语法错误处理 23
4.5解释执行 23
参考文献 26
致谢 27

第二章  设计开发使用的主要技术
2．1正则语言
计算理论的第一个问题是：什么是计算机？
现实世界的计算机相当复杂，很难直接对他们建立一个易于处理的数学理论。因此采用称为计算模型的理想计算机来描述。同科学中的其他模型一样，一个计算模型准确地刻画了某些特征，同时忽略一些特征。因此，针对关注的特征，我们采取几个不同的计算模型。最简单的模型：有穷状态机或有穷自动机。
2.1.1有穷自动机
有穷自动机是描述能力和资源极其有限的计算机的模型。
有穷自动机作为一种识别装置，它能准确地识别正规集。即识别正规文法所定义的语言和正规式所表示的集合，引入有穷自动机这个理论正是为词法分析程序的自动构成寻找特殊的方法和工具。
有穷自动机分为两类：确定的有穷自动机（DFA）和不确定的有穷自动机（NFA）。
从数学的角度考察有穷自动机
        
图2.1一台有3个状态的有穷自动机M1
图2.1被称为M1的状态图。它有3个状态，记作q1、q2和q3。起始状态q1用一个指向他的无出发点的箭头表示，接受状态q2带有双圈。从一个状态指向另一个状态的箭头称为转移。
当这个自动机接收到输入字符串，例如1101时，他处理这个字符串并且产生一个输出。输出是接收或拒绝。处理从M1的起始状态开始。自动机从左至右一个接一个地接收输入字符串的所有符号。读到一个符号之后，M1沿着标有该符号的转移从一个状态移动到另一个状态。当读到最后一个符号时，M1产生它的输出。如果M1现在处于一个接收状态，则输出为接收否则输出为拒绝。
例如，把输入字符串1101提供给图的有穷自动机M1处理如下进行：
开始时处于状态q1。
读到1，沿着转移从q1到q2。
读到1，沿着转移从q2到q2。
读到0，沿着转移从q2到q3。
读到1，沿着转移从q3到q2。
输出接受，因为在输入字符串的末端M1处于接受状态q2。
2.1.2有穷自动机的形式化定义
定义2.1有穷自动机是一个5元组（Q,Σ,δ,q0,F），其中
Q是一个有穷集合，他的每个元素成为一个状态。
Σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称Σ为输入符号表。
δ是转换函数，是Q*Σ¬—>Q上的映像。即，如δ(qi,a)=qj (qi  Q,qj Q)就意味着，当前状态为qi,输入字符为a时，将转换到下一状态qj,我们把qj称作qi 的一个后继状态；
q0 Q,是唯一的一个初态；
F Q是一个终态集，终态也称可接受状态或结束状态。
若A是机器M接受的全部字符串集，则A是机器M的语言记L(M)=A是接受的字符串的集合。