程序语言基础
zKing 2018-11-19 专业知识
# 基本概念
# 低级语言和高级语言
# 低级语言
机器语言和汇编语言称为低级语言
# 高级语言
从人类的逻辑思维角度出发、面向各类应用的程序语言
# 编译程序和解释程序
- 高级语言或汇编语言编写的程序为源程序，源程序不被曝光直接再计算机上运行
- 如果源程序是汇编语言编写的，则需要一个称为汇编程序的翻译程序将其翻译成目标程序，然后才能执行
- 如果源程序是高级语言时，这个翻译程序称为编译程序。
- 按源程序中语句的执行顺序，逐条翻译并立即执行相关功能的处理程序、称为解释程序
# 程序执行方式
- 编译执行
- 先编译后运行
- 执行效率高，占用资源小，兼容性差
- 解释执行
- 源程序中的每个语句已经解释就立即执行
- 可移植性较好，开发速度快，与用户通信方便，但是效率低
# 编译系统基本原理
6个阶段（不可更改顺序）
# 词法分析
# 一个程序语言的基本语法符号分为5类
- 关键字
- 标识符
- 常量
- 运算符
- 界符
# 词法分析器所输出单词符号常表示为如下的二元式
- （单词种别，单词符号的属性值）
- 对于标识符，单词字符的属性值是使用指针来进行描述的
# 状态转换图
- 定义
- 状态有限的有向图，是一种非形式化的表示方法
- 用圆圈表示结点状态
- 结点之间用有向边来代表状态转换
- 有向边上可标记字符，表示前一状态接受某个字符之后的- 状态转移
- 功能
- 用于识别一定的字符串
- 要求
- 状态（即结点）个数有限
- 至少一个初始状态，若干终止状态（终止状态用同心圆表示）
- 每条边上标有字符（也可以是空字符）（多读进一个字符用“*”表示）
# 描述词法的规则
- 正规式（正规表达式）
- 正则表达式与正规集（定义和运算 ）
- 正规表达式是词分析的形式化表示方法，是指用一整套带有严格规定的符号体系来描述问题的方法
- 正规式与正规集的递归定义
- ε 和 φ 是字母表 ∑ 上的正规式，它们所表示的正规集分别为 { ε }和 φ （一定存在于 ∑ 中的）
- 任何 a ∈ ∑，a 是 ∑ 上的一个正规式，它所表示的正规集为 { a }
- 正规式定义中
- “ | ”读为 "或"
- “ . ”读为 "连接"
- ”*“读为 "闭包"
- 正则表达式与正规集（定义和运算 ）
- 有限自动机
- 以状态转换图为基础
- 初始状态
- 终止状态（接收状态）
- 后继状态
- 有限状态机在读入一个字符时，其状态改变为另一状态，则改变后的状态被称为后继状态
- 分类
- 确定有限自动机（DFA） --转换后的后继状态是唯一的
- 注：要学会从 M 的公式画出状态图，反之也要
- 一个确定的有限自动机 M 是一个五元式
- M=（S，∑，δ，s0，F）
- S 是一个有限集，它的每个元素称为一个状态
- ∑ 是一个有穷字母表，它的每个元素称为一个输入字符
- δ 是一个从 s x ∑ 至 s 的单值部分映射。δ（s，a）=s'，意味着：当现行状态为 s，输入 a 时，将转换到下一状态 s'，即后继状态
- s0 ∈ S，是 S 唯一的初态
- F 是 S的一个终态集（可空）
- 不确定有限自动机（NFA） --转换后的后继状态不唯一的
- 确定有限自动机（DFA） --转换后的后继状态是唯一的
# 语法分析
- 语法分析器以单词符号作为输入，分析单词符号串是否形成符合语法规则的语法单位，如表达式、赋值、循环等。
- 按语法规则分析检查每条语句是否有正确的逻辑结构
- 方法
- 自上而下分析法
- 自下而上分析法
# 语义分析
- 语义分析阶段主要是检查源程序是否存在语义错误，并收集类型信息以供后面的代码生成阶段使用。其主要工作是进行各类型分析和检查。赋值语句的右端和左端的类型不匹配。表达式的除数是否为零等。
- 只有语法和语义都正确的源程序才能编译成正确的目标代码
# 中间代码生产（了解）
- 根据语义分析的输出生成中间代码
- 中间代码是一种简单且含义明确的记号系统，可以有若干种形式，常见的有逆波兰记号、四元式、三元式和树
- 它们共同的特征是代码的方式与具体的机器无关
# 代码优化（了解）
- 对前阶段产生的中间代码进行变换和进行改造
- 使生成的目标代码更为高级，即省时间和声空间
# 目标代码（了解）
- 把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。
- 这是编译的最后阶段，与硬件系统的结构和指令的含义有关
# 程序语言的控制结构
# 表达式
# 前缀表达式（波兰表示法）
- 将操作符至于操作数之前
- 从右至左扫描表达式
- 遇到数字，将数字压入堆栈
- 遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算，并将结构入栈
- 重复上述过程直到表达式最左端，最后运算得出的值为表达式结果
- 示例： ”-x+3456“
# 中缀表达式
- 生活中常用的数学运算表示方法
- 示例：”(3+4)x5-6“
# 后缀表达式（逆波兰法）
- 将操作符至于操作数之后
- 与前缀表达式类似，只是顺序是从左至右
- 示例：”34+5x6-“
# 操作符的优先级
- 指针最优，单目运算优于双目运算。如正负号
- 先乘除（模），后加减
- 先算术运算，后移位运算，最后位运算
- 逻辑运算最后计算
# 语句间的结构
- 顺序语句
- 选择语句
- 循环语句
# 过程控制
# 参数传递的方式（以 swap 函数为例）
- 传值调用
- 数据传送是单向的
- 引用调用（地址调用）
- 数据传送是双向的