软件设计师笔记-第二章-程序设计语言基础知识_语法分析主要任务是根据程序设计语言的语法规则将词法分析产生的单词符号串构

第二章-程序设计语言基础知识

2.1 编译过程

​ 编译程序的工作，从输入源程序开始到输出目标程序为止的整个过程，是非常复杂的。但就其过程而言，它与人们进行自然语言直接的翻译有许多相近之处。当我们把一种文字翻译为另一种文字，例如把一段英文翻译为中文时，通常需经下列步骤：

（1）识别出句子中的一个个单词；

（2）分析句子的语法结构；

（3）根据句子的含义进行初步翻译；

（4）对译文进行修饰；

（5）写出最后的译文。

​ 类似地，编译程序的工作过程一般也可以划分为五个阶段：词法分析、语法分析、语义分析与中间代码产生、优化、目标代码生成。

1. 第一阶段：词法分析

词法分析的任务是：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词（亦称单词符号或简称符号），如基本字（begin、end、if、for、while），标识符、常数、运算符和界符（标点符号、左右括号）。

单词符号是语言的基本组成成分，是人们理解和编写程序的基本要素。识别和理解这些要素无疑也是翻译的基础。如同将英文翻译成中文的情形一样，如果你对英语单词不理解，那就谈不上进行正确的翻译。在词法分析阶段的工作中所依循的是语言的词法规则（或称构词规则）。描述词法规则的有效工具是正规式和有效自动机。

2. 第二阶段：语法分析

语法分析的任务是：在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位（语法范畴），如“短语”、“句子”、“程序段”和“程序”等。

通过语法分析，确定整个输入串是否构成语法上正确的“程序”。语法分析所依循的是语言的语法规则。语法规则通常用上下文无关文法描述。词法分析是一种线性分析，而语法分析是一种层次结构分析。例如：

Z = X + 0.618 * Y;

代表一个“赋值语句”，而其中的X + 0.618 * Y 代表一个“算术表达式”。因而，语法分析的任务就是识别X + 0.618 * Y为算术表达式，同时，十倍上述整个符号串属于赋值语句这个范畴。

3. 第三阶段:词义分析与中间代码产生

这一阶段的任务是：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。

这一阶段通常包含两个方面的工作。首先，对每种语法范畴进行语义i安插，例如，变量是否定义、类型是否正确等等。如果语义正确，

则进行另一方面工作，即进行中间代码的解释。这一阶段所依循的是语言的语义规则。通常使用属性文法描述语义规则。

“翻译”仅仅在这里才开始涉及到。所谓“中间代码”是一种含义明确、便于处理的记号系统，它通常独立于具体的硬件。这种记号系统或者与现代计算机的指令形式有某种程度的接近，或者能够比较容易地把它变换成现代计算机的机器指令。

3.1 中间代码形式的分类

例如，许多编译程序采用了一种与“三地址指令”非常近似的“四元式”作为中间代码。这种寺院是的形式是：

它的意义是：对“左右操作数”进行某种运算（由“算符”指明），把运算所得的值作为“结果”保留下来。在采用四元式作为中间代码的情形下，中间代码产生的任务就是按语言的语法规则把各类范畴翻译成四元式序列。例如，下面的赋值语句

Z = (X + 0.418) * Y / W;

可被翻译为如下的四元式序列：

其中，T1和T2是编译期间引进的临时工作变量；第一个四元式意味着把X的值加上0.418存放在T1中；第二个四元式值将T1的值和Y的值相乘存于T2中；第三个四元式指将T2的值除以Y的值留结果于Z中。

一般而言，中间代码是一种独立于具体硬件的记号系统。

4. 第四阶段：优化

优化的任务在于对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效（省时间和空间）的目标代码。

优化的主要方面有：公关子表达式的提取、循环优化、删除无用代码等等。有时，为了便于“并行运算”，还可以对代码进行并行化处理。优化所依循的原则是程序的等价变换规则。

5. 第五阶段：目标代码生成

这一阶段的任务是：把中间代码（或经优化处理之后）变换成特定机器上的低级语言代码。

这阶段实现了最后的翻译，它的工作有赖于硬件系统结构和机器指令含义。这阶段工作非常复杂，设计到硬件系统功能部件的运用，机器指令的选择，各种数据类型变量的存储空间分配，以及寄存器和后援寄存器的调度，等等。

目标代码的形式可以是绝对指令代码或可重定位的指令代码或汇编指令代码。如目标代码是绝对指令代码，则这种目标代码可立即执行。如果目标代码是汇编指令代码，则需汇编器汇编之后才行运行。必须指出，现在多数实用编译程序所产生的目标代码都是一种可重定位的指令代码。这种目标代码在运行前必须借助于一个连接装配程序把各个目标模块（包括系统提供的库函数）连接在一起，确定程序变量（或常数）在主存中的位置，装入内存中指定的起始地址，使之成为一个可以运行的绝对指令代码程序。

2.1.1 文法的定义以及语法推导树

1. 文法的定义

2. 文法的分类

3. 语法推断树

2.1.2 有限自动机与正规式

• 优先自动机的格式

  

1. 有限自动机与状态图

• 有限状态自动机可以形象地用状态转换图表示，以下为展示例子：

  

  • 状态图的用法：

  问S到终点的路径，用路径上的0或1来代表路径线

  如01就是一个终点路径。

示例：

解析：

A：0 “A->B” 0 “B->B” 0 “B->B” 0 “B->B”

C: 0 “A->B” 1 “B->C” 0 “C->B” 1 “B->C”，最终到了终态，所以选C。

2. 正规式

示例：

解析：

（1）：对A选项分析，S->aA,aA->abS->abaA->ababS->ababaA-ababab。如A选项分析，可得D 选项无法识别。

（2）：A选项可以实现（1）的A，B，C三种情况，但待定，因为它太广泛，

​ B选项无法实现（1）的B情况

​ C选项完美契合（1）的A，B，C三种情况，选 C。

2.2 表达式

1. 表达式分类

示例：

解析：

• 根据构造出来的树，来进行树的后序遍历可得结果为 D。

2.3 函数调用-传值与传址

2.4 各种程序语言的特点