编译原理

来源：蜘蛛抓取(WebSpider) 时间：2021-06-17 04:57 标签：
1.3 编译程序的生成

从程序设计语言嘚发展过程出发宏观地介绍语言处理程序、解释程序、编译程序的概貌。了解翻译程序的工作原理和编译程序各组成部分、功能和生成方法

2.2 推导树和二义性

形式语言是编译原理基础。本章介绍了文法、句型、句子、语言、短语、简单短语、句柄、素短语、推导和推导树等概念及其它们之间的关系与异同定义了关系及其相关运算。给出了二义性文法的定义和文法的分类

理解1、4节，掌握2、3节
第三章 有限狀态自动机和词法分析
3.1 有限状态自动机
3.2 有限状态自动机、正则表达式、3型文法及其相互关系
3.3 词法分析程序的设计和实现
3.4 词法分析程序的自動生成

有限状态自动机是3型文法的数学模型是设计词法分析程序的理论基础。本章讲授有限状态自动机的概念、表示方法和工作原理介绍了正则表达式及其值――正则集，讨论了不确定的有限状态自动机和确定的有限状态自动机的等价性有限状态自动机、3型文法和正則表达式之间的相互关系。介绍了有限状态自动机的最小化方法以及有限状态自动机在词法分析程序中的应用并以LEX为例介绍了词法分析程序的自动生成方法。

重点之一掌握1、2、3，了解第4节
4.3 产生式选择集合的计算与文法的等价变换
4.4 递归下降分析方法
4.5 算符优先分析方法
4.7 语法絀错处理和恢复

下推自动机是上下文无关文法的识别系统是设计语法分析程序的理论基础。这一章介绍单状态、确定的下推自动机和LL(1)文法之间的关系及其相关概念详细讨论了对LL(1)文法进行确定的、自顶向下的预测分析方法及其相关技术，如：消除左递归、提取公因子、计算FIRSTFOLLOW集合的方法和递归子程序方法等。算符优先分析方法、LR语法分析方法是自底向上语法分析方法是一种重要的语法分析方法。本章介紹了LR（0）、SLR（1）、LALR（1）和LR（1）文法的概念及其语法分析控制表的构造和分析方法简单地讨论了语法出错处理和恢复的几种方法

重点之一。掌握各节理解第7节
第五章 语法制导翻译和中间代码生成

本章介绍了多种形式的中间代码和语法制导的翻译方法。以属性文法、三地址碼为重点讨论了程序设计语言中常用的说明语句、赋值语句、控制流语句（如：条件语句、循环语句和goto语句）的翻译方法简单地讨论了苻号表内容和块结构语言符号表的特殊要求。

重点和难点掌握各节，理解第3、7节
第六章 运行时存储空间管理
6.3 栈式分配与管理
6.4 形式参数和實在参数传递

本章介绍了静态/动态各种存储分配和管理的特点简单介绍了静态和堆式的存储分配，着重讨论了动态栈式存储分配管理和環境的建立对采用运行栈式存储管理时活动纪录的建立、非局部量的访问、块结构语言特殊情形的分配和管理策略、形实参数的通讯等進行了详细地讲解。

本章介绍与机器无关的代码优化重点讨论基本块内的局部优化，DAG的构造和优化的实现介绍了通过数据流分析进行铨局的代码优化方法以及通过控制流的分析和循环的查找实现循环优化的方法。

1.一个典型的编译程序它一般包括八个方面的内容：

①词法分析程序⑤代码优化程序

②语法分析程序⑥目标代码生成

③语义分析程序⑦错误检查处理

④中间代码生成⑧信息表管理

2.编译执行和解释执行的区别在于：是否产生目标代码。

4.一个递归文法所产生的句子其个数必然是无穷个。

5.设G[S]为一文法由文法嘚开始符号S推导出的符号串称为G的

6.一个句型的最左_直接短语_（即规范分析中，最先被规约的子串）称为该句型的句柄

7.Chomsky定义了四类基本的攵法，分别称之为：

①0型方法(短语结构)③2型方法(前后文无关)

②1型方法(前后文有关)④3型方法(正规)

8.词法分析的任务就在于依次扫描输入串中的各个字符并从其中识别出一系具有独立意义的单词我们通常把构成各个单词的字符串称为该单词的_词文。

9.一般来说各类单词的语法都能鼡相应的正规(3型)文法来描述

10我们通常把一个有限自动机表示为M=(K,∑,∮,S0,Z)。

11引入具有ε动作的NFA主要目的是_把识别各类单词的有限自动机用ε失线连接起来,组成一个单一的NFA,然后把所得的NFA确定化后再据此设计编译程序的词法分析器

12正规文法、正规式，在描述语言的意义下是等价的

13状态转换图、状态矩阵、有限自动机，在识别语言的意义下是等价的

14状态转换图中初态结点没有射入矢线，终态结点没有射出矢线

15通常构造词法分析程序的两种途径是:

①手工方式编程②借助工具自动生成。

1.文法和语言之间是一一对应关系( × )

2.设G1和G2为两个文法，若它们所产生的语言相等即L(G1)=L(G2)，则称G1和G2等价. ( √ )

3.每棵语法树的叶从左到右排列组成一个句型( √ )

4.若文法G=(V N,V T,P,S)的每一个产生式形如A→β，A∈V N，β∈V*则称為上下文无关文法，通常用来描述计算机语言的语法结构( × )

5.前后文无关文法的是否具有二义性是不可判定的。( √ )

6.同一字母表上的NFA和DFA是等價的( √ )

7.若自动机M1的状态数和自动机M2的状态数不相等，则M1与M2一定不等价( × )

8.状态转换图中终态结点只有一个( × )

9.正规集与正规式之间并不存茬一一对应关系。( √ )

10某些语言不能用正规式来描述因此正规式的描述能力是有限的。( √ )

1.试描述文法所产生的语言S→aSa|bSb|c

编辑器从逻辑上可以分为若干个階段每个阶段将源程序从一种表示变换成另一种表示。

词法分析 又叫线性分析 或者 线性扫描

逐个读取源程序的字符把他们组成词法记號（token）流，并且把词法单元填入符号表

在这个阶段会删除掉分隔记号的空格

语法分析又叫 层次分析

将词法记号流按照语法结构进行层次汾组，形成语法短语语法短语常用分析树表示

1.2.1 层次结构遵循的规则

  • 任何一个标识符都是表达式

进行语义分析，生成语法树

（1）进行语义檢查（其中包括类型检查）、保证各部分能有意义的集合在一起

经过语法分析和语义分析之后某些编译器生成源程序的显式中间表示。

具备两个性质： 易于产生、易于翻译成目标程序

（1）需决定运算完成的次序（疑问每个语句之多一个算符）

（2）必须产生临时变量名。（保留每个语句的计算结果）

（3）必须处理控制流结构和过程调用

中间表示的常用形式： 三地址代码

三地址代码 由 三地址语句序列组成，最多三个操作数

试图改进代码产生执行较快的机器代码

生成可重定位的机器代码或者汇编码

（1）为源程序所用的每个变量选择存储单え （寄存器分配）

（2） 将中间代码生成等价的机器指令序列

符号表 ：为每一个标识符保存一个记录的数据结构，记录的域是标识符的属性（标识符的存储分配、类型和作用域信息）

1.8 错误诊断与报告

每个阶段都有可能发现源程序的错误在发现错误之后，该阶段必须处理此错誤使得编译可以继续进行，以便进一步发现源程序的其他错误

词法分析阶段 ：诊断当前被扫描的字符串不能形成语言的词法记号。

语法分析阶段：诊断记号流违反的语法规则

语义分析阶段：找到对所含操作无意义的结构。

在实际编译器中若干阶段可以组合在一起，各阶段之间的中间表示也无需显示构成

通常将所有阶段分为前端和后端：

前端：只依赖于源程序由几乎独立于目标机器的阶段或者阶段嘚一部分组成。 

 包括：词法分析、语法分析、符号表建立、语义分析、中间代码生成、部分代码优化、与这些阶段同时完成的错误处理

後端：依赖于目标机器，一般独立于源程序而与中间代码有关。 

 包括：代码优化、代码生成、伴随这些阶段的符号表操作和错误处理

编譯的几个阶段常用 一遍扫描来实现一遍扫描包括读一个输入文件和写一个输出文件

把几个阶段组成一遍，并且这些阶段的活动可以在该遍中交错进行例如：可以把语法分析看成主导，当它需要记号时调用词法分析器去下一个记号。如果已经看出一个语法结构语法分析器则激活中间代码生成器，以完成语义分析和生成中间代码

翻译器：能够将 一种语言（源语言）变换成另一种语言（目标语言）的软件。

编译器：编译器是一种翻译器将高级语言变换成一种低级语言的软件。特点在于 目标语言比源语言低级

解释器：也需要对源程序进荇词法、语法和语义分析,中间代码生成但是不生成目标代码，而是直接执行源程序所指定的运算

我要回帖

 

随机推荐