第二章 程序设计语言基础知识
2.1 程序设计语言概述
2.1.1 程序设计语言的基本概念
程序设计语言是为了书写计算机程序而人为设计的符号语言，用于对计算过程进行描述、组织和推导。
低级语言：机器语言（有0和1序列构成）、汇编语言
高级语言：功能更强，抽象级别更高，与人们使用的自然语言比较接近
各程序设计语言特点
C语言（指针操作能力强，且高效）
Java语言（面向对象，中间代码，跨平台）
python语言（面向对象，脚本语言，解释型语言）
2.1.2 程序设计语言的基本成分
数据成分
指一种程序设计语言的数据和数据类型。数据分为常量（程序运行时不可改变）、变量（程序运行时可以改变）、全局量（存储空间在静态数据区分配）、局部量（存储空间在堆栈区分配）。数据类型有整型、字符型、单精度浮点型、双精度浮点型、布尔型、枚举类型等。
运算成分
指明允许使用的运算符及运算规则。包括算术运算、逻辑运算、关系运算、位运算等。
控制成分
指明语言允许表述的控制结构。包括顺序结构、选择结构、循环结构(初始化+循环体+循环终止条件)
传输成分
指明语言允许的数据传输方式。如赋值处理、数据的输入输出等。
函数
函数：是一段具有处理独立功能的代码块。函数使用涉及三个概念：函数定义、函数声明（先声明再使用）、函数调用。
函数调用的两种方式
传值调用：将实参的值传递给形参，形参的改变不会导致实参的改变。实参可以是合法的变量、常量或表达式。
引用调用：即传址调用，将实参的地址传递给形参，即相当于实参存储单元的地址引用，因此形参的值改变的同时，实参的值也跟着改变。实参不能为常量，只能是合法的变量和表达式。
2.2 语言处理程序基础
2.2.1 汇编程序基本原理
汇编语言是为特定的计算机或计算机系统设计的面向机器的符号化的程序设计语言
汇编程序将汇编语言所编写的源程序翻译成机器指令程序。汇编程序一般需要两次扫描源程序才能完成翻译过程。
第一次扫描：检查语法错误，确定符号名称；建立符号表；
第二次扫描：产生目标程序。
2.2.2编译程序基本原理
1. 编译程序概述
编译程序的功能是把某高级语言书写的源程序翻译成与之等价的目标程序（汇编语言或机器语言）。编程程序工作分为6个阶段，如下图所示：
词法分析：
这个阶段的任务是从左到右一个字符一个字符地扫描源程序，从而识别出一个个==“单词“符号==。
语法分析：
语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语，如“程序”，“语句”，“表达式”等等。语法分析程序判断源程序在结构上是否正确
语义分析：
语义分析的任务是结构上正确的源程序进行上下文有关性质的审查和类型审查。如类型匹配、除数不为0等。又分为静态语义错误（在编译阶段能够查找出来）和动态语义错误（只能在运行时发现）。
中间代码生成（非必须）：
中间代码是根据语义分析产生的，需要经过优化链接，最终生成可执行的目标代码。引入中间代码的目的是进行与机器无关的代码优化处理，有助于提高可移植性。常见的中间代码有后缀式（逆波兰式）、三元式（三地址码）、四元式、树和图等形式。
代码优化（非必须）：
当需要生成高效的目标代码时，就进行优化。所依据的原则是程序的等价交换原则。
目标代码生成：
把中间代码变换成特定机器上的绝对指令代码、可重定位的指令代码或汇编指令代码，这个阶段的工作与具体的机器密切相关。需要考虑三个问题（一是如何生成较短的目标代码；二是如何充分利用计算机中的寄存器，减少目标代码访问存储单元的次数；三是如何充分利用计算机指令系统的特点，以提高目标代码的质量）。
中间代码生成的后缀式
前缀表达式： +ab
中缀表达式： a+b
后缀表达式： ab+
掌握以上三种表达式即可，其实就是树的三种遍历，一般正常的表达式是中序遍历，即中缀表达式，根据其构造出一棵树，再按题目要求求出前缀表达式和后缀表达式。
后缀式即逆波兰式，是逻辑学家卢卡西维奇发明的一种表示表达式的方法。这种表达方式把运算符写在运算对象的后面，例如，把a+b写成ab+。这种表示法的有点是根据运算对象和运算符的出现次序进行计算，不需要使用括号。
后缀式简单求法：按运算的优先顺序依次将运算符写在运算对象的后面，例如，把a+b携程ab+
2.文法
描述语言语法结构的规则。一个形式文法是一个有序四元组G=（VN，VT，P，S），
其中：
VN：非终结符集合。不是语言组成部分，不是最终结果，可理解为占位符。
VT：终结符集合。是语言的组成部分，是最终结果。VN∩ VT= 空集（没有交集）
P：产生式集合。形如 α→β。用非终结符推导出终结符的规则。
S：起始符。是语言的开始符号。
终结符：最终结果，不能推导出其他元素。
非终结符：能够推导出其他元素。
产生式：即非终结符推导出终结符的公式。
3. 文法的分类
程序设计语言的绝大多数语法规则可以采用上下文无关文法进行描述
4. 正规表达式（正则表达式）
5.有限自动机
确定的有限自动机
是词法分析的工具，一个确定的有限自动机DFA是一个五元组$ M = （S，\Sigma ，f，S0，Z）$，其中：
S是一个有限集，其每个元素称为一个状态。
Σ\SigmaΣ是一个有穷字母表，其每个元素称为一个输入字符。
f是状态转换函数，为S×ΣS × \SigmaS×Σ上的单值部分映像。f（A，a） = Q 表示当前状态为A、输入为a时，将转换到下一个状态Q，称Q为A的一个后继状态。
S 0 ∈SS~0~ \in SS0∈S，是唯一的一个开始状态
z是非空的终止状态集合，其中Z⊆SZ \subseteq SZ⊆S。
不确定的优先自动机
DFA是NFA的特例；对于每一个NFA，都可以转换为DFA
如何分辨确定的有限自动机和不确定的有限自动机：输入一个字符，看是否能得出唯一的后继，若能，则是确定的有限自动机，否则就是不确定的有限自动机。
正规式与有限自动机之间的转换
6.语法分析方法
自上而下语法分析法
递归下降分析法（一种自上而下的方法）
自下而上语法分析法
移进-归约分析法（一种自下而上的方法）
2.2.3解释程序基本原理
编译和解释，都是将高级语言翻译成计算机硬件认可的机器语言加以执行。
自上而下语法分析法*
递归下降分析法（一种自上而下的方法）
自下而上语法分析法
移进-归约分析法（一种自下而上的方法）
2.2.3解释程序基本原理
编译和解释，都是将高级语言翻译成计算机硬件认可的机器语言加以执行。
[外链图片转存中…(img-K4V373ee-1777681015841)]
