编译原理复习要点（打印版）

3.0 文小白 2023-09-15 521 0 113.5KB 3 页 10文币

侵权投诉

翻译程序：有这样的一个程序，它把用

汇编语言或高级语言编写的程序转换成

等价的机器语言程序，我们把这种执行

转换功能的程序统称为翻译程序。

编译：高级语言的翻译程序称为编译程

序。

编译程序的输入对象称为源程序，输出

对象称为目标程序。

编译程序支持的源程序的执行分为两个

阶段：编译阶段，运行阶段。

编译阶段：对整个源程序进行分析，翻

译成等价的目标程序，翻译的同时做语

法检查和语义检查，凡是有错误的源程

序均指出其错误。运行阶段在运行子程序

的支持下执行目标程序。运行子程序是为

了支持目标程序的运行而开发的程序。

编译程序的功能结构：

词法分析：扫描程序的 ASCII 码序列，识

别出一个个具有独立意义的最小语法单

位，并把每个单词的 ASCII 码序列替换为

所谓的 token 形式。

语法分析：根据程序设计语言的语法规

则，把词法分析的结果分解陈各种语法

单位，同时检查程序中的语法错误。

语义分析：对语法分析所识别出的各类

语法范畴，分析其含义，并进行静态语

义检查。

中间代码生成：上述过程后，有些编译

程序将程序变成一种内部表示形式，这

种表示形式叫做中间代码

中间代码优化：对前阶段产生的中间代

码在不改变源程序的前提下进行加工变

化，使生成的代码更高效，缩短运行时

间或节省存储空间。

目标代码生成：把中间代码变换成特定

机器上的机器指令代码或汇编指令代码。

表格管理：编译程序在对源程序的分析

过程中，需要创建和管理一系列的表格，

以登记源程序的各类信息和编译各阶段

的进展情况。

错误处理：一个编译程序不仅能对书写

正确的程序进行翻译，而且能对出现在

源程序中的错误进行处理。

文法：是用有限的规则表示无穷字符串

集的一种方法

O型文法: 也称为短语文法，其产生式具

有形式:a→b，其中 a,bÎ(VTÈVN)*，并且

a至少含一个非终极符;

1型文法: 也称为上下文有关文法。它是 0

型文法的特例。其产生式具有形式 :

（1）aAb→agb,AÎVN, g为非空串 .或

（2）|a| £ |b| (S 是开始符,S→e除外，

且S不出现在任何产生式的右部)

2型文法: 也称为上下文无关文法。它是 1

型文法的特例。其产生式具有形式:A→ b,

AÎVN, b为非空串. 即要求产生式左部是

一个非终极符.

3型文法: 也称为正则文法。它是 2型文

法的特例。其产生式的右部至多有两个符

号，而且具有下面形式之一: A →a ，A

→a B, 其中 A,BÎVN ，aÎVT

文法描述能力 O型文法 > 1 型文法 > 2 型

文法 > 3 型文法

文法对应自动机

O型文法(短语文法):图

灵机 1型文法（上下文有关文法）:线性

有界自动机 2型文法（上下文无关文

法）:下推自动机 3型文法（正则文法）:

有限自动机

句型:如果有 S Þ* a, S 是文法的开始符,

a∈ (VTÈVN )*，则称 a是G的句型

句子:如果有 S Þ+ a, S 是文法的开始符,

a∈ VT*，则称 a是G的句子

短语：一个句型形如 abg, 如果存在一个

句型 aAg,而且 AÞ+b, 则称 b为句型 abg

的短语;

一个句型形如 abg, 如果存在一个句型

aAg,而且

A Þ b, 则称 b为句型 abg 的简单短语;

句柄:一个句型的简单短语可能有多个，

称最左简单短语为句柄

规范推导：最右推导

每个句子一定有最右(规范)推导，每个句

型不一定有最右(规范)推导

二义性文法：如果文法的一个句子有两

棵或两棵以上不同的语法分析树，则称

该文法为二义性文法。

消除文法二义性的常用方法： 1、规定符

号的优先级 2、规定符号的结合性

文法变换：有些语法分析方法要求被分

析的文法满足一定的约束条件，当被分

析的文法不满足这些条件时，常常要进

行文法变换。文法变换必须保证变换前后

的两个文法 G1 和G2 是等价的，即 L(G1)

= L(G2)

消除公共前缀

A ® ab1 | … | abn| g1|…|

gm提取公因子A ® aA’| g1|…| gm，A’

® b1 | … | bn

消除左递归

A ® A a1 | … | A an| b1|…|

bm消除: A ® b1A’|…| bmA’ ，A’ ® a1A’

| … | anA’|e

自动机：是为研究有限内存的计算过程

和某些语言类而抽象出的一种计算模型。

NFA

到

DFA

的转化思想：将 NFA 的状态

集当作DFA 的状态，同时确保转化后的

DFA 与原 NFA 等价

DFA

化简思想：等价状态：对于DFA 中

的两个状态 s1 和 s2，如果分别将 s1 和

s2 当作开始状态，它们接受的字符串集

合相同，则称 s1 和 s2 是等价状态;

DFA

化简的两种方式 :合并等价状态; (状

态合并法)分离不等价状态;（状态分离

法）

DFA

和

NFA

的不同：

DFA

NFA

初始

一个初

初始状态

e边

不允许

允许

f (S, a)

S’ or ⊥

{S1, …,

实现

容易

有不确定

自顶向下语法分析主要思想：是从文法

的开始符号出发，试图为输入串建立一

个最左推到，或者为输入串构造一个语

法树。

自顶向下语法分析条件：对任意非终极

符A，A的任意两条产生式

predict(A→bk)Ç predict(A→bj )=Æ，k ¹ j

不满足

LL(1)文法条件的情形：文法的产

生式存在左递归或公共前缀。

递归下降语法的做法：对文法中每个非

终极符 U都编写一个子程序，以完成该

非终极符所对应的语法成分的分析和识

别任务。

某个非终极符的语法分析子程序的功能：

用该非终极符的规则的右部符号串去匹

配输入串。

递归下降法优点：程序结构和层次清晰

明了，易于手工实现，就语义加工来说，

这种方法是十分灵活的。缺点：对文法的

限制太严格，频繁调用子程序，分析效

率低

LL(1

的主要思想：LL 的含义是从左到右

扫描输入串，采用最左推导分析句子。数

字1表示分析句子时需向前看一个输入

符号。LL(1)方法和递归下降法属于同一级

别的自顶向下分析法(分析条件相同)。

LL(1) 文法的特性：无二义性，无左递归，

对于一个非终极符来讲,最多只有一个空

产生式

递归下降法与

LL(1) 的相同点：同属于自

顶向下分析法，分析条件相同。不同点：

递归下降法对每个非终极符产生子程序，

而LL(1)方法则产生 LL 分析表；递归下降

法能判断每个产生式的结束，而 LL(1)方

法则不能；递归下降法分析法不用符号

栈，而 LL(1)方法则用符号栈。

自底向上分析主要思想：从输入串出发 ;

尽可能地找到可归约子串并将其归约成

一个非终极符;直到归约成文法的开始符

或发现语法错误;

规范推导：最右推导

规范句型：最右推导导出的句型

规范前缀:若有规范句型 α η ，且 η是终

极符串或空串，则称 α为规范前缀。

规范活前缀:若规范前缀α不含句柄或含

一个句柄并且句柄在 α的最右端，则称

规范前缀α为规范活前缀。

规约规范活前缀:活前缀α是含句柄的活

前缀，并且句柄在 α的最右端，则称活

前缀α为规约规范活前缀。

LR 方法主要思想：从左至右读入输入串;

每次找到句柄(归约规范活前缀)来进行归

约;归约直到得到开始符或报告语法错误;

LR(0) 项目 :带圆点的产生式,圆点只能出

现在产生式的右部符号串的任意位置;

LR(0) 分析的局限：LR(0)文法仅凭符号栈

里的内容来确定可归约活前缀, 非常容易

产生冲突;LR(0)文法易于产生冲突的原因

在于在确定分析动作时没有考虑输入串

信息。

LR(1) 分析基本思想 :对于非终极符的每

个不同出现求其后继终极符(follow), 称

为展望符;一个非终极符的一个出现的所

有后继终极符构成的集合称为展望符集;

展望符集的作用: 对于移入型项目, 不起

作用,但是需要保存;对于归约型项目, 表

示只有当下一个输入符是其中一个展望

符时, 才可以进行归约动作

LR(1) 分析存在的问题：为消除冲突，引

入太多的状态，构造分析表的工作量及

所占存储空间较大;

LALR(1) 分析主要思想：合并文法 G的

LR(1)自动机中的同心状态，得到的自动

机称为 LALR(1) 自动机；若这个得到的

LALR(1)自动机没有冲突，则称文法 G是

LALR(1)文法。

分析能力 : LR(1) É LALR(1) É

SLR(1) É LR(0)

状态数: LR(1) > LALR(1) = SLR(1) = LR(0)

语法：是描述一个合法定义的程序结构

的规则

语义：说明一个合法定义的程序的含义

词法分析和语法分析是对源程序形式上

的识别和处理，而语义分析是对源程序

的语义做相应的处理工作。

静态语义：编译时可以检查的语义

动态语义：目标程序运行时才能检查的

语义

静态语义检查内容：各种条件表达式的

类型是不是 Boolean 型，运算符的分量

的类型是否相容，赋值语句的左右部的

类型是否相容，形参和实参的类型是否

相容，下表表达式的类型是否为所允许

的类型等。

符号表：可看作是从标识符名字到它的

属性的映射;用于存储程序中声明的标识

符及其属性;

为什么在语义分析时需要符号表 ?从标识

符的 Token 定义，我们仅仅知道了标识

符的名字，对于其它属性，例如类型，

种类等没有记录，对于标识符的更多信

息需要进行语义分析，从而检查语义错

误;

为表示标识符的属性，我们需要建立：

标识符的内部表示，类型的内部表示，

值的内部表示。

为什么需要类型的内部表示?类型是标识

符的重要属性;类型检查是语义分析的重

要部分;类型的结构对类型检查很重要;

标识符声明：查找符号表检查标识符是

否已经被声明过;如果是，则重复声明错；

如果不是，则建立标识符的内部表示，

将其放入符号表;

标识符使用：查找符号表检查标识符是

否有声明；如果是，则取出标识符的属

性进行语义分析；如果不是，则未声明

错；

声明的语义分析:收集被声明的标识符的

属性;建立被声明标识符的内部表示;检查

重复声明错误;将被声明标识符的内部表

示插入符号表;

中间代码生成方法：语法制导的翻译方

法：属性文法和动作文法,基于 Token 序

列,基于抽象语法树

运行时间环境:是指目标计算机的寄存器

和内存结构，该结构用于管理内存和维

护目标程序执行时需要的信息.

过程活动记录:每当过程/函数被调用时，

为其分配的局部空间的一种统一结构。存

放在栈区的一段连续的存储单元中，由

目标程序进行管理。是过程一次活动的一

个现场记录。过程调用的时候进行填写，

过程返回的时候释放。

活动记录通用结构：

临时变量

局部变量

形参

返回地址

控制信息

动态链：如果每个 AR 是等长的则用 sp

减去这个长度就可以了，但实际上每个

AR 的长度不一定相同，所以在每个 AR

中要保存其前一个 AR 的始地址，于是栈

上的 AR 被连起来了，这样连起来的AR

结构称之为动态链。

目标代码生成器主要任务: 给变量分配实

际地址,寄存器分配,生成管理 AR 的指令

和其他指令。

寄存器分配应遵循的原则：寄存器优先

原则：即变量的值尽可能的存放在寄存

器中。寄存器活跃原则：即变量的值至少

有下一次的引用时才分配寄存器。寄存器

多载原则：即一个寄存器中可能存放多

个变量的值。典型的例子是通过赋值操作

的结果。源变量和被赋值的变量共用一个

寄存器

表达式四元式生成算法

(1)初始化: S1 和S2 为空;

(2) 读token: tk=ReadOne();

(3) Switch tk of

(i) #: if (S1 为空) exit;

else while (S1 不为空)

{op = pop(S1); (a, b)=pop(2); t=

NewTemp(dir);

GenIR(op, b, a, t); push(S2, t);

}

(ii)操作数: push(tk, S2); goto (2);

(iii)操作符: if (S1 为空 || tk 优先级大于

Top(S1))

{ push (tk, S1); goto(2);}

else { while(tk 小于等于Top(S1) && S1

不为空))

{op = pop(S1); (a, b)=pop(2); t=

NewTemp(dir);

GenIR(op, b, a, t); push(S2, t);

}

push(tk, S1); goto (2);

}

带括号表达式四元式生成算法:

(1)初始化: S1 和S2 为空;

(2) 读token: tk=ReadOne();

(3) Switch tk of

(i) #: if (S1 为空) exit;

else while (S1 不为空) {

op = pop(S1); (a, b)=pop(2); t=

NewTemp(dir);

GenIR(op, b, a, t); push(S2, t);}

(ii)操作数: push(tk, S2); goto (2); ‘(’：

push(tk,s1);goto(2);

(iii)操作符: if (S1 为空 || tk 优先级大于

Top(S1))

{ push (tk, S1); goto(2)}

else { while(tk

小于等于

Top(S1)

&& Top(S1) ≠ ‘(’ && S1

不为空 )))

{ op =

pop(S1); (a, b)=pop(2);

t= NewTemp(dir);

GenIR(op, b, a, t);

push(S2, t); }

push(tk, S1); goto (2);}

(iv) ‘)’: while (Top(S1) ≠ ‘(’ ) {op = pop(S1);

(a, b)=pop(2); t= NewTemp(dir); GenIR(op,

b, a, t);

push(S2, t);}

pop(S1); goto (2);

正则表达式

对于给定的字母表å, å 上的一个正则表

达式定义了 å的一个字符串集合。如果

用RS 表示 å上的一个正则表达式, 则用

L(RS) 表示 RS定义的字符串集合。

规范活前缀决定分析动作

移入:规范前缀不包含简单短语; 移入型

规范前缀

归约:该规范前缀只包含一个简单短语,而

且是在该规范前缀的最后;

可归约规范前缀：归约规范活前缀

LR(K) 分析法的工作过程输入流分析栈

分析表驱动程序移入归约成功报错

标识符的不同种类常量标识符类型标识

符变量标识符函数标识符过程标识符

域名标识符

语法制导定义语法制导文法就是基于文

法结构，在每个产生式的右部增加的语

义动作（或语义子程序），在语法分析

过程中，如果遇到语义动作，就完成对

应的语义处理

语法制导的方法两部分，一是抽象的部

分，即带有动作的文法描述；二是实现

部分，即语法分析的同时能够处理语义

动作的驱动程序

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 文币 0人已下载

立即下载

已全部加载

摘要：

翻译程序：有这样的一个程序，它把用汇编语言或高级语言编写的程序转换成等价的机器语言程序，我们把这种执行转换功能的程序统称为翻译程序。编译：高级语言的翻译程序称为编译程序。编译程序的输入对象称为源程序，输出对象称为目标程序。编译程序支持的源程序的执行分为两个阶段：编译阶段，运行阶段。编译阶段：对整个源程序进行分析，翻译成等价的目标程序，翻译的同时做语法检查和语义检查，凡是有错误的源程序均指出其错误。运行阶段在运行子程序的支持下执行目标程序。运行子程序是为了支持目标程序的运行而开发的程序。编译程序的功能结构：词法分析：扫描程序的ASCII码序列，识别出一个个具有独立意义的最小语法单位，并把每个单词...

展开>> 收起<<

编译原理复习要点（打印版）.doc

共3页,预览3页

还剩页未读，继续阅读

编译原理复习要点（打印版）

相关推荐

开通VIP享超值会员特权

作者详情

相关文档

推荐作者

热门标签

举报选择: