计算机导论_第4章

内容提要

程序设计语言翻译系统
操作系统
工具软件

第1节程序设计语言翻译系统

1.1 概述

计算机硬件只能识别并执行机器指令，但人们普遍习惯于使用高级程序设计语言或汇编语言来编写程序。为了让计算机能够理解高级程序设计语言或汇编语言并执行用它编写的程序，必须要为它配备一个"翻译"，这就是程序设计语言翻译系统。

定义：程序设计语言翻译系统是一类系统软件，它能够将使用某一种源语言编写的程序翻译成为与其等价的使用另一种目标语言编写的程序。

源程序：使用源语言编写的程序

目标程序：使用目标语言编写的程序

三类翻译系统：

类型	说明
汇编语言翻译系统	将汇编语言翻译为机器语言
高级程序设计语言编译系统	将高级语言源程序整体翻译为目标程序
高级程序设计语言解释系统	逐条翻译并立即执行

1.2 汇编语言翻译系统

功能：将用汇编语言书写的程序翻译成用二进制码（0/1）表示的等价机器语言，形成计算机可以执行的机器指令代码。

翻译步骤：

用机器操作码代替符号化的操作符
用数值地址代替符号名字
将常数翻译为机器的内部表示
分配指令和数据的存储单元

工作示意：

1汇编源程序 ──→ [汇编程序翻译器] ──→ 二进制机器语言程序
2  (输入)                                (输出)
3

例子：汇编指令 MOV AX, BX 经汇编器翻译后变成机器码 89D8（十六进制），CPU 可以直接执行。

1.3 高级程序设计语言编译系统

定义：编译程序是将用高级语言书写的源程序翻译成等价的机器语言程序或汇编程序的处理系统。它以源程序为输入，以目标程序为输出，最终产生一个可在具体计算机上执行的目标程序。

编译程序的结构（五道"工序"）

1源程序
2  ↓
3[词法分析] ──→ 单词（属性字序列）
4  ↓
5[语法分析] ──→ 语法单位（表达式、语句、程序等）
6  ↓
7[中间代码生成] ──→ 中间代码
8  ↓
9[优化] ──→ 优化后的中间代码
10  ↓
11[目标代码生成] ──→ 目标程序
12

辅助模块：表格管理程序、出错处理程序

1.3.1 词法分析

定义：编译过程中的一个阶段，在语法分析前进行。输入是源程序字符串，输出是等价的属性字序列（内部表示形式）。

任务：从左至右逐个字符地扫描源程序，产生一个个单词符号，把源程序改造为由单词符号串组成的中间程序。

词法分析器的结构：

1输入缓冲区 → 预处理子程序 → 扫描缓冲区 → 扫描器 → 单词符号列表
2

单词符号的识别：

类别	说明	例子
基本字（关键字）	语言预定义的保留字	DO、IF、GOTO、int、for
标识符	字母开头的字母数字串	num、sum、i、count
常数	算术常数，转为二进制内码	5000、5.8
算符和界符	运算符和分隔符	=、==、++、--、>=、(、{

例子：对于代码 for (i=0; i<10; i++)，词法分析器将其拆分为：

关键字：for

界符：(、)、;

标识符：i

算符：=、<、++

常数：0、10

1.3.2 状态转换图与确定型有穷状态自动机（DFA）

状态转换图：一张有限方向图，用于识别（或接受）一定的字符串。

结点：代表状态，用圆圈表示
箭弧：状态之间用箭弧连结，箭弧上的标记（字符）代表该状态下可能出现的输入字符
一张转换图有一个初态和至少一个终态

识别标识符的状态转换图：

1  (字母)       (字母或数字)
2[初态] ──→ [状态2] ←──┐
3  │         │         │
4  └──(其他)─→ [终态]  └──(其他)──→ [终态]
5

例子：标识符 sum 的识别路径：

当前状态	读入字符	下一状态
初态	s（字母）	状态2
状态2	u（字母）	状态2
状态2	m（字母）	状态2
状态2	␣（其他）	终态 ✓

识别整常数的状态转换图：

1  (数字)         (数字)
2[初态] ──→ [状态2] ←──┐
3  │         │         │
4  └──(其他)─→ [终态]  └──(其他)──→ [终态]
5

1.3.3 确定型有穷状态自动机（DFA）—— 形式化定义

定义：一个确定的有穷自动机 D 是一个五元组：D = (K, Σ, M, S, F)，其中：

符号含义
K 有穷非空的状态集合
Σ 有穷非空的输入符号字母表
M 转换函数，M: K × Σ → K，表示当前状态 ki 遇到输入符号 a 时转移到 kj
S 唯一初态，S ∈ K
F 非空终态集合，F ⊆ K

符号	含义
K	有穷非空的状态集合
Σ	有穷非空的输入符号字母表
M	转换函数，M: K × Σ → K，表示当前状态 ki 遇到输入符号 a 时转移到 kj
S	唯一初态，S ∈ K
F	非空终态集合，F ⊆ K

例子：为正则语言 {(ab)^n b² | n ≥ 0} 构造状态转换图：

1        a         b         b
2[S] ──→ [A] ──→ [B] ──→ [C] ──→ [Z(终态)]
3        ↑         │
4        └────(a)──┘（回路实现 (ab)^n 部分）
5

该 DFA 接受的语言：字符串由 n 个 “ab” 重复后跟两个 “b” 组成。如 bb（n=0）、abbb（n=1）、ababbb（n=2）等。

1.3.4 语法分析

语法分析程序对词法分析产出的单词序列进行分析，按照语法规则识别出语法单位（表达式、语句、程序等）。

1.3.5 中间代码生成与优化

中间代码生成：将语法单位转换为某种中间代码（便于后续优化和目标代码生成）
优化：对中间代码进行优化，使生成的目标代码在运行速度和存储空间方面具有较高的质量

1.3.6 目标代码生成

将优化后的中间代码转换为目标程序（机器语言或汇编语言）。

1.4 高级程序设计语言解释系统

定义：按照源程序中语句的动态顺序，逐条翻译并立即执行相应功能的处理系统。

工作过程：

由总控程序完成初始化工作
依次从源程序中取出一条语句进行语法检查，如有错则输出错误信息；通过检查则翻译成相应指令并执行
检查源程序是否已全部解释执行完毕，未完成则继续解释并执行下一个语句，直到全部处理完毕

1源程序 + 原始数据 ──→ [解释系统（逐句解释、执行）] ──→ 结果
2

优缺点：

优点	缺点
实现算法比较简单	运行效率比较低

例子：Python 和 JavaScript 是典型的解释型语言。以下 Python 代码逐行被解释执行：

1x = 10          # 解释：分配变量 x，赋值 10
2y = x + 5       # 解释：取 x 的值，加 5，赋给 y
3print(y)        # 解释：输出 y 的值 → 15
4

1.5 编译 vs 解释对比

对比维度	编译系统	解释系统
翻译方式	整体翻译，生成目标程序	逐条翻译并执行
执行效率	高（一次翻译，多次执行）	低（每次执行都要翻译）
典型代表	C、C++、Go	Python、JavaScript、PHP
产物	独立的可执行文件（.exe 等）	无独立目标程序
错误发现	编译阶段集中报告	执行到出错语句时才报告

第2节操作系统

2.1 什么是操作系统

定义：操作系统是用来管理计算机系统的软硬件资源、提高计算机系统资源的使用效率、方便用户使用的程序集合。它是对计算机系统进行自动管理的控制中心。

操作系统是计算机硬件（裸机）的直接外层，对硬件功能进行首次扩充
操作系统通过各种命令提供给用户操作界面
操作系统是其他软件运行的基础

引导过程：从外存储器装入主存储器 → 管理程序部分常驻主存（驻留程序）→ 其他部分按需调入（临时程序）

2.2 操作系统的功能

2.2.1 资源管理功能

功能	说明
处理机管理	控制程序执行，登记各处理机及状态，按策略分配 CPU 给用户作业（进程）。目前大多为"多任务"、"多线程"操作系统
存储器管理	按策略分配存储空间，记录主存使用情况，提供信息保护，作业结束后回收内存单元
输入输出设备管理	响应外部 I/O 请求，记录设备状态，按设备特点分配和回收外部设备，控制设备按用户程序要求操作
文件管理	对信息进行逻辑和物理组织，维护文件目录结构，实现对文件的各种操作。用户可按文件名存取数据，不必了解数据的物理位置

2.2.2 人机交互功能

主要依靠输入输出设备和相应软件完成：

传统设备	新型设备
键盘、显示器、鼠标	语音输入设备、文字读入设备、图形图像扫描输入设备

2.3 操作系统的分类

按照性能分类：

2.3.1 多道批处理操作系统

定义：在主存储器中存放多道用户作业，使其按照一定策略插空在 CPU 上运行，共享 CPU 和输入输出设备等系统资源。

宏观上：多道作业同时运行
微观上（单 CPU）：某一瞬间只有一道作业在 CPU 上运行

例子：一台计算机同时处理三个批处理作业：作业 A（数据统计）、作业 B（文件转换）、作业 C（日志分析）。在宏观上看三个作业同时在跑，实际上 CPU 快速在它们之间切换分配时间片。

2.3.2 分时操作系统

定义：多个用户终端共享使用一台计算机，把 CPU 时间分割成一个个时间片，分别提供给各个用户终端。设计目标是提高对用户响应的及时性。

例子：大学机房里，一台小型机连接了 30 个终端，30 名学生同时登录使用，每人感觉就像独占了整台计算机——实际上 CPU 以极短的时间片轮流为每个人服务。

2.3.3 实时操作系统

定义：能够对外部事件作出及时的响应并对其进行处理的系统。强调对外部事件响应的及时性和快捷性及系统的可靠性。

例子：

工业控制：化工厂的温度监测系统，必须在温度超标的瞬间立即触发降温操作，延迟不可接受

航空航天：火箭发射控制系统，对外部传感器数据的响应必须在毫秒级别

2.3.4 网络操作系统

定义：使网络上的计算机能够方便而有效地共享网络资源，为网络用户提供各种服务的软件和有关协议的集合。

协议：由于网络上计算机的硬件特性、数据表示格式等不同，为了在互相通信时彼此能够理解，必须共同遵循的约定。

额外功能（相比普通操作系统）：

高效、可靠的网络通信（按网络协议进行）
多种网络服务：文件传输、远程登录、电子邮件、信息检索等

例子：Windows Server 是典型的网络操作系统，一个办公室的多台电脑通过它共享打印机、共享文件夹，并通过 TCP/IP 协议互相通信。

2.4 几种常用的操作系统

2.4.1 MS-DOS

全称：Microsoft Disk Operating System（微软磁盘操作系统）
广泛用于 PC 及其兼容机

三大功能：

磁盘文件管理
输入输出管理
命令处理

命令格式：

类型	格式
内部命令	<命令动词> [<参数>]
外部命令	[<驱动器名>][<路径名>]<命令动词> [<参数>]

引导过程：启动后检查驱动器 A 或 C 中是否有系统文件 MSDOS.SYS 和 IO.SYS，有则引导入主存，否则显示出错信息。

例子：DIR C:\ 列出 C 盘根目录下的所有文件；COPY A:\file.txt C:\ 将 A 盘的文件复制到 C 盘。

2.4.2 Microsoft Windows

由 Microsoft 公司开发的一系列基于图形界面、多任务的操作系统，又称视窗操作系统。

2.4.3 Unix 操作系统

发展历程：20 世纪 60 年代末由 AT&T 贝尔实验室的 K.Thompson 和 D.M.Ritchie 等研制。两位学者因卓越贡献获得了 1983 年图灵奖。

主要特点：

多用户操作系统，适合终端或工作站连接到小型机或主机的场合
功能由许多小的功能模块连接组装而成
提供功能完备、使用灵活、可编程的 Shell 命令语言
具有分层的、可装卸的文件系统，提供完整的文件保护功能
采用输入输出缓冲技术，主存和磁盘的分配与释放自动高效进行
提供了文本编辑程序、Shell 解释程序、汇编程序、多种编译程序、调试程序、通信程序以及系统管理与维护程序
代码大部分用 C 语言书写，有很好的可移植性
有一系列网络通信工具和协议，TCP/IP 协议就是在 Unix 上开发成功的

Unix 的框架结构（四层）：

1用户层：
2  Shell 语言解释程序 | 程序设计语言编译程序 | 各种应用程序包子系统
3
4      ↓ 系统调用命令
5
6内核层：
7  进程管理 | 存储管理 | 设备管理 | I/O中断管理 | 文件管理 | 汇编程序
8
9      ↓
10
11计算机硬件（裸机）
12

四个基本成分：

成分	作用
内核	核心，调度和管理计算机系统的各种资源
文件系统	组织并管理数据资源
Shell	命令解释程序，读入用户命令并调用相应程序执行
公用程序	常用标准软件：编辑工具、网络管理工具、开发工具、保密与安全工具等

2.4.4 Linux

定义：一种可以运行在微机上的免费的 Unix 操作系统。由芬兰赫尔辛基大学学生 Linus Torvalds 于 1991 年开发。源代码免费开放，但部分发行版可能收费。