【编译原理】:编译原理期末复习1

1&＃xff0c;关于文法
一个文法G可以抽象的分为四元组&＃xff08;VN,VT,P,S&＃xff09;
VN表示非终结符 VT表示终结符 P表示产生式 S表示开始符

2&＃xff0c;老师上课说的编译原理的阶段说的是&＃xff1a;词法分析&＃xff0c;语法分析&＃xff0c;语义分析&＃xff0c;中间代码生成&＃xff0c;代码优化&＃xff0c;目标代码生成
其中 语法分析&＃xff0c;语义分析&＃xff0c;中间代码生成称为 语法制导翻译
语义分析&＃xff0c;中间代码生成称为 语义翻译

3&＃xff0c;乔姆斯基创造了文法&＃xff0c;克林创造了自动机&＃xff0c;其实这两种东西是等价的

4&＃xff0c;优化可生成“运行时间段且存储空间小的代码”

5&＃xff0c;如何判断文法是不是二义文法
对一个串进行识别&＃xff0c;判断其是否能够分出两个串
已知文法 G[S] 为 S → aSb|Sb|b &＃xff0c;试证明文法 G[S] 为二义文法。
证明&＃xff1a; 　　　
　　由文法G[S]&＃xff1a;S→aSb|Sb|b&＃xff0c;对句子aabbbb对应的两棵语法树为&＃xff1a;

6&＃xff0c;如果文法G是无二义性的&＃xff0c;那么它对应的最左推导和最右推导对应的语法树必定相同

7&＃xff0c;构造编译程序应该掌握&＃xff1a;源程序&＃xff0c;目标语言&＃xff0c;编译方法

8&＃xff0c;两个正规式等价说的是两个正规式所识别的语言集相等

9&＃xff0c;计算机执行用高级语言编写的程序主要有&＃xff1a;解释 和 编译

10&＃xff0c;自上而下分析法操作 &＃xff08;自己想&＃xff09;

11&＃xff0c;题型&＃xff1a;消除左递归&＃xff0c;提取公因子
解题方法&＃xff1a;
很好想&＃xff0c;左递归就套公式&＃xff0c;用一个临时变量解决&＃xff0c;提取公因子就用提取公因子&＃xff0c;换一个新变量出来
例题&＃xff1a;
考虑文法 G[S]:
S → (T) | a&＃43;S | a
T → T,S | S
消除文法的左递归及提取公共左因子。
解&＃xff1a;消除文法G[S]的左递归&＃xff1a;
S→(T) | a&＃43;S | a
T→ST′
T′→,ST′| ε
提取公共左因子&＃xff1a;
S→(T) | aS′
S′→&＃43;S | ε
T→ST′
T′→,ST′| ε

12&＃xff0c;几个填空题
词法分析输入&＃xff1a;源程序 输出&＃xff1a;单词符号
语法分析输入&＃xff1a;单词符号 输出&＃xff1a;语法单位
语法分析的方法大致分为&＃xff1a;自上而下分析法 &＃43; 自下而上分析法&＃xff08;现在我还没看&＃xff09;
预测分析使用 预测分析表 &＃43; 符号栈 联合控制
最右推导 规范推导&＃xff01; 最右推导就是从右边开始推&＃xff1f;哦了&＃xff1f;
根据优化所设计的范围&＃xff0c;可把优化分为&＃xff1a;局部优化&＃xff0c;循环优化&＃xff0c;全局优化
优化的定义&＃xff1a;对程序进行各种变换&＃xff0c;使的从变换后的程序出发&＃xff0c;能够产生更高效的代码
文法G含有终结符的句型成为 句子

自上而下分析法: 从开始符号开始推&＃xff0c;推出句子 &＃xff08;句子为下&＃xff09;
自下而上分析法&＃xff1a;从句子开始逐步归约&＃xff0c;直到归约到开始符

目标代码的形式&＃xff1a;机器语言&＃xff0c;汇编语言&＃xff0c;待装配机器语言模块
代码考虑问题&＃xff1a;&＃xff08;1&＃xff09;生成目标代码短 &＃xff08;2&＃xff09;减少访问内存&＃xff08;3&＃xff09;考虑到计算机指令系统的特点

display表&＃xff1a;嵌套层次显示表
作用:登记外层每个活动的最新的起始地址

13&＃xff0c;几个填空题&＃xff1a;
13.1编译程序首先要识别出源程序中每个&＃xff08;单词&＃xff09;&＃xff0c;然后分析每个&＃xff08;句子&＃xff09;并翻译其含义
13.2通常把分析前端和综合后端两大阶段&＃xff0c;词法&＃xff0c;语法和语义分析是对源程序的&＃xff08;分析&＃xff09;&＃xff0c;中间代码生成&＃xff0c;代码优化&＃xff0c;目标代码生成是对源程序的&＃xff08;综合&＃xff09;
13.3程序设计语言的发展带来了日渐多变的运行时存储管理方案&＃xff0c;主要分为&＃xff08;静态存储分配&＃xff09; &＃43; &＃xff08;动态存储分配&＃xff09;
13.4对于编译程序而言&＃xff0c;输入数据是&＃xff08;源程序&＃xff09;&＃xff0c;输出结果是&＃xff08;目标程序&＃xff09;