第六章自底向上先分析.ppt

第六章 自底向上优先分析法 学习目标： 掌握：构造算符优先关系表，进行算符优先分析，构造优先函数 理解：算符优先文法，最左素短语 了解：简单优先分析法 6.1 自底向上分析方法概述 6.2 自底向上优先分析方法概述 6.3 算符优先分析法 6.1 自底向上分析方法概述 基本思想 从输入符号串开始，利用文法的产生式逐步进行归约，试图归约到文法开始符 从语法树角度看，是以输入符号串作为语法树的末端结点符号串，自底向上的构造语法树，使文法开始符正好是该语法树的根。如果最终根结点是开始符，则输入符号串是语言的一个句子，否则不是。 自底向上分析过程实际上是一个不断进行直接归约的过程。 遇到的问题 如何找出进行直接归约的“可归约串”（句柄） 基本实现方法－“移进－归约”方法 引进一个先进后出的符号栈来存放符号 对输入符号串自左向右进行扫描，并把当前输入符号下推入栈中（移进）， 边移进边分析，一旦栈顶符号串形成某个句型的句柄（为某产生式的右部）时，就用相应的非终结符（产生式的左部）替换它(归约)。 重复这一过程，直到输入符号串的末端，此时如果栈中只剩文法开始符号，则输入符号串是文法的句子，否则不是。 规范归约： 自底向上分析的移进－归约过程是自顶向下最右推导的逆过程，因为最右推导为规范推导，所以自左向右的归约称为规范归约。 例 文法： (1) S→aAcBe (2)???A→b (3)???A→Ab (4) B→d 判断输入串 abbcde# 是否为该文法的句子 关键问题：如何在分析的过程中确定句柄 何时移进？栈顶末形成句柄 何时归约？栈顶形成句柄 常用自底向上分析法： 算符优先分析法（6.3） LR类分析法（第7章） 6.2 自底向上优先分析法概述 优先分析法两类： 简单优先分析法 基本思想：按一定原则定义文法中所有符号（终结符和非终结符）之间的优先关系，按照这种关系确定归约过程中的句柄并实行归约。 是一种规范归约。 简单优先分析法准确、规范，但效率低，不实用，不介绍。 算符优先分析法 基本思想：只定义文法中终结符之间的优先关系（不考虑非终结符），并由这种关系指导分析过程 不是规范归约 算符优先分析法分析速度快，特别适用于表达式的分析。缺点是不规范，常常要采用适当措施克服其缺点。 6.3 算符优先分析法 算符优先分析法特别适用于表达式的分析 从表达式得到的启发： 表达式的归约顺序与运算顺序是一样的 通常算术表达式的运算次序是先乘除后加减，同优先级时服从左结合 运算次序只与运算符（优先级，结合性）有关，与运算对象无关 可以根据运算符（终结符）的优先关系指导归约过程，与运算对象（非终结符）无关 6.3.1 优先关系 6.3.2 算符优先文法的定义 6.3.3 算符优先关系表的构造 6.3.4 算符优先分析算法 6.3.5 优先函数 6.3.6 算符优先分析法的局限性 6.3.1 优先关系 优先关系只存在于句型中相邻出现的符号 相邻：算符优先分析法只考虑终结符之间的优先关系，不考虑非终结符，所以两个终结符相邻指其中没有其他的终结符（但可以有非终结符） 如：E+T×i，＋和×相邻，×和i相邻， 但＋和i不相邻 终结符间优先关系表示： 终结符a和b之间的优先关系表示如下： ab 表示a的优先级低于b a=b 表示a的优先级等于b ab 表示a的优先级高于b 优先关系定义的依据 在当前句柄中的符号优先于与其相邻的不在句柄中的符号被归约，其优先关系大 同一句柄中的相邻符号同时被归约，其优先关系相同 注意：，=，是三种有序关系，与数学中的，=，不同，所以a=b不意味b=a，ab不意味ba 按公认的计算顺序规定优先级和结合性，得到优先关系如下： ×,/的优先级高，遵循左结合，得××, ×/, //, /× +,-的优先级低，遵循左结合，得++, +-, →-, →+ ‘(’, ‘)’规定括号的优先级大于括号外的运算符，小于括号内的运算符，如…E + ( E + T )…，有 + (，( + 规定:‘＃’任何与它相邻的运算符， 任何与它相邻的运算符‘#’ 运算对象 i 的优先级最高 优先关系表如右图所示： 算符优先分析法 1 文法要满足一定的条件，即为算符优先文法 2 根据文法按一定规则计算算符之间的优先关系 3 按优先关系进行算符优先分析 6.3.2 算符优先文法的定义 算符文法 定义： 设有上下文无关文法 G ，如果G中产生式的右部没有两个非终结符相连，则称G为算符文法（Operater Grammar），也称OG