03. 程序设计语言基础¶
程序设计语言、基本成分、函数调用与语言处理程序基础。
配套阅读：程序设计语言基础：课件笔记，含课程配图、例题和参考解析。
本章目录¶
语言分类、编译与形式语言¶
---
markmap:
height: 760
initialExpandLevel: 2
autoFit: true
colorFreezeLevel: 2
maxWidth: 280
spacingHorizontal: 80
spacingVertical: 12
nodeMinHeight: 24
paddingX: 10
---
# 编程语言与执行方式
## 语言层次与范式
- 机器语言：直接以机器指令编码表示操作
- 汇编语言：用助记符和符号地址描述机器指令，由汇编器翻译
- 高级语言：用更抽象的数据与控制结构表达程序
- 常见范式：过程式、面向对象、函数式、逻辑式；一种语言可支持多种范式
## 编译、解释与混合实现
- 编译：先把源程序翻译为目标代码
- 目标可以是机器码，也可以是字节码或其他中间表示
- 提前编译的本机程序通常不需要编译器参与执行，但可能依赖运行库
- 解释：运行时由解释器执行源程序或中间表示
- 解释执行不等于逐行读取源代码，也不排斥预先生成字节码
- 混合方式：先编译为字节码，再解释执行或进行即时编译 JIT
- 编译和解释属于实现方式，不能把语言永久划为互斥的两类
- 性能取决于实现、优化、运行环境与工作负载
- 可移植性取决于语言规范、平台依赖及工具链；机器码通常依赖目标架构
## 常见语言
- Fortran：科学与数值计算，擅长数组和高性能计算
- Pascal：强调结构化程序设计；Delphi 使用 Object Pascal 并提供开发环境
- C：过程式语言，支持指针与底层内存操作，常用于系统开发
- Lisp：以符号和列表处理见长，支持函数式编程，常用于人工智能研究
- C++：支持过程式、面向对象和泛型编程，兼顾抽象能力与底层控制
- Java：通常先编译为字节码，由 JVM 执行；跨平台依赖兼容运行时与库
- C#：主要面向 .NET，通常生成中间语言，再由运行时编译或解释执行
- Prolog：用事实、规则和查询进行逻辑推理，适合知识表示与专家系统
- Python：支持多种范式，常用于脚本、自动化和系统集成
- CPython 通常先编译为字节码，再由虚拟机执行
---
markmap:
height: 760
initialExpandLevel: 2
autoFit: true
colorFreezeLevel: 2
maxWidth: 280
spacingHorizontal: 80
spacingVertical: 12
nodeMinHeight: 24
paddingX: 10
---
# 编译过程与程序错误
## 词法分析
- 输入：字符流；输出：单词符号 Token 流
- 识别关键字、标识符、字面量、运算符和分隔符
- 处理空白与注释，报告非法字符或不完整字面量等问题
## 语法分析
- 按文法把 Token 组织成表达式、语句等语法结构
- 构造语法树或抽象语法树 AST
- 检查括号配对、结构和语句形式等语法约束
## 语义分析
- 检查名字是否声明、作用域、类型与调用参数是否符合语言规则
- 静态类型检查能发现的错误取决于语言的类型系统与编译器能力
## 中间代码与目标代码
- 中间表示：三地址码、字节码等，便于分析与转换
- 优化：在保持程序规定语义的前提下改进代码
- 目标代码生成：选择指令、分配寄存器，生成目标平台代码
- 链接：解析外部符号并组合目标模块与库
- 装入：把可执行映像映射到内存，完成运行所需的准备
## 符号表
- 保存名字、类型、作用域、存储位置等信息
- 支持插入、查找、更新与作用域退出时的处理
- 为语义检查、存储分配和代码生成提供依据
## 错误分类
- 静态错误：在运行前通过词法、语法、语义等检查发现
- 动态错误：在执行过程中暴露，如某些越界访问或除零
- 具体表现由语言规则决定，可能是异常、终止或未定义行为
- 逻辑错误：程序可以运行，但结果不符合预期；不一定自动报错
---
markmap:
height: 760
initialExpandLevel: 2
autoFit: true
colorFreezeLevel: 2
maxWidth: 280
spacingHorizontal: 80
spacingVertical: 12
nodeMinHeight: 24
paddingX: 10
---
# 形式语言、文法与自动机
## 文法的组成
- 终结符、非终结符、产生式与开始符号
- 从开始符号反复应用产生式，推导出语言中的句子
## Chomsky 文法层次
- 0 型：无限制文法，对应图灵机可识别语言
- 对不属于语言的输入，识别过程不保证停机
- 1 型：上下文有关文法，对应线性有界自动机
- 2 型：上下文无关文法，对应非确定性下推自动机
- 产生式左部是单个非终结符；常用于描述程序语法
- 3 型：正规文法，对应有限自动机
- 常用于描述标识符、数值字面量等词法模式
- 表达能力：正规语言 ⊂ 上下文无关语言 ⊂ 上下文有关语言 ⊂ 图灵可识别语言
## 正则表达式与正规集
- 正则表达式描述字符串集合，ε 表示空串
- `ab`：先出现 a 再出现 b，即集合 {ab}
- `a|b`：选择 a 或 b，即集合 {a, b}
- `a*`：零次或多次重复 a，包含 ε、a、aa 等
- `(a|b)*`：由 a、b 构成的所有有限字符串，包含 ε
- 基本运算：连接、选择、闭包；括号改变结合范围
- 此处指形式语言中的正则表达式；带反向引用等扩展的正则引擎能力可能更强
## 有限自动机
- 组成：有限状态集合、输入字母表、转移、初态与接受状态
- DFA：每个状态对每个输入符号有唯一的转移结果
- NFA：可有多个候选转移，也可使用 ε 转移
- DFA、NFA 与正规文法在识别能力上等价
- 处理完全部输入后处于接受状态，才接受该字符串
基本成分、函数调用与表达式¶
---
markmap:
height: 760
initialExpandLevel: 2
autoFit: true
colorFreezeLevel: 2
maxWidth: 280
spacingHorizontal: 80
spacingVertical: 12
nodeMinHeight: 24
paddingX: 10
---
# 程序的基本成分
## 数据成分
- 常量与变量：表示程序处理的值，类型约束可用操作
- C 的常见类型
- 整数、浮点、字符；数组、指针、结构体、联合体、枚举等
- 数组连续存储；指针保存地址，使用时受对象边界与生命周期约束
- Python 的常见对象
- 数值、字符串、元组：通常不可变；元组中的元素仍可能引用可变对象
- 列表：可变、有序、允许重复元素
- 元组与字符串：有序、允许重复元素
- 集合 set：可变、不保证迭代顺序、元素唯一；frozenset 不可变
- 字典 dict：可变、键唯一；Python 3.7 起保证保留插入顺序
- 集合元素与字典键须可哈希；不可变与可哈希不是完全相同的概念
## 运算成分
- 算术、比较、逻辑、位运算与赋值
- 优先级与结合性决定表达式如何分组，括号可明确分组
- 分组顺序不必等于操作数的求值顺序；后者取决于语言规则
- Python 序列操作
- `+` 连接；`*` 重复；下标访问；切片；`in` 成员判断
- 列表重复复制的是元素引用，嵌套可变对象可能被多个位置共享
- Python 的 `/` 为真除法，`//` 为向下取整除法；不同语言的整数除法规则可能不同
## 控制成分
- 顺序：依次执行语句
- 选择：根据条件执行分支，如 if、switch、match
- 循环：重复执行，如 for、while
- break 退出循环，continue 进入下一轮，return 结束函数调用
## 传输成分
- 输入：从键盘、文件、网络等获取数据
- 输出：把数据写入屏幕、文件、网络等
- 输入输出常伴随格式转换、缓冲和错误处理
---
markmap:
height: 760
initialExpandLevel: 2
autoFit: true
colorFreezeLevel: 2
maxWidth: 280
spacingHorizontal: 80
spacingVertical: 12
nodeMinHeight: 24
paddingX: 10
---
# 函数调用与递归
## 函数与调用过程
- 定义：名称、形参、函数体以及返回值约定
- 实参：调用时提供的表达式或对象；形参：被调用函数中接收参数的名字
- 调用栈帧通常保存返回地址、参数、局部变量和需恢复的状态
- 局部变量的作用域与对象的生命周期是不同概念
## 参数传递
- 传值：形参获得实参值的副本
- 给形参重新赋值，一般不改变调用者变量
- 若复制的是指针或对象引用，仍可能通过它修改所指对象
- 传引用：形参成为调用者变量的别名
- 对形参代表的对象赋值，可以改变调用者的值
- C：参数按值传递；传递指针值可间接修改目标对象
- Java：始终按值传递，包括对象引用的值
- Python：传递对象引用，常称对象共享传递
- 修改可变对象的内容可能被调用者观察到
- 在函数内重新绑定形参，不会重新绑定调用者变量
## 递归调用
- 函数直接或间接调用自身
- 基本情形：无需继续递归即可得到结果
- 递归步骤：把问题转化为规模更小的同类问题
- 终止性：每次递归须朝基本情形推进
- 每次调用拥有独立的局部执行状态，共享对象仍可被共同访问
- 空间开销与最大递归深度有关；过深可能造成栈溢出
- 尾递归能否消除栈增长，取决于语言和实现是否提供尾调用优化
---
markmap:
height: 760
initialExpandLevel: 2
autoFit: true
colorFreezeLevel: 2
maxWidth: 280
spacingHorizontal: 80
spacingVertical: 12
nodeMinHeight: 24
paddingX: 10
---
# 表达式的表示与求值
## 中缀表达式
- 运算符位于操作数之间，如 `(a + b) * c`
- 依靠优先级、结合性和括号确定结构
## 前缀表达式
- 运算符在前，如 `* + a b c`
- 对应表达式树的先序遍历
- 从右向左扫描：操作数入栈，运算符取出操作数计算
## 后缀表达式
- 运算符在后，如 `a b + c *`，又称逆波兰式
- 对应表达式树的后序遍历
- 从左向右扫描：操作数入栈，遇运算符计算并把结果入栈
- 二元运算符先弹出右操作数，再弹出左操作数
- `a b -` 表示 a 减 b，不能颠倒顺序
## 中缀转后缀
- 操作数直接输出；运算符用栈暂存
- 根据优先级与结合性弹出应先执行的栈顶运算符
- 左括号入栈，右括号触发弹出直到匹配的左括号
- 扫描结束后输出剩余运算符；括号本身不进入结果
## 结构关系
- 前缀与后缀式在运算符元数明确时，无需括号即可确定结构
- 表达式树叶结点通常为操作数，内部结点为运算符