编译原理SELECT()集合的求法.ppt

编译原理 第一章 编译程序概述 第二章 PL/0编译程序的实现 第三章 文法和语言 第四章 词法分析 第五章 自顶向下语法分析方法 第六章 自底向上优先分析方法 第七章 LR分析方法 第八章 语法制导翻译和中间代码生成 第九章 符号表 第一○章 代码优化 第一一章 代码生成 自顶向下语法分析方法 自顶向下分析法就是从文法的开始符号出发，试图推导出与输入的单词串完全匹配的句子。 如果能够推导出，则该输入串是给定文法的句子； 如果不能推导出，则该输入串不是给定文法的句子。 自顶向下语法分析要解决的关键问题 假定要被代换的最左非终结符号是B，且有n条规则：B→A1|A2|…|An，那么如何确定用哪个右部去替代B？ 自顶向下语法分析方法 自顶向下分析法分确定性和不确定性两种。 自顶向下的确定性分析法对文法有一定的限制，但实现简单直观，便于手工或自动构造； 自顶向下的不确定性分析法是带有回溯的分析方法，效率低，代价高，极少使用。 自顶向下语法分析要解决的关键问题 假定要被代换的最左非终结符号是B，且有n条规则：B→A1|A2|…|An，那么如何确定用哪个右部去替代B？ 如何根据输入串的第1个符号来确定产生式呢？ 根据当前输入符号属于哪个产生式右部的开始符号集合而决定选择相应产生式进行推导。 自上而下语法分析要解决的关键问题 假定要被代换的最左非终结符号是B，且有n条规则：B→A1|A2|…|An，那么如何确定用哪个右部去替代B？ 根据规则的选择集合来确定。 LL(1)的含义：从左L向右扫描输入串，分析过程中采用最左L推导，只需向右看1个符号就可确定如何推导（选择哪个产生式进行推导）。 当需要选用自顶向下分析技术时，首先必须判定所给的文法是否是LL(1)文法。 例：递归子程序实现 表达式的语法分析 表达式的EBNF〈表达式〉∷=[+|-]〈项〉{（+|-）〈项〉}〈项〉∷=〈因子〉{（*|/）〈因子〉}〈因子〉∷=ident|number|‘（’〈表达式〉‘）’ 〈表达式〉∷=[+|-]〈项〉{（+|-）〈项〉} procedure expr;begin if sym in [ plus, minus ] then begin getsym; term;  endelse term; while sym in [plus, minus] do begin getsym; term; endend; 〈项〉∷=〈因子〉{（*|/）〈因子〉} Procedure term; begin factor; while sym in [times,slash] do begin getsym;factor end end; 〈因子〉∷=ident|number|‘（’〈表达式〉‘）’ Procedure factor; begin if sym=ident then getsym else if sym=number then getsym else if sym=‘(‘ then begin getsym; expr; if sym=‘)’ then getsym else error end else error end; 预测分析表可用一个矩阵表示。矩阵元素M[A,a]中的A表示非终结符， a表示终结符或句子结束符#，矩阵元素M[A,a]中的内容是一条关于A的产生式，表明当用非终结符A向下推导时，面临输入符a时，所采用的候选产生式，当元素内容无产生式时，表明用A为左部向下推导时遇到了不该出现的符号，因此元素内容为转向出错处理。 如何构造预测分析表？ 分析算法 BEGIN 首先把’#‘然后把文法开始符号推入栈；把第一个输入符号读进a; FLAG：=TRUE； WHILE FLAG DO BEGIN 把栈顶符号上托出去并放在Ｘ中； IF X ? Vt THEN IF X=a THEN