《编译原理》教学大纲

课程代码

045100293

课程名称

编译原理

英文名称

Principles of Compilers

课程类别

专业基础课

课程性质

必修

学时

总学时:56实验学时:16

学分

3.0

开课学期

第四学期,第三学期

开课单位

计算机科学与工程学院

适用专业

计算机科学与技术,网络工程,信息安全

授课语言

中文授课

先修课程

计算机科学概论、高级程序设计语言

课程对毕业要求的支撑

本课程对学生达到如下毕业要求有如下贡献:

1.(思政建设)实现计算机专业知识教学与立德树人教育的有机融合;激发学生“实干兴邦”的爱国奋斗精神。

2.(工程知识)培养学生熟练掌握英语,掌握扎实的计算机科学与技术专业基本原理、方法和手段等方面的基础知识用于解决复杂工程问题,并通过计算机系统分析、建模和计算等方面的先进方法,为将所学基础知识应用到计算机科学与技术研发和工程实践做好准备。

3.(问题分析)培养学生能够创造性地利用计算机科学基本原理解决计算机领域遇到的问题。

4.(设计/开发解决方案)能够设计针对计算机工程复杂问题的解决方案,设计满足特定需求的计算机软硬件系统,并能够在设计环节中体现创新意识,考虑社会、健康、安全、法律、文化以及环境等因素。

5.(研究) 培养学生具备计算机系统相关知识并对计算机工程复杂问题进行研究,具有计算机系统研发基本能力、具备问题分析和建模的能力,具有系统级的认知能力和实践能力,掌握自底向上和自顶向下的问题分析方法。

6.(使用现代工具)能够针对计算机工程复杂问题,开发、选择与使用恰当的技术、资源、现代工程工具和信息技术工具。


课程目标

完成课程后,学生将具备以下能力:

1)掌握编译器构造的基本原理和实现技术,具有设计、构造、分析和维护编译程序的能力[46

2)掌握将编译器构造的技术和方法应用于解决其他计算机领域的相关问题。[45

3)掌握计算机学科中解决问题的思路、抽象问题和解决问题的方法,具备计算机综合应用的能力,掌握计算思维的方法[45


课程简介

本课程介绍将高级语言源程序翻译成低级语言目标程序的基本原理、方法和技术。课程主要内容包括:编译程序概述,词法分析,上下文无关文法和语法分析,自上而下的语法分析方法,自底向上的语法分析方法,语义分析,目标程序运行时的存储组织,以及代码生成。使学生掌握编译器构造的基本原理和方法,并能将编译器的构造中蕴含的计算机科学中解决问题的思路和方法,应用于一般软件的设计和构造中。

教学内容与学时分配

(一)第一章 编译程序概述(2学时)

教学内容:

    1. 课程目的、意义与内容组织:结合思政建设,实现计算机专业知识教学与立德树人教育的有机融合,了解学习这门课程的目的和意义以及内容组织。(0.5学时)

    2. 什么是编译器和解释器(0.5学时)

    3. 编译过程的各个阶段(0.5学时)

    4. 编译器的结构(0.5学时)

教学要求:

  1. 掌握:编译过程各个阶段的主要功能

  2. 理解:编译程序的概念

  3. 了解:解释器,编译器的结构


(二)第二章 文法和语言(4学时)

教学内容:

  1. 文法的概念理解(0.5学时)

  2. 文法和语言的关系(0.5学时)

  3. 文法的分类及上下文无关文法(1学时)

  4. 语法树及推导、归约、句柄、句子等内容(2学时)

教学要求:

  1. 理解:上下文无关文法的定义,推导,归约,分析树,抽象语法树

  2. 了解:文法的分类,文法的二义性


(三)第三章 词法分析(4学时)

教学内容:

  1. 词法分析过程(1学时)

  2. 正规表达式(1学时)

  3. 有穷自动机(1学时)

  4. 从正规表达式到有穷自动机的转换(1学时)

教学要求:

  1. 掌握:构造正规表达式,从正规表达式到确定的有穷自动机的转换,词法分析程序的设计方法

  2. 理解:正规表达式,非确定的有穷自动机,确定的有穷自动机

  3. 了解:词法分析程序的自动构造原理


(四)第四章 自上而下的语法分析方法(6学时)

教学内容:

  1. 预测分析法概述(2学时)

  2. LL1)文法的判别(1学时)

  3. LL1)文法到LL1)文法的转换(1学时)

  4. 递归下降分析法(1学时)

  5. LL(1)分析法(1学时)

教学要求:

  1. 掌握:LL1)文法的判别,构造递归下降分析器,LL(1)分析表的构造,LL1)分析法,

  2. 理解:FIRST集,FOLLOW集,LL(1)文法

  3. 了解:带回退的语法分析方法,自上而下语法分析中语法树的构造


(五)第五章 自底向上的语法分析方法(6学时)

教学内容:

  1. 自底向上语法分析方法和LR分析法概述(2学时)

  2. LR(0)项目构成的有穷自动机和LR(0)分析法(3学时)

  3. SLR1)分析法(2学时)

  4. LR1)分析法和LALR1)分析法(1学时)

教学要求:

  1. 掌握:LR(0)分析法,SLR(1)分析法

  2. 理解:右句型,可变前缀,句柄

  3. 了解:LALR(1)分析法,LR1)分析法


(六)第六章 语法制导翻译(8学时)

教学内容:

  1. 属性文法与语义分析(1学时)

  2. 中间代码形式(1学时)

  3. 自上而下语法制导翻译方法(3学时)

  4. 自下而上的语法制导翻译方法(3学时)

教学要求:

  1. 掌握:属性文法;语法制导翻译方法

  2. 理解:属性文法,继承属性,综合属性,S属性文法,L属性文法

  3. 了解:符号表


(七)第七章 目标程序运行时的存储组织(2学时)

教学内容:

  1. 目标程序运行时的存储空间结构(0.5学时)

  2. 运行时的存储组织(0.5学时)

  3. 参数传递机制(1学时)

教学要求:

  1. 掌握:参数传递的几种主要方法与实现过程

  2. 理解:完全静态存储组织,栈式存储组织,完全动态存储组织的概念


(八)第八章 代码优化(4学时)

教学内容:

  1. 中间代码优化(2学时)

  2. 中间代码优化方法(2学时)

教学要求:

  1. 掌握:基本语法结构(简单赋值语句、算术表达式、布尔表达式、控制语句,说明语句)的中间代码生成方法,控制流图的构造,DAG图的构造

  2. 理解:三地址中间代码,三元式,四元式

  3. 了解:常用的优化技术

  1. 第九章 代码生成(4学时)

教学内容:寄存器分配算法及目标代码生成(4学时)

教学要求:掌握寄存器分配算法;目标代码生成


实验教学(包括上机学时、实验学时、实践学时)

实验学时16学时:

(一)实验一:词法分析程序(4学时)

  1. 实验目的:通过为已有的样例语言SAMPLE语言构造词法分析程序,从而掌握词法分析程序的构造方法

  2. 实验内容:了解样例语言SAMPLE语言,用高级程序设计语言(CC++JAVA等语言)构造SAMPLE语言的词法分析程序。

  3. 实验要求:将SAMPLE语言翻译成对应的TOKEN序列,并能检查一定的词法错误

(二)实验二:语法分析程序(6学时)

  1. 实验目的:通过对已有的样例语言SAMPLE语言,构造语法分析程序,从而掌握语法分析程序的构造方法

  2. 实验内容:用自上而下语法分析方法或自下而上的语法分析方法,构造SAMPLE语言的递归下降语法分析器或预测分析器。

  3. 实验要求:将TOKEN序列转换成语法分析树,并能检查一定的语法错误

(三)实验三:语义分析程序及中间代码生成(6学时)

  1. 实验目的:构造SAMPLE语言的语义分析程序并生成中间代码

  2. 实验内容:构造符号表,用高级程序设计语言构造SAMPLE语言的语义分析器,生成中间代码

  3. 实验要求:能检查一定的语义错误,将SAMPLE语言转换成三地址中间代码

教学方法

课程以课堂教学、课外作业、综合讨论等形式教学。

考核方式

本课程注重过程考核,成绩比例为:

平时作业、实验和课堂表现:30%

期末考试(闭卷):70%

教材及参考书

现用教材:《编译原理》,吕映芝,张素琴,蒋维杜等著,清华大学出版社,2015

主要参考资料:

JAlfred V.Aho, Ravi Sethi, Jeffrey D.Ullman著《编译原理 技术与工具》(英文版),机械工业出版社,2012


制定人及制定时间

董敏,20194

  “Principles of CompilersSyllabus

Course Code

045100293

Course Title

Principles of Compilers

Course Category

Specialty Basic Courses

Course Nature

Compulsory Course

Class Hours

56

Credits

3.0

Semester

The Fourth SemesterTheThird Semester

Institute

School of Computer Science and Engineering

Program Oriented

Computer Science and Technology, network engineering, information safety

Teaching Language

Chinese

Prerequisites

Foundations of Computer Science, Advanced Programming Language

Student Outcomes

 (Special Training Ability)

This course can be helpful for students to get the following abilities:  

1.Ideological and political construction: realize the organic integration of computer professional knowledge teaching and moral education;Inspire the students' patriotic spirit of "making the country prosperous by doing".

2.Engineering Knowledge: An ability to apply knowledge of English, solid knowledge of professional basic principles, methods and means of computer science and technology for solving complex engineering problems, to well prepare the required knowledge applied to the computer science and technology research & development and engineering practice through computer systems analysis, modeling and calculation and any other aspects of the advanced approach.  

3.Problem Analysis: An ability to creatively use the basic principles of computer science to solve the problems encountered in the computer field.

4.Design / Development Solutions: An ability to design solutions for computer engineering complex problems, to design computer hardware and software systems that meet with specific requirements, and to embody innovation awareness in the design process and take into account social, health, safety, cultural and environmental factors.

5.Research: An ability to develop computer system-related knowledge and research computer engineering complex issues, to develop the basic capacity of computer systems research & development, systematic cognitive and practice, master the Bottom-up and top-down problem analysis methods.

6.Applying Modern Tools: An ability to develop, select and use appropriate technologies, resources, modern engineering tools and information technology tools for complex computer engineering issues.

Teaching Objectives

Upon completion of this course, each student should be able to:

  1. Understand the theoretical foundation of compiler principles. Know the basic organization and operation of compilers.

Know how to build a compiler for a simplified programming language. [4,6]

  1. Apply the principles and techniques of compiler construction to software design and practice. [4,5]

  2. Learn how to work on a large software project. Have the ability of computational thinking. [4,5]

Course Description

This course introduces the fundamental principles of compiler construction and the basic techniques of realization. It covers lexical analysis, syntax analysis, semantic analysis, runtime environments, code generation, and optimization.

Teaching Content and Class Hours Distribution

Session 1 Introduction: 2 periods

a.What is a compiler and interpreter: 1 period

b.The phases of a compiler: 0.5 periods

c.Compiler structure: 0.5 period

Master: the phases of compiler

Understand: what is a compiler

Know: interpreter, compiler structure

Session 2 Grammars and Languages: 4 periods

a.The Grammar: 0.5 period

b.The relationship between grammars and languages: 0.5 period

c.The grammar types: 1 period

d.Grammar tree:s2 periods

Master:  

a.Grammars

b.Grammar types and grammar tree

Understand:  

  1. Ambiguous grammars


Session 3 Lexical Analysis: 4 periods

a.The scanning process: 0.5 period

b.Regular expression: 0.5 period

c.Finite automata: 1 periods

d.From regular expression to DFAsDeterministic Finite Automata: 2 periods

Master:  

a.Construction of regular expression

b.The transition from regular expression to DFA

c.The construction of scanner

Understand:  

a.Concept of regular expression,

b.NFA (Nondeterministic Finite Automata)

c.DFA (Deterministic Finite Automata)


Session 4 Top-down parsing: 6 periods

a.Predictive parsing: 1 periods

b.Recognition of LL(1) grammar: 2.5 periods

c.Non LL(1) grammar to LL(1) grammar: 0.5 period

d.Recursive-decent Parser: 1 periods

e.LL(1) parsing: 1 periods

Master:  

a.Recognition of LL(1) grammar,

b.Construction of recursive-descent parsing

c.LL(1) parsing

Understand:  

a.First set and follow set

b.LL(1) grammar

Know:  

a.Backtracking parsing,

b.Syntax tree construction in top-down parsers


Session 5 Bottom-Up parsing: 6 periods

a.Overview of bottom-up parsing and LR method: 1 periods

b.Finite automata of LR(0) items and LR(0) parsing: 2 periods

c.SLR(1) parsing: 2 periods

d.General LR(1) and LALR(1) parsing: 1 periods

Master:  

a.LR(0) parsing

b.SLR(1) parsing

Understand: right sentential form, variable prefix, and handle

Know: LALR(1) parsing and LR(1) parsing


Session 6 Syntax directed translation: 8 periods

a.Attribute grammars: 1 period

b.Intermediate code translation 1 period

c.Syntax directed translation: 6 periods

Master: the algorithms for attribute computation

Understand:  

a.Attribute grammar,

b.Syntax directed translation


Session 7 Runtime Environments: 2 periods

a.Memory organization: 0.5 period

b.Three kinds of runtime environment: 1.5 period

Master: stack-based runtime environments

Understand: the main idea of full static and fully dynamic runtime environments


Session 8 Code optimization: 4 periods

a.Intermediate code optimization: 1 period

b.Technologies of Intermediate code optimization:2 periods

Master: intermediate code generation for basic structures

Understand: three-address code, triple, and quadruple

Know:  

a.principal sources of code optimization

b.classification of optimization


Session 9 Target code generation:4 periods

Register allocation;

Experimental Teaching

Experiment Hours (16 Periods)

Experiment 1 Lexical Analysis (4Periods)

Experiment 2 Syntax Analysis(6 Periods)

Experiment 3 Intermediate code generation(6 Periods)

Teaching Method

Classroom teaching, extracurricular homework, comprehensive discussion,  

Examination Method

Classroom performance and Experiments30%

The final exam70%

Teaching Materials and Reference Books

Textbook:

Principles of Compilers, Yingzhi Lv, Qing Hua University Press,2015

Reference book:

JAlfred V.Aho, Ravi Sethi, Jeffrey D.Ullman, Compilers: Principles, Technologies and tools,China Machine Press2012

Prepared by Whom and When

Dong Min, 2019.04


编译原理》实验教学大纲

课程代码

045100293

课程名称

编译原理

英文名称

Principles of Compilers

课程类别

学科基础课

课程性质

必修

学时

总学时:56,上机学时:16

学分

3.0

开课学期

第四学期,第三学期

开课单位

计算机科学与工程学院

适用专业

计算机科学与技术,网络工程,信息安全

授课语言

中文授课

先修课程

计算机科学概论、高级程序设计语言

毕业要求(专业培养能力)

本课程对学生达到如下毕业要求有如下贡献:

1.(思政建设)实现计算机专业知识教学与立德树人教育的有机融合;激发学生“实干兴邦”的爱国奋斗精神。

2.(工程知识)培养学生熟练掌握英语,掌握扎实的计算机科学与技术专业基本原理、方法和手段等方面的基础知识用于解决复杂工程问题,并通过计算机系统分析、建模和计算等方面的先进方法,为将所学基础知识应用到计算机科学与技术研发和工程实践做好准备。

3.(问题分析)培养学生能够创造性地利用计算机科学基本原理解决计算机领域遇到的问题。

4.(设计/开发解决方案)能够设计针对计算机工程复杂问题的解决方案,设计满足特定需求的计算机软硬件系统,并能够在设计环节中体现创新意识,考虑社会、健康、安全、法律、文化以及环境等因素。

5.(研究) 培养学生具备计算机系统相关知识并对计算机工程复杂问题进行研究,具有计算机系统研发基本能力、具备问题分析和建模的能力,具有系统级的认知能力和实践能力,掌握自底向上和自顶向下的问题分析方法。

6.(使用现代工具)能够针对计算机工程复杂问题,开发、选择与使用恰当的技术、资源、现代工程工具和信息技术工具。

课程培养学生的能力(教学目标)

完成课程后,学生将具备以下能力:

1)掌握编译器构造的基本原理和实现技术,具有设计、构造、分析和维护编译程序的能力[46

2)掌握将编译器构造的技术和方法应用于解决其他计算机领域的相关问题。[45

3)掌握计算机学科中解决问题的思路、抽象问题和解决问题的方法,具备计算机综合应用的能力,掌握计算思维的方法[45

课程简介

本课程介绍将高级语言源程序翻译成低级语言目标程序的基本原理、方法和技术。课程主要内容包括:编译程序概述,词法分析,上下文无关文法和语法分析,自上而下的语法分析方法,自底向上的语法分析方法,语义分析,目标程序运行时的存储组织,以及代码生成。使学生掌握编译器构造的基本原理和方法,并能将编译器的构造中蕴含的计算机科学中解决问题的思路和方法,应用于一般软件的设计和构造中。

主要仪器设备与软件

PC机,Eclipse

实验报告

1)实验目的

2)实验步骤

3)实验结果

4)总结与思考

考核方式

主要考查程序功能的完备性和实验报告的规范性。实验完成后,提交程序和实验报告。成绩占课程总成绩的30%

教材、实验指导书及教学参考书目

现用教材:《编译原理》,吕映芝,张素琴,蒋维杜等著,清华大学出版社,2015

主要参考资料:

JAlfred V.Aho, Ravi Sethi, Jeffrey D.Ullman著《编译原理 技术与工具》(英文版),机械工业出版社,2012

制定人及发布时间

董敏,20194

编译原理》实验教学内容与学时分配

实验项目编号

实验项目名称

实验学时

实验内容提要

实验类型

实验要求

每组人数

主要仪器设备与软件

1

实验一:词法分析程序(4学时)

4

  1. 实验目的:通过为已有的样例语言SAMPLE语言构造词法分析程序,从而掌握词法分析程序的构造方法

  2. 实验内容:了解样例语言SAMPLE语言,用高级程序设计语言(CC++JAVA等语言)构造SAMPLE语言的词法分析程序。


综合性

必做

1

PC机,Eclipse,Visual Studio

2

实验二:语法分析程序(6学时)

6

  1. 实验目的:通过对已有的样例语言SAMPLE语言,构造语法分析程序,从而掌握语法分析程序的构造方法

  2. 实验内容:用自上而下语法分析方法或自下而上的语法分析方法,构造SAMPLE语言的递归下降语法分析器或预测分析器。

  3. 实验要求:将TOKEN序列转换成语法分析树,并能检查一定的语法错误


综合性

必做

1

PC机,Eclipse,Visual Studio

3

实验三:语义分析程序及中间代码生成(6学时)

6

  1. 实验目的:构造SAMPLE语言的语义分析程序并生成中间代码

  2. 实验内容:构造符号表,用高级程序设计语言构造SAMPLE语言的语义分析器,生成中间代码

  3. 实验要求:能检查一定的语义错误,将SAMPLE语言转换成三地址中间代码

设计性

必做

1

PC机,Eclipse,Visual Studio



 “Principles of CompilersSyllabus

Course Code

045100293

Course Title

Principles of Compilers

Course Category

Specialty Basic Courses

Course Nature

Compulsory Course

Class Hours

Total: 56hours, Computer Practice:16 hours

Credits

3.0

Semester

The fourth semesterThe third semester

Institute

School of computer science and engineering

Program Oriented

Computer Science and Technology, network engineering, information safety

Teaching Language

English

Prerequisites

None

Student Outcomes (Special Training Ability)

This course can be helpful for students to get the following abilities:  

1.Ideological and political construction: realize the organic integration of computer professional knowledge teaching and moral education;Inspire the students' patriotic spirit of "making the country prosperous by doing".

2.Engineering Knowledge: An ability to apply knowledge of English, solid knowledge of professional basic principles, methods and means of computer science and technology for solving complex engineering problems, to well prepare the required knowledge applied to the computer science and technology research & development and engineering practice through computer systems analysis, modeling and calculation and any other aspects of the advanced approach.  

3.Problem Analysis: An ability to creatively use the basic principles of computer science to solve the problems encountered in the computer field.

4.Design / Development Solutions: An ability to design solutions for computer engineering complex problems, to design computer hardware and software systems that meet with specific requirements, and to embody innovation awareness in the design process and take into account social, health, safety, cultural and environmental factors.

5.Research: An ability to develop computer system-related knowledge and research computer engineering complex issues, to develop the basic capacity of computer systems research & development, systematic cognitive and practice, master the Bottom-up and top-down problem analysis methods.

6.Applying Modern Tools: An ability to develop, select and use appropriate technologies, resources, modern engineering tools and information technology tools for complex computer engineering issues.

Teaching Objectives

Upon completion of this course, each student should be able to:

  1. Understand the theoretical foundation of compiler principles. Know the basic organization and operation of compilers.

Know how to build a compiler for a simplified programming language. [4,6]

  1. Apply the principles and techniques of compiler construction to software design and practice. [4,5]

Learn how to work on a large software project. Have the ability of computational thinking. [4,5]

Course Description

This course introduces the fundamental principles of compiler construction and the basic techniques of realization. It covers lexical analysis, syntax analysis, semantic analysis, runtime environments, code generation, and optimization.

Instruments and Equipments

Personal computer; Eclipse

Experiment Report

( 1 ) the purpose of the experiment

( 2 ) experimental steps

( 3 ) experimental results

( 4 ) summary and thinking

Assessment

The completeness of the program and the standardization of the experimental report. After the experiment is complete, submit the program and the experimental report. Results accounted for 30 percent of the total curriculum.

Teaching Materials and Reference Books

Y. Daniel Liang, Introduction to Java Programming, 10th Edition, 2017

Bruce Eckel, Thinking in Java (4th edition), China MachinePress, 2009.

Prepared by Whom and When

Dong Min, 2019.4

 “Principles of CompilersExperimental Teaching Arrangements

No.

Experiment Item

Class Hours

Content Summary

Category

Requirements

Number of StudentsEach Group

Instruments, Equipments and Software

1

Lexical Analysis (4 Periods)


4

Design the lexical Analysis of SAMPLE language. The results will be a series of TOKEN. Lexical errors should be checked out.

Comprehensive

Compulsory

1

Personal Computer; Eclipse,Visual Studio

2

Syntax directed translation (12 Periods)

6

Syntax analysis of SAMPLE language.

Syntax errors should be checked out.


Comprehensive

Compulsory

1

Personal Computer; Eclipse,Visual Studio

3

Intermediate code generation

6

Intermediate code generation

Comprehensive

Compulsory

1

Personal Computer; Eclipse,Visual Studio