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

《《编译原理》课程内容中的离散 数学基础理论还原,离散数学论文.docx》由会员分享，可在线阅读，更多相关《《编译原理》课程内容中的离散 数学基础理论还原,离散数学论文.docx（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 (编译原理）课程内容中的离散 数学基础理论还原,离散数学论文离散数学是当代数学的一个重要分支，也是计算机科学与技术的理论基础，所以又称为计算机数学。 离散数学研究离散量的构造及其互相关系，通过离散数学的学习，不但能够把握处理离散构造的描绘叙述工具和方式方法，为后续课程的学习创造条件，而且能够提高抽象思维和严格的逻辑推理能力，为将来介入创新性的研究和开发工作打下坚实的基础。离散数学在各学科领域，十分在计算机科学与技术领域有着广泛的应用，离散数学是很多计算机相关专业课的先行课程，例如(数据构造、(算法分析与设计、(计算机网络、(操作系统、(数据库、(软件工程，当然也包括(编译原理或称(编译方式方

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

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

4、并且能够在致力于提高学生在编译技术方面的动手能力的同时，加强学生的数学理论修养和数学意识。因此，本文将致力于从(编译原理课程内容中复原离散数学原理，提高学生对这两门课的学习兴趣，谈到的离散数学内容包括数理逻辑、关系理论、图论和代数系统。 1、等价原理复原 等价是数学的一个基本原理，是替换定理的理论根据。在离散数学内容中，多处牵涉到等价原理，包括集合相等关系、逻辑恒等式、等价关系、图同构、代数系统同构等。实际上，在程序设计语言的编译原理很多课程内容中皆可复原出等价原理。 形式文法作为(编译原理的最重要理论基础，也是表示语言规则的一种重要手段，华而不实有文法等价的定义，如定义1所示。 定义1：假如

5、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化简的理论根据。 能够复原等价原理的(编译原理课程内容还有很多，主要是对于同一内涵的不同外延表示形式，

6、例如中间代码的逆波兰式、三元式、四元式以及树形等。针对词法规则，(编译原理课程内容中至少有正规文法、正则式和有穷自动机三种表示形式，它们互相间都是等价的。实际上，这些等价性也是语言规则三种不同表示方式方法文法、正则式与有穷自动机互相转换的理论根据。 2、演绎与归纳复原 (离散数学的数理逻辑中最重要的内容就是逻辑推理，由前提出发，采用相应的逻辑恒等式、永真蕴涵式、推理规则、推理方式方法等进行不停地推导，最终得到结论，这是一个严格的演绎分析经过，图2(a)就是一个典型的数理逻辑中的逻辑推理经过。对于表示语言的形式文法而言，需要通过推导经过得到语言的句型或句子；文法的推导经过实际上就是离散数学的逻辑

7、推理经过，从文法的开场符号前提出发，利用文法规则产生式永真蕴涵式，采用相应的推理方式方法最左或最右推导，最终得到句型或句子结论。图2(b)就是根据形式文法进行句子 i*i+i 的一个典型最左推导经过，文法推导实际上对应自顶向下的分析方式方法，当然在这一分析经过中，可能会牵涉到递归和回溯。 在推理证明中还有一种常用的证明方式方法，那就是从要求证的结论出发，依次为其找到相应的逻辑恒等式、永真蕴涵式、推理规则等作为结论的根据，即从结论出发追根究底到前提，这是一种典型的归纳逻辑。在编译原理的语法分析中，除自顶向下的分析方式方法外，还有一类自底向上的分析方式方法，即从要得到的句型或句子出发，利用文法产生

8、式规则和推理方式方法，进行不停的归约，一直到开场符号或直失败，这是一个明显的归纳逻辑推理经过，对应最右推导。表1就是图4(b)的GE文法采用自底向上的分析方式方法对句子 i+i*i 的归约经过，这里的底指句子 i+i*i ；实际上，从步骤10至2就是从开场符号出发得到最终句子的最右推导经过，如此图4(c)所示。 3、图论复原 编译原理的很多内容中都使用了形式化技术，最典型的就是使用产生式规则表示形式文法以及用状态图来描绘叙述有穷自动机，如此图1所示。编译原理中具体表现出形式化的最重要的内容就是使用语法树来对应文法的句型或句子的推导经过，图2(b)的最左推导经过对应语法树图3(a)，而图2(c)

9、的最右推导经过对应语法树图3(b)。 除以上提到的形式文法、有穷自动机状态图以及语法树外，编译原理内容中与离散数学图论严密相关的内容还包括： 1LL(1)文法FIRST集、FOLLOW集计算中使用的关系图；2算符优先文法FIRSTVT集、LASTVT集计算中使用的关系图；3算符优先文法的优先函数关系图；4LR类文法中辨别活前缀的有穷自动机；5描绘叙述语法树中属性之间信息流和语义规则的依靠图；6抽象语法树；7表示出式描绘叙述时使用的有向无环图；8空间栈式分配中的活动树；9使用图着色方式方法进行托存器分配；10基本块有向图中的遍历。 4、代数系统复原 编译原理的处理对象是语言，课程基础内容为形式文

10、法和有穷自动机，既能够表示于产生语言，可以以计算语言。实际上，编译程序中随处都具体表现出了计算思维。在语言中，表示出完好意义的基本单位是句子，而在符号系统中，句子就是字符串；因此，字符串计算在编译原理中尤其重要。 在编译原理中，语言被定义为句子的集合，假设将语言指定为集合 *，则 *与定义在其上的计算则可构成代数系统。假设考虑语言符号串集合 *上的连接运算，显然连接运算 在语言 *上是封闭的，因此， *， 为代数系统。 对于 *上任意三个句子x，y，z，x y z=xy z=xyz=x yz=x y z，连接运算 在语言 *上知足结合律，因此， *， 为半群。对于语言 *上的空串空字、空白&e

11、psilon;，显然，ε x=x=x ε，ε为半群 *， 的单位元幺元，则 *， 为含幺半群。 在编译原理中，除形式文法外，正规式可以以表示规则，正规式与定义其上的运算可以以构成代数系统。 实际上，广义来讲，有穷自动机、语法树等都能够作为运算对象，根据定义其上的运算，尤其是转换，都能够讨论它们独有的代数系统。 5、结束语 本文考察了(编译原理课程的形式文法、有穷自动机、语法分析、形式化以及语言运算等内容，关键是要通过对这些课程内容的讨论与分析，获取并复原隐含华而不实的离散数学原理，这些原理包括等价、演绎与归纳、图论以及代数系统。通过复原(编译原理

12、课程内容的离散数学原理，让计算机相关专业的大学生认识到离散数学课程在后续的专业课中的重要地位，激发离散数学和编译原理的学习兴趣，进而提高离散数学修养，具有成熟的离散数学意识。 以下为参考文献： 1傅彦，顾小丰，王庆先等.离散数学及其应用M.北京:高等教育出版社,2007 2屈婉玲，王元元，傅彦等.(离散数学课程教学施行方案J.中国大学教学,2018(1):3941 3何炎祥.编译原理第三版M.武汉：华中科技大学出版社，2018 4何炎祥，伍春香计算机专业不需要编译原理课程吗?J计算机教育，2018(4)：6162，85 5张素琴，吕映芝，蒋维杜等.编译原理第2版M.北京:清华大学出版社,2018 6王挺，李梦君，周会平.对编译原理课程教学中计算思维培养的讨论J.计算机教育,2018(21)：1113