软件设计师教程—— 第二章 程序设计语言基础知识（上）
前言
在竞争激烈的就业市场中，证书是大学生求职的重要加分项。中级软件设计师证书专业性强、认可度高，是计算机相关专业学生考证的热门选择，既能检验专业知识，又有助于职业发展。本教程将聚焦核心重点，以点带面构建知识体系，秉持“以考促学”理念，助力大家高效备考、顺利通关。
目录
前言
1.程序语言基本概念
1.低级语言和高级语言
(1)低级语言
(2)高级语言
2.编译程序和解释程序
3.程序的执行方式
2.编译系统基本原理
编译程序的工作过程
1)词法分析阶段
(1)状态转换图
(2)状态转换图的表示习惯
(3)正规表达式与正规集（定义和运算）
正规式与正规集的递归定义：
正规式定义中
(4)初始/终止/后继状态
(5)确定有限自动机（DFA）
2）语法分析阶段
3）语义分析阶段
4）中间代码生成阶段
5）代码优化阶段
6）目标代码生成阶段
3.程序语言的控制结构
1.表达式
1.程序语言基本概念
1.低级语言和高级语言
(1)低级语言
机器语言和汇编语言称为低级语言
1)机器语言指0、1组成的机器指令序列
2)汇编语言指用符号表示指令的语言
MOV AX,2
MOV BX,3
ADD AX,BX
(2)高级语言
高级语言是从人类的逻辑思维角度出发、面向各类应用的程序语言，抽象程度大大提高，需要编译成特定机器上的目标代码才能执行。这类语言与人们使用的自然语言比较接近，大大提高了程序设计的效率。
2.编译程序和解释程序
高级语言或汇编语言编写的程序称为源程序，源程序不能直接在计算机执行
(1)如果源程序是汇编语言编写的，则需要一个称为汇编程序的翻译程序将其翻译成目标程序，然后才能执行
(2)如果源程序是为高级语言时，这个翻译程序称为编译程序
(3)按源程序中语句的执行顺序，逐条翻译并立即执行相关功能的处理程序、称为解释程序
3.程序的执行方式
1.编译执行：按编译的方式在计算机上执行用高级语言编写的程序，需经过两个阶段：
编译阶段，把源程序翻译成目标程序；
运行阶段，真正执行此目标程序
(1)优点：执行效率高、占用资源小
(2)缺点：兼容性差
2.解释执行：源程序的每个语句一经解释就立即执行
(1)优点：可移植性较好、开发速度较快、与用户通信方便
(2)缺点：效率低
2.编译系统基本原理
编译程序的工作过程
可以分为6个阶段
词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成
1)词法分析阶段
输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词，删掉无用信息，报告分析时的错误。
一个程序语言的基本语法符号分为五类：关键字、标识符、常量、运算符、界符等
词法分析器所输出单词符号常常表示成如下的二元式：
(单词种别，单词符号的属性值)
描述词法规则通常用：正规式和有限自动机
(1)状态转换图
状态转换图是状态有限的有向图，用圆圈表示结点状态，结点之间有向边代表状态转换，有向边上
可标记字符，表示前一状态接受某一个字符之后的状态转移。
下图表示在状态i下的状态转换：
若输入字符为x，则读入x并转换到状态j；
若输入字符为y，则读入y并转换到状态k。
(2)状态转换图的表示习惯
(3)正规表达式与正规集（定义和运算）
状态转换图可以构造词法分析程序，但属于非形式化描述正规表达式（简称正规式）是词法分析的
形式化表示方法。所谓形式化的方法，是指用一整套带有严格规定的符号体系来描述问题的方法。
优点：更加清晰和准确
正规式与正规集的递归定义：
正规式定义中
“|" 读为"或"
"·” 读为“连接”
"*" 读为“闭包”（即，任意有限次的自重复连接）。
(4)初始/终止/后继状态
初始状态
终止状态(接收状态):
后继状态：有限状态机在读入一个字符时，其状态改变为另一状态，则改变后的状态被称为后继状
态。
如果有限状态机每次转换后的状态是唯一的则称之为确定有限状态自动机(DFA)；如果转换后的后
继状态不是唯一的则称之为不确定有限自动机(NFA)
(5)确定有限自动机（DFA）
2）语法分析阶段
语法分析器以单词符号作为输入，分析单词符号串是否形成符合语法规则的语法单位，如表达式、
赋值、循环等，
按语法规则分析检查每条语句是否有正确的逻辑结构。
int arr[2],b;
b=arr * 10;
语法分析的方法：
(1)自上而下分析法
(2)自下而上分析法
3）语义分析阶段
语义分析阶段主要是检查源程序是否存在语义错误，并收集类型信息供后面的代码生成阶段使用，
只有语法和语义都正确的源程序才能翻译成正确的目标代码。
语义分析的主要工作是进行各类型分析和检查。赋值语句的右端和左端的类型不匹配。表达式的除
数是否为零等。
int arr[2],b;
b= arr * 10;
4）中间代码生成阶段
中间代码生成阶段的工作是根据语义分析的输出生成中间代码。
(1)中间代码是一种简单且含义明确的记号系统，可以有若干种形式，常见的有逆波兰记号、四元
式、三元式和树。
(2)他们的共同特征是代码的方式与具体的机器无关。
5）代码优化阶段
代码优化阶段是对前阶段产生的中间代码进行变换或进行改造，目的是使生成的目标代码更为高
级，即省时间和省空间。
6）目标代码生成阶段
是把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。这是编译
的最后阶段，它的工作与硬件系统的结构和指令的含义有关。
3.程序语言的控制结构
1.表达式
前缀表达式：也被称为波兰表示法，其特点是将操作符置于操作数之前，如：-×+3456。
中缀表达式：即我们常用的表示方法，(3+4)× 5-6。
后缀表达式：又被称为逆波兰法，其特点是将操作符置于操作数之后，34+5×6-。