[toc]
软件设计师笔记02_程序设计语言基础
下面的内容参考自《软件设计师教程(第5版)》 这本书的第2章 程序设计语言基础。
参考图如下所示 
程序语言的基本概念
低级语言和高级语言
由于计算机硬件只能识别由 0、1 组成的机器指令序列，即机器指令程序，因此机器指令是最基本的计算机语言。由于机器指令是特定的计算机系统所固有的、面向机器的语言，所以用机器语言进行程序设计时效率很低，程序的可读性很差，也难以修改和维护。
之后，人们就用容易记忆的符号代替 0、1 序列来表示机器指令。例如用 ADD 表示加法、用 SUB 表示减法等。用符号表示的指令称为汇编指令，汇编指令的集合被称为汇编语言。
汇编语言与机器语言十分接近，其书写格式在很大程度上取决于特定计算机的机器指令，因此它仍然是一种面向机器的语言。人们称机器语言和汇编语言为低级语言。
再之后，人们开发了功能更强、抽象级别更高的语言以支持程序设计，于是就产生了面向各类应用的程序设计语言，称为高级语言。常见的有 Java、C、C++、PHP、Python、Delphi、PASCAL 等。这类语言与人们使用的自然语言比较接近，提高了程序设计的效率。
小结：
- 低级语言：机器语言，汇编语言。
- 高级语言：功能更强，抽象级别更高，与人们使用的自然语言比较接近，常见的有Java，C，C++，PHP，Python，Delphi等。
编译程序和解释程序
由于计算机只能理解由 0、1 序列构成的机器语言，因此高级程序设计语言需要翻译，担负这一任务的程序称为 “语言处理程序”。语言之间的翻译形式有多种，基本方式为汇编、解释和编译。
用某种高级语言或汇编语言编写的程序称为源程序，源程序不能直接在计算机上执行。如果源程序是用汇编语言编写的，则需要一个对应的“语言处理程序”将其翻译成目标程序后才能在计算机上运行。如果源程序是用某种高级语言编写的，则需要对应的解释程序或编译程序对其进行翻译，然后在机器上运行。
- 解释程序（解释器），它或者直接解释执行源程序，或者将源程序翻译成某种中间代码后再加以执行；
- 编译程序（编译器）则是将源程序翻译成目标语言程序，然后在计算机上运行目标程序。
这两种语言处理程序的根本区别是：在编译方式下，机器上运行的是与源程序等价的目标程序，源程序和编译程序都不再参与目标程序的执行过程；而在解释方式下，解释程序和源程序都要参与到程序的运行过程中，运行程序的控制权在解释程序。
简单来说，在解释方式下，翻译源程序时不生成独立的目标程序，而编译器则将源程序翻译成独立保存的目标程序。
小结
- 编译程序是将源程序编译完之后,生成一个独立的可执行文件。然后再运行这个可执行文件。因此运行效率高。
- 解释程序不生成可执行文件，它是一边解释源程序，然后一边运行解释后的目标程序。因为解释程序一边解释一边运行，因此执行速度慢，效率低。
程序设计语言的定义
一般地，程序设计语言的定义都涉及语法、语义和语用等方面。
语法是指由程序设计语言的基本符号组成程序中的各个语法成分（包括程序）的一组规则，其中由基本字符构成的符号（单词）书写规则称为词法规则，由符号构成语法成分的规则称为语法规则。程序设计语言的语法可用形式语言进行描述。
语义是指程序设计语言中按语法规则构成的各个语法成分的含义，可分为静态语义和动态语义。静态语义指编译时可以确定的语法成分的含义，而运行时刻才能确定的含义是动态语义。一个程序的执行效果说明了该程序的语义，它取决于构成程序的各个组成部分的语义。
语言的实现则有个语境问题。语境是指理解和实现程序设计语言的环境，包括编译环境和运行环境。
- 总结：语法（一组规则）、语义（语法成分的含义）、语用（构成语言的各个记号和使用者的关系）。
程序设计语言的分类
程序设计语言基本上可以分为命令式程序设计语言、函数式程序设计语言、面向对象程序设计语言和逻辑程序设计语言。
- 命令式程序设计语言：通常所称的结构化程序设计语言属于命令式语言类。：例如Fortran,Pascal和C语言等。
- 函数式程序设计语言的代表有Lisp、ML等。
- 面向对象程序设计语言的代表有C++、Java等。它们都支持数据隐藏、数据抽象、用户定义类型、继承和多态等特性。
- 逻辑程序设计语言的代表有Prolog。
- 逻辑型程序设计语言： 逻辑型语言是一类以形式逻辑为基础的语言，其代表是建立在关系理论和一阶谓词理论基础上的 Prolog
程序设计语言的基本成分
程序设计语言的基本成分包括：数据、运算、控制、传输、函数。
数据成分
程序设计语言的数据成分包括：常量和变量，全局量和局部量，数据类型。
运算成分
程序设计语言的运算成分包括：算式运算、关系运算、逻辑运算。
控制成分
程序设计语言的控制成分包括：顺序结构、选择结构、循环结构。如图所示
传输成分
程序设计语言的传输成分是指数据传输的方式。如赋值处理，数据的输入和输出等。
函数成分
程序设计语言的函数成分包括：定义函数，声明函数，调用函数。
函数调用传值
当在一个函数中需要使用另一个函数时，称为函数调用。
函数调用分为值调用和引用调用。
值调用
值调用是指在调用函数时，将实际参数的值传递给形式参数，实参可以是变量、常量和表达式。
值调用的过程中改变形式参数的值不会影响实际参数的值。即不可以实现形参和实参之间的双向传递数据。
引用（地址）调用
引用调用是指在调用函数时，将实际参数的地址传递给形式参数，形参必须有地址，实参不能是常量（值）、表达式。
引用（地址）调用可以实现形参和实参间双向传递数据的效果，即改变形式参数的值会影响实际参数的值。
汇编程序的基本原理
汇编语言源程序
汇编语言是为特定的计算机或计算机系统设计的面向机器的符号化的程序设计语言。用汇编语言编写的程序称为汇编语言源程序。
用汇编语言编写程序要遵循所用语言的规范和约定。汇编语言源程序由若干条语句组成，一个程序中可以有三类语句：指令语句、伪指令语句和宏指令语句。
汇编程序
因为计算机不能直接识别和运行汇编语言源程序，所以要用专门的翻译程序—汇编程序进行翻译。因此汇编程序的作用是将汇编语言所编写的源程序翻译成机器指令程序。
汇编程序一般需要两次扫描源程序才能完成翻译过程。
- 第一次扫描：检查语法错误，确定符号名字；建立使用的全部符号名字表；每一符号名字后跟一个对应值（地址或数）。
- 第二次扫描：在第一次扫描的基础上，将符号地址转换成真地址（代真）；利用操作码表将助记符转换成相应的目标码。
编译程序的基本原理
编译过程概述
编译程序的功能是把某高级语言书写的源程序翻译成与之等价的目标程序（汇编语言或机器语言），从而让机器运行目标程序。
编译程序的工作过程可以分为 6 个阶段，如图所示，在实际的编译器中可能会将其中的某些阶段结合在一起进行处理。
词法分析
词法分析阶段是编译过程的第一个阶段，这个阶段的任务是对源程序从前到后（从左到右）逐个字符地扫描，从中识别出一个个“单词”符号（记号），并分析一个个符号是否符合程序语言的规定。
- 输入：源程序。
- 输出：记号流。
正规式
正规文法，表示的语言集合是正规集，正规集的规律可以用正规式表示。
有限自动机
有限自动机是词法分析的一个工具，它能正确地识别正规集。
如图所示 
主要有五个符号集，由上图示例，可知用状态来表示十分清晰，由s输入一个0，可得出B，依次类推.
一般考试，给出一个状态图，问能否构造出001这样的字符串，解决方法就是从起始s到终点f之间是否有一条路，权值为001。本质就是有向图从起点到终点的遍历。
- 确定的有限自动机(DFA):对每一个状态来说识别字符后转移的状态是唯一的
- 不确定的有限自动机(NFA):对每一个状态来说识别字符后转移的状态是不唯一的
确定的有限自动机和不确定的有限自动机的区别
输入一个字符，看是否能得出唯一的后继，若能，则是确定的有限自动机。否则若得出多个后继，则是不确定的有限自动机。
语法分析
语法分析阶段是编译过程的第二个阶段，这个阶段的任务是在词法分析的基础上，根据语法规则将一个个单词符号分解成各个语法单位，如“表达式”“语句”等,并分析是否符合语法规则。
- 输入：记号流。
- 输出：语法树(分析树)。
- 主要作用是对各条语句的结构进行合法性分析分析程序中的句子结构是否正确。可以发现程序中所有的语法错误。
常见语法错误如下
单词拼写错误、标点符号错误、表达式中缺少操作数、括号不匹配等语法结构上的错误。
语法分析的几种方法
- 自上而下语法分析：最左推导，从左至右。给定文法G和源程序串r。从G的开始符号s出发，通过反复使用产生式对句型中的非终结符进行替换(推导)，逐步推导出r。
- 递归下降思想：原理是利用函数之间的递归调用模拟语法树自上而下的构造过程，是一种自上而下的语法分析方法。
- 自下而上语法分析：最右推导，从右至左。从给定的输入串r开始，不断寻找子串与文法G中某个产生式P的候选式进行匹配，并用P的左部代替(归约)之，逐步归约到开始符号S。
- 移进-规约思想：设置一个栈，将输入符号逐个移进栈中，栈顶形成某产生式的右部时，就用左部去代替，称为归约。很明显，这个思想是通过右部来推导出左部，因此是自下而上语法分析的核心思想。
语义分析
语义分析阶段是编译过程的第三个阶段，这个阶段的任务是根据语法分析的结果，分析各个表达式，各个语句。检查是否包含静态语义错误,不能发现程序中所有的语义错误。
- 输入：语法树
- 语义分析阶段可以发现静态语义错误，不能发现动态语义错误。动态语义错误只有运行时才能发现。有语义错误是可以编译成功的，例如a/0；这是符合语法的，也符合静态语义，编译器检验不出来这个是错的，只有运行才会报错，也就是动态语义，动态语义错误常见的有死循环。
什么是静态语义错误和动态语义错误？
静态语义错误：一般是指运算符与运算对象类型不合法等错误。
动态语义错误：程序运行时产生的语义错误，也叫动态语义错误。包括死循环、变量取零时做除数、引用数组元素下标越界等错误。
中间代码生成
中间代码生成阶段是编译过程的第四个阶段。此阶段与具体机器无关。根据语义分析的结果，将源程序转换为一种中间表示形式。
例如将源程序 “int a = 5 + 3;” 转换为中间代码形式可能是 “t1 = 5 + 3; a = t1;” 利于后续处理。
代码优化
代码优化阶段是编译过程的第五个阶段。
此阶段的任务是对中间代码进行等价变换，旨在提高目标代码的运行效率，减少运行时间和空间开销。
目标代码生成
目标代码生成阶段是编译过程的第六个阶段。
此阶段与具体机器硬件紧密相关。把中间代码转换为特定机器上的代码。例如将中间代码转换为 x86 架构下的机器指令，让程序能在对应硬件上运行。
符号表管理
符号表的作用是记录源程序中各个符号的必要信息，以辅助语义的正确性检查和代码生成，在编译过程中需要对符号表进行快速有效地査找、插入、修改和删除等操作。
符号表的建立可以始于词法分析阶段，也可以放到语法分析和语义分析阶段，但符号表的使用有时会延续到目标代码的运行阶段。
解释程序的基本原理
解释程序是另一种语言处理程序，在词法、语法和语义分析方面与编译程序的工作原理基本相同，但是在运行用户程序时，它直接执行源程序或源程序的内部形式。
因此，解释程序不产生源程序的目标程序，这是它和编译程序的主要区别。
解释过程
如图是解释程序实现高级语言的三种方式
解释过程直接执行源程序（词法分析、语法分析、语义分析过程是有的，但是没有中间代码生成，也没有目标机器码代码），其最大的特点是不产生目标程序代码，并且程序每执行一次就要解释一次，因此运行效率低。
编译过程和解释过程的区别
- 编译方式：词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成。
- 解释方式：词法分析、语法分析、语义分析。
文法
一般的程序设计语言属于上下文无关文法。
表达式
在考试当中，该知识点的考查，通常形式是给出一个表达式的中缀表达形式（或前缀、后缀），让考生将其转换为前缀或后缀表达形式。
中缀表达式
中缀表达式：运算符位于操作数中间，是人们常用的算术表示方法，如 “(3 + 4) × 5 - 6”。
前缀表达式
前缀表达式：运算符位于操作数之前，也称为波兰式。如 “- × + 3 4 5 6” 是前缀表达式，等价于中缀表达式 “(3 + 4) × 5 - 6”。
后缀表达式
后缀表达式：运算符位于操作数之后，也称为逆波兰式。如 “3 4 + 5 × 6 -” 是后缀表达式，等价于中缀表达式 “(3 + 4) × 5 - 6”。