《编译原理》教学大纲

课程代码

045100293

课程名称

编译原理

英文名称

Principles of Compiler

课程类别

选修课

课程性质

选修

学时

总学时:48,实验学时:16,其他学时:16

学分

2.5

开课学期

第四学期

开课单位

计算机科学与工程学院

适用专业

计算机科学与技术全英创新班,计算机科学与技术全英联合班

授课语言

英语

先修课程

高级语言程序设计、数据结构、计算机组成与体系结构

课程对毕业要求的支撑

2.3能认识到解决复杂工程问题有多种方案可选择,能通过文献寻求可能的解决方案。

3.1能够设计满足计算机复杂工程特定需求和功能的系统、单元(部件)或计算机系统研发的全生命周期过程

5.3能够开发或者选用满足特定需求的现代工具,仿真和模拟计算机工程问题,并能够分析其局限性

课程目标

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

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

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

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


课程简介


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


教学内容与学时分配


 1-概述, 2-COOL程序设计语言, 2学时授课,2学时MOOC线上学习

 1-概述

 01-01: 概述

 01-02: 编译器的结构

 2- COOL程序设计语言

 02-01: COOL语言概述

 02-02: COOL程序实例

以“编译原理”的第一堂课为抓手,实现专业教育与课程思政的有效结合;结合“大数据”、“人工智能”、“互联网+”、等国家战略,培养学生的学习兴趣和动力,激发学生的爱国情怀。

掌握:

 a.编译器的结构:编译的5个阶段

理解:

 a.什么是编译器和解释器

了解:

 a.编译器发展的历史

 b.COOL程序设计语言


 3- 词法分析, 2学时授课,2学时MOOC线上学习

 03-01: 词法分析概述

 03-02: 正规表达式

 03-03: 词法描述

掌握:

 a.用正规表达式定义语言

理解:

 a.词法分析器的主要任务

 b.什么是正规表达式


 4-有限自动机, 2学时授课,2学时MOOC线上学习

 04-01: 有限自动机的定义

 04-02: 正规表达式到不确定的有限自动机的转换

 04-03: 不确定的有限自动机到确定的有限自动机的转换

 04-04: 有限自动机的实现

掌握:

 a.将正规表达式转换成不确定的有限自动机

 b.将不确定的有限自动机转换成确定的有限自动机

理解:

 a.什么是不确定的有限自动机

 b.什么是确定的有限自动机

了解:

 a.有限自动机的实现


 5-语法分析,  2学时授课,2学时MOOC线上学习

 05-01: 语法分析概述

 05-02: 上下文无关文法

 05-03: 推导

 05-04: 错误处理

 05-05: 抽象语法树

掌握:

  1. 最左推导和最右推导

  2. 构造分析树和抽象语法树

理解:

 a.上下文无关文法

了解:

 a.错误处理


 6-自顶向下的语法分析,2学时授课,2学时MOOC线上学习

 06-01: 递归下降分析法

 06-02: 左递归

 06-03: 预测分析法

 06-04: First集和Follow

 06-05: LL(1)分析表

掌握:

  1. 左递归的消除及提取左公因子

  2. 构造LL(1)分析表

 b.对给定的字符串进行LL(1)分析

理解:

 a.自顶向下语法分析的基本思想

了解:

 a.递归下降分析法


 7-自底向上语法分析, 2学时授课,2学时MOOC线上学习

 07-01: 自底向上语法分析法

 07-02: 移入规约分析法

 07-03: 句柄

 07-04: 可行前缀的识别

 07-05: SLR分析方法

掌握:

  1. 构造识别可行前缀的确定的有限自动机

  2. 构造Action表和Goto

  3. 对给定的字符串进行LR(0)分析和SLR(1)分析

理解:

  1. 自底向上语法分析的基本思想

  2. 句柄和可行前缀


 8-语义分析和类型检查, 2学时授课,2学时MOOC线上学习

 08-01: 语义分析概述

 08-02: 符号表

 08-03: 类型检查的实现

掌握:

 a.类型检查的实现

理解:

 a.什么是语义Fenix

 b.类型的形式化定义

了解:

 a.符号表的作用


 9-运行时的存储组织, 10-目标代码生成, 2学时授课,2学时MOOC线上学习

 9-运行时的存储组织

 09-01: 运行时存储器的机构

 09-02: 过程调用

 09-03: 过程活动记录

 09-04: 全局变量的存储及堆存储

 09-05: 栈式计算机

 10-目标代码生成

 10-01: 目标代码生成概述

 10-02: 目标代码生成方法

掌握:

 a.对于给定的程序,画出过程活动记录栈的内容及变化

 b.利用栈式计算机生成目标代码

理解:

 a.运行时存储组织的基本结构

 b.过程活动记录

 c.   1个寄存器的栈式计算机的工作


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

有,上机学时:16

教学方法

MOOC学习,翻转课堂、课外作业,实验项目

考核方式


期末成绩,课程目标13

考核形式:闭卷

考核目标:考核对理论教学部分所讲授的编译器构造的基本原理和方法的掌握情况

所占总评成绩比例:60%


实验项目,课程目标13

考核形式:构造一个小型语言的编译器

考核目标:考察学生运用所学的编译器构造的原理和方法的理论知识,以及掌握编译器自动生成工具,设计并实际构造一个小型语言编译器的能力。

所占总评成绩比例:20%


平时成绩,课程目标123

考核形式:包括作业成绩、翻转课堂表现

考核目标:作业考察学生对各章节知识重点的掌握情况,翻转课堂表现考察学生课堂参与,讨论及表达能力。

所占总评成绩比例:20%


教材及参考书


教材:无

引进的MOOC课程:

 Alex Aiken, Compilers, Sandford Online Lagunita, https://lagunita.stanford.edu/courses/Engineering/Compilers/Fall2014/about

参考书:

1Alfred V.Aho, Monica S. Lam, Ravi Sethi, Jeffrey D.Ullman著《编译原理》(英文版 第2版),机械工业出版社,2011.1

2Alfred V.Aho, Monica S. Lam, Ravi Sethi, Jeffrey D.Ullman著《编译原理 技术与工具》(英文版 第2版),人民邮电出版社,2008.2


制定人及制定时间

刘欣欣,20190408

 “Principles of Compiler” Syllabus

Course Code

045100293

Course Title

Principles of Compiler

Course Category

Elective Courses

Course Nature

Elective Course

Class Hours

Class Hours: 48, Experiment Hours:16, Other:16

Credits

2.5

Semester

The Fourth Semester

Institute

School of Computer Science & Engineering

ProgramOriented

Computer Science and Technology Full English Creative Class, Computer Science and Technology Full English Union Class

Teaching Language

English

Prerequisites

Advanced Language Programmer, Data Structure, Computer Organization and Architecture

 Student Outcomes

 (Special Training Ability)


1.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.

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

3.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.

4.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.

 5.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.


Course 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. [3,5]

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

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


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


1-Introduction, 2- the Cool Programming Language, 2 periods of lectures and 2 period of MOOC online study

1-Introduction

01-01: Introduction

01-02: Structure of a Compiler

2- the Cool Programming Language

02-01: Cool Overview

02-02: Cool Example

 Using the first class of “Principles of Compiler”, realize the effective combination of   professional education and curriculum ideology and politics. Combining the national strategy, such as “big data”, “Artificial Intelligence”, “Internet +” to develop students’ interest and motivation in learning and inspire students’ patriotic feelings.

Master:

  1. The structure of compilers: five phases.

Understand:

  1. What are compilers and Interpreters?

Know:

  1. The brief history of compiler.

  2. Cool programming language


3- Lexical Analysis, 2 periods of lectures and 2 period of MOOC online study

03-01: Lexical Analysis

03-02: Regular Languages

03-03: Lexical Specifications

Master:

  1. Using regular expressions to define language

Understand:

  1. The main work of lexical analysis

  2. What are regular expressions


4-Finite Automata, 2 periods of lectures and 2 period of MOOC online study

04-01: Finite Automata

04-02: Regular Expressions into NFAs

04-03: NFA to DFA

04-04: Implementing Finite Automata

Master:

  1. Converting regular expressions into non-deterministic finite automata

  2. Converting nondeterministic finite automata into deterministic finite automata

Understand:

  1. NFA (Nondeterministic Finite Automata)

  2. DFA (Deterministic Finite Automata)

Know:

  1. Implementing Finite Automata


5-Parsing, 2 periods of lectures and 2 period of MOOC online study

05-01: Introduction to Parsing

05-02: Context Free Grammars

05-03: Derivations

05-04: Error Handling

05-05: Abstract Syntax Trees

Master:

  1. Left-most and right-most derivations

  2. Construct parse tree and abstract syntax tree

Understand:

a.Context-free grammar

Know:

  1. Error Handling


6-Top-Down Parsing, 2 periods of lectures and 2 period of MOOC online study

06-01: Recursive Descent Parsing

06-02: Left Recursion

06-03: Predictive Parsing

06-04: First Sets and Follow Sets

06-05: LL(1) Parsing Tables

Master:

  1. Left recursion removal and left factoring

  2. Construct the LL(1) parsing table

  3. Give the LL(1) parsing for a given string

Understand:

a.The main idea of Top-down parsing

Know:

  1. Recursive Descent Parsing


7-Bottom-Up Parsing, 2 periods of lectures and 2 period of MOOC online study

07-01: Bottom-Up Parsing

07-02: Shift-Reduce Parsing

07-03: Handles

07-04: Recognizing viable Prefixes

07-05: SLR Parsing

Master:

  1. Build DFA for recognizing viable prefixes

  2. Construct the action table and goto table

  3. Give the LR(0) and SLR(1) parsing process of a given string

Understand:

  1. The main idea of Bottom-Up parsing

  2. Handle and viable prefix


8-Semantic Analysis and Type Checking, 2 periods of lectures and 2 period of MOOC online study

08-01: Introduction to Semantic Analysis

08-02: Symbol Tables

08-03: Implementing Type Checking

Master:

  1. Implementing Type Checking

Understand:

  1. What is the semantic analysis?

  2. Formal notations for specifying types

Know:

  1. The function of symbol tables


9-Runtime Organization, 10-Code Generation, 2 periods of lectures and 2 period of MOOC online study

9-Runtime Organization

09-01: Runtime Organization

09-02: Activations

09-03: Activation Records

09-04: Globals and Heap

09-05: Stack Machines

10-Code Generation

10-01: Introduction to Code Generation

10-02: Code Generation

Master:

  1. Draw the stack of activation records for a given program

  2. Code generation for a simple language to the stack machine language

Understand:

  1. The general structure of runtime organization

  2. What is an activation record?

  3. How the 1-register stack machine works?


Experimental Teaching

Computer-aided Class Hours:16

Teaching Method

MOOC Study, Flipped-Classroom, homework, lab

Examination Method


Writing examinationCourse Objectives1, 3;

 Assessment form: closed book exam

 Assessment objectives: examine the basic principles and techniques of compiler construction taught in the theory teaching section.  

 Accounted for: 60% of the total score.


Experiments, Course Objectives1, 3;

 Assessment form: construct a compiler for a small language

 Assessment objectives: examine the ability to design a small language compiler using compiler generation tools and the knowledge of compiler construction principles and methods.  

 Accounted for: 20% of the total score.


Usual grade, Course Objectives1, 2,3;

 Assessment form: homework, flipped-classroom performance

 Assessment objectives: homework examines the mastery of key knowledge of each chapter. Flipped-classroom performance examines the ability to participate in class discussions and presentation.

 Accounted for: 20% of the total score.


Teaching Materials and Reference Books


No Textbook:

 MOOC:

 Alex Aiken, Compilers, Standford Online Lagunita, https://lagunita.stanford.edu/courses/Engineering/Compilers/Fall2014/about

Reference Books:

  1. Alfred V.Aho, Monica S. Lam, Ravi Sethi, Jeffrey D.Ullman, Compiler: Principles, Techniques, and Tools (Second Edition), China Machine Press, 2011.1

  2. Alfred V.Aho, Monica S. Lam, Ravi Sethi, Jeffrey D.Ullman, Compiler: Principles, Techniques, & Tools (Second Edition), Posts & Telecom Press, 2008.2


Prepared by Whom and When

Xinxin Liu, 8th April, 2019


编译原理》实验教学大纲

课程代码

045100293

课程名称

编译原理

英文名称

Principles of Compiler

课程类别

选修课

课程性质

选修

学时

总学时:48,实验学时:16,其他学时:16

学分

2.5

开课学期

第四学期

开课单位

计算机科学与工程学院,计算机教学实验中心

适用专业

计算机科学与技术全英创新班、计算机科学与技术全英联合班

授课语言

英语

先修课程

高级语言程序设计、数据结构、计算机组成与体系结构

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


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

2.3能认识到解决复杂工程问题有多种方案可选择,能通过文献寻求可能的解决方案。

3.1能够设计满足计算机复杂工程特定需求和功能的系统、单元(部件)或计算机系统研发的全生命周期过程

5.3能够开发或者选用满足特定需求的现代工具,仿真和模拟计算机工程问题,并能够分析其局限性


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


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

1. 掌握编译器各个阶段工作的实现,能为小型高级程序语言构造编译器,完成从该高级语言程序到目标程序的转换。[3,4,5]

2. 掌握计算机科学中抽象问题和表示问题的方法,掌握高级程序设计语言的词法、语法和语义的形式化表示方法。[3,4]

3. 能根据理论部分学习的编译各阶段的实现方法,设计针对具体程序设计语言的实现方案。[3,4]

  1. 掌握使用高级程序设计语言工具,编码实现编译器各个阶段的工作。 [3,5]


课程简介


编译原理课程内容较抽象,理解难度大,实验是其中的一个重要环节。实验通过对一个较完整的编译器的开发,让学生对编译的各组成部分的实现技术有更好的理解,同时掌握编译的各部分如何整合,从而形成一个完整的编译系统。通过实验,学生可深入理解所学的理论知识,熟悉编译中的一些重要算法的应用,基本掌握编译器构造的方法,提高理论联系实际的能力。另外,在实验过程中,学生将数据结构、高级程序设计语言等相关知识内容进行综合运用,提高了学生的计算机综合应用能力。


主要仪器设备与软件

PC机:硬件:PIII500以上;操作系统: Windows 8Windows 10

虚拟机VirtualBox 6或以上;

实验报告

考核方式


实验课考核方式包括上机检查实验完成情况,及提交实验源代码和实验报告。

考核的评分标准:

40%:是否完成了实验规定的全部内容,运行结果是否正确,系统运行是否稳定;

30%:提交的实验源代码编写是否规范;

30%:实验报告中对实验方案设计是否合理,实验步骤和方法是否正确,描述是否充分。

实验教学环节占课程总成绩的20%,实验教学环节中预习、考勤、实验纪律占实验环节总成绩的20%,提交的实验报告和实验源代码的完成情况占实验环节总成绩的40%,上机检查占实验环节总成绩的40%


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

教材:无

实验指导书:由所引进的MOOC课程提供

Alex Aiken, Compilers, Stanford Online Lagunita, https://lagunita.stanford.edu/courses/Engineering/Compilers/Fall2014/about


制定人及发布时间

刘欣欣,20190408


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

实验项目编号

实验项目名称

实验学时

实验内容提要

实验类型

实验要求

每组人数

主要仪器设备与软件

1

搭建实验虚拟环境,熟悉COOL程序设计语言

4


  1. 搭建实验环境,实验在虚拟机VirtualBox中完成

  2. 获取虚拟机镜像文件Compilers.vbox. 在该镜像中安装了Linux操作系统以及实验所需的全部工具软件。

  3. 熟悉实验要编译的源语言Cool程序设计语言


设计性

必做

1

PC机:硬件:PIII500以上;操作系统:Windows XPWindows 8Windows 10

编程语言:CC++

2

构造COOL语言的词法分析器


4


使用词法分析器的自动生成器flex,构造COOL语言的词法分析器

  1. 熟悉Flex的规则和使用方法

  2. Flex的规则定义COOL语言中各类单词

  3. 构造词法分析器的动作,包括:返回所识别的单词,记录单词的值,当出现词法错误时报告词法错误


设计性

必做

1

PC机:硬件:PIII500以上;操作系统: Windows 8Windows 10

VirtualBox 6或以上

3

构造COOL语言的语法分析器


4


用词法分析器的自动生成器,bison, 构造COOL语言的词法分析器

  1. 熟悉YACC规则的定义和bison的使用方法

  2. 定义非终结符的类型声明和过程声明

  3. COOL语法定义转换成YACC规则


设计性

必做

1

PC机:硬件:PIII500以上;操作系统: Windows 8Windows 10

VirtualBox 6或以上

4

构造COOL语言语法分析器的输出,抽象语法树

4

构造COOL语言语法分析器的输出,抽象语法树

  1. YACC规则中添加生成抽象语法树的动作

  2. 添加进行语法错误处理的动作

设计性

必做

1

PC机:硬件:PIII500以上;操作系统: Windows 8Windows 10

VirtualBox 6或以上

 “Principles of Compiler” Experiment Syllabus

Course Code

045100293

Course Title

Principles of Compiler

Course Category

Elective Courses

Course Nature

Elective Course

Class Hours

Class Hours: 48, Experiment Hours:16, Other:16

Credits

2.5

Semester

The Fourth Semester

Institute

School of Computer Science & Engineering, Laboratory of Computer Teaching

Program Oriented

Computer Science and Technology Full English Creative Class, Computer Science and Technology Full English Union Class

Teaching Language

English

Prerequisites

Advanced Language Programmer, Data Structure, Computer Organization and Architecture

Student Outcomes (Special Training Ability)


1.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.

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

3.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.

4.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.

5.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


1. Through the construction of a compiler, students will really appreciate the theory, apply the important algorithms for each step in the compilation process and understand how all the parts of a compiler fit together. [3,4,5]

2. Understanding the basic techniques of compiler construction, especially the construction of scanner, parser, semantic analyzer and intermediate code generator. [3,4]

3. Familiar with the source language to be compiled, including its lexical, syntax and semantic regulation. Design the structure of compiler basing on the source language and the properties the compiler wants to have. Determine the operations done by each pass of compiling. [3,4]

4. Develop the code for each phase of the compiler using the important algorithms designed for scanning, parsing, semantic analyzing and code generating. [3,5]

Course Description


Experiment of compiler construction is an important part of the course Principles of Compiler. It plays a key role in helping students to understand the underlying theory and training students’ abilities to programming an actual compiler. Students are asked to do a compiler project for designing and implementing a compiler for a small language. Having traced through and implemented the various phases of compilation, you will gain a clear understanding of how a compiler works. You will learn standard techniques that can be applied to a variety of compilation problems. Exposure to programming language implementation will strengthen your development and debugging skills and generally aid your understanding of language and programming issues.


Instruments and Equipments

PC: Hardware: PIII500 or above; Operating SystemWindows 8Windows 10

VirtualBox 6 or above

Experiment Report

Yes

Assessment


Source codes and reports must be submitted for the experiment. Grading will be based on both the quality of report and the organization and correctness of the source codes.

The overall grade of the experiment will be assigned using the following weights

40%: experiment is completed and submitted before the due date. Program written works correctly;

30%: quality of the experiment report

30%: organization and correctness of the submitted code


Teaching Materials and Reference Books


No Textbook for the experiments

Instruction for the experiments is provide by MOOC:

Alex Aiken, Compilers, Stanford Online Lagunita, https://lagunita.stanford.edu/courses/Engineering/Compilers/Fall2014/about


Prepared by Whom and When

Xinxin Liu, 8th April, 2019

 “Principles of Compiler” Experimental Teaching Arrangements

No.

Experiment Item

Class Hours

Content Summary

Category

Requirements

Number of StudentsEach Group

Instruments, Equipments and Software

1

Getting started with the virtual machine and COOL programming language.

4


  1. Set up the experiment environment. The experiment will be doned inside the virtual machine(VM) VirtualBox

  2. Get the VM image file: Compilers.vbox. It’s a pre-configured Linux system with all the needed tools installed.

  3. Familiar with the Cool Programming Language


Design

Compulsory

1

PC: Hardware: PIII500 or above; Operating SystemWindows 8Windows 10

VirtualBox 6 or above

2

Write a lexical analyzer of COOL programming language


4


Using a lexical analyzer generator, flex, to build the COOL lexical analyzer

  1. Familiar with Flex rules and the use of Flex

  2. Write Flex rules that match on the appropriate regular expressions defining valid tokens in Cool

  3. Perform the appropriate actions:

Returning a token

Recording the value of a lexeme

Reporting an error when an error is encountered


Design

Compulsory

1

PC: Hardware: PIII500 or above; Operating SystemWindows 8Windows 10

VirtualBox 6 or above

3

Write a parser for COOL programming language


4


Using a parser generator, bison, to build the COOL parser

  1. Familiar with YACC rules and the use of Bison

  2. Add type declarations for non-terminals, add precedence declarations.

  3. Turn the cool syntax to YACC rules


Design

Compulsory

1

PC: Hardware: PIII500 or above; Operating SystemWindows 8Windows 10

VirtualBox 6 or above

4

Generate the output of the parser, that is an abstract syntax tree(AST)

4

Build the output of the parser, that is an abstract syntax tree(AST)

  1. Add the actions for AST generation to rules

  2. Error handling

Design

Compulsory

1

PC: Hardware: PIII500 or above; Operating SystemWindows 8Windows 10

VirtualBox 6 or above