编译原理复习总结东北大学.pptVIP

19. 会填写单寄存器下 从四元式 = 目标语言的生成表: 如 设有语句序列： If (a+b10) x=(a*b)/(i+(a*b));y=x; 18. 基本块划分和优化 1.写出四元式序列; 2.进行基本块划分; 3.进行必要的优化; 4.写出目标代码. 放映结束！ * * 编译方法 2013年12月 复习.总结 第一部分 考试范围 一. 概念部分 ⒈ 概念词语解释(简单明确) ⒉ 概念词语填空(不求全，只求准) 二. 形式语言基础 ⒈ 简单文法构造 ※ 自己总结。 如：给定一符号串集合，构造文法。 ⒉ 主要语法成分的识别 给定一文法和一个符号串?，证明? 是句型(句子)，并画语法树求短语、简单短语和句柄。 (接上页) ⒊ 简单文法变换技术 如 消除文法的直接左递归！主要是三种常用的文法变换方法 – 圆括号、方括号和花括号。 三. 自动机基础 ⒈ 简单有限自动机的构造 如 给定一符号串集合(或正规式或正规文法)，构造有限自动机（DFA） ⒉ 求一个有限自动机所定义的语言(符号串集合)。 (接上页) 四. 词法分析 1. 2个实验。 五. 语法分析 ⒉ 给定文法，构造递归子程序（框图） ⒈ 判断一个文法是否是 LL(1)文法； (1) 消除 ?边， ?NFA=DFA (2) NFA = DFA。 5. 有限自动机的实现 ⒊ 有限自动机的确定化。 4. 确定的有限自动机的最小化。 2. 会写TOKEN 序列； 3. 词法分析技术应用； (接上页) 七. 中间代码生成 ⒈ 会写常用语句的中间代码(逆波兰式，四元式)； ⒉ 会构造常用语法成分的翻译文法； ⒊ 给定翻译文法和动作序列，会走翻译过程。 ⒊ 给定文法，构造LL(1)分析表， ⒋ LR(0)文法的判断和相应分析表的构造。 六. 符号表组织 符号表结构以及填写。 5. 简单优先文法的判断和相应分析表的构造。 6. 语法分析器的构造。 4. 语法制导翻译技术的应用。 (接上页) 九. 目标代码生成 1. 会写常用语句在单寄存器下的目标代码生成过程； 八. 优化处理 3. 基本块内四元式的优化。 1. 基本块的划分。 2. 局部优化的几种常见方法。 1. 编译程序(compiler) 目标语言 词法 分析 源 语言 语法 分析 语义 分析 优化 处理 代码 生成 错 误 处 理 符 号 表 管 理 2. 编译程序结构 五个阶段 第二部分 基本概念总结 是一种语言翻译程序，它特指把 某种高级程序设计语言翻译成具体计算机上的 低级程序设计语言。 4. 文法(上下文无关文法) (接上页) 3. 形式语言 所有符号串之集合；其中的每个符号串称为句子。 G(Z)=(VN, VT, S, P) VN : 非终结符集（定义的对象集，如：语法成分等)； 例： G(E) E - E + T | E – T | T T - T * F | T / F | F F - i | ( E ) 简单算术表达式文法 其中： VN ={E,T,F}; VT={i,+,-,*,/,(,)}; Z= E ; P： 可用四元组表示： VT : 终结符集（字母表）； S : 开始符号（研究范畴中，最大的定义对象）； P : 规则集（又称产生式集）； 字母表上的符号，按一定的规则组成的 是定义语言的规则集， (接上页) 5. 有限自动机(finite automata）FA 是一种数学模型，用于描述正规语言, FA=( Q,∑,S,F,? ) ?：变换（二元函数）： Q(有限状态集); F(结束状态集,F ? Q ）； S(开始状态集,S ? Q）； ∑(字母表)； i j a 或 ?(i,a）=j ⒈ 确定的有限自动机(DFA) 特征：①开始状态唯一; ②变换函数单值；③不带?边。 ⒉ 非确定的有限自动机(NFA) ⑴ 带有?边的非确定的有限自动机(?NFA) ⑵ 不带有?边的非确定的有限自动机( NFA) -- 不能全部具备上述特征者！ ? 6. 有限自动机的分类 其中 可定义为五元组： (接上页) (1)识别单词—从用户的源程序中把单词分离出来; (2)翻译单词—把单词转换成机内表示，便于后续处理。 7. 词法分析任务 标识符(i)，常数(c)，关键字(k)，界符(p)。 8. 单词的分类 9. 有限自动机作为单词识别器 ③ ① + ⑥ - ⑤ - # l d - ④ d ? ② ⑩ I|d ? … 标识符|关键字 无符号整数 界符 注 如何区别标识符|关键字？ 通过查关键字表决定之： 若表中存在，则视为关键字；否则视为标识符！ 滤掉回车换行、空格！ (接上页) 形式上说，语法分析是指对给定的符号串（?），判定其是