自考13007编译原理考试大纲（2024年版）

北京市高等教育自学考试课程考试大纲课程名称：编译原理课程代码：13007（笔试） 2024 年 3 月版

第一部分课程性质与设置目的

一、课程性质与特点

《编译原理》是北京市高等教育自学考试计算机科学与技术（专升本）专业的一门重要专业课程，是在完成公共基础课程及专业基础课程学习后开设的选考课。本课程主要讲述高级语言翻译为计算机能执行的代码的原理、过程、方法和技术，核心是介绍高级语言到汇编语言的翻译。让学生理解编译和高级语言程序之间的关系，掌握词法分析、语法分析语义分析、中间代码生成、代码优化和目标代码生成等各个阶段的原理、方法和实现技术真正认识计算机信息处理的实质、训练抽象思维能力、体验系统软件的开发过程，进一步提升计算机科学与技术的专业素养。

二、课程目标与基本

要求本课程的目标是全面贯彻落实立德树人根本任务，通过学习，达到识记、理解或者应用编译原理课程的下述知识点：

1. 识记形式语言和自动机的基本概念，理解高级语言编译的基本原理，并能够将这些原理应用于高级语言的设计之中；

2. 理解现有某高级语言的编译系统中各模块的功能和实现方法，能够对不同方法的优劣进行对比和分析；

3. 理解编译程序的结构及各个模块的功能，利用软件工程方法分析和设计某语言的编译程序的各个模块，并能够选择合适的方法实现。

本课程的考核章节为第一到第八章，重点章节是：第一章，第二章，第三章，第四章，

第五章。无不考核章节。

三、与本专业其他课程的关系编译原理课程

通过形式语言与自动机的相关基础知识、高级语言到汇编语言的翻译原理、方法和实现技术等教学内容，传授高级语言编译程序构造的一般原理和基本方法，如词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等各个阶段的原理等知识，从而有针对性地培养学生模型构建能力、系统分析能力和方案选择与实现能力。

同时，根据计算机科学与技术专业人才培养总体目标，以及课程所面向学生特点，课程内容还涉及计算机体系结构、汇编语言、项目管理等内容，旨在培养知识交叉应用、沟通交流等综合能力。为了满足课程教学目标，建议先修课程有：高级语言程序设计，数据结构与算法，离散数学，软件工程，计算机系统原理。

第二部分考核内容与考核目标

第一章 编译概述

通过本章的学习，了解编译技术的发展，编译程序的构造方法。掌握高级语言程序编译系统，编译过程，程序设计语言的结构和规范。掌握编译过程和编译程序的结构。

重点：高级语言的编译过程。

难点：编译程序的结构，高级语言的编译过程。

(一) 程序设计语言及翻译程序理解: 计算机语言的层次关系；

编译程序或者编译器概念；

编译方式与解释方式的异同。

(二) 编译系统

识记：高级语言编译实例。

理解：高级语言编译流程。

(三）编译过程和编译程序的结构理解：编译阶段的组合。

应用：编译过程的六个阶段；对应六个阶段的编译程序的六个模块。

（四）编译程序的构造方法识记：构造编译程序的五种方法理解：构造编译程序要考虑的三个要素

（五）认识 Sample 语言识记：高级语言的构成成分理解：高级语言规范应用：高级语言程序结构

（六）编译程序的发展及编译技术的应用识记：编译程序的发展编译技术的应用理解：学习编译原理的目的

第二章 词法分析

通过本章的学习，了解词法分析器自动生成工具。了解高级语言中单词的种类。掌握利用状态转换图识别单词的方法。掌握利用正则表达式进行单词识别的原理和方法。

重点：状态转换图，有穷自动机。

难点：正则式转 NFA，NFA 转 DFA，DFA 最小化。

(一) 词法分析概述识记：词法分析的两种实现方式理解: 词法分析的任务。

(二) 高级语言中的单词理解：单词的种别码。

应用：单词的分类。

(三）单词的识别

理解：超前搜索技术和双界符的识别。

数值型常量的识别与状态转换图的合并。

应用：状态转换图；

基于状态转换图的单词识别程序。

（四）词法分析器的设计识记：词法分析程序接口理解：词法分析工作流程

（五）正则表达式与有穷自动机识记：符号和符号串理解：集合的运算语言的定义应用：正则表达式有穷自动机：DFA 模型，NFA 模型，NFA 确定化，DFA 最小化， 正则表达式与有穷自动机的等价性

（六）词法分析器的自动生成工具识记：Lex 概述Lex 源文件的书写 Lex 使用中的注意事项理解：Lex 的工作原理；

应用：使用 Lex 自动词法分析器（七）词法分析中的错误处理识记：词法分析中常见的错误种类；

词法分析器错误恢复操作常见方法

第三章 语法分析

通过本章的学习，了解语法分析自动生成器。掌握上下文无关文法相关概念，熟悉用上下文无关文法定义某种高级语言的语法结构。掌握自上而下语法分析的特点，对文法的要求，能用两种不同的自上而下分析方法对给定的文法进行判断和分析。掌握自下而上语法分析的基本概念和特点，掌握用两种不同的自下而上分析方法，能对给定的文法进行判断和分析。

重点：上下文无关文法的基本概念，LL(1）文法，OPG 文法，LR 文法，各种文法的分析的基本算法。

难点：对文法进行判断和分析。

(一) 语法分析概述识记：语法分析的基本概念：上下文无关文法，自上而下分析法，自下而上分析法(二) 上下文无关文法理解：文法的定义；

文法的推导；

文法产生的语言；

应用：语法树；

二义文法；

消除二义性；

(三）自上而下的语法分析应用：自上而下分析方法中的问题探究；

LL(1）文法递归下降分析方法；

预测分析方法。

（四）自下而上的语法分析理解：自下而上分析方法概述应用：算符优先分析LR 分析法；

（五）语法分析器的自动生成工具 YACC识记：YACC 概述YACC 源文件的格式 YACC 的翻译规则；

YACC 的辅助程序；

（六）语法分析中的错误处理理解：语法分析中的错误处理的一般原则；

应用：自上而下语法分析的错误处理自下而上语法分析的错误处理；

第四章 语义分析

通过本章的学习，掌握语义分析的相关概念。掌握符号表管理技术。掌握静态语义检查的相关方法和技术。熟悉某种具体的高级语言对语义的要求。

重点：高级语言的语义描述方法，符号表管理技术。

难点：符号表管理技术、静态语义检查技术。

(一) 语义分析概述识记：静态语义和动态语义理解：语义分析的任务(二) Sample 语言的语义描述识记：程序的语义；

函数的语义；

各种名字的声明和使用的语义；

各种语句的语义

理解：表达式的语义；

(三）符号表管理技术识记：符号表概述应用：符号表的组织方式；

符号表的操作

（四）静态语义检查

理解：静态语义检查概述应用：声明与定义语义检查表达式语义检查；

语句语义检查；

第五章 中间代码生成

通过本章的学习，掌握中间代码的形式，语法制导的翻译方法。掌握属性文法的概念， 能用属性文法表示某高级语言特定语法成分的语义信息。掌握高级语言各种语法成分的翻译技术。了解中间代码生成器的设计。

重点：用属性文法描述各种语法成分的语义信息，各种语法成分语法制导的翻译方法。

难点：用属性文法描述各种语法成分的语义信息。

(一) 中间代码生成概述识记：属性文法生成中间代码的好处；

(二) 中间代码

理解：逆波兰式；

三地址代码；

应用：有向无环图表示；

(三）属性文法和语法制导的翻译应用：属性文法；

属性的计算属性的计算顺序；

语法制导翻译的实现方法。

（四）常见语句的语法制导的翻译理解：声明语句的语义处理应用：表达式的翻译布尔表达式的翻译；

控制语句的翻译

（五）中间代码生成器的设计识记：Sample 语法成分组成中间代码生成器的接口；

理解：四元式序列和四元式表；

第六章 运行时存储组织

通过本章的学习，掌握程序运行时存储器的划分，活动记录。掌握函数调用方式及相关概念。理解各种存储分配方式，掌握栈式存储分配策略。

重点：程序运行时存储器的划分，函数调用机制，栈式存储分配策略。

难点：函数的相关概念，函数运行时的存储分配。

(一) 存储组织

识记：程序执行时存储器的划分；

理解：活动记录；

局部数据布局；

(二) 函数调用

识记：源程序中的函数；

名字的作用域；

名字的绑定；

理解：函数执行时的活动参数的传递；

(三）存储分配策略

理解：静态存储分配；

栈式存储分配；

堆式存储分配

（四）C 语言编译程序运行时存储实例识记：内存的划分及程序执行的总体情况案例：程序运行时内存的变化；

第七章 代码优化

通过本章的学习，掌握基本块的划分方法，画程序流图。掌握局部优化技术。掌握全局优化技术。

重点：基本块划分，流图，优化技术。

难点：基本块划分。

(一) 代码优化概述识记：代码优化的地位应用：基本块的概念及流图；

(二) 局部优化

理解：删除公共子表达式；

复写传播；

删除无用代码；

代数恒等变换；

应用：基本快的 DAG 表示及优化；

(三）循环优化

理解：循环的定义；

代码外提；

强度削弱；

删除归纳变量。

第八章 目标代码生成

通过本章的学习，了解目标代码生成器所涉及到的相关信息。熟悉某种目标机器结构及指令系统。掌握简单的代码生成技术。掌握引用信息、活跃信息，寄存器描述器和地址描述器，基本块的代码生成技术。了解从 DAG 生成目标代码的方法。熟悉目标代码生成器的设计方法。

重点：简单代码生成技术、基本块的代码生成技术。

难点：引用信息、活跃信息，寄存器描述器和地址描述器。

(一) 概述

识记：代码生成器的设计目标；

目标代码生成过程的细节；

(二) 目标机及指令系统简介识记：80×86 体系结构；

80×86 中的寄存器；；

80×86 指令系统介绍；

(三）一个简单的代码生成器理解：各种四元式代码的翻译方法；

（四）基本块的代码生成器理解：引用信息和活跃信息；

应用：寄存器描述和地址描述；基本块的代码生成；

（五）从 DAG 生成目标代码识记：利用一个基本块的 DAG 表示来生成较优目标代码的方法；

（六）代码优化及目标代码生成器的设计理解：目标代码生成器的结构；

汇编指令的选择构成完整的汇编语言程序；

第三部分有关说明与实施要求

一、考核的能力层次表述

本大纲在考核目标中，按照“识记”、“理解”、“应用”三个能力层次规定其应达到的能力层次要求。各能力层次为递进等级关系，后者必须建立在前者的基础上，其含义是：识记：能知道有关的名词、概念、知识的含义，并能正确认识和表述，是低层次的要求。

理解：在识记的基础上，能全面把握基本概念、基本原理、基本方法，能掌握有关概念、原理、方法的区别与联系，是较高层次的要求。

应用：在理解的基础上，能运用基本概念、基本原理、基本方法联系学过的多个知识点分析和解决有关的理论问题和实际问题，是最高层次的要求。

二、指定教材

编译原理及实践教程（第 3 版），黄贤英王柯柯曹琼魏星编著，清华大学出版社， 2019 年版。

三、

自学方法指导

1、在开始阅读指定教材某一章之前，先翻阅大纲中有关这一章的考核知识点及对知识点的能力层次要求和考核目标，以便在阅读教材时做到心中有数，有的放矢。

2、阅读教材时，要逐段细读，逐句推敲，集中精力，吃透每一个知识点，对基本概念必须深刻理解，对基本理论必须彻底弄清，对基本方法必须牢固掌握。

3、在自学过程中，既要思考问题，也要做好阅读笔记，把教材中的基本概念、原理、方法等加以整理，这可从中加深对问题的认知、理解和记忆，以利于突出重点，并涵盖整个内容，可以不断提高自学能力。

4、完成书后作业和适当的辅导练习是理解、消化和巩固所学知识，培养分析问题、解决问题及提高能力的重要环节。在做练习之前，应认真阅读教材，按考核目标所要求的不同层次，掌握教材内容，在练习过程中对所学知识进行合理的回顾与发挥，注重理论联系实际和具体问题具体分析，解题时应注意培养逻辑性，针对问题围绕相关知识点进行层次（步骤）分明的论述或推导，明确各层次（步骤）间的逻辑关系。

四、对社会助学的要求

1、应熟知考试大纲对课程提出的总要求和各章的知识点。

2、应掌握各知识点要求达到的能力层次，并深刻理解对各知识点的考核目标。

3、辅导时，应以考试大纲为依据，指定的教材为基础，不要随意增删内容，以免与大纲脱节。

4、辅导时，应对学习方法进行指导，宜提倡”认真阅读教材，刻苦钻研教材，主动争取帮助，依靠自己学通”的方法。

5、辅导时，要注意突出重点，对考生提出的问题，不要有问即答，要积极启发引导。

6、注意对应考者能力的培养，特别是自学能力的培养，要引导考生逐步学会独立学习，在自学过程中善于提出问题，分析问题，做出判断，解决问题。

7、要使考生了解试题的难易与能力层次高低两者不完全是一回事，在各个能力层次中会存在着不同难度的试题。

8、助学学时：本课程共 4 学分，建议总课时 72 学时，其中助学课时分配如下：

章次 内容 学时

第一章

编译概述

第二章

词法分析

第三章

语法分析

第四章

语义分析

第五章

中间代码生成

第六章

运行时存储组织

第七章

代码优化

第八章

目标代码生成合 计

五、关于命题考试的若干规定

1．本大纲各章所提到的内容和考核目标都是考试内容。试题覆盖到章，适当突出重点。

2．笔试的比例一般为识记占 30%，理解占 40%，应用占 30%。

3. 试题难易程度应合理：易、中等难度、难。难题部分比例不超过 20%。

4．笔试试题类型一般分为：填空题、名词解释题、单项选择题、多项选择题、简答题、综合题。

5．笔试采用闭卷考核方式，考试时间 150 分钟，按百分制计分，60 分为及格。

六、题型示例

（一）填空题

词法分析是编译程序的第一步，它读入源程序，输出____________ 。

（二）名词解释题

文法等价

（三）单项选择题

词法分析器的输入是：

A．单词符号串 B．源程序 C．语法单位 D．目标程序（四）多项选择题如果在文法 G 中存在一个句子，满足下面的条件之一时，则该文法为二义文法：

A．其最左推导和最右推导相同； B．该句子有两个不同的最左推导； C．该句子有两个不同的最右推导； D．该句子有两个不同的语法树。

（五）简答题

何谓二义性文法?试举一例说明。

（六）综合题

设计一个状态数最少的 DFA，其输入字母表是{0，1}，它能接受以 00 或 01 结尾的所有序列。