编译原理引论概要.ppt

第二阶段，语法分析 语法分析的任务是： 在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位（语法范畴），如“短语”、“子句”、“语句”、“程序段”和“程序”等。通过语法分析，确定整个输入串是否构成语法上正确的“程序”。 语法分析所依循的是语言的语法规则。语法规则通常用上下文无关文法描述。词法分析是一种线性分析，而语法分析是一种层次结构分析。 例如，在很多语言中，符号串 z:=X十0.618*Y 代表一个“赋值语句”，而其中的 X＋0.618*Y代表一个“算术表达式”。因而，语法分析的任务就是识别 X＋0.618*Y为算术表达式，同时，识别上述整个符号串属于赋值语句这个范畴。 第三阶段，语义分析与中间代码产生 这一阶段的任务是： 对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。 “翻译”仅仅在这里才开始涉及到。所谓“中间代码”是一种含义明确、便于处理的记号系统，它通常独立于具体的硬件。这种记号系统或者与现代计算机的指令形式有某种程度的接近，或者能够比较容易地把它变换成现代计算机的机器指令。 例如，许多编译程序采用了一种与“三地址指令”非常近似的“四元式”作为中间代码。这种四元式的形式是： 算符 左操作数 右操作数 结果 它的意义是：对“左、右操作数”进行某种运算（由“算符”指明），把运算所得的值作为“结果”保留下来。在采用四元式作为中间代码的情形下，中间代码产生的任务就是按语言的语义规则把各类语法成份翻译成四元式序列。 例如，下面的赋值句 Z:＝（X＋0.418）*Y／W 可被翻译为如下的四元式序列： 序号 算符 左操作数 右操作数 结果 1 十 X 0.418 T1 2 * T1 Y T2 3 ／ T2 W Z 一般而言，中间代码是一种独立于具体硬件的记号系统。 第四阶段，优化 优化的任务: 对前述阶段产生的中间代码进行加工变换，以期在最后代码生成阶段能产生出更为高效（省时间和空间）的目标代码。 优化的主要方面有： 公共子表达式提取、循环优化、删除无用代码等等。 优化所依循的原则: 是程序的等价变换规则。 第五阶段，目标代码生成 这一阶段的任务是： 把中间代码（或经优化处理之后）变换成特定机器上的低级语言代码。 这阶段实现了最后的翻译，它的工作有赖于硬件系统结构和机器指令含义。这阶段工作非常复杂，涉及到硬件系统功能部件的运用，机器指令的选择，各种数据类型变量的存储空间分配，以及寄存器和后援寄存器的调度，等等。如何产生出足以充分发挥硬件效率的目标代码是一件非常不容易的事情。 上述编译过程的五个阶段是一种典型的分法。 事实上，并非所有编译程序都分成这五阶段。 有些编译程序对优化没有什么要求，优化阶段就可省去。在某些情况下，为了加快编译速度，中间代码产生阶段也可以去掉。 有些最简单的编译程序是在语法分析的同时产生目标代码。但是，多数实用编译程序的工作过程大致都像上面所说的那五个阶段。 §1.3 编译程序的结构 1.3.1 编译程序总框 上述编译过程的五个阶段是编译程序工作时的动态特征。编译程序的结构可以按照这五阶段的任务分模块进行设计。图1.5给出了编译程序总框。 图1.5 编译程序总框 词法分析器 语法分析器 语义分析与中间代码生成器 中间代码优化器 目标代码生成器 表 格 管 理 出 错 处 理 目标代码程序 源程序 单词符号串 语法单位 中间代码串 中间代码串 词法分析器，又称扫描器，输入源程序，进行词法分析，输出单词符号。 语法分析器，简称分析器，对单词符号串进行语法分析（根据语法规则进行推导或归约），识别出各类语法单位，最终判断输入串是否构成语法上正确的“程序”。 语义分析与中间代码产生器，按照语义规则对语法分析器归约出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间代码。 武汉理工大学计算机科学系陈天煌