35.计算机基础知识

目录

计算机系统概述

计算机系统组成

计算机系统是一个复杂的整体，由硬件系统和软件系统两大部分组成。

硬件系统组成

软件系统组成

系统软件是计算机系统的核心，主要包括：

• 操作系统：管理计算机硬件资源，为应用程序提供服务
• 编译程序：将高级语言程序翻译成机器语言
• 数据库管理系统：管理和维护数据库
• 网络软件：支持网络通信和资源共享

应用软件是为解决特定问题而开发的程序，直接为用户服务。

计算机工作原理

冯·诺依曼体系结构

现代计算机基本都采用冯·诺依曼体系结构，其核心思想是：

1. 程序存储：程序和数据都存储在同一存储器中
2. 顺序执行：程序按地址顺序执行，可通过转移指令改变执行顺序
3. 二进制表示：指令和数据都用二进制表示
4. 统一编址：程序和数据统一编址，可通过地址访问

指令执行过程

计算机执行程序的基本过程可以概括为取指-译码-执行循环：

1. 取指令(Fetch)：从存储器中取出当前要执行的指令
2. 译码(Decode)：分析指令的操作码和操作数
3. 取操作数：根据寻址方式获取操作数
4. 执行(Execute)：完成指令规定的操作
5. 存储结果：将运算结果存储到指定位置
6. 修改PC：更新程序计数器，指向下一条指令

计算机分类与发展

按规模和性能分类

计算机发展历程

第四代计算机的主要特征：

• 采用大规模集成电路(LSI)和超大规模集成电路(VLSI)
• 微处理器的出现使个人计算机成为可能
• 软件技术快速发展，出现了各种高级编程语言
• 网络技术的发展实现了计算机互联

性能评价指标

主要性能指标

性能计算公式

CPU执行时间 = 指令数 × CPI × 时钟周期时间

程序执行时间 = (指令数 × CPI) / 主频

其中：

• 指令数：程序包含的指令总数
• CPI(Cycles Per Instruction)：每条指令平均需要的时钟周期数
• 时钟周期时间：主频的倒数

性能优化策略

硬件优化方向：

• 提高主频：采用先进制造工艺，优化电路设计
• 增加并行度：多核处理器、超标量、超线程技术
• 改进存储层次：增大缓存容量，提高存储带宽

软件优化方向：

• 算法优化：选择更高效的算法和数据结构
• 编译优化：利用编译器的优化功能
• 代码优化：减少不必要的计算和内存访问

数据表示与运算

数制转换

常用数制系统

数制转换方法

十进制转其他进制：

• 除基取余法：连续除以目标进制的基数，余数倒序排列

十进制25转二进制：
25 ÷ 2 = 12 ... 1
12 ÷ 2 = 6  ... 0  
6  ÷ 2 = 3  ... 0
3  ÷ 2 = 1  ... 1
1  ÷ 2 = 0  ... 1
结果：11001₂

其他进制转十进制：

• 按权展开法：各位数字乘以对应的权值之和

二进制11001转十进制：
1×2⁴ + 1×2³ + 0×2² + 0×2¹ + 1×2⁰ = 16 + 8 + 0 + 0 + 1 = 25

快速转换技巧

二进制与八进制转换：

• 每3位二进制对应1位八进制
• 例：101110₂ = 101|110 = 5|6 = 56₈

二进制与十六进制转换：

• 每4位二进制对应1位十六进制
• 例：10111010₂ = 1011|1010 = B|A = BA₁₆

数据编码

字符编码

中文编码

编码特点对比：

• GB2312：最早的中文编码标准，收录常用汉字
• GBK：扩展GB2312，增加更多汉字和符号
• GB18030：国家标准，完全兼容Unicode
• Unicode：国际标准，支持世界各国文字

数值编码

BCD码(Binary Coded Decimal)：

• 用4位二进制表示1位十进制数字
• 例：十进制59 → BCD码：0101 1001

格雷码(Gray Code)：

• 相邻两个码字只有1位不同
• 用于减少数字电路中的竞争冒险

定点数与浮点数

定点数表示

原码表示：

• 最高位为符号位，0表示正数，1表示负数
• 例：+5 = 00000101，-5 = 10000101

反码表示：

• 正数的反码等于原码
• 负数的反码为原码除符号位外各位取反
• 例：+5 = 00000101，-5 = 11111010

补码表示：

• 正数的补码等于原码
• 负数的补码为反码加1
• 例：+5 = 00000101，-5 = 11111011

补码运算优势

浮点数表示

IEEE 754标准：

浮点数值计算公式： V = (-1)^S × (1.M) × 2^(E-127) (单精度) V = (-1)^S × (1.M) × 2^(E-1023) (双精度)

特殊值表示：

• 零值：E=0，M=0
• 无穷大：E=255(单精度)或2047(双精度)，M=0
• NaN：E=255(单精度)或2047(双精度)，M≠0

算术逻辑运算

加法运算

二进制加法规则：

0 + 0 = 0
0 + 1 = 1  
1 + 0 = 1
1 + 1 = 10 (进位)

补码加法运算：

• 直接将两个补码相加
• 符号位参与运算
• 超出位数的进位自动丢弃

乘法运算

移位相加法：

Booth算法：

• 用于有符号数乘法
• 通过分析乘数的连续1串来减少加法次数
• 提高乘法运算效率

除法运算

恢复余数法：

1. 余数左移1位
2. 余数减除数
3. 如果结果为正，商位置1；否则商位置0，恢复余数
4. 重复直到所有位处理完毕

不恢复余数法：

• 改进的除法算法
• 避免恢复余数的步骤
• 提高除法运算速度

逻辑运算

位运算应用实例：

• 清零特定位：x & ~mask
• 设置特定位：x | mask
• 翻转特定位：x ^ mask
• 检测特定位：x & mask
• 快速乘除2的幂：左移/右移操作

存储系统

存储器层次结构

存储器分类

存储器性能指标

存储器层次原理

局部性原理是存储器层次结构的理论基础：

1. 时间局部性：最近访问的信息很可能再次被访问
2. 空间局部性：相邻地址的信息很可能被连续访问

主存储器

DRAM工作原理

动态随机存储器(DRAM) 是主存的主要技术：

DRAM特点：

• 存储原理：利用电容存储电荷表示0和1
• 刷新需求：电容会漏电，需要定期刷新(2-64ms)
• 访问方式：行列地址分时复用，降低引脚数
• 成本优势：结构简单，成本低，适合大容量存储

主存组织方式

存储器芯片组织：

多体交叉存储器：

交叉存储优势：

• 并行访问：多个存储体可同时工作
• 提高带宽：有效提升存储器带宽
• 流水线支持：支持指令流水线的连续访问

存储器接口

同步DRAM(SDRAM)：

• 与系统时钟同步工作
• 支持突发传输模式
• 提高数据传输效率

双倍数据速率SDRAM(DDR)：

• 在时钟上升沿和下降沿都传输数据
• 有效数据传输率翻倍
• 发展历程：DDR → DDR2 → DDR3 → DDR4 → DDR5

高速缓存

Cache基本原理

缓存工作机制：

地址映射方式

直接映射：

• 主存块只能映射到Cache的固定位置
• 映射关系：Cache行号 = 主存块号 mod Cache行数
• 优点：硬件简单，成本低
• 缺点：冲突率高，灵活性差

全相联映射：

• 主存块可以映射到Cache的任意位置
• 需要全相联比较器
• 优点：冲突率低，灵活性好
• 缺点：硬件复杂，成本高

组相联映射：

• 直接映射和全相联映射的折中
• Cache分为若干组，组内全相联，组间直接映射
• 平衡了性能和成本

替换算法

写策略

写命中策略：

写缺失策略：

• 写分配(Write Allocate)：先将块调入Cache，然后写入
• 写不分配(Write No-Allocate)：直接写入主存，不调入Cache

虚拟存储器

虚拟存储概念

虚拟存储器是一种存储管理技术，为程序提供比物理内存更大的地址空间。

分页存储管理

页面组织：

• 页(Page)：虚拟地址空间的固定大小块(通常4KB)
• 页框(Page Frame)：物理内存的固定大小块
• 页表(Page Table)：记录页到页框的映射关系

地址转换过程：

页面置换算法

最佳置换算法(OPT)：

• 理论最优算法
• 置换将来最长时间不被访问的页面
• 实际无法实现，用作性能比较基准

最近最少使用(LRU)：

• 置换最长时间未被访问的页面
• 基于时间局部性原理
• 实现复杂度较高

时钟算法(Clock)：

• LRU的近似算法
• 使用访问位和指针实现
• 硬件实现简单

TLB快表

转换后备缓冲器(TLB)：

• 缓存最近使用的页表项
• 加速地址转换过程
• 通常采用全相联或组相联映射

TLB性能影响因素：

• 命中率：通常在95%以上
• 访问时间：1-2个时钟周期
• 容量：32-1024个表项
• 相联度：影响命中率和访问时间

指令系统

指令格式

指令的基本组成

指令格式分类：

指令长度设计

定长指令：

• 所有指令长度相同
• 优点：译码简单，取指方便
• 缺点：代码密度低，浪费存储空间

变长指令：

• 指令长度可变
• 优点：代码密度高，节省存储空间
• 缺点：译码复杂，取指困难

扩展操作码技术：

寻址方式

基本寻址方式

立即寻址：

• 操作数直接包含在指令中
• 优点：无需访存，速度快
• 缺点：操作数长度受限

直接寻址：

• 地址码直接给出操作数地址
• 有效地址 = 地址码
• 优点：简单直接
• 缺点：寻址范围受限

间接寻址：

• 地址码给出操作数地址的地址
• 有效地址 = (地址码)
• 优点：扩大寻址范围
• 缺点：需要多次访存

相对寻址方式

寻址方式比较：

指令类型

数据传送指令

基本传送指令：

• LOAD：从存储器加载数据到寄存器
• STORE：从寄存器存储数据到存储器
• MOVE：寄存器间数据传送
• EXCHANGE：交换两个操作数

栈操作指令：

• PUSH：数据压入栈
• POP：数据弹出栈
• 栈指针自动调整

算术逻辑指令

控制转移指令

无条件转移：

• JMP：无条件跳转
• CALL：子程序调用
• RET：子程序返回

条件转移：

• 根据标志位状态决定是否跳转
• 常见条件：零标志(ZF)、进位标志(CF)、符号标志(SF)

循环控制指令：

• LOOP：循环控制
• LOOPZ/LOOPNZ：条件循环

输入输出指令

程序控制I/O：

• IN：从I/O端口输入数据
• OUT：向I/O端口输出数据
• CPU直接控制I/O操作

中断I/O：

• STI/CLI：开/关中断
• IRET：中断返回
• 提高CPU利用率

RISC与CISC

设计理念对比

特征对比

RISC设计原则

关键设计原则：

1. 指令简单化：每条指令完成简单操作
2. 规整化设计：指令格式统一，便于译码
3. 优化常用操作：重点优化频繁使用的指令
4. 硬件简化：减少硬件复杂度，提高频率
5. 编译器优化：依靠编译器进行代码优化

RISC优势：

• 高频率：简单设计支持更高时钟频率
• 流水线友好：规整指令便于流水线实现
• 功耗较低：硬件简单，功耗控制好
• 设计周期短：降低处理器设计复杂度

现代处理器发展

CISC与RISC融合：

发展趋势：

• 指令级并行：超标量、乱序执行
• 专用指令：SIMD、向量指令
• 异构计算：CPU+GPU协同
• 低功耗设计：移动设备需求驱动

中央处理器

CPU结构

CPU基本组成

寄存器分类

通用寄存器：

• 存储操作数和中间结果
• 数量：8-32个(现代处理器)
• 位宽：32位或64位

专用寄存器：

控制器设计

硬布线控制器：

• 用组合逻辑电路实现
• 速度快，效率高
• 设计复杂，不易修改

微程序控制器：

微程序控制优势：

• 灵活性好：修改微程序即可改变指令功能
• 设计规整：控制逻辑结构化
• 易于扩展：添加新指令相对容易
• 调试方便：可以单步执行微指令

指令执行过程

指令执行周期

数据通路设计

单总线结构：

• 所有部件共享一条总线
• 结构简单，成本低
• 同时只能进行一次数据传输

多总线结构：

• 采用多条专用总线
• 提高数据传输并行度
• 硬件复杂度增加

专用数据通路：

• 为特定操作设计专用路径
• 最高性能，最大并行度
• 硬件成本最高

指令流水线

流水线基本概念：

流水线技术

流水线性能分析

性能指标：

其中：

• n：指令总数
• T：流水线总执行时间
• T₀：非流水线执行时间
• k：流水线段数

理想流水线性能：

• 吞吐率：1条指令/时钟周期
• 加速比：等于流水线段数
• 效率：100%

流水线冲突

结构冲突(资源冲突)：

数据冲突：

• RAW(Read After Write)：真数据相关
• WAR(Write After Read)：反相关
• WAW(Write After Write)：输出相关

控制冲突：

• 分支指令改变程序执行流程
• 条件分支的不确定性
• 影响指令预取的连续性

冲突解决技术

数据冲突解决：

数据前推技术：

• 将ALU输出直接送到下一指令的输入
• 避免写回再读取的延迟
• 硬件实现相对复杂

分支预测

静态分支预测

预测策略：

动态分支预测

一位分支预测：

• 使用1位历史信息
• 预测错误后立即改变预测
• 对于规律性分支效果不佳

两位分支预测：

全局分支预测：

• 使用全局分支历史
• 考虑分支间的相关性
• 预测准确率可达90%以上

分支目标缓冲

BTB(Branch Target Buffer)：

BTB组织结构：

• 标记字段：分支指令地址
• 目标地址字段：分支目标地址
• 预测信息字段：分支预测状态
• 有效位：表项是否有效

超标量处理器

超标量特征：

• 每个时钟周期可以启动多条指令
• 动态调度指令执行顺序
• 多个功能部件并行工作

关键技术：

性能限制因素：

• 指令间相关性：限制并行度
• 分支指令频率：影响指令预取
• 存储器访问延迟：数据获取瓶颈
• 硬件资源限制：功能部件数量

输入输出系统

IO接口

IO接口功能

IO端口编址

统一编址(存储器映射IO)：

• IO端口占用存储器地址空间
• 使用存储器指令访问IO设备
• 地址译码电路统一设计

独立编址：

• IO端口有独立的地址空间
• 使用专门的IO指令
• 需要专门的IO控制信号

IO接口类型

并行接口：

• 多条数据线同时传输
• 传输速度快
• 适合短距离高速传输

串行接口：

• 单条数据线逐位传输
• 传输距离远
• 成本低，抗干扰能力强

IO控制方式

程序控制IO

无条件传送：

• CPU直接控制IO操作
• 不检查设备状态
• 适用于简单、可靠的设备

程序查询方式：

程序查询方式特点：

• CPU主动查询设备状态
• 简单可靠，硬件开销小
• CPU利用率低，实时性差

中断控制IO

中断IO工作原理：

中断优先级管理：

中断系统

中断处理过程

中断响应条件：

1. 中断源发出中断请求
2. CPU开中断(中断允许触发器为1)
3. 当前指令执行完毕
4. 没有更高优先级中断正在处理

中断处理流程：

中断向量表

中断向量：

• 存储中断服务程序入口地址
• 通常存放在固定的存储区域
• 支持快速中断响应

向量中断vs非向量中断：

多级中断系统

中断嵌套：

• 高优先级中断可以打断低优先级中断
• 需要保存多层现场信息
• 使用栈结构管理嵌套关系

中断屏蔽技术：

• 通过屏蔽字控制中断响应
• 可以动态调整中断优先级
• 支持中断的选择性响应

DMA技术

DMA基本原理

直接存储器访问(DMA)：

• 外设直接与存储器交换数据
• 不需要CPU参与数据传输过程
• 大幅提高数据传输效率

DMA传输方式

停止CPU访问：

• DMA控制器完全占用总线
• CPU停止工作直到传输完成
• 传输速度最快，CPU利用率最低

周期挪用：

• DMA在CPU不访问总线时传输
• 利用CPU的空闲总线周期
• 对CPU影响最小

交替访问：

• CPU和DMA交替使用总线
• 需要总线仲裁机制
• 平衡传输速度和CPU效率

DMA传输过程

总线仲裁

集中仲裁方式：

分布仲裁方式：

• 各设备自行决定总线使用权
• 无需中央仲裁器
• 适用于高性能系统

现代IO技术

IO虚拟化：

• 虚拟机环境下的IO管理
• 提高IO资源利用率
• 支持IO设备共享

高速IO接口：

NVMe存储：

• 专为SSD设计的接口协议
• 充分利用SSD的并行性能
• 大幅降低存储访问延迟

操作系统基础

操作系统概念

操作系统定义与功能

操作系统是管理计算机硬件资源，为应用程序提供服务的系统软件。

操作系统类型

系统调用

系统调用接口：

进程管理

进程概念

进程是程序在执行过程中的一个实例，是系统进行资源分配和调度的基本单位。

进程与程序的区别：

进程状态转换

进程控制块PCB

PCB包含信息：

进程调度算法

先来先服务(FCFS)：

• 按进程到达顺序调度
• 简单公平，但平均等待时间长
• 不利于短作业

短作业优先(SJF)：

• 优先调度执行时间短的进程
• 最小化平均等待时间
• 可能导致长作业饥饿

时间片轮转(RR)：

优先级调度：

• 根据进程优先级分配CPU
• 支持抢占式和非抢占式
• 需要防止优先级倒置

多级反馈队列：

• 多个优先级不同的就绪队列
• 进程可在队列间移动
• 兼顾响应时间和公平性

内存管理

内存分配方式

连续分配：

动态分区分配算法：

虚拟内存

虚拟内存原理：

• 程序使用虚拟地址空间
• 操作系统负责地址转换
• 支持程序大小超过物理内存

页面置换算法：

最优置换(OPT)：

• 理论最优算法
• 置换将来最长时间不访问的页面
• 实际无法实现

先进先出(FIFO)：

• 置换最早调入的页面
• 实现简单，但可能产生Belady异常
• 不符合局部性原理

最近最少使用(LRU)：

段页式存储

分段存储：

• 按程序逻辑结构分段
• 段长可变，便于共享和保护
• 地址转换：段号+段内偏移

分页存储：

• 按固定大小分页
• 消除外部碎片
• 地址转换：页号+页内偏移

段页式存储：

• 结合分段和分页优点
• 先分段再分页
• 地址转换：段号+页号+页内偏移

文件系统

文件系统功能

文件组织方式

顺序文件：

• 记录按顺序存储
• 适合批处理和顺序访问
• 插入删除效率低

索引文件：

• 建立索引表加速检索
• 支持随机访问
• 需要额外存储空间

散列文件：

• 使用散列函数确定记录位置
• 访问速度快
• 可能产生冲突

目录结构

单级目录：

• 所有文件在同一目录
• 结构简单，但文件名冲突

两级目录：

• 用户目录+文件目录
• 解决文件名冲突
• 不支持文件分类

树形目录：

磁盘空间管理

空闲空间管理：

文件分配方式：

连续分配：

• 文件占用连续的磁盘块
• 访问速度快，实现简单
• 外部碎片，文件大小难以扩展

链接分配：

• 文件块通过指针链接
• 消除外部碎片，支持动态扩展
• 随机访问效率低

索引分配：

混合索引分配：

• 结合直接索引和间接索引
• 小文件使用直接索引
• 大文件使用间接索引
• Unix/Linux文件系统采用此方式

网络基础

网络协议栈

OSI七层模型

TCP/IP模型

四层结构对比：

数据封装过程

TCP/IP协议

IP协议

IPv4地址结构：

• 32位地址，分为4个8位字段
• 网络部分 + 主机部分
• 支持约43亿个地址

地址分类：

子网划分：

• 使用子网掩码划分子网
• 增加网络层次，提高地址利用率
• CIDR(无类域间路由)支持可变长子网

TCP协议

TCP特点：

• 面向连接：通信前需建立连接
• 可靠传输：保证数据正确到达
• 流量控制：防止发送方过快发送
• 拥塞控制：避免网络拥塞

TCP连接建立(三次握手)：

TCP连接释放(四次挥手)：

UDP协议

UDP特点：

UDP头部格式：

• 源端口号(16位)
• 目的端口号(16位)
• 长度(16位)
• 校验和(16位)

网络安全

网络安全威胁

加密技术

对称加密：

• 加密和解密使用相同密钥
• 速度快，适合大量数据加密
• 密钥分发困难

非对称加密：

• 使用公钥和私钥对
• 解决密钥分发问题
• 计算复杂度高

数字签名：

防火墙技术

防火墙类型：

网络性能优化

网络性能指标

关键指标：

拥塞控制

TCP拥塞控制算法：

拥塞窗口变化：

1. 慢启动阶段：cwnd指数增长
2. 拥塞避免阶段：cwnd线性增长
3. 拥塞发生：cwnd减半
4. 快恢复阶段：快速恢复传输

服务质量QoS

QoS机制：

DiffServ模型：

• 基于数据包标记提供服务
• 支持多种服务等级
• 可扩展性好，实现简单

IntServ模型：

• 为每个流预留资源
• 提供严格的QoS保证
• 可扩展性差，状态复杂

数据库基础

数据库模型

数据模型发展

数据库系统结构

三级模式结构：

数据独立性：

关系数据库

关系模型基础

基本概念：

• 关系(Relation)：一个二维表
• 元组(Tuple)：表中的一行
• 属性(Attribute)：表中的一列
• 域(Domain)：属性的取值范围
• 主键(Primary Key)：唯一标识元组的属性组合

关系的性质：

1. 每个分量都是不可分的数据项
2. 不同列可以来自同一个域
3. 列的顺序无关紧要
4. 任意两个元组不能完全相同
5. 行的顺序无关紧要

关系代数

基本运算：

扩展运算：

函数依赖

函数依赖定义： 设R(U)是属性集U上的关系模式，X和Y是U的子集。若对于R(U)的任意一个可能的关系r，r中不可能存在两个元组在X上的属性值相等，而在Y上的属性值不等，则称X函数确定Y或Y函数依赖于X，记作X→Y。

函数依赖类型：

范式理论

第一范式(1NF)：

• 关系中每个属性都是不可分的数据项
• 消除重复组

第二范式(2NF)：

• 满足1NF
• 每个非主属性完全函数依赖于主键
• 消除部分函数依赖

第三范式(3NF)：

• 满足2NF
• 每个非主属性不传递依赖于主键
• 消除传递函数依赖

BCNF范式：

SQL语言

SQL语言分类

数据定义语言(DDL)：

• CREATE：创建数据库对象
• ALTER：修改数据库对象结构
• DROP：删除数据库对象

数据操纵语言(DML)：

• SELECT：查询数据
• INSERT：插入数据
• UPDATE：更新数据
• DELETE：删除数据

数据控制语言(DCL)：

• GRANT：授予权限
• REVOKE：撤销权限
• COMMIT：提交事务
• ROLLBACK：回滚事务

查询语句结构

SELECT语句语法：

SELECT [DISTINCT] 属性列表
FROM 表名列表
[WHERE 条件表达式]
[GROUP BY 属性名 [HAVING 条件表达式]]
[ORDER BY 属性名 [ASC|DESC]]

查询执行顺序：

连接查询

内连接：

-- 等值连接
SELECT * FROM Student S, Course C 
WHERE S.course_id = C.id;

-- 自然连接
SELECT * FROM Student NATURAL JOIN Course;

外连接：

事务处理

事务概念

事务定义：事务是数据库操作的逻辑单位，由一系列操作组成，这些操作要么全部成功，要么全部失败。

ACID特性：

并发控制

并发问题：

隔离级别：

锁机制

锁的类型：

共享锁(S锁)：

• 多个事务可同时持有
• 只能读取，不能修改
• 用于实现读操作

排他锁(X锁)：

• 只有一个事务可以持有
• 可以读取和修改
• 用于实现写操作

锁的粒度：

死锁处理

死锁预防：

• 一次性申请所有锁
• 对资源排序，按序申请锁
• 设置锁超时时间

死锁检测与解除：

死锁预防vs死锁检测：

• 预防：保守策略，可能降低并发度
• 检测：乐观策略，允许死锁发生后处理

编译原理

编译过程

编译器结构

编译阶段功能

词法分析

词法分析任务

主要功能：

• 单词识别：将字符序列组织成单词
• 单词分类：标识符、关键字、运算符、常数等
• 符号表管理：记录标识符信息
• 错误处理：发现并报告词法错误

正规表达式

基本运算：

常用正规表达式：

标识符: [a-zA-Z][a-zA-Z0-9]*
整数: [0-9]+
实数: [0-9]+\.[0-9]+

有限自动机

确定有限自动机(DFA)：

非确定有限自动机(NFA)：

• 允许多个转换路径
• 可以有ε转换
• 需要转换为DFA实现

语法分析

上下文无关文法

文法定义： G = (V_N, V_T, P, S)

• V_N：非终结符集合
• V_T：终结符集合
• P：产生式集合
• S：开始符号

产生式示例：

E → E + T | E - T | T
T → T * F | T / F | F  
F → (E) | id | num

语法分析方法

自顶向下分析：

自底向上分析：

• LR分析：Left-to-right scan, Rightmost derivation
• SLR分析：Simple LR
• LALR分析：Look-Ahead LR
• LR(1)分析：LR with 1 symbol lookahead

语法制导翻译

属性文法：

• 综合属性：由子节点属性计算得出
• 继承属性：由父节点和兄弟节点属性计算得出

翻译模式：

E → E₁ + T    { E.val = E₁.val + T.val }
E → T         { E.val = T.val }
T → F         { T.val = F.val }
F → num       { F.val = num.val }

语义分析

类型检查

类型系统：

类型检查规则：

• 算术运算：操作数类型兼容
• 赋值语句：右值类型与左值类型兼容
• 函数调用：实参与形参类型匹配
• 数组访问：下标为整数类型

作用域分析

作用域规则：

• 块作用域：在代码块内有效
• 函数作用域：在函数内有效
• 全局作用域：在整个程序内有效

符号表组织：

代码优化

优化分类

按优化范围分类：

数据流分析

到达定义分析：

数据流方程：

• 前向数据流：OUT[B] = GEN[B] ∪ (IN[B] - KILL[B])
• 后向数据流：IN[B] = GEN[B] ∪ (OUT[B] - KILL[B])

常见优化技术

局部优化：

• 常数折叠：编译时计算常数表达式
• 强度削弱：用简单运算替代复杂运算
• 窥孔优化：在小范围内进行模式匹配优化

全局优化：

• 公共子表达式删除：避免重复计算
• 代码移动：将循环不变代码移出循环
• 死代码删除：删除永远不会执行的代码

循环优化：

现代编译优化

高级优化技术：

• 向量化：利用SIMD指令并行处理
• 自动并行化：识别并行机会，生成并行代码
• 预测执行：基于分支预测进行优化
• 缓存优化：改善数据局部性

编译器优化级别：

链接时优化(LTO)：

• 在链接阶段进行全程序优化
• 跨模块优化机会
• 更好的内联和死代码删除

总结

计算机基础知识涵盖了计算机系统的各个层面，从底层硬件到高层软件，从理论基础到实际应用。掌握这些知识对于理解现代计算机系统的工作原理、进行系统设计和性能优化都具有重要意义。

核心要点回顾：

1. 系统层次：理解计算机系统的层次结构，从硬件到软件的抽象层次
2. 性能优化：掌握各层次的性能瓶颈和优化方法
3. 并发与并行：理解多级并发机制，从指令级到系统级
4. 存储层次：掌握存储系统的设计原理和性能特征
5. 网络通信：理解网络协议栈和分布式系统基础
6. 系统安全：关注各层次的安全机制和威胁防护

这些基础知识为深入学习专业技术、进行系统架构设计和解决实际工程问题提供了坚实的理论基础。在实际工作中，需要将这些理论知识与具体的技术实践相结合，不断提升系统设计和问题解决能力。