编译原理第一章

引言

程序设计语言的产生

语言本质：一组规则的组合

• 字母表的定义
• 词法规则：单词符号的形成规则——规定了该单词由哪些字母、按照什么顺序进行排序
• 语法规则：语法单位的形成规则——短语、从句、句子、段落、文章

程序设计：给出解决特定问题的方法和过程，并以某种程序设计语言为工具，编写出该语言的程序

程序设计语言的发展

机器语言->汇编语言->高级语言

机器语言：

第一代程序设计语言

字母表：{0,1}

单词符号：操作码，地址

语法单位：指令（1000 1011）、程序（指令的组合）

优点：可以直接运行

缺点：

• 编写十分繁琐和痛苦
• 程序不便于记忆、阅读和书写，容易出错
• 可移植性差

汇编语言

将机器语言符号化产生汇编语言

字母表：主要增加了英文字母

单词符号：操作码、内存符号、寄存器、数据

单词符号：指令（ADD A，R0）、程序（指令的组合）

高级语言

特点

• 直观、自然、易于理解
• 易读、易写、易于交流、存档
• 易于移植

翻译与执行

翻译等价的变换

计算机只可以直接执行用机器语言编写的程序。而用汇编语言和高级语言编写的程序，机器不能直接执行，必须翻译成完全等价的机器语言程序才能执行

汇编器：汇编语言->机器语言

编译器：高级语言->机器语言

解释：语言的一种翻译与执行方式

BASIC最简单的解释型高级语言

解释执行特别适用于动态语言和交互式环境，便于人机对话。

解释器边编译边执行重复执行的语言需要重复翻译，比编译执行要花更多的时间，执行效率较低

三种语言与三种程序

源语言、宿主语言、目标语言

源程序、翻译程序、目标程序

语言的设计与实现

高级语言涉及三类人：设计者、实现者、使用者

• 设计：确定一个高级语言的各种规则的工作
• 实现：编写一个高级语言的编译器的工作

强制式语言

程序设计语言的分类

按语言的设计的理论基础：

• 强制式语言：基础冯诺伊曼模型
• 函数式语言：基础数学函数
• 理解式语言：基础数学逻辑、谓词演算
• 对象式语言：基础是抽象数据类型

按语言的发展进程分类

• 第一代语言：机器语言
• 第二代语言：汇编语言
• 第三代语言：高级语言：命令式、过程式
• 第四代语言：说明性语言、超高级语言
• 新一代语言：函数式、逻辑式语言

冯诺伊曼体系结构

构成基础

存储器，控制器，处理器，IP

特点

• 数据，指令二进制形式存储
• 存储程序的工作方式
• 程序顺序执行，可强制修改执行顺序
• 存储器的内容可以被修改

在命令式语言上的表现

• 变量：存储单元由变量的概念代替，变量可以代表一个或一组单元
• 赋值：存储计算结果
• 重复：语句顺序执行，指令存储子啊有限的存储器中，完成复杂的计算时需要重复执行某些指令序列

绑定的概念

• 实体：程序的组成部分，如变量、表达式、程序单元等

• 属性、实体具有的特性

• 绑定：实体与其各种属性建立联系的过程称为绑定

• 描述符：描述实体属性的表格

• 静态特性：编译时确定的特性

• 动态特性：运行时才能确定的特性

若绑定在编译时完成，且在运行时不会改变，则称为静态绑定。若绑定在运行时完成，则称为动态绑定

变量

变量是对一个或若干个存储单元的抽象；

一个存储单元至少一个字节构成；

一个变量至少占用一个存储单元；

变量用名字来表示

赋值是对修改单元内容的抽象

变量的4个属性

• 作用域：可以访问变量的程序范围。
• 生存期：变量绑定存储区的时间区间、变量获得存储器的活动称为分配、变量分配的存储单元的个数称为变量长度
• 值：存储区的内容
• 类型：与变量相关联的值，以及对这些值进行操作的抽象

程序单元

程序单元是程序执行过程中被独立调用的单元，如子程序、分程序、函数、过程等

单元表示：

• 编译时：单元表示为单元等源程序
• 运行时：单元表示由一个代码段和活动记录组成，称为单元实例活动记录

执行单元：需要的信息，及该单元的局部变量的存储区

非局部单元：一个程序单元可以未被本单元说明而被其单元说明的变量

全局变量：在一个程序中，各个单元都可以引用的变量。

引用环境：一个程序单元可以引用的局部变量、非局部变量和全局变量

局部环境：局部变量绑定在存储U的当前活动记录中的数据对象，称为局部环境

非局部环境：非局部变量绑定与其他的程序单元的活动记录中的数据对象；或非局部变量绑定的全局数据区中的数据对象称为非局部环境

别名：同一单元的引用环境有两个或多个变量绑定于同一数据对象，称为这些变量互为别名

副作用：对一个非局部变量的修改