编译原理部分复习材料
编译原理部分复习材料 本文关键词：编译，复习，原理，材料
编译原理部分复习材料 本文简介：1．翻译器：能够完成从一种语言到另一种语言的变化软件。编译器：一种翻译器，它进行语言变换的特点是目标语言比源语言低级。编译的各个阶段：P2词法分析器——》语法分析器——》语义分析器——》中间代码生成器——》独立于机器的代码优化器——》代码生成器——》依赖于机器的代码优化器2．词法记号：由记号名和属性
编译原理部分复习材料 本文内容：
1．
翻译器：能够完成从一种语言到另一种语言的变化软件。
编译器：一种翻译器，它进行语言变换的特点是目标语言比源语言低级。
编译的各个阶段：P2
词法分析器——》语法分析器——》语义分析器——》中间代码生成器——》独立于机器的代码优化器——》代码生成器——》依赖于机器的代码优化器
2．
词法记号：由记号名和属性值构成的二元组，属性值有时不必要。记号名是代表一类词法单元的抽象名字，如标识符、某个特定的关键字。记号名是语法分析的输入符号。通常直接用记号名来引用记号。
模式：记号的模式描述属于该记号的词法单元的形式。在一个关键字作为一个记号的情况下，它的模式就是构成该关键字的字符序列。对于标识符和其他一些记号，它们的模式有更复杂的结构并且有很多字符串可以匹配它们。
词法单元：又称单词，是源程序中匹配一个记号模式的字符序列，它由词法分析器标识为该记号的实例。
在大多数编程语言中，关键字、算符、标识符、常数、文字串（字符串）和标点符号都处理为记号。
P16词法错误（概念）
P18正规式的定义
不确定的有限自动机：P23
1.
一个有限的状态集合S；
2.
一个输入符号的集合∑（也称输入符号字母表，空串ε绝不会出现在∑中）；
3.
一个转换函数move：S*(∑∪{ε})→P(S),它把状态和符号（可以是ε）两组映射到一个状态集合。
4.
状态s。是一个唯一的开始状态；
5.
状态集合F是接受（或终止）状态集合，并且F包含于S；
3
上下文无关文法定义：P39
（1）
VT
是一个非空有限集合，其元素称为终结符。
（2）
VN是一个非空有限集合，其元素称为非终结符，并有VT∩VN=非空
（3）
S是一个非终结符，称为开始符号。
（4）
P是产生式的有限集合。
概念：句子;
推导；语言；句型
P41
文法的优点：
（1）
文法为语言给出了精确的、易于理解的语法说明。
（2）
对于某些文法类，可以自动产生高效的分析器。
（3）
如果文法设计得当，则它赋予语言的结构对于把源程序翻译成为正确的目标代码和对于错误诊断都是有用的。
（4）
语言也是逐渐完善的，增加新构造以完成新任务的情况时有发生。
分离词法分析器的理由：
（1）
编译器的效率会改进。
（2）
编译器的可移植性加强。
（3）
把语言的语法结构分成词法和非词法两部分，为编译器前端的模块划分提供了方便的途径。
P47
消除左递归
普通的编程错误会出现在不同的层次上：
（1）
词法错误。如标识符、关键字或算符的拼写错误，遗漏字符串两端的引号。
（2）
语法错误。如算术表达式的刮号不配对。
（3）
语义错误。如算符和运算对象之间类型不匹配。
（4）
逻辑错误。如在c语言中用赋值号“＝”代替了比较算符“=
=”。
LR分析器富有吸引力的原因：
（1）
LR分析器能够被构造来识别所有能用上下文无关文法写出的编程语言构造。
（2）
LR分析方法是已知的最一般的无回溯的移进－归约方法，它能和其他移进－归约方法一样有效地实现。
（3）
LR方法能分析的文法类是预测分析法或者说LL方法能分析的文法类的直超集。
（4）
在自左向右扫描输入的前提下，LR分析器尽可能快地发现语法错误。
4．
综合属性：如果b是A的属性，c1，c2，····，ck是产生式右部文法符号的属性或A的其他属性，那么b称为A的综合属性。
继承属性：如果b是产生式右部某个文法符号X的属性，c1，c2，···，ck是A的属性或右部文法符号的属性，那么b称为X的继承属性。
S属性定义：仅仅使用综合属性的语法制导定义称为S属性定义。
注释分析树：每个结点的属性值都标注出来的分析树。
依赖图：分析树结点的属性之间的互相依赖可以用依赖图的有向图来描绘。
构造翻译方案的规则：
（1）
产生式右部符号的继承属性必须在先于这个符号的动作中计算。
（2）
一个动作不能引用该动作右边符号的综合属性。
（3）
左部非终结符的综合属性只能在它所引用的所有属性都计算完后才能计算。
（4）
只有综合属性的情况最简单。
6
活动纪录的结构：
（1）
临时数据；保存临时值。
（2）
局部数据；保存过程的局部数据。
（3）
保存的机器状态；保存刚好在过程调用前的机器状态信息，包括返回地址及调用过程使用并且在返回时必须恢复的寄存器的内容。
（4）
访问链；有些语言需要通过访问链来访问非局部数据。
（5）
控制链；用来指向调用者的活动记录。
（6）
参数；调用过程提供的实在参数，由被调用过程使用。
（7）
返回值。用于存放被调用过程返回给调用过程的值。
活动纪录设计布局原则：
（1）
调用者和被调用者之间交流的数据一般放在被调用者活动纪录的开始处，并尽可能靠近调用者的活动纪录。
（2）
固定长度的项通常放在活动纪录的中间，一般包括控制链、访问链和机器状态链。
（3）
在编译时不能及时知道大小的一些项放在活动纪录的末端。
参数传递的方法及特点：
（1）
值调用。值调用是最简单的传递参数的方法。调用者计算实参，并把它的值（右值）传给被调用过程。
（2）
引用调用。调用者把实参存储单元的地址（即实参的左值）传给被调用者，被调用者对形参的任何访问就是对对应实参的访问。
（3）
换名调用。P181
7.
使用独立于机器的中间形式的好处：
（1）
再目标比较容易。把针对新机器的后端加到现成的前端上，可以得到另一种机器的编译器。
（2）
独立于机器的代码优化器可用于这种中间表示。
8.
目标程序类型和特点：
（1）绝对机器语言程序。目标程序可以放在内存的固定地方并且立即执行，因此程序可用被迅速地编译和执行。
（2）可重定位机器语言程序。需要连接装入程序把一组可重定位目标模块连接成一个可执行的目标程序。虽然产生可重定位目标模块必须增加额外的开销来进行连接，但它带来的好处是灵活性。
（3）汇编语言程序。产生汇编语言程序作为输出使得代码生成的过程变得容易，因为可用产生符号指令并可利用汇编器的宏机制来帮助生成代码，所付出的代价是代码生成后的编译工序。
基本块
确定入口语句：
（1）
序列的第一个语句；
（2）
能够作为条件转移或无条件转移目标的语句。
（3）
紧跟在条件转移之后的语句。
篇2：编译原理课程信息(杨晓波)
编译原理课程信息(杨晓波) 本文关键词：编译，原理，课程，信息，杨晓波
编译原理课程信息(杨晓波) 本文简介：课程基本信息课程名称编译原理开课学期2011春季学期开课单位信息科学与工程学院（软件学院）授课教师杨晓波讲师课号编号26039学分/学时4/（48+48）全年/半年半年必修/选修必修上课时间2-13周星期一星期五上课地点复临舍课程网页核心能力关联备注课程大纲课程概述这是一门为计算机学科学生开设的专业
编译原理课程信息(杨晓波) 本文内容：
课程基本信息
课程名称
编译原理
开课学期
2011
春季学期
开课单位
信息科学与工程学院（软件学院）
授课教师
杨晓波
讲师
课号编号
26039
学分/学时
4/（48+48）
全年/半年
半年
必修/选修
必修
上课时间
2-13周
星期一
星期五
上课地点
复临舍
课程网页
核心能力关联
备注
课程大纲
课程概述
这是一门为计算机学科学生开设的专业基础课，通过该课程的教学使学生能够掌握编译过程中所涉及的基本理论、方法和技术。
课程目标
掌握编译原理课程的基本方法和基本原理，具体包括：词法分析、语法分析、语法制导翻译、中间代码生成、代码生成、代码优化等。通过编译原理的整个教学过程逐渐培养学生分析问题、解决问题的能力，使用编译程序中的原理和技术应用于一般的软件设计和实现中。
课程要求
本课程的前导课程为数据结构和程序设计语言等
答疑地点
软件学院办公楼317
指定教材
Alfred
V.Aho,Ravi
Sethi,Jeffrey
D.Ullman著,赵建华,郑滔,戴新宇译.编译原理第2版.北京：机械工业出版社,2009年5月
参考阅读
《编译原理(第二版)》，
张素琴、吕映芝、蒋维杜，清华大学出版社，2005
《程序设计语言编译原理》，陈火旺，国防工业出版社，2001
评分方式
(仅供参考)
20%
作业及出勤
30%
课程实验
50％
期末考试
Course
Basic
information
Name
Compilers
Principles
Semister
2010-2011(2)
School
Software
school
Teacher
Yang
Xiaobo
Course
Code
26039
Credit/Class
Hours
4/（48+48）
Whole
Year/half
Year
Half
year
Type
Compulsory
Time
2-13week
Tuesday
/
Friday
Location
Fulin
building
Course
web
Syllabus
Course
Description:
This
is
a
basic
course
for
majors
of
computing,aiming
at
the
students’
mastery
of
the
basic
concepts,theories
and
techniques
of
compilers.
Course
Objectives
The
study
of
this
course
develops
the
students’
ability
to
analyze
and
solve
practical
problems,and
to
understand
and
use
the
principles
and
techniques
of
compilers
in
the
software
design
and
implementation.
The
main
contents
of
this
course
are
the
basic
approaches
and
principles
of
compilers,including
lexical
analysis,syntax
analysis,syntax-directed
translation,immediate
code
generation,code
generation
and
optimization.
Requirements
Data
Structures,Programming
Languages
Location
for
answer
questions
Room
317,Software
Building
Book
《Compilers
Principles,Techniques
&tools,Second
Edition》，Alfred
V.Aho,China
Machine
Press,2009
Reference
《Principles
of
compiling,Second
Edition》,Zhangsuqin,Tsinghua
University
Press，2005
《Compiling
principles
for
Programming
Language》，Chenhuowang，National
Defence
Industry
Press，2003
Evaluation
20%
Exercise
and
attendance
30%
Experimentation
50％
Final
exam
课
程
教
学
进
程
表
星期
日
期
授
课
内
容
作
业
课程实验
2
2月28日
课程介绍，编译原理的基本概念，语言处理器，编译器结构，编译程序的其他问题。编译程序的构造方法
1.1.1,3月4日
程序语言的发展历程，编译技术的应用，程序设计语言基础
1.6.1，1.6.2
3
3月7日
词法分析器的作用；
记号的说明
3.3.2，3.3.3，
3月11日
记号的识别，词法分析器生成工具lex介绍，有限自动机
3.4.1a)b)，3.6.3，
3.6.4
4
3月14日
有限自动机，从正则式到有限自动机，词法分析器生成工具的设计方法
3.7.1，3.7.2，3.9.3
3月18日
语法分析器介绍，上下无关文法，推导、句型、句子、语言、语法分析树，二义性
4.2.1，
4.2.2
5
3月21日
消除左递归，提取左公因子
4.3.2
3月25日
自顶向下语法分析
4.4.4
6
3月28日
LL(1)分析表的构造
4.4.1
4月1日
自底向上分析
LR(0)分析
7
4月4日
SLR分析
LR(1)分析
4.6.4，
4.6.6
4月8日
LR(1)分析
4.7.4
8
4月11日
LALR分析
4.7.5
4月15日
语法制导定义
SDD的求值顺序
5.1.1，
5.2.3，
5.2.4
9
4月18日
语法制导定义的应用
5.3.1
4月22日
语法制导定义的翻译方案
L属性定义SDD
5.4.4
10
4月25日
中间代码的分类与介绍
类型和声明
6.1.1，
6.1.2，
6.2.1，
6.3.1
4月29日
表达式中间代码生成
控制流
6.4.3，6.4.6，
6.6.4
11
5月2日
回填
开关语句翻译模式
过程中间代码
6.7.1
5月6日
存储组织
空间的栈式分配
7.2.5，7.2.6
12
5月9日
非局部名字访问
堆管理
7.3.2
5月13日
代码生成器设计
目标语言
基本块划分
8.2.1，8.2.6
13
5月16日
流图
基本块内优化
8.5.1，8.5.5
5月20日
简单的代码生成器
窥孔优化
复习
8.6.1
a）
篇3：编译原理实验报告yacc的使用
编译原理实验报告yacc的使用 本文关键词：编译，原理，实验，报告，yacc
编译原理实验报告yacc的使用 本文简介：1.1错误信息统计1.2正确运行及结果：2yacc脚本%{#include#include%}%tokenNUMBER%%command:exp{printf(“%d/n“,$1);};/*printtheresult/exp:exp+term{$$=$1+$3;}|exp-term{$$=$1-$
编译原理实验报告yacc的使用 本文内容：
1.1错误信息统计
1.2正确运行及结果：
2
yacc脚本
%{
#include
#include
%}
%token
NUMBER
%%
command:
exp
{printf(“%d/n“,$1);}
;/*
the
result/
exp:exp
+
term
{$$
=
$1
+
$3;}
|exp
-
term
{$$
=
$1
-
$3;}
|term
{$$
=
$1;}
;
term:term
factor
{$$
=
$1
$3;}
|factor{$$
=
$1;}
;
factor:NUMBER{$$
=
$1;}
|
(
exp
)
{$$
=
$2;}
%%
main()
{
return
yyparse();
}
int
yylex(void)
{
int
ch;
ch
=
getchar();
if(isdigit(ch))
{yylval
=
ch
-
0
;
return
NUMBER;};/*
数字/
if(ch
==
/n
)
return
0;
return
ch;
}
void
yyerror(chars)
{
fprintf(stderr,“%s/n“,s);/*
error
message/
}
3．
Yacc脚本中，%token是定义的终结符还是非终结符？
NUMBER又是属于什么性质的符号？
%token是定义的是终结符，NUMBER属于宏定义常量，是由yacc内部决定的终结符编号常量。
4.指出上面的Yacc脚本中，其定义部分、规则部分和辅助程序(用户程序)部分各是什么？
定义部分：
%{
#include
#include
%}
%token
NUMBER
规则部分：
%%
command:
exp
{printf(“%d/n“,$1);}
;/*
the
result/
exp:exp
+
term
{$$
=
$1
+
$3;}
|exp
-
term
{$$
=
$1
-
$3;}
|term
{$$
=
$1;}
;
term:term
factor
{$$
=
$1
$3;}
|factor{$$
=
$1;}
;
factor:NUMBER{$$
=
$1;}
|
(
exp
)
{$$
=
$2;}
%%
辅助程序部分：
main()
{
return
yyparse();
}
int
yylex(void)
{
int
ch;
ch
=
getchar();
if(isdigit(ch))
{yylval
=
ch
-
0
;
return
NUMBER;};/*
数字/
if(ch
==
/n
)
return
0;
return
ch;
}
void
yyerror(chars)
{
fprintf(stderr,“%s/n“,s);/*
error
message/
}
5.规则部分定义了几个非终结符成分，各是什么？其中，开始符是哪一个？如何从Yacc脚本中快速寻找开始符？
规则定义了3个非终结符，分别是exp,term,factor；其中exp时开始符，寻找最初输入变量接收值的非终结符。
6.这个Yacc脚本实现了几条规则，试根据Yacc的规则部分，写出实现的这几条规则。
实现了三条规则，分别是加法，减法和乘法。
7.在这个Yacc脚本中，哪一部分代码实现了数字的输入？
command:
exp
{printf(“%d/n“,$1);