文档介绍：编译原理复****br/>一、简述题
1、简述编译程序的工作过程
编译程序的工作,即从输入源程序开始到输出目标程序为止的整个过程是非常复杂的。通常,编译程序的工作过程可以划分为5个阶段:
第1阶段,词法分析。词法分析的任务是输入源程序,对构成源程序的字符串进行扫描和分解,识别出一个个的单词(亦称单词符号或简称符号),如保留字(基本字)、标识符、算符、界符等。
依循的原则:构词规则
描述工具:有限自动机
第2阶段,语法分析。语法分析的任务是在词法分析的基础上,根据语言的语法规则,把单词符号串分解成各类语法单位(语法范畴),如语句、程序块、函数等,判断整个输入串是否是一个语法上正确的“程序”。
依循的原则:语法规则
描述工具:上下文无关文法
第3阶段,语义分析与中间代码产生。这一阶段的任务是对语法分析所识别出的各类语法范畴,分析其含义,并进行初步翻译(产生中间代码)。通常的中间代码有三元式、四元式、间接三元式、逆波兰式等。
依循的原则:语义规则
第4阶段,优化。优化的任务在于对前段产生的中间代码进行加工变换,以期在最后阶段能产生更为高效(省时间和空间)的目标代码。优化的主要方法有公共子表达式的提取、循环优化等。
依循的原则:程序的等价变换规则
第5阶段,目标代码生成。这一阶段的任务是把中间代码(或经优化处理之后的中间代码)变换成特定机器上的低级语言代码。
目标代码三种形式:
绝对指令代码: 可直接运行
可重新定位指令代码: 需要连接装配
汇编指令代码: 需要进行汇编
2、编译程序在分析语言程序的过程中将源语言程序的各种信息都保留在各种表格中,同时,在源语言程序出错时,编译程序要帮助进行错误判断、错误定位等,因此表格管理及出错处理和编译程序的各个阶段都有关联。
编译程序的结构图如图所示。
其中词法分析器,又称扫描器,输入源程序,进行词法分析,输出单词符号。
语法分析器,简称分析器,对单词符号串进行语法分析,识别出各类语法单位,最终判断输入串是否构成语法上正确的“程序”。
语义分析器与中间代码产生器,按照语义规则对语法分析器规约出的语法单位进行语义分析并把它们翻译成一定形式的中间代码。
优化器,对中间代码进行优化处理。
目标代码生成器,把中间代码翻译成目标程序。
3、程序语言的定义
一个程序语言是一个记号系统。如同自然语言一样,程序语言主要是由语法和语义两方面定义的。有时,语言定义也包含语用信息,语用主要是有关程序设计技术和语言成分的使用方法,它使语言的基本概念与语言的外界(如数学概念或计算机的对象和操作)联系起来。任何语言程序都可以看做是一定字符集(称为字母表)上的一个字符串。合乎语法的字符串才算是一个合法的程序。
语言的语法是用来形成一个合法程序的一组规则。这些规则的一部分称为词法规则,另一部分称为语法规则(或产生规则)。语言的词法规则是指单词符号的形成规则。语法规则则规定了如何从单词符号形成更大的结构(即语法单位),因此语法规则也可以说是语法单位的形成规则。
词法规则和语法规则定义了程序语言的形成规则,而程序的意义则用语言的语义规则来定义。语义规则规定了语言的单词符号和语法单位的意义,是定义一个程序意义的一组规则。
4、上下文无关文法
文法是描述语言的语法结构的形式规则即语法规则。这些规则