编译原理——大学计算机专业课程要点.doc

第一章 编译系统概述 编译程序的工作过程 ㈠词法分析 执行词法分析任务的程序称为词法分析器。 任务：字符串形式的单词 ( 编码形式的单词内部码（二元式） 依据：语言的构词规则 ㈡语法分析 执行语法分析任务的程序称为语法分析器。 任务：检查源程序的语法结构是否正确 依据：语言的语法规则 ㈢语义分析 执行语义分析任务的程序称为语义分析器或中间代码产生器。 任务：建立符号表和常数表，记录源程序中标识符属性和常数值，根据语言的语义规定生成中间代码。 依据：语言的语义内涵 ㈣目标代码生成 执行目标代码生成的程序称为目标代码生成器。 任务：中间代码 ( 目标代码（机器指令或汇编语言） 依据：目标机器的系统结构 编译程序与解释程序 ①源程序：用程序设计语言书写的程序 ②源语言：源程序设计语言 ③翻译程序：将源程序译成逻辑上等价的目标程序的程序 ④目标语言：机器语言(二进制数)，也可以是汇编语言 ⑤目标程序：经翻译程序加工后用目标语言表示的程序 ⑥编译程序：也叫编译系统，是把用高级语言编写的面向过程的源程序翻译成目标程序的语言处理程序。对源程序的加工过程是边解释边执行 ㈡单词的性质 个数确定和不确定 单字符或多字符构成 ㈢单词二元式编码 经词法分析后，单词用二元式 (code,val) 表示。 code表示单词的种别，用整数码表示，在语法分析时使用；单词的语法特性。 val表示单词的值，在本书中用字符串表示，在语义分析时使用；单词语义特性。 ㈣编码原则 通常将标识符归为一种，常数按类型分种，基本字、运算符及界符采用一符一种。 预处理工作的主要内容： ①删除注释 ②删除续行符，以及后续换行符(0AH)。 ③换行符、TAB和空格具有界符作用，预处理时通常予以保留 ④大多数语言（除C语言）不区分大小写，可在预处理时，将大写字母变换成小写字母，或相反，以方便后续处理。 ⑤对于受书写格式限制的语言，还应识别标号区，正确给出语句标号 遍：由外存获得前一遍的工作结果(对于第一遍而言，从外存获得源程序)，完成它所含 的有关阶段工作之后，再把结果存于外存。 正规集：是程序设计语言单词集的抽象 正规式：是程序设计语言构词规则的抽象；二个正规式是相等的，当且仅当二个正规式所表示的正规集是相等的； 构造正规式的非确定有限自动机 一个非确定的有限自动机M是一个五元式 M=（S，Σ，f，S0，Z） S是一个有限集，它的每一个元素称为状态。 Σ是一个有穷字母表，它的每个元素称为一个输入字符。 f是一个从S×Σ*到S的子集映照，即， f：S×Σ*→2S（多值函数） 2S表示幂集，若S={0，1}，则2S ={{}，{0}，{1}，{0，1}}。 S0S，是一个非空初态集，即NFA的初态不一定唯一。 ZS，是一个终态集。 非确定有限自动机的确定化 一个非确定的有限自动机M是一个五元式 M=（S，Σ，f，S0，Z） S是一个有限集，它的每一个元素称为状态。 Σ是一个有穷字母表，它的每个元素称为一个输入字符。 f是一个从S×Σ*到S的子集映照，即， f：S×Σ*→2S（多值函数） 2S表示幂集，若S={0，1}，则2S ={{}，{0}，{1}，{0，1}}。 S0S，是一个非空初态集，即NFA的初态不一定唯一。 ZS，是一个终态集。 正规式与确定有限自动机的等价性 对于Σ上的每个正规式V，存在一个Σ上的确定有限自动机M，便得L(V)=L(M)。 ㈠V(NFA ①将V表示成拓广NFA ②根据三条规则对V进行分裂，直至每条弧上的标记为Σ上的一个字符或ε。 ㈡NFA(DFA ①I的ε闭包 ②Ia ③NFA确定化算法 10.自动生成过程 ①构造描述每个单词的正规式Pi(1≤i≤N)。 ②根据正规式Pi构造NFA Mi(1≤i≤N)，假定初态均为0。在构造NFA Mi的同时，逐步并且最终形成识别全部单词的NFA M。 ③NFA M确定化 ④重新标记，构造DFA M。 ★11.构造下列正规式相应的DFA（状态转换矩阵形式） 1(0|1)*101 第三章 程序设计语言的语法描述 文法：对语言结构的定义和描述。 语法树：句子结构的图形表示法。 ①非叶结点称为语法单位，在形式语言中称为非终结符。 ②处于根结点位置的结点又称为开始符号。 ③叶结点称为单词符号，在形式语言中称为终结符。 语法规则的符号：“→”读作“定义为”,有些书表示“：：=”； 产生式：规则在形式语言中的名称；“→”左边的符号串称：产生式左部；右部称产生 一个语法正确的句子不能保证其语义是正确的，故一个句子是否正确，需要进行