程序设计语言
程序设计语言基本概念
- 低级语言
a. 计算机硬件只能识别由0、1组成的机器指令序列，即机器指令程序，因此机器指令是最基本的计算机语言。
b. 人们用容易记忆的符号代替0、1序列来表示机器指令，例如：用ADD表示加法、用SUB表示减法等。用符号表示的指令称为汇编指令，汇编指令的集合被称为汇编语言。汇编语言仍然是一种面向机器的语言。
c. 机器语言和汇编语言都为低级语言。 - 高级语言：人们开发了功能更强、抽象级别更高的语言以支持程序设计，于是就产生了面向各类应用的程序设计语言，称为高级语言。常见的有：Java、C、C++、PHP、Python、Delphi、PASCAL等。
编译程序和解释程序
计算机只能理解由0、1构成的机器语言，因此高级程序设计语言需要翻译，担负这一任务的程序称为“语言处理程序”。语言之间的翻译形式由多种，基本方式为汇编、解释和编译。
用某种高级语言或汇编语言编写的程序称为源程序，源程序不能直接在计算机上执行。如果源程序是用汇编语言编写的，则需要一个汇编程序将其翻译成目标程序后才能执行。如果源程序是用某种高级语言编写的，则需要对应的解释程序或编译程序对其进行翻译，然后机器上运行。
- 解释程序（解释器）
。翻译源程序时不产生独立的目标程序。
。解释程序和源程序要参与到程序的运行过程中。 - 编译程序（编译器）
。翻译时将源程序翻译成独立保存的目标程序。
。机器上运行的是与源程序等价的目标程序，源程序和编译程序都不再参与目标程序的运行过程。 - 解释器和编译器在处理源程序时都会进行优化。
- 许多程序设计语言规定，程序中的数据必须具有类型，其作用是：
。便于为数据合理分配存储单元
。便于对参与表达式计算的数据对象进行检查
。便于规定数据对象的取值范围及能够进行的运算
程序设计语言的控制成分
- 顺序结构
- 选择结构
- 循环结构（重复结构）
C
程序设计语言基本成分
函数定义
函数的定义包括两部分：函数首部和函数体。函数的定义描述了函数做什么和怎么做。
函数定义的一般形式为
- 值调用。若实现函数调用时将实参的值传递给相应的形参，则称为是传值调用。在这种方式下形参不能向实参传递信息。
- 引用调用。引用是C++中引入的概念，当形式参数为引用类型时，形参名实际上时实参别名，函数中对形参的访问和修改实际上就是针对相应实参所做的访问和改变。
- 传值调用：将实参的值传递给形参，实参可以时变量、常量和表达式。不可以实现形参和实参间双向传递数据的效果。
- 传引用（地址）调用：将实参的地址传递给形参，形参必须有地址，实参不能时常量（值）、表示式。可以实现形参和实参间双向传递数据的效果，即改变形参的值的同时也改变了实参的值。
编译、解释程序翻译阶段
- 编译方式：词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成
- 解释方式：词法分析、语法分析、语义分析
- 编译器和解释器都不可省略词法分析、语法分析、语义分析且顺序不可交换。即词法分析、语法分析、语义分析是必须的
- 编译器方式中中间代码生成和代码优化不是必要，可省略
- 即编译器方式可以在词法分析、语法分析、语义分析阶段后直接生成目标代码
符号表
不断收集、记录和使用源程序中一些相关符号的类型和特征信息，并将其存入符号表中。记录源程序中各个字符的必要信息，以辅助语义的正确性检查和代码生成。
编译过程概述
- 词法分析
a. 输入：源程序
b. 输出：记号流
c. 词法分析阶段的主要作用是：分析构成程序的字符及由字符按照构造规则构成的符号，是否符合程序语言的规定。 - 语法分析
a. 输入：记号流
b. 输出：语法树（分析树）
c. 语法分析阶段的主要作用是：对各条语句的结构进行合法性分析，分析程序中的句子结构是否正确。
d. 语法分析阶段可以发现程序中所有的语法错误 - 语义分析
a. 输入：语法树
b. 语义分析阶段的主要作用是进行类型分析和检查
c. 语义分析阶段不能发现程序中所有的语义错误
d. 语义分析阶段可以发现静态语义错误，不能发现动态语义错误，动态语义错误运行时才能发现（eg：除数为0时只能在运行阶段检查出来，死循环） - 中间代码生成
a. 常见的中间代码有：后缀式、三地址码、三元式、四元式和树（图）等形式。
b. 中间代码与具体的机器无关（不依赖具体的机器），可以将不同的高级程序语言翻译成同一种中间代码
c. 中间代码可以跨平台
d. 因为与具体的机器无关，使用中间代码有利于进行与机器无关的优化处理和提高编译程序的可移植性 - 目标代码生成
a. 目标代码生成阶段的工作与具体的机器密切相关
b. 寄存器的分配工作处于目标代码生成阶段
正规式
词法分析的一个工具
A
D（注意题目式所有字符串）
有限自动机
- 有限自动机是词法分析的一个工具，它能正确地识别正规集
- 确定的有限自动机（DFA）：对每一个状态来说识别字符后转移的状态是唯一的
- 不确定的有限自动机（NFA）：对每一个状态来说识别字符后转移的状态是不唯一的
上下文无关文法
- 程序设计语言的绝大多数语法规则可以采用上下文无关文法进行描述
- 上下文无关文法属于乔姆斯基定义的2型文法。
中缀后缀表达式
中缀式：a ? b ==>后缀式：ab?
后缀式转中缀式可以用：栈
中间代码有多种形式，其中树与后缀表示形式适用于解释器，而编译器多采用与机器指令格式较接近的四元形式。
根据生成的语法树，按照不同的方式遍历一遍即可生成形式不同的表达式：
- 中缀表达式：中序遍历（左-根-右）
- 后缀表达式：后序遍历（左-右-根）
逆波兰式就是后缀式
