软考笔记

Appearance

第17章 程序设计语言与语言处理程序基础 ​

📚 章节概述 ​

程序设计语言与语言处理程序基础是软考中级软件设计师考试的重要内容，涵盖程序设计语言的基本概念、编译原理和语言处理技术。本章将系统学习程序设计语言的理论基础和编译技术。

🎯 学习目标 ​

通过本章学习，你将掌握：

  • 程序设计语言的基本概念和分类
  • 编译程序和解释程序的区别
  • 编译过程的各个阶段
  • 文法和语言的形式化描述
  • 有限自动机和正规表达式

📖 课程安排 ​

17.1 程序设计语言概述 (10课时) ​

17.1.1 程序设计语言概述知识点概述 ​

  • 程序设计语言的定义 - 人与计算机交流的工具
  • 语言的发展历程 - 从机器语言到高级语言
  • 语言的分类方法 - 按不同标准进行分类
  • 语言的重要性 - 软件开发的基础工具

17.1.2 编译程序与解释程序 ​

  • 编译程序特点
    • 将源程序翻译成目标程序
    • 翻译和执行分离
    • 执行效率高
    • 典型语言：C、C++、Pascal
  • 解释程序特点
    • 边翻译边执行
    • 翻译和执行同时进行
    • 交互性好，调试方便
    • 典型语言：Python、JavaScript、BASIC
  • 混合方式
    • Java：编译成字节码，再解释执行
    • C#：编译成中间语言，JIT编译

17.1.3 多种程序设计语言特点 ​

  • 过程式语言
    • 特点：以过程为中心，自顶向下设计
    • 代表：C、Pascal、FORTRAN
    • 优点：结构清晰，易于理解
    • 缺点：数据和操作分离
  • 面向对象语言
    • 特点：以对象为中心，封装、继承、多态
    • 代表：Java、C++、C#
    • 优点：代码重用性好，维护性强
    • 缺点：学习曲线陡峭
  • 函数式语言
    • 特点：以函数为基本单位，无副作用
    • 代表：Lisp、Haskell、ML
    • 优点：数学基础严格，并行性好
    • 缺点：与传统思维差异大
  • 逻辑式语言
    • 特点：基于逻辑推理，声明式编程
    • 代表：Prolog
    • 优点：适合人工智能应用
    • 缺点：执行效率相对较低

17.1.4 程序设计语言的基本成分 ​

  • 数据成分
    • 常量：程序中不变的值
    • 变量：可以改变值的存储单元
    • 数据类型：整型、实型、字符型、布尔型等
    • 数据结构：数组、记录、指针等
  • 运算成分
    • 算术运算：+、-、*、/、%
    • 关系运算：>、<、>=、<=、==、!=
    • 逻辑运算：&&、||、!
    • 位运算：&、|、^、~、<<、>>
  • 控制成分
    • 顺序结构：语句的顺序执行
    • 选择结构：if-else、switch-case
    • 循环结构：for、while、do-while
    • 跳转语句：break、continue、goto、return
  • 传输成分
    • 赋值语句：变量赋值
    • 输入输出：scanf、printf、cin、cout

17.1.5 函数调用方式 ​

  • 传值调用（Call by Value）
    • 将实参的值复制给形参
    • 形参的改变不影响实参
    • 适用于基本数据类型
  • 传址调用（Call by Address）
    • 将实参的地址传递给形参
    • 通过地址可以修改实参的值
    • 适用于数组、结构体等
  • 传名调用（Call by Name）
    • 将实参的名字传递给形参
    • 每次使用形参时重新计算实参
    • 较少使用，主要在宏定义中
  • 传引用调用（Call by Reference）
    • 形参是实参的别名
    • 形参和实参共享同一存储空间
    • C++、C#等语言支持

17.2 编译程序基本原理 (12课时) ​

17.2.1 编译程序基本原理知识点概述 ​

  • 编译程序的作用 - 将高级语言翻译成机器语言
  • 编译过程的复杂性 - 语法分析、语义分析、代码生成
  • 编译技术的应用 - 不仅用于编程语言，还用于其他领域

17.2.2 编译过程概述 ​

  • 词法分析（Lexical Analysis）
    • 任务：将字符流转换为记号流
    • 输入：源程序字符序列
    • 输出：记号（Token）序列
    • 工具：有限自动机
  • 语法分析（Syntax Analysis）
    • 任务：检查记号序列的语法正确性
    • 输入：记号序列
    • 输出：语法树（Parse Tree）
    • 工具：上下文无关文法
  • 语义分析（Semantic Analysis）
    • 任务：检查语义正确性，类型检查
    • 输入：语法树
    • 输出：带属性的语法树
    • 内容：类型检查、作用域分析
  • 中间代码生成
    • 任务：生成中间表示形式
    • 形式：三地址码、四元式等
    • 优点：便于优化和目标代码生成
  • 代码优化
    • 任务：改进代码效率
    • 类型：局部优化、全局优化
    • 技术：常量折叠、死代码删除等
  • 目标代码生成
    • 任务：生成目标机器代码
    • 考虑：寄存器分配、指令选择
    • 输出：可执行的机器代码

17.2.3 文法 ​

  • 文法的定义 - G = (VN, VT, P, S)
    • VN：非终结符集合
    • VT：终结符集合
    • P：产生式集合
    • S：开始符号
  • 产生式的形式 - α → β
    • α：产生式左部（非空）
    • β：产生式右部（可为空）
  • 文法的分类（Chomsky层次）
    • 0型文法（无限制文法）：α → β，无限制
    • 1型文法（上下文相关文法）：|α| ≤ |β|
    • 2型文法（上下文无关文法）：A → β，A∈VN
    • 3型文法（正规文法）：A → aB 或 A → a
  • 语言的定义 - 文法产生的所有句子的集合
  • 句型和句子
    • 句型：从开始符号推导出的符号串
    • 句子：只含终结符的句型

17.2.4 正规式与正规集 ​

  • 正规式的定义
    • 基本正规式：∅、ε、a（a∈VT）
    • 复合正规式：r1|r2、r1r2、r*
  • 正规式的运算
    • 选择（|）：r1|r2 表示 r1 或 r2
    • 连接：r1r2 表示 r1 后跟 r2
    • 闭包（）：r 表示 r 的零次或多次重复
  • 正规集 - 正规式表示的语言
  • 正规式与正规文法的等价性
    • 每个正规式对应一个正规文法
    • 每个正规文法对应一个正规式

17.2.5 有限自动机 ​

  • 有限自动机的定义 - M = (Q, Σ, δ, q0, F)
    • Q：状态集合
    • Σ：输入字母表
    • δ：转换函数
    • q0：初始状态
    • F：终结状态集合
  • 确定有限自动机（DFA）
    • 对每个状态和输入符号，最多有一个转换
    • 识别能力：正规语言
  • 非确定有限自动机（NFA）
    • 对每个状态和输入符号，可能有多个转换
    • 可以有ε转换
    • 与DFA等价，但更容易构造
  • 自动机的应用
    • 词法分析器的实现
    • 模式匹配
    • 协议验证

17.2.6 后缀表达式 ​

  • 中缀表达式 - 运算符在操作数中间：a + b
  • 后缀表达式 - 运算符在操作数后面：a b +
  • 前缀表达式 - 运算符在操作数前面：+ a b
  • 中缀转后缀算法
    1. 从左到右扫描中缀表达式
    2. 操作数直接输出
    3. 运算符根据优先级入栈或出栈
    4. 左括号入栈，右括号弹出到左括号
  • 后缀表达式求值
    1. 从左到右扫描后缀表达式
    2. 操作数入栈
    3. 运算符弹出操作数计算，结果入栈
    4. 最终栈中剩余一个元素即为结果

17.3-17.4 章节总结 (2课时) ​

  • 17.3 章节概述 - 知识点梳理和重点回顾
  • 17.4 章节回顾 - 典型题目分析和解题技巧

⏰ 学习时间安排 ​

  • 总学习时间：24课时
  • 建议学习周期：3-4周
  • 每日学习时间：1-2课时
  • 重点难点：编译过程、文法理论、自动机

🔍 重点难点 ​

重点内容 ​

  1. 语言分类 - 掌握不同类型语言的特点
  2. 编译过程 - 理解编译的各个阶段
  3. 文法理论 - 掌握文法的定义和分类
  4. 自动机理论 - 理解有限自动机的工作原理
  5. 表达式转换 - 掌握中缀到后缀的转换

难点突破 ​

  1. 文法分类 - 理解Chomsky文法层次
  2. 自动机构造 - 从正规式构造自动机
  3. 编译阶段 - 理解各阶段的输入输出
  4. 算法实现 - 掌握表达式转换算法

📝 考试要点 ​

选择题考点 ​

  • 语言特点 (2-3分)
  • 编译过程 (3-4分)
  • 文法理论 (3-4分)
  • 自动机 (2-3分)
  • 表达式转换 (2-3分)

计算题考点 ​

  • 后缀表达式转换 (5-8分)
  • 自动机构造 (5-8分)
  • 文法分析 (3-5分)

🔄 编译过程示例 ​

源程序到目标程序 ​

源程序: int a = b + c * 2;

词法分析:
int | a | = | b | + | c | * | 2 | ;

语法分析:
赋值语句
├── 变量: a
└── 表达式
    ├── 变量: b
    ├── 运算符: +
    └── 表达式
        ├── 变量: c
        ├── 运算符: *
        └── 常量: 2

语义分析:
类型检查，符号表管理

中间代码:
t1 = c * 2
t2 = b + t1
a = t2

目标代码:
LOAD R1, c
MUL R1, #2
LOAD R2, b
ADD R2, R1
STORE a, R2

📊 文法分类对比 ​

文法类型产生式形式识别机器语言类型应用
0型α → β图灵机递归可枚举语言理论研究
1型αAβ → αγβ线性界限自动机上下文相关语言自然语言
2型A → α下推自动机上下文无关语言程序设计语言
3型A → aB, A → a有限自动机正规语言词法分析

🤖 自动机应用 ​

词法分析器设计 ​

标识符识别的DFA:
状态0 --字母--> 状态1
状态1 --字母/数字--> 状态1 (接受状态)

数字识别的DFA:
状态0 --数字--> 状态1 (接受状态)
状态1 --数字--> 状态1

正规式示例 ​

标识符: [a-zA-Z][a-zA-Z0-9]*
整数: [0-9]+
实数: [0-9]+\.[0-9]+
注释: //.*
字符串: ".*"

预计完成时间：24课时 | 难度等级：★★★★☆