公开课网 公开课网

当前位置:首页 > 计算机 > 专业课程 > 软件工程 > 中国科技大学编译原理和技术
中国科技大学编译原理和技术

中国科技大学编译原理和技术

  • 共50讲 更新完毕
    • 来源:中国科技大学   由陈意云主讲
    • 种类: 精品课程
    • 格式: 高清单视频 , 大小:6.71GB
    •   视频下载:会员介绍 充值学习币 |   QQ客服:1187529019  点击这里给我发消息
    • 用户评分: 8 分 我要评分: 5 分 评分次数:31 次
    在线学习(手机视频) 在线学习Media 批量下载(百度网盘)
    课程简介

       

      • 课程介绍

        一、课程发展历史概述

        编译器产生于20世纪60年代,在计算机科学技术的发展过程中发挥着巨大的作用,是开发计算机应用系统不可缺少的重要工具。编译器的原理和技术具有十分普遍的意义,在每一个计算机科技工作者的职业生涯中,这些原理和技术都被反复用到。编译器的设计涉及到形式语言和自动机理论、编程语言和类型理论、计算机体系结构、算法设计和软件工程等多个学科的知识。

        第一个编译器诞生后不久,国外就开设了编译原理课程,并且随着相关理论和技术的不断发展和完善,课程内容在不断地更新、充实和深化。例如:

        语法分析从介绍递归下降和算符优先分析方法过渡到主要介绍LR语法分析方法及语法分析器的自动生成;

        语义分析从分离地介绍各个问题的解决办法到系统地介绍基于属性文法的语法制导定义及其实现方法;

        运行时存储空间的组织和管理从静态分配、栈式分配、堆分配一直发展到增加垃圾收集算法;

        代码优化从孤立地介绍各种优化技术到突出介绍数据流分析的理论基础,强调在数据流分析的一般框架下解决各个具体数据流问题。

        编译原理课程自开设以来,一直是计算机科学技术专业学生的必修课程。

        中国科学技术大学计算机专业1958年由老一辈计算机科学家夏培肃院士等亲自创办。创办之初就参与了中科院计算所自主设计并研制成功的我国第1台通用计算机107机的研制。1980年前后就开设了编译原理课程,由中科院计算所研究人员主讲,采用他们基于开发BCY语言(类ALGOL60语言)编译器的经验编写的讲义。1982年成立计算机科学技术系时,由王汝传老师(现在是南京邮电大学博导)采用自编讲义主讲编译原理,以介绍编译器各逻辑阶段的流程图为课程的主要内容。

        1984年改由完成过Pascal语言编译器开发的陈意云老师主讲编译原理,从那时起到目前为止,编译原理课程的师资队伍中,除个别人外,都从事编程语言的理论和实现技术方面的研究工作,从而都很好地具备从事编译原理教学所需的理论和技术背景。

        中国科学技术大学计算机专业编译原理课程1984年开始采用陈火旺、钱家骅和孙永强编写的教材《程序设计语言编译原理》(国防工业出版社,1984);1987年开始在教学中补充Compilers: principles, techniques, and toolsAlfred V. Aho, Ravi Sethi Jeffrey, D. Ullman. New York: Addison-Wesley, 1986)书上有关属性文法和类型检查等方面的内容;1990年开始采用陈意云根据上述经典教材编写的教材。随着教学经验和相关科研工作的积累,对编译原理课程讲授内容和方法逐步形成自己的观点。为此,教材内容也在不断调整,现在采用的是陈意云和张昱编写的《编译原理》(高等教学出版社,第二版,2008)。

        编译原理的课程实践从1984年开始,以实现扩展PL/0语言到扩展PL/0抽象机的编译器和实现扩展PL/0抽象机的解释器为内容。这个实验的内容经不断充实,一直持续到2000年以后。2007年开始实施新的课程实践,它以“源语言-抽象语法树-低级中间表示-汇编代码的内部表示-x86/MIPS汇编”为主线搭建的课程实践体系,安排了各种循序渐进、规模适度、“综观全局、实现局部”、强调工程质量规范的课程设计,并提供配套的实验支持库和课程设计开发包。

         

        二、课程内容体系结构

        近十年来,我们基于下面观点不断进行教学内容更新、教学方法改革和教材编写:

        1强调主线:让学生在宏观上理解和全局上把握编译原理和技术比掌握一些细节算法重要得多。

        2、重视编程语言有关理论和形式方法:这对深刻理解和把握编译原理和技术是必要的。

        3、鼓励将所学理论和技术用于解决或解释实际问题:这些问题源于学生编写、编译和运行程序的实践,能激发学生学习本课程的兴趣。

        4、跟踪新技术:及时将新技术反映在教学中,利于学生了解技术的动态和发展趋势。

        课程内容粗略地可以分成如下几个板块(板块并非完全对应教材的章节):

        1、编译器各逻辑阶段的功能、接口和所采用的主要技术

        该部分包括词法分析、语法分析、类型检查(静态语义分析)、中间代码生成、代码生成和独立于机器的优化。此外,还有学习代码生成部分必不可少的运行时存储空间的组织和管理。该部分构成编译原理课程的核心。

        2、和编译技术相关的理论知识

        该部分包括形式语言和自动机理论、语法制导的定义和属性文法、类型论和类型系统、数据流分析的理论基础。这是深入把握编程语言及其实现技术的必备知识。

        3、和编译及编程相关的一些实用知识

        该部分强调编译知识与实际编写、编译和运行程序的联系,它包括:

        用编译原理的知识分析实际编写、编译和运行程序中碰到问题的例题或习题。

        编译系统和运行系统(其中无用单元收集部分因课时压缩到60学时而从未作为课堂教学内容)。

        依赖于机器的优化。依赖于体系结构的优化涉及一些复杂算法,不太可能作为本科生编译原理课程的内容,但是简要介绍现代计算机体系结构、指令调度、基本块调度、全局调度、软件流水、并行性和数据局部性优化等,会引导学生关注如何编写高效的程序。

        4、其它范型paradigm的编程语言的编译技术

        该部分简要介绍面向对象语言和函数式语言的编译(课时压缩到60学时后,函数式语言的编译未再继续作为教学内容),以拓宽对编程语言和编译技术的了解。

         

        三、教学内容组织方式与目的

        在教学内容的组织上有以下几个特点。

        1、以编译的各逻辑阶段为主线,按照它们的逻辑次序逐个介绍,这和其他学校没有什么区别。但是,我们把相关理论都穿插在这些逻辑阶段的适当位置介绍,使学生及时体会到学习这些理论的必要性。

        2、把学生的注意力集中到对编译原理和技术的宏观理解和全局把握上。对于一些枝节的算法,如计算开始符号集合和后继符号集合的算法、多态类型检查的合一算法、控制流翻译的回填技术等,仅介绍其思想而不讲具体算法,避免学生过于关注这些枝节算法。

        3、及时把编译理论和技术的发展,特别是计算机体系结构的发展对编译技术的推动等新内容补充进入教学和教材,如安全语言和类型可靠性、数据流分析的理论基础等。并及时删除过时的内容,如实际编译器已经不再使用的算符优先分析方法。目的是让学生及时了解编译理论和技术方面的最新热点。

        4、几乎每章都有理论联系实际的例题和习题,使学生体会到编译知识和日常编写、编译和运行程序是息息相关的。用编译原理的知识把这些问题分析清楚,对激发学习编译原理的热情有出人意料的效果。

        5、介绍其它范型语言的编译时,用已学技术和方法能解决的词法和语法分析、静态语义分析等都不介绍,只讲语言特征的不同给编译器设计带来的问题和解决办法。这样,花的课时不多,但对理解编程语言和学习编译技术都很有帮助。

         

        • 教学大纲

          课程名称:并行计算
          预修课程:计算机体系结构、数据结构等
          开课学期:
          总 学 时:60
          学 分:
          大纲撰写人:陈国良、徐云、孙广中

          一、教学目标及要求

          本课程是为计算机科学与技术专业的高年级本科生开设的专业课,也可作为面向科学和工程计算的非计算机专业的高年级本科生和研究生的选修课程。通过此课程的学习,可使学生了解和掌握计算机学科中以及大型科学与工程问题中的基本的并行与分布计算方法及其软硬基础。

          二、教学重点和难点

          重点:并行计算机系统结构、模型、互连方式和性能评价,并行计算模型,并行算法设计策略、基本设计技术和PCAM设计方法学,典型的并行数值算法,并行程序设计等。
          难点:并行结构模型和计算模型的理解,并行算法基本设计技术,并行数值算法等。

          三、教材及主要参考书教材

          陈国良,《并行计算:结构,算法,编程》,北京:高教出版社,1999(初版),2003(修订版)
          主要参考书:
          1.陈国良等,《并行计算机体系结构》,北京:高教出版社,2002
          2.陈国良,《并行算法的设计与分析》,北京:高教出版社,2002 (修订版)
          3.陈国良等,《并行算法实践》,北京:高教出版社,2003
          4.Barry Wilkinson等,陆鑫达等译,《并行程序设计》,北京:机械工业出版社,2001

          四、课程章节及学时分配

          第一部分 并行计算硬件基础
          1.并行计算机系统结构和模型 4课时
          (1)并行计算机系统结构(PVP、SMP、MPP、DSM、COW)。
          (2)并行计算机存储器访问模型(UMA、NUMA、COMA、NORMA)。
          2.并行计算机系统互连 4课时
          (1)系统互连技术(节点内的互连:总线,开关,Buses,switches;节点间的互连:SAN;系统间的互连:LAN,MAN,WAN)。
          (2)互连网络拓扑(静态互连网络:LA,RC,MC,TC,HC,CCC;动态互连网络:Buses,crossbar,MINI)。标准网络(FDDI、ATM、SCI)。
          3.并行系统性能评价 4课时
          (1)加速比(Amdahl负载固定加速定律;Gustafson负载可扩放加速定律;Sun和Ni存储受限加速定律)。
          (2)可扩放性(等效率;等速度;平均延迟)。
          (3)基准测试程序(数学库;并行库;商业库;SPEC库等)。
          第二部分 并行算法的设计
          1.并行计算模型(PRAM,APRAM,BSP,LogP,C3)。4课时
          2.并行算法的常用设计方法(串行算法的并行化,重新设计一个全新的并行算法,借用其它成熟算法来设计新的并行算法)。6课时
          3.并行算法的基本设计技术(划分法,平衡树法,倍增法,分治法,流水线法,破对称法等)。6课时
          4.并行算法的一般设计过程(PCAM:划分,通信,组合,映射)。4课时
          5.典型并行数值算法(稠密矩阵运算,稀疏线性方程组求解,快速富氏变换等)。10课时
          第三部分 并行程序设计
          1.并行程序设计模型(自动并行,数据并行,共享变量,消息传递)。2课时
          2.共享存储编程(ANSIX3H5,Pthreads,OpenMP,π计算)。4课时
          3.消息传递编程(MPI,PVM,π计算)。6课时
          4.数据并行编程(HPF,高斯消去法)。4课时
          5.并行程序设计环境和工具(向量化的并行化编译器,并行程序性能分析,计算可视化等)。 2课时

           

          参考文献目录

          一、并行计算系列丛书

          [1] 陈国良 编著. 并行计算-结构·算法·编程. 高等教育出版社(修订版),2003


          [2] 陈国良 编著. 并行算法的设计与分析. 高等教育出版社(修订版),2002


          [3] 陈国良 等编著. 并行计算机体系结构. 高等教育出版社,2002


          [4] 陈国良 等编著. 并行算法实践. 高等教育出版社,2003

          二、并行算法系列丛书

          [5] 陈国良 编著. 并行算法:排序和选择. 中国科大出版社,1990;台湾儒林图书公司,
          [6] 陈国良,陈崚 编著. VLSI计算理论与并行算法.中国科大出版社,1991;台湾儒林图书公司,1994
          [7] 陈国良 主编. 并行图论算法. 中国科大出版社,1991;台湾儒林图书公司,1993

          三、国外相关教材

          [8] Andrews G R. Foundations of multithreaded parallel, and distributed programming,Pearson Education, 2002
          [9] Akl S G.. The design and analysis of parallel algorithms. Prentice-Hall, Inc, 1989
          [10] Buyya R. High performance cluster computing. Prentice-Hall, Inc, 1999
          [11] Cunha J C et al. Parallel program development for cluster computing:methodology, tools and integrated environments (In advances in computation: theory and practice), Nova Science Publishers Inc, 2001
          [12] Foster I. Designing and building parallel programs: concepts and tools for parallel software engineering, Addison-Wesley, 1995
          [13] Hwang K. Advanced computer architecture: parallelism, scalability, and programmability. McGraw-Hill, 1993
          [14] Hwang K, Xu Z. Scalable parallel computing: technology, architecture, programming. WCB/McGraw-Hill Companies, 1998
          [15] JaJa J. An introduction to parallel algorithm. Addison-Wesley Pub. Company, 1992
          [16] Kumar V et al. Introduction to parallel computing: design and analysis of parallel algorithms. Benjamin/Cummings Publishing Company, Inc. 1994
          [17] Quinn M J. Parallel computing: theory and practice, McGraw-Hill, 1994
          [18] Wilkinson B. Parallel programming: techniques and applications using networked workstations and parallel computers, Prentice-Hall, Inc, 1999

          四、国内相关教材

          [19] 李晓梅 等编著. 并行算法. 湖南科技出版社,1992
          [20] 沈志宇 等编著. 并行程序设计. 国防科大出版社,1997
          [21] 孙家昶 等编著. 网络并行计算与分布式编程环境. 科学出版社,1996
          [22] 王鼎兴,陈国良编著. 互联网络结构分析. 科学出版社,1990
          [23] 徐士良 编著. 计算机常用算法(第二版). 清华大学出版社,1996
          [24] 都志辉 编著. 高性能计算并行技术—MPI并行程序设计,清华大学出版社,2001

          五、其它参考文献

    学习讨论

    发表评论:

    用户名:   Email: