编译原理ReviewWord版.docVIP

编译原理 PAGE4 / NUMPAGES4 编译器 一个编译程序就是一个语言翻译程序，它把一种语言（称作源语言）书写的程序翻译成另一种语言（称作目标语言）书写的等价的程序。 编译的分析-综合模型 分析：分析源程序，计算其基本属性，生成源程序的中间表示 综合：将源程序的中间表示转换为目标代码 编译的逻辑阶段 词法分析?语法分析?语义分析?中间代码生成?代码优化?目标代码生成 遍 对源程序或源程序中间表示的一次扫描，每一遍读入一个文件，执行一个或几个阶段的编译操作，并输出源程序的一个中间表示 ?遍数多：编译器结构清晰，但时间效率不高 ?遍数少：编译速度快，但对机器的内存要求高 语言 某个字母表上的符号串的集合 文法G —四元组（VT，VN，S，P）： ?上下文无关文法??A →ε???A →α 推导与归约 推导是用产生式的右部代替左部，归约是用产生式的左部代替右部，归约是推导的逆过程 最左推导与最右推导?最右归约与最左归约 句型与句子 ?句型：从文法的开始符号出发进行零步或多于零步的推导得到的文法符号串 ?句型可以既包含终结符号又包含非终结符号，只包含终结符号的句型称为句子 语言的形式定义 ?文法G 推导出的所有句子组成的集合，称为语言，记为L（G） 句型的短语、直接短语和句柄 ??如果S αAδ和A β，则称β是关于A的，句型αβδ的一个短语（子树的叶子） ??如果S αAδ和A =β，则称β是关于A的， 句型αβδ的一个直接短语（只有父子两代的子树的叶子） ?最左直接短语称为句柄 最左性体现在分析树和句型中 ?句型的素短语、最左素短语1、β是关于A的，句型αβδ的一个短语2、β至少含有一个终结符3、β除自身外不含更小的带终结符的短语称β是关于A的，句型αβδ的一个素短语 ?句型最左边的素短语称为最左素短语 ?句子、文法和语言的二义性 ?如果一个文法的句子有两棵或两棵以上的分析树，称此句子是二义的 ?最左（右）推导与分析树一一对应，句子二义说明它有两个或以上最左（右）推导 如果一个文法有一个句子是二义的，此文法称为二义文法 ?如果一个语言的所有文法都是二义的，称此语言是二义的 ?正规表达式???正规表达式是一个表示字符串格式的模式 ?用来描述单词符号的结构 ?递归定义 ?有限自动机 ?是具有离散输入与离散输出的一种数学模型?输入：字符串?输出：是、否 ?它能对输入字符串是否属于某个模式（正规集、正规语言）作出判断 非确定的有限自动机—NFA ?S —状态集合?Σ —输入符号集合?move —转换函数（S×Σ→2S）?S0—开始状态 ?F —接受状态集合 确定的有限自动机—DFA ?没有ε边转移?一个状态面临一个输入符号时最多只转移到一个状态 NFA-DFA 的转换——子集构造法 ?从正规表达式构造NFA ?DFA 的化简（最小化） 自顶向下分析： ?从根到叶子来建立句子的分析树 ?或，给出句子的一个从开始符号出发的推导序列 自底向上分析： ?从叶子到根来建立句子的分析树 ?或，给出一个从句子出发到开始符号的归约序列 不确定的自顶向下分析： ?带回溯的分析方法 ?本质上是一种基于穷举原理的试探方法，是个反复使用不同的产生式谋求匹配输入串的过程 ?不确定性体现在每次选择的产生式不一定是正确的 确定的自顶向下分析： ?基本思想：从文法的开始符号出发，根据当前的输入符号和其它信息，唯一地确定选用哪条产生式往下推导，构造分析树。 ?无论对错，都没有回溯 自底向上分析法，又称为移进-归约法，它的实现思想： ?对输入符号串自左向右进行扫描，并将输入符逐个移入一个先进后出栈中，边移进边分析，一旦栈顶符号串形成某个句型的可归约串时，就用相应产生式的左部非终结符代替此可归约串。重复这一过程，直到归约到栈中只剩下文法的开始符号时分析成功。 LR（k）分析技术： ?L 指从左至右扫描输入符号串 ?R 指构造一个最右推导的逆过程（最左归约） ?k 指在作出分析决定前要向前看的输入符号个数，通常为0 或1 ?LR 分析技术是功能最强的（自底向上）语法分析技术，适用文法广，效率高，分析能力强 LR分析过程中的性质与特点： ?栈中的文法符号串并上剩余的输入串构成一个右句型（规范句型） ?当该右句型的句柄出现在栈顶时，归约，否则，移进 ?栈中的文法符号串是当前句型的前缀，该前缀不包含句型句柄后面的符号，称之为活前缀 文法符号的属性： 1、综合属性：属性值是分析树中该结点的子结点的属性值的函数 2、继承属性：属性值是分析树中该结点的父结点和/或兄弟结点的属性值的函数 S -属性定义 ?只含有综合属性的语法制导定义 L -属性定义 ?是一种语法制导定义 ?对于产生式A→X1X2…Xn 右部Xj 的继承属性，它依赖于： 1、X