西电编译原理_总复习.pptVIP

* 第四章 语法制导翻译生成中间代码 本章讨论程序设计语言的静态语义分析，并且在语法分析的基础上生成中间代码，采用的基本方法是语法制导翻译。 与前两章词法分析和语法分析不同的是，词法分析和语法分析的讨论侧重于理论，而本章则侧重于结合程序设计语言的实际例子讨论语言结构的具体翻译方法和一些实用的技术。 主要内容 1 语法制导翻译与中间代码 2 符号表的组织 3 声明语句的翻译 4 可执行语句的翻译 * 1 语法制导翻译与中间代码 语法与语义：语法和语义描述语言的不同方面、二者之间没有严格界线、语义形式化描述的困难性； 属性：用属性表示语义特征（语义值），属性的计算和属性之间的依赖关系； 语法制导翻译：为产生式配上“语义规则”并在适当的时刻执行；语义规则的两种形式； 分析方法与翻译方案：以语法分析为基础，分析树的作用； 中间代码：为什么生成中间代码，中间代码的特征，各种形式的中间代码及它们之间的关系，最常用中间代码形式。 * 3 声明语句的翻译 定义与声明：类型定义与变量声明，过程定义与过程声明 变量声明：符号表信息的填写 过程声明： 左值与右值 参数传递：参数传递的不同形式 名字的作用域：静态作用域与最近嵌套原则 声明中作用域信息的保存 符号表的条目与信息的存储（关键字＋内容） 作用域信息的保存（栈结构） 线性表与散列表 2 符号表的组织 * 4 可执行语句的翻译 简单算术表达式和赋值句的翻译：语法制导翻译的设计，类型转换； 数组元素的引用：数组元素地址计算的递推公式，地址的可变部分与不变部分，可变部分计算的语法制导翻译； 布尔表达式短路计算的翻译：为什么需要短路计算，短路计算的控制流，真出口与假出口，真值链与假值链； 控制语句的翻译：控制语句的分类，无条件转移与条件转移，拉链/回填技术； 结 束（串讲） 《编译原理》复习 西安电子科技大学 软件工程研究所 习题与试题 认真复习，重点是掌握基本概念。基本概念掌握了，相当一部分试题的解就有了 习题与试题的目的区别：习题的目的是通过反复的练习理解、掌握所学知识，会有不少繁、难、大量步骤的题；试题的目的是考察对本课程综合掌握的情况，特点是短时间内覆盖大量内容。太繁琐步骤或太难等需要耗费大量时间的题是不可能出的 自己要会辨别什么是主要的什么是次要的，抓什么丢什么。“基本概念要严谨（清楚），基本方法要灵活” 总之一句话，学习方法的掌握是个人努力的结果，单纯靠别人教是学不会的 如果是我复习 词法分析 基本概念：正规式、正规集、有限自动机，词法分析器的构造 常见计算题类型：已知集合求正规式、DFA；已知正规式求DFA、集合；已知FA求正规式、集合；FA的确定化、最小化。 语法分析 基本概念：上下文无关文法、语言、下推自动机，LL分析与LR分析； 一些必要的定义、公式、算法的核心思想等； 常见的计算题类型：（自己思考） 基本解题方法与技巧等。 3. 语法制导翻译（略）（哪些最重要？） * 关于考试 题目类型：简答题(30分)、填空题(20分)、计算题(50分) 内容分布(大概)：概述与词法分析(30分)、语法分析(40分)、语法制导翻译与运行环境(30分) 考试范围：1－4章讲过的内容 侧重考察：基本概念与基本方法的掌握 易犯的错误 不认真审题（题目的要求理解错误：意思理解错、难题想容易、容易题想难。关键问题是基本概念不清楚） 所答非所问(例如：没有要求LL分析却将文法改为LL的) 画蛇添足(例如：仅问有无冲突却将分析表先构造出来) 偷工减料(例如：有若干问，仅回答部分或问题仅答一半) 警示 千万不要作弊！命运掌握在自己的手中！ 实际试题举例一、简答题 1.1（2分）有哪些方法可以去除文法的二义性。 1.2（2分）写出 -((a+b)*c)+d 的后缀式。 1.5（4分）试证明正规式(ab)*a与a(ba)*是等价的。 1.1 （1）改写文法 （2）规定文法符号的优先级和结合性 1.2 ab+c*@d+（或ab+c*-d+） 1.5 证明： 考虑L((ab)*a)中的任意一个串ababab...aba， 由串连接的结合性可得：a(ba)(ba)(b...a)(ba)，它恰好是L(a(ba)*)， 即L((ab)*a)= L(a(ba)*)。 也可以用归纳法证明（提示：以ab重复0次、1次作为归纳基础，假设ab重复n次成立，证明ab重复n+1次也成立）。 二、填空题 2.2（6分）编译程序的基本组成有：词法分析、 、 、中间代码生成、 、 、 和 。 2.3（1分）正规式r和s等价说明 相同。 2.4（2分）不含子串baa的所有a、b符号