关注编译原理的等价性

1、关注编译原理的等价性,赵银亮 西安交通大学 2011年5月14日,关注编译原理的等价性,在编译原理课程中，知识间存在等价关系，一定条件下恰当地利用它，能取得取得举一反三、化难为易、创新思维等教学效果，也有助于裁剪教学内容,本文提出一种应用等价关系提高教学效果的方法论。,内容,问题的提出 知识的层次组织 一种教学方法论 教学中的应用 结语,1. 引言,在教学中，我们常常会使用断言：“甲与乙是一样的”，“甲乙二者是等价的”等等。,建立知识之间的联系，有助于对知识进行组织，构建知识框架； 减轻记忆的负担，即本来对“甲”和“乙”的细节需要分别地记忆，现在二者被等价关联起来，有大量细节不必重复记忆了；,在教学中，我们常常会使用断言：“甲与乙是一样的”，“甲乙二者是等价的”等等。,便于知识的灵活运用。例如原来使用“甲”知识解决的问题换做用“乙”知识去求解或许是一条更加简洁有效的途径；另外，求解某问题时，可用的知识从原来的一种增加到两种，理论上增加了求解成功的可能性； 便于突出重点，对于等价的知识，可以从其他的适合性角度做出选择，不使总的知识量过于膨胀。,在教学研究中常用,举一反三（等效思维） 在效

2、果相同的前提下，把实际的、难于理解的问题变成理想的、易于思考的问题 化难为易（等价转化） 使一种研究对象在一定条件下转化为另一种研究对象的数学思想称为等价转化思想，能运用所学的知识把复杂的问题转换为较简单的问题解决 创新思维（等值变换） 等值变换法是从已有的事物中，通过模拟、借鉴、产生联想来改变原来的对象而进行创造的方法 ，如：蚕变成飞蛾、桑叶变成蚕丝,存在的问题,关注等价性的教学方法广为人们所接受 但是属于概念和经验层面 缺方法论,针对编译原理课程中的知识，构造了一种关注知识等价性的教学方法论，并初步应用于教学实践。,2.知识的层次组织,知识单元 知识抽象 知识单元间等价关联 等价关系的抽象,知识单元,知识单元：问题域中用于阐述或解决问题的概念、算法、定理等；内容上独立、完整,简单栈式活动记录,嵌套过程活动记录,访问连,D表,变长参数,过程参数,知识个体、实例 例：对 ，调调排列位置，确定调用序列、返回序列代码,例：栈帧知识单元,参个,访问链,控制链,返址,空白,fp,sp,参个,静态链,控制链,返址,形参 ,top,sp,局变 ,形参 ,局变 ,空白,D表指针,D表,临时单元,超长

3、局变 变长局变,a),b),d),c),知识单元的抽象,抽象为层次结构。 编译知识典型分为三层：理论、方法、实现,理论层,方法层,实现层,K1,K2,K3,K4,K5,K6,知识抽象的形式定义,编译原理知识单元全集 知识抽象关系的全集,（1）(:), 是上严格偏序关系 （2）1, 2, K, K1 (K, K1)1(K1, K)2, (K, K1)2(K1, K)1,知识的层次结构,给定A，按照A把的知识单元组织成为一个层次结构，当A=时，所得到的层次结构是完全的。在知识的层次结构组织中，上层知识单元是下层知识单元的抽象。层次结构的底层是程序代码，顶层是一些特殊的知识单元。,栈帧相关知识单元抽象,过程调用语义,栈帧,静态连,D表,变长参数,过程闭包,程序代码,理论层,方法层,实现层,知识单元之间的等价关系,有三类等价关系。,K,K,K1,K2,1,2,K1,K2,a),b),c),栈帧相关知识单元抽象,过程调用语义,栈帧,静态连,D表,变长参数,过程闭包,程序代码,理论层,方法层,实现层,K,K,K1,K2,1,2,K1,K2,等价关系的抽象,等价关系的抽象采用等价性金字塔表示，用于解

4、释两个知识单元为什么是等价的,(R0: ) = ,S,Q,R,P,S,Q,R,P,S, (x,y)S (x,y)Q,SQR,在某一抽象层次以上看是等价的，否则不是等价的,如果两个知识单元在较高抽象层次上等价，则它们之间的共性的东西少，否则共性多,S,Q,R,P,(x,y)Q (x,y)S,在等价性金字塔的某个位置，若两个知识单元是等价的，则在这个位置之上的其它位置，这两个知识单元仍然是等价的,3. 关注知识等价性的教学方法论,K, (:KK), 给定aK找出ba,K1,K2, , (K1)=(K2), (:K1K2), 给定aK1可以得出(a)K2,K1,K2, , K1=(K2), (:K2K1), 给定aK1可以得出-1(a)K2,K1,K2, , K1=(K2), (:K2K1), 给定aK2可以得出(a)K1,教学效果：举一反三,其含义是从知识单元的一些知识实例出发能够找出等价的另一些知识实例，体现了举一反三的效果。,K,例：对栈帧 ，任意排列位置，确定调用序列、返回序列代码 ： 对代码的要求等,教学效果：化难为易,从K1 到K2；从K2到K1,K,K1,K2,1,2,从上往下

5、：从理论到实现 从下往上：从具体中总结出规律,S,Q,R,P,教学效果：创新思维,从上往下：从理论到实现 从下往上：从具体中总结出规律 从已知到未知,K1,K2,过程调用语义,活动记录,程序代码,理论层,方法层,实现层,4. 关注等价性的教学实践,过程调用语义与栈帧的等价性 正规式、正规文法和有穷自动机的等价性 属性文法、翻译模式等价性 名字作用域与层次符号表等价性,正规式正规文法有穷自动机知识单元,r,DFA,Lex,自下而上,scanner,parser,matcher,理论层,方法层,实现层,M,G,NFA,GL,GR,自上而下,r、G、M,S: L(r)=L(G)=L(M),R：相互等价转换,Q： sL(r)当且仅当s与r进行模式匹配成功 sL(G)当且仅当s由G的开始符号推导出 sL(M)当且仅当s由对M执行得到,P：matcher, scanner, parser 之间的等价,等价关系Q,Q： sL(r)当且仅当s与r进行模式匹配成功 sL(G)当且仅当s由G的开始符号推导出 sL(M)当且仅当s由对M执行得到,s与r的模式匹配是陈述性的，s不是结构化的，r是对L(r)的概

6、括（模式） 由G的开始符号推导出s是过程性的，可能有回溯，s是结构化的（结构是指非终结符） 执行M得到s，这是过程性的，没有回溯，便于程序实现，s不是结构化的,属性文法与翻译模式知识单元,AG,与LR集成,与LL集成,理论层,方法层,实现层,SDT,后缀式SDT,语义分析程序,SDT A123 后缀式SDT AM1M23；M11；M22 AG M11；A1M12；AA13,等效思维举一反三可以描述为寻找等价的AG（SDT或后缀式SDT），差别是采用的属性不同（文法符号的不同属性、属性值的不同计算方法、对翻译结果的不同表示，对翻译结果的优化等），或者对语法做不同修剪。 等价转化化难为易可以描述为AG、SDT和后缀式SDT之间等价转化，差别是对文法修剪的程度、对左递归和回溯的处理、非终结符有无语法意义等。 等值变换创新思维可以描述为理论层的三种知识单元如何集成到语法分析模型中，以及进一步实现在语义分析程序中。,作用域知识单元,P,y:,Q,x:,:x,:y,:y,:y,y,Q,x,结语,在教学中，基于知识抽象的知识单元层次结构能够用于有效组织编译原理课程中的理论、方法和实现层面上的知识，而知识单元之间存在的等价关系抽象为等价性金字塔表示，可以解释任意知识在一定抽象层次之上都存在等价关系。在此基础上提出的关注知识等价性的教学方法论，确定性地表达了举一反三、化难为易、创新思维等教学效果。已有的教学实践反映出这种等价教学法的可用性和有效性。 进一步工作是在课程实践中归纳出更多的等价关系并进行性能评估。,谢谢指正！,

《关注编译原理的等价性》由会员小**分享，可在线阅读，更多相关《关注编译原理的等价性》请在金锄头文库上搜索。