计算机导论_第4章_笔记

内容提要

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

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

1.1 概述

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

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

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

三类翻译系统：

1.2 汇编语言翻译系统

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

翻译步骤：

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

工作示意：

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

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

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

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

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

源程序 ↓ [词法分析] ──→ 单词（属性字序列） ↓ [语法分析] ──→ 语法单位（表达式、语句、程序等） ↓ [中间代码生成] ──→ 中间代码 ↓ [优化] ──→ 优化后的中间代码 ↓ [目标代码生成] ──→ 目标程序

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

1.3.1 词法分析

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

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

词法分析器的结构：

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

单词符号的识别：

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

• 关键字：for
• 界符：(、)、;
• 标识符：i
• 算符：=、<、++
• 常数：0、10

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

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

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

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

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

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

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

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

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

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

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

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

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

该 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. 依次从源程序中取出一条语句进行语法检查，如有错则输出错误信息；通过检查则翻译成相应指令并执行
3. 检查源程序是否已全部解释执行完毕，未完成则继续解释并执行下一个语句，直到全部处理完毕

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

优缺点：

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

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

1.5 编译 vs 解释 对比

第2节 操作系统

2.1 什么是操作系统

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

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

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

2.2 操作系统的功能

2.2.1 资源管理功能

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 及其兼容机

三大功能：

1. 磁盘文件管理
2. 输入输出管理
3. 命令处理

命令格式：

引导过程：启动后检查驱动器 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 的框架结构（四层）：

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

四个基本成分：

2.4.4 Linux

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

主要特点：

• 与 Unix 兼容的32 位操作系统，支持 32 位和 64 位硬件
• 继承 Unix以网络为核心的设计思想，是性能稳定的多用户网络操作系统
• 支持多任务、多进程和多 CPU
• 模块化设计结构，有优于其他操作系统的扩充性
• 用户不仅可以免费获得源代码，还可以修改以实现特定功能，任何人都可以参与开发
• 提供完整网络集成，可轻松与 TCP/IP、LAN Manager、Windows for Workgroups、Novell NetWare 或 Windows NT 集成

流行版本：

例子：一名开发者在 Raspberry Pi（树莓派）上安装免费的 Raspbian（基于 Linux），搭建了自己的 Web 服务器；同时，大部分互联网公司的服务器都运行 Linux（如 CentOS、Ubuntu Server），支撑着全球的云服务和网站。

2.4.5 Mac OS

• Apple 公司为 Mac 计算机设计的操作系统
• 最早利用图形用户界面（GUI）的操作系统
• 具有极强的图形处理能力，广泛用于桌面出版和多媒体应用

Mac OS X（新一代）：

• 核心系统Darwin，采用卡耐基梅隆大学开发的Mach 微内核
• 可看作符合POSIX（Portable Operating System Interface，可移植操作系统接口）标准的 Unix 变种
• Darwin 本身开放源代码

Mac OS X 的特点：

2.5 操作系统对比总结

本章小结

• 程序设计语言翻译系统和操作系统是计算机系统软件中最重要的两种类型
• 程序设计语言翻译系统：将高级语言翻译为可执行机器指令，包括汇编、编译、解释三大类
• 操作系统：管理软硬件资源、提供人机交互界面、作为其他软件运行的基础
• 常用操作系统包括 Windows、Unix、Linux、Mac OS 等，各有特点与适用场景

人物介绍——埃德斯加·狄克斯特拉（Edsgar Wybe Dijkstra）

• 1972 年图灵奖获得者，荷兰计算机科学家
• 因最早指出“goto 是有害的”以及首创结构化程序设计而闻名
• 在算法理论、编译器、操作系统等多方面均有杰出贡献
• 1983 年 ACM 评选 1958-1982 年的 25 篇里程碑论文，狄克斯特拉一人入选两篇
• 1956 年设计了在有障碍物的两点之间找出最短路径的“狄克斯特拉算法”（Dijkstra’s Algorithm），至今仍被广泛应用

例子：导航软件（如高德地图、Google Maps）在计算从起点到终点的最短路线时，底层核心算法就是狄克斯特拉算法——它能够在复杂的道路网络中找到时间最短或距离最短的路径。
（内容由AI生成，仅供参考）