编译原理局部方法对比与总结.doc

LR（1）理解：从左向右处理输入，生成最右推导，使用先行的一个符号 分析方法 增添符号 动作 满足要求 消二义性方法 NFADFA LL（1） （自顶向下） $ 匹配：将栈顶部的记号与下一个输入记号匹配 生成：利用文法选择A→a将栈顶部的非终结符A替换成串a M[N,T]表单项至多一个式子； 任意非终结符的第一个token不存在重复； 左递归消除； 提取左因子； 最近嵌套（规则法） SLR（1） （自底向上） $ 移进：将终结符从输入的开头移进到栈的顶部 归约：假设有BNF选择A→a，将栈顶部的串a归约为非终结符A 没有移进-归约冲突 （A→a·Xb 与B→c·在同一状态中同时存在，且X在Follow（B）中） 没有归约-归约冲突 （A→a· 与B→b·在同一状态中同时存在，且Follow（A）∩Follow（B）不为空） 移进-归约冲突：选取移进而不是归约 LR（0） S’→S 移进：A→a·Xb（X是终结符） 归约：A→a· 没有移进-归约冲突 （A→a·Xb 与A→a·同时存在） 没有归约-归约冲突 （A→a· 与B→b·同时存在） 在文法中加入“· ”生成项，再做NFA LR（1） A→(A)|a 扩展成： [A’→·A,$] [A→·(A),$] [A→·a,$] “，”后其实为“·”后非终结符的后面的元素 移进：[A→c·Xb,a] =[A→cX·b,a] 归约：[A→c·,a] 没有移进-归约冲突 [A→c·Xb,a] 与[B→d·,X]在同一状态中同时存在 没有归约-归约冲突 [A→c·,a] 与[B→d·,a]在同一状态中同时存在 [A’→·A,$] [A→·(A),$] [A→·a,$] 通过“（”后;状态改变为： [A→(·A),$] [A→·(A),)] [A→·a,)] 分析动作表：(根据DFA制作) 步骤 分析栈 输入 动作 值栈（有时用到） 0 $0 ......$ 1 $0... ...$ 2 $0...... $ LR（0）分析表：(根据DFA制作) 状态 动作 规则 输入 Goto a b c A B C 0 1 2 3 SLR（1）分析表： 状态 输入 Goto a b c A B C 0 1 2 3 名词概念： 1、编译器，汇编器和解释器之间的区别 解释器是如同编译器的一种语言翻译程序。 它与编译器的不同之处在于：它立即执行源程序而不是生成在翻译完成之后才执行的目标代码。 汇编器是用于特定计算机上的汇编语言的翻译程序。 有时，编译器会生成汇编语言以作为其目标语言，然后再由一个汇编程序将它翻译成目标代码。 2、扫描，分析（语法，词法）的任务 扫描的任务是将源程序读作字符文件并将其分为若干个记号 扫描程序的任务是从源代码中读取字符并形成由编译器的以后部分（通常是分析程序）处理的逻辑单元。 由扫描程序生成的逻辑单元称作记号（ t o k e n） 分析的任务是确定程序的语法，或称作结构 分析程序的任务是从由扫描程序产生的记号中确定程序的语法结构，以及或隐式或显式地构造出表示该结构的分析树或语法树 3、编译器的前端（front end），后端（back end），遍（passes）*2 前端：扫描程序、分析程序和语义分析程序 后端：代码生成器 遍：在生成代码之前多次处理整个源程序 前后端好处：给编译器带来更方便的可移植性 分析树与抽象语法树 分析树：表示岀终结符串的结构，（终结符将推导的主要特征抽取出来，同时将表面的差别顺序分解开来） 分析树：表述记号串结构； 抽象语法树：源代码记号序列的抽象表示。不能从其中得到记号序列，但包含了转换所需的所有信息，比分析树效率更高 编译的各个阶段 阶段 输入 输出 扫描阶段（scanner） 源程序 记号（token）串 语法分析程序（parser） 记号串 分析树或语法树 语义分析程序（semantic analyzer） 分析树或语法树 注释了的分析树或语法树 源代码优化程序（source code optimizer） 源程序或注释了的语法树 中间代码 代码生成器（code generator） 中间代码 目标机器代码 目标代码优化程序（target code optimizer） 目标机器代码 目标机器代码 上下文无关文法 上下文无关文法说明程序设计语言的语法结构，用来描述上下文无关语言消除死循环避免程序回溯