第二章程序设计语言设计

编译原理。在上午考，一般3分。

语言设计概述

描述计算过程。

低级语言：机器语言（机器码 01）、汇编（用符号替换01）等。

高级语言：功能更加强大，抽象级别高，接近人类的语言。

常见语言特点：

基本成分

1、数据成分：语言中的数据类型。

2、运算成分；语言中的逻辑运算和算术运算。

3、控制成分：语言中运行表示控制的结构。包括顺序、选择（if switch）、循环(while & for)

4、传输成分；数据传输的方式。赋值

5、函数：具有独立功能的代码块。函数定义、声明和使用。传值调用(传变量 值)和引用调用（传指针地址，引用等）

汇编基础

汇编语言是为特定计算机设计的面向机器的符号化的语言。

汇编程序-->机器程序。需要扫描两次才会完成这个过程。第一次检测语法错误，确定符号名字，建立符号表。第二次将程序翻译成机器码。

编译程序的基本原理

将高级语言翻译为低级语言。翻译的过程有6个阶段。如下图：

1、词法分析；从左向右扫描程序，识别出单词符号（记号）。（这个过程很像分词）

2、语法分析：在1的基础上将单词序列组合成各类语法短语。主要作用是判断源程序在结构上是否正确，比如括号缺失的。

3、语义分析；类型审查和上下文有关的性质审查 。如类型匹配。可分为静态语义错误（在编译阶段能够查找出来的）和动态语义错误（在运行时发现，如死循环）

4、中间代码生成（非必须）；目的是进行与机器无关的代码优化，有助于提高移植性。常见中间代码后缀式（逆波兰式）、三元式（三地址码）、四元式、树和图等。

5、代码优化（非必须）；程序的等价变换原则

6、目标代码生成：把中间代码编程特定机器的代码，与具体的机器相关。考虑最小化、充分利用存储等，高效。

中间代码生成的后缀式

根据语法树，进行遍历得到前中后缀表达式。题目中树的遍历技巧在结点一次标注123，依次画一圈，圈先经过的标注为前中后遍历的顺序。

注意：左右值的摆法顺序不可以乱。

考察方式将中缀表达式转换后缀表达式。（数据结构中也有类似的考法）

语言处理程序基础

编译的基本原理

文法

描述语言的语法结构的规则即文法。一个文法的形式是一个有序四元组$G=(V_N,V_T,P,S)$。

$V_N$；非终结符集。不是语言的组成部分，不是最终结果，可以是占位符。

$V_N$；；终结符集合。是语言的组成部分，是最终结果。$V_N\cap V_T=\varnothing$

$P$；产生式集合。$\alpha \to \beta$，用非终结符号推导出终结符规则。

$S$；起始符。是语言开始的符号。

终结符：最终结果，不能推导出其他元素，一般是0|1。

非终结符号：能推导出其他元素。

产生式：即非终结符推导出终结符的公式。

考法：给出文法，推导字符串，根据过程代入消除非终结符。

文法分类

大部分的语言的上下文无关文法，语法是上下文无关，但语义是上下有关的。

闭包

正则闭包：所幂的集合。

闭包；在正则闭包加上0次幂即空集$A^0=\{\epsilon \}$

正规式和正规集

用于语法分析中，对于字母表。

正规式

有限自动机

识别和表示正规集，是一个词法分析工具。

确定的有限自动机DFA；五元组$M=(S,{\displaystyle \sum ,f,S_0,Z)}$。S是有限集合，元素的状态。${\displaystyle \sum }$ 是有限的字母表。f是状态转换函数，如$f(A,a)=Q$，当输入a时当前状态A转换为Q（后继状态），当后继状态多个时，该状态机为不确定的有限自动机(NFA)。$S_0$唯一的开始状态。Z时终止态的集合。

实例：图中的终止状态中可以用(a*)表示转换方程的输入。

语法分析方法

自上而下分析法和递归下降分析法；从左向右上跟上述的文法推导一样。后者是理工函数递归模拟语法树的自上而下的分析法。

自下而上分析法和移进-归约分析法**；最右推导，是从右边推导到左边。

解释的基本原理

编译和解释的区别

编译和解释都是将高级语言翻译成计算机硬件可执行的机器语言并加以执行的过程。