编译原理复习提纲讲述.ppt

* * 自底向上分析法，又称为移进-归约法，它的实现思想： 对输入符号串自左向右进行扫描，并将输入符逐个移入一个先进后出栈中，边移进边分析，一旦栈顶符号串形成某个句型的可归约串时，就用相应产生式的左部非终结符代替此可归约串。重复这一过程，直到归约到栈中只剩下文法的开始符号时分析成功。 第4章 语法分析 * * 算符优先分析的基本思想： 利用算符优先关系来寻找可归约串 算符优先分析 第4章 语法分析 * * LR（k）分析技术： L 指从左至右扫描输入符号串 R 指构造一个最右推导的逆过程（最左归约） k 指在作出分析决定前要向前看的输入符号个数，通常为 0 或 1 LR 分析技术是功能最强的（自底向上）语法分析技术，适用文法广，效率高，分析能力强 第4章 语法分析 * * LR分析过程中的性质与特点： 栈中的文法符号串并上剩余的输入串构成一个右句型（规范句型） 当该右句型的句柄出现在栈顶时，归约，否则，移进 栈中的文法符号串是当前句型的前缀，该前缀不包含句型句柄后面的符号，称之为活前缀 第4章 语法分析 * * 语义分析阶段分析源程序的含义，并作相应的处理，语义分析的基本功能： 确定类型 类型检查 产生中间代码 语义分析的主流技术 —— 语法制导翻译技术 第5章 语法制导翻译 * * 文法符号的属性： 1、综合属性：属性值是分析树中该结点的子结点的属性值的函数 2、继承属性：属性值是分析树中该结点的父结点和/或兄弟结点的属性值的函数 第5章 语法制导翻译 * * 语法制导定义： 为每一条产生式（A ?α）引入一套语义规则 规则形式：b := f (c1,c2,…,ck) 第5章 语法制导翻译 * * 语法制导翻译: 根据语法分析中产生式对应的语义规则进行翻译的方法称为语法制导翻译。 第5章 语法制导翻译 * * S -属性定义 只含有综合属性的语法制导定义 第5章 语法制导翻译 * * L -属性定义 是一种语法制导定义 对于产生式 A→X1X2…Xn 右部 Xj 的继承属性，它依赖于： 1、 X1，X2，…，Xj-1 （ Xj左边的文法符号）的属性 2、A 的继承属性 ** L-属性定义包含 S-属性定义 第5章 语法制导翻译 * * 翻译模式： 将语义规则放到 { } 中，并插入到产生式右部的适当位置，以反映语义规则的计算顺序，这种书写形式称之为翻译模式 第5章 语法制导翻译 * * 从 L-属性定义出发，构造一个满足要求的翻译模式 将计算产生式右边某文法符号的继承属性的语义规则插入到此符号之前 将计算产生式左边非终结符号综合属性的语义规则放在产生式右端的末尾 第5章 语法制导翻译 * * L-属性定义 — 深度优先翻译 — 两遍扫描 S-属性定义 — 自底向上翻译 — 一遍扫描 第5章 语法制导翻译 * * 三地址代码 一般形式：x := y op z 一般含三个地址（名字、常数、临时变量），两个操作数，一个运算结果 中间代码 第7章 中间代码生成 * * 根据给定语法制导定义，翻译赋值语句、布尔表达式、控制流语句等，得到中间代码 参考例子，掌握方法 第7章 中间代码生成 * * 代码优化 编译时刻为改进目标程序的质量而进行的各项工作 与机器相关的优化 与机器无关的优化 第9章 代码优化 * * 根据优化范围 局部优化 —— 针对程序基本块 循环优化 —— 针对循环体 全局优化 —— 针对整个程序 第9章 代码优化 * * 名字的联编 名字的左值— 内存地址，存储名字的瞬时值 名字的右值— 名字的瞬时值 名字的联编 — 将一个内存地址与一个名字联系起来 在程序的一次运行中，一个名字右值（瞬时值）可能会经常改变，一个名字也可能被联编到多个地址（如递归调用中） 第6章 运行时刻环境的组织 * * 运行时刻内存的典型划分 操作系统收到运行目标程序的指令，分配一块连续的内存空间使目标程序在其上运行 栈：支持过程的递归调用 堆：支持动态内存申请 第6章 运行时刻环境的组织 代码 静态数据 栈 堆 * * 活动记录 是一段连续的存储区，用以存放过程的一次执行所需要的信息，如局部数据 第6章 运行时刻环境的组织 * * 第6章 运行时刻环境的组织 参数域、状态域、数据域 返回的值 临时变量 实在参数 控制链（可选择的） 存取链（可选择的） 保存的机器状态 局部数据 TOP TOP_SP * * 静态存储分配 动态存储分配 栈式分配 和 堆式分配 第6章 运行时刻环境的组织 * * 栈式存储分配的思想： 在运行空间中划分一块存储空间作为栈区 程序运行时每当调用一个过程，就将该过程的活动记录压入栈中