覆盖软考官方教程《程序设计语言基础知识》章节全部考点。 本章是上午科目必考内容，重点集中在：语言处理程序、编译过程各阶段、文法分类、正规式与有限自动机、中间代码（后缀式）、传值与传引用。
第 1 部分 程序设计语言概述
1.1 语言分类
低级语言（机器/汇编）与机器相关；高级语言与机器无关、可移植性强
高级语言需要翻译才能执行，翻译方式：编译 或 解释
1.2 高级语言分类
1.3 程序设计语言基本成分
数据成分：常量、变量、数据类型（整型、实型、字符型、布尔型、数组、指针等）
运算成分：算术运算、关系运算、逻辑运算
控制成分：顺序、选择（if/switch）、循环（for/while）
传输成分：输入输出
第 2 部分 语言处理程序（必考）
2.1 三种处理程序
2.2 编译与解释对比（高频）
注意：Java 是先编译成字节码，再由 JVM 解释/即时编译执行，属于"编译+解释"结合。
第 3 部分 编译过程（核心必考）
3.1 编译的六个阶段
符号表管理：记录标识符的属性（类型、地址、作用域），贯穿各阶段
出错处理：发现并报告错误（语法错误、语义错误），贯穿各阶段
前端（与机器无关）：词法、语法、语义、中间代码生成
后端（与机器相关）：代码优化、目标代码生成
3.2 词法分析（重点）
输入：源程序字符流；输出：记号流
记号（token）由三部分构成：模式 + 词素 + 属性值
记号种类：关键字、标识符、常量、运算符、界符
实现工具：正规式（描述单词结构）+ 有限自动机（识别）
NFA（不确定有限自动机）：同一状态对同一输入可有多个后继或 ε 转移
DFA（确定有限自动机）：每个状态对每个输入符号有唯一后继
NFA 可等价转换为 DFA（子集构造法），DFA 可最小化
3.2.1 正规式（正则表达式，必考）
正规式：用运算符描述字符串集合（正规集）的式子，是词法分析描述单词结构的工具
运算符优先级（从高到低）：*（闭包）> ·（连接）> |（或），括号最高；连接符 · 常省略
运算含义：
等价关系：正规式 ↔ 正规文法（3 型）↔ 有限自动机（NFA/DFA）三者等价
【例题 1】 正规式 a(a|b)* 表示的语言？ → 以 a 开头的任意 a、b 串（含单独的 a）
【例题 2】 正规式 (a|b)a(a|b) 表示？ → 含有至少一个 a 的任意 a、b 串
【例题 3】 表示"以 00 结尾的二进制串"的正规式是？ → (0|1)*00
3.2.2 有限自动机（必考）
DFA（确定有限自动机）五元组：M = (S, Σ, δ, s₀, F)
S：有限状态集合；Σ：输入字母表；δ：状态转移函数 S×Σ→S（唯一后继）
s₀：唯一初态；F：终态集合（可多个）
NFA（不确定有限自动机）：δ 的后继不唯一，或存在 ε 转移
DFA 是 NFA 的特例；NFA 可用子集构造法转换为等价的 DFA
用状态转换图表示：结点=状态，有向边标输入字符，初态标 →，终态用双圈
串被接受：从初态出发沿字符转移，读完串后落在终态则接受
【例题】 某 DFA 识别"偶数个 0"的二进制串：状态 A（偶数个 0，初态且终态）、B（奇数个 0）；转移：A 读 0→B、读 1→A；B 读 0→A、读 1→B。判断串
0101是否被接受？ → A→(0)→B→(1)→B→(0)→A→(1)→A，落在终态 A（含 2 个 0，偶数）→ 接受
3.3 语法分析（重点）
任务：按文法判断记号串是否符合语法规则，构造语法树（分析树）
依据文法：上下文无关文法（2 型文法）
自顶向下分析：递归下降分析法、LL(1) 分析法（预测分析）
自底向上分析：LR(0)、SLR(1)、LR(1)、LALR(1) 分析法（移进-归约）
二义性：一个句子存在两棵不同的语法树，则该文法有二义性（需改写消除）
3.3.1 推导与规约（考点）
推导：从开始符号出发，反复用产生式替换非终结符，直至得到句子
最左推导：每次替换最左边的非终结符；最右推导（规范推导）：每次替换最右边的非终结符
规约：推导的逆过程，从句子逐步归约为开始符号
例：文法 E → E+E | EE | a，求 aa 的最左/最右推导
最左推导：E ⇒ EE ⇒ aE ⇒ a*a
最右推导：E ⇒ EE ⇒ Ea ⇒ a*a
短语、直接短语、句柄（相对某句型）：
短语：句型中能规约为某个非终结符的子串
直接短语：经一步规约得到的短语
句柄：最左直接短语（最右推导的逆——最左规约所规约的对象）
乔姆斯基文法分类（必考）
包含关系：0 型 ⊇ 1 型 ⊇ 2 型 ⊇ 3 型
判断技巧：产生式左侧只有一个非终结符 → 2 型；左侧非终结符前后有上下文 → 1 型；形如 A→aB / A→a → 3 型
【例题】 判断下列产生式所属文法类型：
S → aS | a → 右线性形式 → 3 型（正规文法）
S → aSb | ε → 左侧单非终结符 S，可生成 aⁿbⁿ → 2 型（上下文无关）
aSb → aCb（非终结符 S 前后有 a、b 上下文）→ 1 型（上下文有关）
ab → ba（左侧非单个非终结符）→ 0 型（短语结构）
3.4 语义分析
任务：进行静态语义检查（类型检查、变量声明检查、运算合法性）
输出：带类型信息等属性标注的语法树
3.5 中间代码（必考计算）
中间代码是与机器无关的中间表示，常见形式：
3.5.1 中缀转后缀（栈算法 + 运算符优先级）
运算符优先级（从高到低）：括号 > 单目 > *、/ > +、- > 关系 > 逻辑
栈算法：
操作数直接输出
遇运算符：栈空、栈顶为 ( 或该运算符优先级高于栈顶 → 入栈；否则弹出栈顶输出，继续比较
遇 ( 入栈；遇 ) 依次弹出栈顶输出，直到弹出 ( 为止（括号不输出）
扫描结束，弹出栈中剩余运算符
后缀式求值：用栈，遇操作数入栈，遇运算符弹出两个操作数运算后压回
【例题】 转换下列中缀表达式为后缀式：
a + b * c→ abc*+(a + b) * c→ ab+c*a + b * c - d→ abc*+d-a*(b+c)-d→ abc+*d-a+b*(c-d)/e→ abcd-*e/+
3.5.2 四元式与三元式（例题）
四元式：（运算符, 操作数1, 操作数2, 结果变量），用临时变量存中间结果
三元式：（运算符, 操作数1, 操作数2），用位置编号引用中间结果
例：a*(b+c)
四元式：① (+, b, c, t1) ② (*, a, t1, t2)
三元式：① (+, b, c) ② (*, a, (1))
区别：四元式便于优化（可移动、重排）；三元式省去临时变量、代码短，但移动/删除困难
第 4 部分 程序语言基础成分
4.1 数据类型
基本类型：整型、实型（浮点）、字符型、布尔型
构造类型：数组、结构体/记录、联合、枚举、指针、字符串
抽象数据类型 ADT：数据 + 操作封装
4.1.1 数组存储与地址计算（了解）
数组在内存中连续存储：行优先（C、C++）或列优先（Fortran）
行优先：Loc(ai) = 起始地址 + (i × 列数 + j) × 元素大小
列优先：Loc(ai) = 起始地址 + (j × 行数 + i) × 元素大小
【例题】 二维数组 a3（3 行 4 列）按行优先存储，起始地址 100，每元素占 2 字节，求 a2 的地址？ → Loc = 100 + (2×4 + 1)×2 = 100 + 18 = 118
4.2 变量与作用域
静态作用域（词法作用域）：作用域由程序文本结构决定（C、Java、Python 等绝大多数语言）
动态作用域：作用域由调用关系决定（早期 Lisp）
全局变量 / 局部变量；块结构
C 语言存储类别：auto（自动）、static（静态）、extern（外部）、register（寄存器）
4.2.1 作用域例题
int x = 1;
void f() { printf("%d", x); }
void g() { int x = 2; f(); } // 调用 g 时静态作用域：f 中的 x 由文本结构决定，取全局 x → 输出 1
动态作用域：f 运行时按调用链取最近的 x（g 的局部 x）→ 输出 2
4.3 参数传递（必考）
C 语言默认传值，用指针可实现传地址效果
Java 基本类型传值，对象传引用值
例题：
void swap(int a, int b)交换 a、b 后，main 中实参不变 → 说明是值传递
4.3.1 参数传递经典例题
【例题 1 传值】 C 语言
void swap(int a,int b){int t=a;a=b;b=t;}调用swap(x,y)后 x、y 不变 → 值传递，形参是副本。【例题 2 传地址】 改用
void swap(int *a,int *b)并调用swap(&x,&y)→ 通过指针改实参，x、y 交换成功。【例题 3 传引用】 C++ 中
void f(int &a,int &b)传引用，形参是实参别名，调用后实参被修改。【例题 4 传值结果】 函数体内形参改变在返回时才写回实参，中途多次赋值以最后值为准。
4.4 函数与递归
函数：参数 + 返回值，实现模块化
递归：函数直接或间接调用自身，必须有递归出口（边界条件）
递归 vs 迭代：递归代码简洁但开销大（栈），可用栈将递归转非递归
4.5 控制结构
顺序结构、选择结构（if-else、switch）、循环结构（for、while、do-while）
结构化程序设计：三种基本结构即可描述任意算法
4.6 运行时存储组织（了解）
静态存储分配：编译时确定存储空间，用于全局变量、静态变量，运行期间不变
栈式存储分配：运行时动态分配，用于函数调用的参数、局部变量、返回地址，后进先出
堆式存储分配：运行时动态分配，大小/生命周期不定（malloc/new），需手动释放或 GC 回收
活动记录（栈帧）：函数调用时压入栈的一段存储，含参数、局部变量、返回地址、控制链
第 5 部分 典型程序设计语言特点（常考选择）
5.1 C 语言
面向过程的高级语言，兼具低级语言能力（指针、位运算）
指针是核心特色；无垃圾回收；内存需手动管理
编译执行，效率高，广泛用于系统软件、嵌入式
5.2 C++ / Java / C#
面向对象三大特性：封装、继承、多态
抽象类、接口、重载（编译时多态）、重写/覆盖（运行时多态）
静态绑定（编译时绑定）：重载、静态方法，编译期确定调用对象
动态绑定（运行时绑定）：重写/覆盖（虚函数、多态），运行期确定调用对象
5.3 脚本语言
Python：解释执行、动态类型、强制缩进、丰富的标准库
JavaScript：浏览器端脚本语言，原型继承、事件驱动
特点：开发效率高、执行效率较低，常用于 Web、自动化
5.4 函数式语言
Lisp / Scheme / Haskell
核心：函数是一等公民、无副作用（纯函数）、递归、λ 演算
适合数学计算、AI 早期研究
5.5 逻辑式语言
Prolog：基于一阶谓词逻辑，由事实 + 规则 + 查询组成
通过归结（消解）推理自动求解
5.6 标记与数据描述语言
HTML：网页展示结构
XML：可扩展标记语言，自定义标签，描述数据，跨系统交换
JSON：轻量级数据交换格式，键值对，易解析
5.7 数据库语言
SQL：数据定义（DDL）、数据操纵（DML）、数据控制（DCL）
属于声明式语言（告诉"做什么"而非"怎么做"）
第 6 部分 易混淆点与易错点
词法分析 ≠ 语法分析
词法：识别单词（标识符、关键字、数字），用正规式 + 有限自动机
语法：判断句子结构，用上下文无关文法 + 下推自动机
正规文法（3 型）对应有限自动机，用于词法；上下文无关文法（2 型）对应下推自动机，用于语法
编译 vs 解释：编译生成目标代码可重复执行；解释不生成目标代码，边译边执行
后缀式：运算符在操作数之后，用栈求值
传值 vs 传引用：传值不影响实参，传引用/传地址会影响实参
静态作用域 vs 动态作用域：静态由文本结构决定，动态由调用链决定
Java 是单继承（C++ 支持多继承）；Java 无指针、自动垃圾回收
1 型文法判断：产生式左右两侧出现上下文（αAβ → αγβ）
正规式 ↔ 正规文法 ↔ 有限自动机 三者等价
四元式 vs 三元式：四元式用临时变量存结果，三元式用位置编号引用结果
后缀式求值用栈；中缀转后缀运算符在操作数之后
第 7 部分 典型例题（真题风格）
后缀式：表达式
a - b * (c + d)的后缀式为？ → 先算括号：c d +；再乘：b c d + *；最后减：a b c d + * -编译阶段：识别标识符、关键字属于哪个阶段？ → 词法分析
文法类型：产生式
S → aS | ε属于？ → 形如 A→aA 或 A→a，属于 3 型（正规文法）文法类型：产生式
A → aB | b的识别装置是？ → 有限自动机（DFA/NFA）参数传递：C 语言中
void f(int x){ x=10; }，调用后实参值？ → 不变（值传递）中间代码：四元式、三元式、后缀式都属于？ → 中间代码（中间表示）
语言类型：Python 属于？ → 脚本语言（解释执行、动态类型）
语言类型：Prolog 属于？ → 逻辑式语言（一阶谓词逻辑、归结推理）
编译执行流程：源程序经过词法、语法、语义分析后生成？ → 中间代码，再经优化生成目标代码
解释程序特点：不生成目标代码、执行速度慢、便于调试
第 7.5 部分 真题精练（含答案与解析）
以下为软考历年高频考查题型，建议先独立作答再核对答案。
【正规式】 正规式 a(b|a)* 表示的语言是（ ）。 → 以 a 开头的任意 a、b 串。
【正规式】 表示"由 a、b 组成且以 b 结尾"的字符串集合的正规式是（ ）。 → (a|b)*b。
【有限自动机】 某 DFA 识别"奇数个 0"的二进制串，则该 DFA 的终态是（ ）。 → 处于奇数个 0的那个状态。
【文法】 产生式 S → aS | ε 属于（ ）型文法。 → 3 型（正规文法），对应有限自动机，用于词法分析。
【文法】 文法 G：S → aSb | ε 生成的语言是（ ）。 → {aⁿbⁿ | n ≥ 0}，属于 2 型（上下文无关文法）。
【编译阶段】 检查变量是否"先声明后使用"属于（ ）阶段。 → 语义分析（静态语义检查）。
【后缀式】 表达式
a + (b - c) * d的后缀式是（ ）。 → abc-d*+。【后缀式】 后缀式
ab+c*对应的中缀表达式是（ ）。 → (a+b)*c。【中间代码】 下列不属于中间代码形式的是（ ）。 A. 后缀式 B. 四元式 C. 三元式 D. 目标代码 → D。目标代码是编译最终产物，不是中间代码。
【参数传递】 C 语言函数参数默认的传递方式是（ ）。 → 值传递（形参修改不影响实参）。
【作用域】 采用动态作用域的语言，变量访问由（ ）决定。 → 运行时调用链（而非代码文本结构）。
【语言类型】 下列属于函数式语言的是（ ）。 A. C B. Java C. Lisp D. Prolog → C。Lisp 是函数式语言；Prolog 是逻辑式语言。
【编译vs解释】 下列语言中，通常采用解释方式执行的是（ ）。 A. C B. C++ C. Python D. 汇编 → C。Python 解释执行。
【C++/Java】 下列关于 Java 的说法正确的是（ ）。 A. 支持多继承 B. 有指针 C. 自动垃圾回收 D. 直接编译为机器码 → C。Java 单继承、无指针、自动 GC、编译为字节码由 JVM 运行。
【递归】 递归程序设计必须包含（ ）。 → 递归出口（边界条件），否则无限递归。
第 8 部分 复习策略建议
五大必考计算/判断：
中缀 ↔ 后缀式转换（每年大概率 1 题）
文法分类判断（0~3 型）
编译各阶段功能归属
正规式与有限自动机（等价关系、判定）
参数传递方式（传值/传引用结果分析）
对比表重点背：编译/解释、词法/语法、NFA/DFA、传值/传引用、C/C++/Java
结合真题：近 5 年本章常考正规式、DFA、后缀式、文法类型、参数传递
编译原理部分偏理论，理解"输入→输出"的流水线关系即可，不必深究算法细节
程序语言特点题以常识记忆为主，注意区分脚本语言、函数式、逻辑式、标记语言
本笔记依据软考《软件设计师教程》程序设计语言基础知识章节整理，仅供备考复习使用。
评论区