「学习笔记」程序设计语言

Apr 25, 2015 · 4 分钟阅读 · 计算机基础学习笔记 ·

文章目录

掌握程序设计语言（Programming Languages）基础知识与基本成分，汇编语言、编译程序、解释程序的基本原理。

一、程序语言基础

低级语言：机器语言（二进制0/1组成的机器指令序列）、汇编语言（使用助记符表示机器指令，需要通过汇编器转换为机器语言）
高级语言：接近自然语言的语法，需要编译器或解释器转换为机器语言；如 C、Java、Python 等。

1.1 程序设计语言的分类

按抽象级别

类型	特点	示例
机器语言	二进制指令，直接由 CPU 执行	`0x90`（NOP 指令）
汇编语言	助记符表示机器指令，需汇编器转换	`MOV AX, 5`
高级语言	接近自然语言，需编译器/解释器	C、Java、Python

按执行方式

类型	特点	示例
编译型语言	先编译成机器码再执行（高效）	C、C++、Go
解释型语言	逐行解释执行（跨平台）	Python、JavaScript
混合型语言	编译为中间代码，再解释执行	Java（JVM）、C#（CLR）

按范式（编程风格）

范式	特点	示例
命令式（Imperative）	通过语句改变程序状态	C、Pascal
面向对象（OOP）	以对象和类为核心	Java、C++
函数式（Functional）	强调纯函数、无副作用	Haskell、Lisp
逻辑式（Logic）	基于规则和推理	Prolog

1.2 程序设计语言定义与成分

程序设计语言的定义一般都涉及语法、语义、语用和语境等方面。
1. 语法:由程序设计语言的基本符号组成程序中的各个语法成分的一组规则，其中由基本字符构成的符号书写规则称为词法规则，由符号构成语法成分的规则称为语法规则。程序语言的语法可通过形式语言进行描述。
2. 语义:程序语言中按语法规则构成的各个语法成分的含义，可分为静态语义和动态语义
3. 语用:表示构成语言的各个记号和使用者的关系，涉及符号的来源、使用和影响。
4. 语境:理解和实现程序设计语言的环境，包括编译环境和运行环境。
程序设计语言成分
1. 数据成分：数据类型、变量、常量、全局/局部变量
2. 运算成分：运算符（算术运算，逻辑运算，关系运算）
3. 控制成分：顺序结构、选择结构、循环结构
4. 传输成分：允许数据传输的方式，如赋值处理、输入输出等
5. 函数：函数首部、函数体
  - 值调用：传递值
  - 引用调用：传递引用

1.3 语言处理程序

汇编程序：将汇编语言转换为机器语言。
编译程序：将高级语言源代码整体转换为目标代码，编译过程划分成：词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成六个阶段。
解释程序：逐行解释执行源代码，不生成独立的目标程序，这是它和编译程序的主要区别。

二、语言处理程序

2.1 编译过程的主要阶段

词法分析（Lexical Analysis）：读取源程序的字符流，将源代码拆分为 Token（单词符号），如 if、id、num、+。（工具：正则表达式、有限自动机（DFA/NFA）。）
语法分析（Syntax Analysis / Parsing）：检查 Token 序列是否符合语法规则，并生成语法树（Parse Tree）。（工具：上下文无关文法（CFG）、自顶向下（LL）或自底向上（LR）分析器。）
语义分析（Semantic Analysis）：检查类型匹配（如 int x = "hello"; 报错），处理变量声明、作用域，生成符号表（Symbol Table）（存储变量类型、作用域等信息）。
中间代码生成（Intermediate Code Generation）：生成与机器无关的中间表示（如 三地址码、四元式）。
代码优化（Optimization）：提高代码效率（如常量传播、死代码删除）。
目标代码生成（Code Generation）：生成目标机器代码（如 x86 汇编）。
符号表管理 & 错误处理：符号表记录变量、函数、类型等信息。错误处理包括词法错误（如int 1x;）、语法错误（如if x > 10 { ... }缺少括号）、语义错误（如int x = "hello";）。

阶段	输入	输出	关键工具
词法分析	源代码	Token 流	正则表达式、DFA
语法分析	Token 流	语法树	CFG、LL/LR 分析
语义分析	语法树	带类型的语法树	符号表、类型检查
中间代码	语法树	三地址码	与机器无关
代码优化	中间代码	优化后的中间代码	常量传播、死代码删除
目标代码	中间代码	机器码	寄存器分配

2.2 程序设计语言中的文法（Grammar）

文法（Grammar） 是用于描述程序设计语言语法结构的形式化规则。它定义了如何从基本符号（如关键字、标识符、运算符等）组合成合法的程序语句。文法在编译器设计、语言解析（Parsing）和形式语言理论中具有重要应用。

2.2.1 文法的基本概念

定义：文法 \( G \) 通常表示为一个四元组：\( G = (V_N, V_T, P, S) \)，其中：
- \( V_N \)（Non-terminals，非终结符）：可以被进一步推导的符号，通常表示语法结构，如 <表达式>、<语句>、<函数定义>等。
- \( V_T \)（Terminals，终结符）：最基本的符号，不能再被分解或推导。如关键字（if、else）、运算符（+、-）、标识符、常量等。
- \( P \)（Productions，产生式）：描述如何从非终结符推导(->)出其他符号的规则，格式：非终结符 -> 符号序列，如：\( <表达式> \rightarrow (<表达式> + <项>) \)。
- \( S \)（Start Symbol，开始符号）：文法的推导从开始符号开始。通常用<程序>或<语句>表示。

2.2.2 文法的分类（Chomsky 层次结构）

文法类型	规则形式	规则形式	对应自动机	应用
0型文法（无限制文法）	\( \alpha \rightarrow \beta \)（无限制）	其中`α`和`β`是任意符号序列，且`α`至少包含一个非终结符。（描述能力最强，难用于实际）	图灵机	通用计算
1型文法（上下文有关文法，CSG）	\( \alpha A \beta \rightarrow \alpha \gamma \beta \)	其中`A`是非终结符，`α`、`β`、`γ`是符号序列，且`γ`不为空。（描述能力较强，实现复杂）	线性有界自动机	自然语言处理
2型文法（上下文无关文法，CFG）	\( A \rightarrow \gamma \)	其中`A`是非终结符，`γ`是符号序列。（描述语法）	下推自动机	编程语言语法
3型文法（正则文法，RG）	\( A \rightarrow aB \) 或 \( A \rightarrow a \)	其中`A`和`B`是非终结符，`a`是终结符。（描述词法结构，如标识符、数字等）	有限状态自动机	词法分析（正则表达式）

重点：

编程语言的语法通常用 2型文法（上下文无关文法，CFG）描述，如 if-else、for 循环等。
词法分析（如标识符、数字）通常用 3型文法（正则文法，RG）描述。

2.2.3 语法推导树（Parse Tree / Derivation Tree，也称为语法分析树或推导树）

描述上下文无关文法（CFG）如何生成一个字符串。根节点为起始符号（如 <S>），叶子节点为终结符（如 a, b）。

示例：
- 文法：\( S → aSb | ε\)，生成 \( aabb \)。（ε读作"epsilon",表示空字符串）

       S
     / | \
    a  S  b
     / | \         推导过程:
    a  S  b               1. S → aSb
       |                  2. aSb → aaSbb
       ε                 3. aaSbb → aabb

2.2.4 有限自动机（Finite Automata, FA）

用于词法分析，识别正则语言（如标识符、数字）。由一组状态组成，包括一个开始状态和若干接受状态（也称为终止状态或最终状态）。

有限自动机是一个五元组 (Q, Σ, δ, q0, F)，其中：
- Q：有限状态集合。
- Σ：输入字母表。
- δ：转移函数。
- q0：开始状态，q0 ∈ Q（元素q0属于Q）。
- F：接受状态集合，F ⊆ Q（集合F是集合Q的子集）。
分为确定有限自动机DFA和不确定有限自动机NFA。
- DFA（确定性有限自动机）：每个状态对同一输入只有唯一转移。没有空转移（ε-transition）。
- NFA（非确定性有限自动机）：允许同一输入有多条转移路径。
示例：
- DFA：识别以 a 结尾的字符串的DFA
  - 状态（Q）：{q0, q1}
  - 字母表（Σ）：{a, b}
  - 转移函数（δ）：δ(q0, a) = q1、δ(q0, b) = q0、δ(q1, a) = q1、δ(q1, b) = q0
  - 开始状态（q0）：q0
  - 接受状态集合（F）：{q1}
- NFA：识别以 a 结尾的字符串的NFA
  - 状态（Q）：{q0, q1}
  - 字母表（Σ）：{a, b}
  - 转移函数（δ）：δ(q0, a) = {q0, q1}、δ(q0, b) = q0、δ(q1, a) = q1、δ(q1, b) = ∅（∅表示空集）
  - 开始状态（q0）：q0
  - 接受状态集合（F）：{q1}

有限自动机的局限性

只能识别正则语言：有限自动机无法识别上下文无关语言（如嵌套的括号结构）。
状态爆炸问题：将 NFA 转换为 DFA 时，状态数量可能指数级增长。

2.2.5 正规式（Regular Expression, RE）

用于词法分析，定义词法单元（如标识符、数字）。

基本操作：
- a|b：a 或 b。
- a*：零或多个 a。
- a+：至少一个 a。
- (ab)：连接。
常见正规式：
- 标识符：[a-zA-Z_][a-zA-Z0-9_]*。
- 整数：[0-9]+。
- 浮点数：[0-9]+\.[0-9]+。
RE → NFA → DFA：
1. RE 通过 Thompson 算法 转换为 NFA。
2. NFA 通过 子集构造法 转换为 DFA。
3. DFA 通过 最小化算法 优化。
示例：写出匹配 C 语言注释（/*...*/）的正规式。
- 答案：/\*.*\*/（需处理换行需用 [\s\S]*）。

2.2.6 真题示例：NFA 转换为 DFA

将以下非确定性有限自动机（NFA）转换为等价的确定性有限自动机（DFA）：
- 状态： {q0, q1, q2}
- 字母表： {a, b}
- 转移函数：
  - δ(q0, a) = {q0, q1}
  - δ(q0, b) = {q0}
  - δ(q1, a) = {q2}
  - δ(q1, b) = {q2}
  - δ(q2, a) = ∅
  - δ(q2, b) = ∅
- 开始状态：q0
- 接受状态： {q2}
解析：
1. 子集构造法：从 NFA 的开始状态 q0 开始，逐步构造 DFA 的状态。
2. DFA 状态：
- A = {q0}
- B = {q0, q1}
- C = {q0, q2}
- D = {q0, q1, q2}
1. 转移函数：
- δ(A, a) = B
- δ(A, b) = A
- δ(B, a) = D
- δ(B, b) = C
- δ(C, a) = B
- δ(C, b) = A
- δ(D, a) = D
- δ(D, b) = C
1. 接受状态：包含q2的状态是接受状态，即 C 和 D。
2. DFA 图示：

                 A --a--> B
                 A --b--> A
                 B --a--> D
                 B --b--> C
                 C --a--> B
                 C --b--> A
                 D --a--> D
                 D --b--> C

2.3 表达式（Expression）与语句（Statement）

表达式（Expression）是由操作数（如常量、变量、函数调用）和运算符组成的语法结构，用于计算一个值。如：算术表达式a + b * c、关系表达式a > b、逻辑表达式a && b、函数调用表达式max(a, b)、条件表达式（三元运算符）a > b ? a : b。
语句（Statement）是程序执行的基本单位，用于完成某种操作或控制程序流程。通常以分号;结尾。如：赋值语句a = b + c;、条件语句if (a > b) { ... }、循环语句for { ... }、函数调用语句print("Hello");、返回语句return a + b;。

2.3.1 表达式与语句的关系

表达式可以作为语句的一部分：如赋值语句：a = b + c; 中，b + c 是一个表达式，而 a = b + c; 是一个语句。
语句可以包含多个表达式：如：if (a > b && b < c) { ... } 中，a > b 和 b < c 是表达式，而整个 if 结构是一个语句。
某些语言中表达式和语句的界限模糊：如在 Python 中，赋值语句 a = b + c 也是一个表达式，可以返回值。

特性	表达式（Expression）	语句（Statement）
定义	计算一个值	执行一个操作
返回值	总是返回一个值	通常不返回值
组成	由操作数和运算符组成	由关键字、表达式和其他语句组成
用途	用于计算、比较、逻辑判断等	用于控制程序流程、赋值、函数调用等
示例	`a + b`、`a > b`、`max(a, b)`	`a = b + c;`、`if (a > b) { ... }`
语法	可以嵌套在其他表达式中	通常以分号结尾（某些语言不需要）

END .