《编译原理》课程内容中的离散 数学基础理论还原

　　0　引言

　　离散数学是现代数学的一个重要分支，也是计算机科学与技术的理论基础，所以又称为计算机数学。

　　离散数学研究离散量的结构及其相互关系，通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。离散数学在各学科领域，特别在计算机科学与技术领域有着广泛的应用，离散数学是很多计算机相关专业课的先行课程，例如《数据结构》、《算法分析与设计》、《计算机网络》、《操作系统》、《数据库》、《软件工程》，当然也包括《编译原理》（或称《编译方法》）课程。

　　编译程序是计算机的重要系统软件，是高级程序设计语言的支撑基础，《编译原理》主要承担了语言实现原理、方法和技术的介绍，《编译原理》是计算机相关专业的一门重要专业基础课。《编译原理》课程内容除了形式语言、有穷自动机等编译原理所涉及的基础知识外，其他内容基本上围绕处理程序设计语言的编译程序应该具有的各功能模块展开，包括词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成等。《编译原理》在理论、技术、方法上都对学生提供了系统而有效的训练，有利于提高软件人员的素质和能力。《编译原理》的先行课包括《高级程序设计语言》、《计算机组成原理》、《数据结构》等，当然还有为编译原理提供数学基础的《离散数学》。

　　作为计算机科学与技术数学理论基础的《离散数学》，不仅描述了计算机科学离散性的特点，而且着力于培养与提高学生的抽象思维能力与严格的逻辑推理能力；《编译原理》在将程序语言编译原理和技术应用于实践,注重提高学生的动手能力的同时，更应该重视学生理论基础的巩固和形式思维能力的培养，这一点正需要离散数学来补充。因此，需要将《编译原理》中的离散数学基础知识还原，以加深对离散数序与编译原理关系的理解，进而体现离散数学基础知识的应用。

　　将编译原理与离散数学结合，不仅可以让学生了解离散数学理论在编译技术中的应用，让学生知道编译原理与离散数学原理的对应关系，加深学生对离散数学原理的理解；并且可以在致力于提高学生在编译技术方面的动手能力的同时，加强学生的数学理论修养和数学意识。因而，本文将致力于从《编译原理》课程内容中还原离散数学原理，提高学生对这两门课的学习兴趣，谈到的离散数学内容包括数理逻辑、关系理论、图论和代数系统。

　　1、等价原理还原

　　等价是数学的一个基本原理，是替换定理的理论依据。在离散数学内容中，多处涉及到等价原理，包括集合相等关系、逻辑恒等式、等价关系、图同构、代数系统同构等。实际上，在程序设计语言的编译原理很多课程内容中皆可还原出等价原理。

　　形式文法作为《编译原理》的最重要理论基础，也是表示语言规则的一种重要手段，其中有文法等价的定义，如定义1所示。

　　定义1：如果L(G1)=L(G2)，则称文法G1和G2是等价的，其中L(G1)表示由文法G1生成的语言。有穷自动机是《编译原理》的另一个重要理论基础，也可以表示语言中句子的生成过程，其中包含了有穷自动机等价的定义，如定义2所示。

　　定义2：对于任意两个有穷自动机M1和M2，如果L(M1)=L(M2)，则称M1与M2是等价的，其中L(M)表示由有穷自动机M生成的语言。图1中的非确定有穷自动机NFAM1和确定有穷自动机DFAM2就是两个等价的有穷自动机。有穷自动机的等价关系是NFA转换为DFA、DFA化简的理论依据。

　　可以还原等价原理的《编译原理》课程内容还有很多，主要是对于同一内涵的不同外延表示形式，例如中间代码的逆波兰式、三元式、四元式以及树形等。针对词法规则，《编译原理》课程内容中至少有正规文法、正则式和有穷自动机三种表示形式，它们相互间都是等价的。实际上，这些等价性也是语言规则三种不同表示方法（文法、正则式与有穷自动机）相互转换的理论依据。

　　2、演绎与归纳还原

　　《离散数学》的数理逻辑中最重要的内容就是逻辑推理，由前提出发，采用相应的逻辑恒等式、永真蕴涵式、推理规则、推理方法等进行不停地推导，最终得到结论，这是一个严格的演绎分析过程，图2(a)就是一个典型的数理逻辑中的逻辑推理过程。对于表示语言的形式文法而言，需要通过推导过程得到语言的句型或句子；文法的推导过程实际上就是离散数学的逻辑推理过程，从文法的开始符号（前提）出发，利用文法规则产生式（永真蕴涵式），采用相应的推理方法（最左或最右推导），最终得到句型或句子（结论）。图2(b)就是根据形式文法进行句子“i*i+i”的一个典型最左推导过程，文法推导实际上对应自顶向下的分析方法，当然在这一分析过程中，可能会涉及到递归和回溯。

　　在推理证明中还有一种常用的证明方法，那就是从要求证的结论出发，依次为其找到相应的逻辑恒等式、永真蕴涵式、推理规则等作为结论的依据，即从结论出发追本溯源到前提，这是一种典型的归纳逻辑。在编译原理的语法分析中，除自顶向下的分析方法外，还有一类自底向上的分析方法，即从要得到的句型或句子出发，利用文法产生式规则和推理方法，进行不停的归约，一直到开始符号或直失败，这是一个明显的归纳逻辑推理过程，对应最右推导。表1就是图4(b)的G[E]文法采用自底向上的分析方法对句子“i+i*i”的归约过程，这里的底指句子“i+i*i”；实际上，从步骤10至2就是从开始符号出发得到最终句子的最右推导过程，如图4(c)所示。

　　3、图论还原

　　编译原理的很多内容中都使用了形式化技术，最典型的就是使用产生式规则表示形式文法以及用状态图来描述有穷自动机，如图1所示。编译原理中体现形式化的最重要的内容就是使用语法树来对应文法的句型或句子的推导过程，图2(b)的最左推导过程对应语法树图3(a)，而图2(c)的最右推导过程对应语法树图3(b)。

　　除以上提到的形式文法、有穷自动机状态图以及语法树外，编译原理内容中与离散数学图论紧密相关的内容还包括：

　　（1）LL(1)文法FIRST集、FOLLOW集计算中使用的关系图；（2）算符优先文法FIRSTVT集、LASTVT集计算中使用的关系图；（3）算符优先文法的优先函数关系图；（4）LR类文法中识别活前缀的有穷自动机；（5）描述语法树中属性之间信息流和语义规则的依赖图；（6）抽象语法树；（7）表达式描述时使用的有向无环图；（8）空间栈式分配中的活动树；（9）使用图着色方法进行寄存器分配；（10）基本块有向图中的遍历。

　　4、代数系统还原

　　编译原理的处理对象是语言，课程基础内容为形式文法和有穷自动机，既可以表示于产生语言，也可以计算语言。实际上，编译程序中随处都体现了计算思维。在语言中，表达完整意义的基本单位是句子，而在符号系统中，句子就是字符串；因而，字符串计算在编译原理中尤其重要。

　　在编译原理中，语言被定义为句子的集合，假设将语言指定为集合∑*，则∑*与定义在其上的计算则可构成代数系统。假如考虑语言（符号串集合）∑*上的连接运算，显然连接运算“·”在语言∑*上是封闭的，因而，<∑*，·>为代数系统。

　　对于∑*上任意三个句子x，y，z，（x·y）·z=xy·z=xyz=x·（yz）=x·（y·z），连接运算“·”在语言∑*上满足结合律，因而，<∑*，·>为半群。对于语言∑*上的空串（空字、空白）ε，显然，ε·x=x=x·ε，ε为半群<∑*，·>的单位元（幺元），则<∑*，·>为含幺半群。

　　在编译原理中，除形式文法外，正规式也可以表示规则，正规式与定义其上的运算也可以构成代数系统。

　　实际上，广义来讲，有穷自动机、语法树等都可以作为运算对象，根据定义其上的运算，尤其是转换，都可以讨论它们独有的代数系统。

　　5、结语

　　本文考察了《编译原理》课程的形式文法、有穷自动机、语法分析、形式化以及语言运算等内容，关键是要通过对这些课程内容的讨论与分析，获取并还原隐含其中的离散数学原理，这些原理包括等价、演绎与归纳、图论以及代数系统。通过还原《编译原理》课程内容的离散数学原理，让计算机相关专业的大学生认识到离散数学课程在后续的专业课中的重要地位，激发离散数学和编译原理的学习兴趣，进而提高离散数学修养，具有成熟的离散数学意识。

　　参考文献：
　　[1]傅彦，顾小丰，王庆先等.离散数学及其应用［M］.北京:高等教育出版社,2007
　　[2]屈婉玲，王元元，傅彦等.《离散数学》课程教学实施方案［J］.中国大学教学,2011(1):39~41
　　[3]何炎祥.编译原理（第三版）［M］.武汉：华中科技大学出版社，2010
　　[4]何炎祥，伍春香．计算机专业不需要编译原理课程吗?[J]．计算机教育，2009(4)：61~62，85
　　[5]张素琴，吕映芝，蒋维杜等.编译原理（第2版）［M］.北京:清华大学出版社,2011
　　[6]王挺，李梦君，周会平.对编译原理课程教学中计算思维培养的探讨［J］.计算机教育,2009(21)：11~13