程序设计语言
编译与解释
语言处理程序分为三类：（考点）
汇编程序、编译程序、解释程序
汇编程序：将汇编语言多编写的源程序翻译成机器指令程序
编译程序：将源程序翻译成目标语言程序，再运行目标程序
解释程序：直接解释执行源程序/翻译成某种中间表示形式后再执行
编译程序生成独立的可执行文件，直接运行，运行时无法控制源程序，效率高。
解释程序不生成可执行文件，可以逐条解释执行，用于调试模式，可以控制源程序，因为还需要控制程序，因此执行速度慢，效率低。
共同点：将高级语言翻译成目标程序执行。
各程序语言的设计特点：（考点）
命令式程序设计语言：
Fortran语言（科学计算，执行效率高）
Pascal语言（为教学而开发的，表达能力强，Delphi）
C语言（指针操作能力强，可以开发系统级软件，高效。）
函数式程序设计语言
Lisp语言（函数式程序语言，符号处理，人工智能）
面向对象的程序设计语言
C++语言（面向对象，高效）
Java语言（面向对象，中间代码，跨平台）
C#语言（面向对象，中间代码，.net）
逻辑型程序设计语言
Prolog语言（是逻辑型程序设计语言，数据库和专家系统）
程序设计语言定义三要素：
语法：由程序设计语言的基本符号组成程序中的各个语法成分（包括程序）的一组规则，其中由基本字符构成的符号（单词）书写规则称为词法规则，由符号构成语法成分的规则称为语法规则。
语义：语法成分的含义，可分为静态语义和动态语义。静态语义指编译时可以确定的语法成分的含义，而运行时刻才能确定的含义是动态语义。
语用： 表示了构成语言的各个记号和使用者的关系，涉及符号的来源、使用和影响。
程序设计语言的基本成分(考点：基本成分)
- 数据成分：指一种程序设计语言数据和数据类型，数据分为常量（程序运行时不可改变），变量（程序运行可以改变），全局变量（存储空间在静态数据区分配），局部变量（存储空间在堆栈区分配）。数据类型有整型，字符型，双精度浮点型，单精度浮点型，布尔型等。
- 运算成分：指明允许使用的运算符号及运算规则。包括算术运算，逻辑运算，关系运算，位运算等。
- 控制成分：指明语言允许表述的控制结构。包括顺序结构，选择结构，循环结构，（考点）
- 传输成分：指明语言允许的数据传输方式。如赋值处理，数据的输入输出等。
函数： 值调用：将实参的值—->形参，形参的改变不会导致调用点所传实参的值改变。实参可以是变量，常量和表达式。
引用调用：将实参的地址—->形参，因此其值改变的同时就改变的实参的值。实参的值不能为常量，只能是合法的变量或表达式。
程序运行时的用户内存空间一般划分为：
代码区，静态数据区，栈区，堆区
栈区和堆区也称为动态数据区
(考点)
若C程序的表达式中引用了未赋初值的变量，则（可以通过编译并运行，但运行结果不一定是期望的结果）
编译器处理过程
编译程序的功能：把高级语言源程序 编译 目标程序（汇编语言和机器语言）。
要不断收集、记录和使用源程序中一些相关符号的类型和特征等信息，并将其存入符号表中。这些信息一般以表格形式存储于系统中（考点）
高级语言程序翻译为机器语言程序，需要依次进行
词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等阶段，中间代码生成和代码优化非必须。
（考点：顺序和内容）
词法分析（词汇检查）：这个阶段的任务是从左到右一个一个字符地读入源程序，即対构成源程序的字符流进行扫描然后根据构词规则识别单词，针对词汇的检查（也称单词符号或符号）
语法分析（结构检查）：是编译过程的一个逻辑阶段。语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语，如“程序”、“语句”、“表达式”等等，语法分析程序判断源程序在结构上是否正确，合法。（考点）
语义分析（句子含义检查）：是编译过程的一个逻辑阶段，语义分析的任务是对结构上正确的源程序进行上下文有关性质的审查。如类型匹配、除法除数不为0等。有分为静态语义错误（在编译阶段能够查找出来）和动态语义错误（只能在运行时发现）
静态语义分析方法是语法制导翻译。（考点）
中间代码和目标代码生成：中间代码是根据语义分析产生的，需要经过优化链接，最终生成可执行的目标代码。
引入中间代码的目的是进行与机器无关的代码优化处理。
常用的中间代码有后缀式（逆波兰式）、三元式（三地址码）、四元式、图和树等形式。
中间代码有利于进行与机器无关的优化处理
主要掌握上述三种表达式即可，其实就是树的三种遍历，一般正常的表达式是中序遍历，即中缀表达式，根据其构造出树，再按题目要求求出前缀或后缀式。
简单求法：后缀表达式是从左往右开始，先把表达式加上括号，再依次把运算符加到本层次的括号后面。
- 编译过程中为变量分配存储单元所用的地址是逻辑地址，程序运行时再映射为物理地址。
- 标记语言常用于描述格式化和链接 脚本语言采用解释方式实现 编译型语言的执行效率更高
- 程序中的错误分为语法错误和语义错误，语法分析不能发现语义错误。
- 编译时发现的语义错误称为静态的语义错误。运行时陷入死循环属于动态语义错误。
文法
文法的定义：描述语言的语法结构的形式规则称为文法。文法G是一个四元组，可表示为G= (V,T, P,S)，其中:
V:非终结符，不是语言组成部分，不是最终结果，可以推导出其他元素。
T:终结符，是语言的组成部分，是最终结果，不能再推导其他元素。
S:起始符，是语言的开始符号。
P:产生式，用终结符代替非终结符的规则，例如a->b。
乔姆斯基(Chomsky)把文法分成4种类型，即0型、1型、2型和3型。
0型文法也称为短语文法，其功能相当于图灵机，任何0型语言都是递归可枚举的;反之，递归可枚举集也必定是一个0型语言。
1型文法也称为上下文有关文法，这种文法意味着对非终结符的替换必须考虑上下文，并且一般不允许替换成e串。例如，若αAB→avβ是1型文法的产生式，α和β不全为空，则非终结符A只有在左边是α，右边是β的上下文中才能替换成γ。
2型文法就是上下文无关文法，非终结符的替换无须考虑上下文。程序设计语言中的大部分语法都是上下文无关文法，当然语义上是相关的，要注意区分语法和语义。
3型文法等价于正规式，因此也被称为正规文法或线性文法。
正规式regular expression
- 语言中具有独立含义的最小语法单位是符号（单词），如标识符、无符号常数与界限符等。词法分析的任务是把构成源程序的字符串转换成单词符号序列。
- 词法规则可用3型文法（正规文法)或正规表达式描述，它产生的集合是语言规定的基本字符集(字母表)上的字符串的一个子集，称为正规集。
(1)选择 取并集.符号:|. 比如两个字符串集合R和S的选择操作,记作R|S.
(2)连接 字符串之间的拼接.两个字符串集合R和S的连接为RS.
(3)闭包 符号:* 字符串集合R的闭包R*是指把R与自身连接零次或者多次形成的所有集合的并集.
由这几个简单的操作可以得到我们平常接触的正则表达式的所有扩展
运算的优先级从高到低顺序排列为“*” “·” “I”。设∑={a, b}，下表列出了∑上的一些正规式和相应的正规集。
有限自动机
有限自动机是一种识别装置的抽象概念，它能准确地识别正规集。有限自动机分为确定的有限自动机和不确定的有限自动机两类。
确定的有限自动机(DFA)
一个确定的有限自动机是个五元组(S，∑，f，s0，z)，其中:
s是一个有限集，其每个元素称为一个状态。
∑是一个有穷字母表，其每个元素称为一个输入字符。
f是S×∑ -> S上的单值部分映像。
f(A, a)=Q表示当前状态为A、输入为a时，将转换到下一状态Q。称Q为A的一个后继状态。
S∈S，是唯一的一个开始状态。
z是非空的终止状态集合，Z⊆S。
一个DFA可以用两个直观的方式表示：状态转换图、状态转换矩阵。
状态转换图是一个有向图，简称转换图。例如：（s0为初态、s3为终态）
不确定的有限自动机(NFA)
一个不确定的有限自动机也是一个五元组，它与确定有限自动机的区别如下:
- f是S×∑ -> S上的映像。对于S中的一个给定状态及输入符号，返回一个状态的集合。即当前状态的后继状态不一定是唯一的。
- 有向弧上的标记可以是ε。
- DFA是NFA的特例。
确定的有限自动机和不确定的有限自动机:输入一个字符，看是否能得出唯一的后继，若能，则是确定的，否则若得出多个后继，则是不确定的。
自上而下语法分析:最左推导，从左至右。给定文法G和源程序串r。从G的开始符号s出发，通过反复使用产生式对句型中的非终结符进行替换(推导)，逐步推导出r。
递归下降思想:原理是利用函数之间的递归调用模拟语法树自上而下的构造过程,是一种自上而下的语法分析方法。
自下而上语法分析:最右推导，从右至左。从给定的输入串r开始，不断寻找子串与文法G中某个产生式P的候选式进行匹配，并用P的左部代替(归约)之，逐步归约到开始符号s.
移进-规约思想:设置一个栈，将输入符号逐个移进栈中，栈顶形成某产生式的右部时，就用左部去代替，称为归约。很明显，这个思想是通过右部来推导出左部，因此是自下而上语法分析的核心思想。