编译原理知识点总结

 对下列错误信息，请指出可能是编译的哪个阶段（词法分析、语法分析、语义分析、 代码生成）报告的。

（1） else 没有匹配的 if 语法分析

（2） 数组下标越界 语义分析

（3） 使用的函数没有定义 语法分析

（4） 在数中出现非数字字符 词法分析

 一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组产生式。

 词法分析器用于识别单词

 LL(1)分析法属于自顶向下的语法分析方法

 算符优先分析算法是自下而上的语法分析方法

 编译程序与解释程序最大的区别之一在于前者生成目标代码，而后者不生成



下表从最高到最低说明了各种正则表达式运算符的优先级顺序：

运算符 说明

\ 转义符

(), (?:), (?=), [] 括号和中括号

*, +, ?, {n}, {n,}, {n,m} 限定符

^, $, \任何元字符、任何字符 定位点和序列

| 替换

 一个上下文无关文法是LL(1)文法的充分必要条件是：

对每个非终结符A的两个不同产生式，A→α, A→β,满足

SELECT(A→α)∩SELECT(A→β)=空

其中α，β不同时能ε

 如果Ｓ* αＡβ and A

+γ，则称γ是句型αγβ的相对于变量A的短语(Phrase)

如果Ｓ* αＡβ and Aγ，则称γ是句型αγβ的相对于变量A的直接（简单）短语

最左直接短语叫做句柄(Handle)

 前端：与目标代码无关的部分，包括词法分析、词法分析、语义分析，以及相关的错误处理和符号表的建立

 后端：与目标代码相关的部分，主要包括代码优化、代码生成和相关错误处理。

 0型(短语文法，图灵机)：

产生式形如：   

其中： (VT  VN)*且至少含有一个非终结符； (VT  VN)*

 1型(上下文有关文法，线性界限自动机)：

编译原理课程教学的几点思考

针对编译原理课程在计算机本科教学中难讲、难学的特点，从理论教学、教学方法、实践能力培养等方面进行了探索，提出了相应的解决方法。

标签：编译原理；教学方法；实践能力

编译原理课程是计算机科学与技术学科下各专业的核心专业课程，其教学目标是通过教学实践训练学生的抽象思维能力和动手能力，旨在使学生掌握程序设计语言的形式化描述和编译的基本理论、原理和技术，并对编译程序有较为具体的认识。使学生能运用所学过的基本知识、着手开发系统程序，为今后的工作（理论研究和技术开发）打下基础。但由于其内容具有较强的理论性和实践性，学生在学习过程中感到内容抽象、算法复杂、难于理解，因此“编译原理”被普遍看作是计算机本科教学中最难讲解、最难学习的课程。针对这种情况，如何提高这门课程的教学效果，是一个值得探讨的问题。笔者近年来一直从事“编译原理”课程的教学，对如何改进教学方法和提高教学效果做了一些研究和探索。

1 明确教学目标，增强学习兴趣

对于编译原理这门课程，普通高校本科的教学目标是：通过编程语言实现技术的学习，提高学习编程语言及在程序开发中应用编程语言的能力，具体解释如下：提高学习、理解和使用编程语言的能力；提高程序排错的能力，即快速理解、定位和解决在程序开发与程序运行中遇到的问题的能力；提高编写高质量代码的能力。

另外，由于编译程序，由于编译程序作为系统软件在性能上具有严格的要求，这使得它所使用的算法经典、高效，而这些算法、思想和实现技术也可广泛地应用于一般软件的设计实现。如正规式和有穷自动机在文本编辑器中的广泛应用，有穷自动机在字符串查找中的运用，必经节点算法在网络中的运用，由文法来定义网络协议等。在教学中，可以鼓励学生尝试将编译程序中的各种算法和技术应用到各个应用领域，从而激发学生的创造性思维，培养学生的创新能力，为今后的学习打下坚实的基础。

2 运用多种教学方法，提高教学效果

“编译原理”课程具有很多概念和定理，再加上大量复杂的算法，抽象程度很高，因此要想获得良好的教学效果，必须借助形象化教学手段，使抽象的理论具体化。

编译原理复习

1.简答题

/**********往年问答题**********/

1)按照次序写出一个完整的编译器的各个阶段以及各个阶段的输入输出(The phases of a

complier)。

扫描程序：执行词法分析将字符序列收集到称作记号的有意义单元中。输入：源程序，输出：记号；

语法分析程序：从扫描程序中获得记号形式的源代码，并完成定义程序结构的语法分析。输入：记号，输出：语法树；

语义分析程序：分析程序中在执行之前被确定但是不易由语法表示和分析程序分析的特征，即分析程序中的静态语言。输入：语法树，输出：注释树；

源代码优化程序：对代码进行改进产生中间代码。输入：注释树，输出：中间代码；

代码生成器：得到中间代码，并生成目标机器的代码。输入：中间代码，输出：目标代码；

目标代码优化程序：改进由代码生成器生成的目标代码，包括：选择编址模式以提高性能、将速度慢的指令更换成速度快的，以及删除多余的操作。输入：目标代码，输出：优化后目标代码。

2)词法分析和语法分析的功能分别是什么(The task of a scanner,parser)

词法分析：将源程序读作字符文件并将其分为若干记号。

语法分析：从扫描程序中获得记号形式的源代码，并确定程序的语法结构，以及构造出表达该结构的语法树或分析树。

3)编译器的前端(front end)和后端(back end)分别包括哪几个阶段？前后端分开有什么好处？

前端：只依赖于源语言的操作，包括：扫描程序、语法分析程序、语义分析程序和中间代码的综合。

后端：只依赖于目标语言的操作，包括：代码生成器和一些优化分析。

好处：该结构对编译器的可移植性十分重要。

4)给出上下文无关文法(context-free grammar)的定义

若一个形式文法 G = (N, Σ, P, S) 的产生式规则都取如下的形式：V -> w，则称之为上下文无关的，其中 V∈N ，w∈(N∪Σ)*

编译技术命题指导意见

教学内容 知识点及题型

第一章 编译器概述 A （1）编译的阶段划分 [选择题 2分]

[1] 编译程序绝大多数时间花在( )上。

A. 出错处理

B. 词法分析

C. 目标代码生成

D. 符号表管理

答案：D

[2] ( ) 和代码优化部分不是每个编译程序都必需的。

A. 语法分析

B. 中间代码生成

C. 词法分析

D. 代码生成

答案：B

[3] 编译程序前三个阶段完成的工作是( )。

A. 词法分析、语法分析和代码优化

B. 代码生成、代码优化和词法分析

C. 词法分析、语法分析和语义分析

D. 词法分析、语法分析和代码生成

答案：C

（2）遍的概念 [填空题 2分]

[1] 编译阶段的活动常用一遍扫描来实现，一遍扫描包括 和 。

答案：读一个输入文件 写一个输出文件

[2] 将编译程序分成若干个“遍”是为了________。 答案：使程序的结构更加清晰

[3] 编译器从逻辑上可以分为7个阶段，其中，可以作为一个后端遍的是___________阶段。

答案：代码生成

（3）前端和后端的划分 [简答题 5分]

[1] 什么是前端？ [5分]

答案：编译器分成分析和综合两大部分。分析部分揭示源程序的基本元素和它们所形成的层次结构，决定它们的含义，建立起源程序的中间表示，分析部分经常被称为前端。

[2] 什么是后端？ [5分]

答案：编译器分成分析和综合两大部分。综合部分从源程序的中间表示建立起和源程序等价的目标程序，它经常被称为后端。

[3] 什么是前端？什么是后端？ [5分]