6-自底向上优先分析法new.ppt

第6章 自底向上优先分析法 6.1 概 述 对待分析的符号串，自左向右逐个扫描，输入符号栈，一旦栈顶符号串形成某个句型的句柄或可归约串（对应于某产生式的右部），就用该产生式的左部非终结符代替相应右部的文法符号，即归约成识别符号。 在分析过程中，每次归约的都是最左边的简单短语（或其它短语）。 从语法树的角度，以输入符号为树的末端结点，试图向根结点方向往上构造语法树。 讨论前提 和自顶向下技术同样，不考虑符号的具体构成方式。 识别过程是从左到右，自底向上进行的。一般都采用规范归约：每一步都是对句柄进行归约（特例除外）。 基本方法 采用移入-归约方法。 使用一个栈来存放归约得到的符号。 在分析的过程中，识别程序不断地移入符号。移入的符号暂时存放在一个栈中。一旦在已经移入的（和归约得到的）符号串中包含了一个句柄时，将这个句柄归约成为相应的非终结符号。 基本方法（续） 归约中的动作有4类 移入：读入一个符号并把它归约入栈。 归约：当栈中的部分形成一个句柄（栈顶的符号序列）时，对句柄进行归约。 接受：当栈中的符号仅有#和识别符号的时候，输入符号也到达结尾的时候，执行接受动作。 错误处理：当识别程序发现输入符号串不是句子时，即出错，调用错误处理模块。 例 子 i *i+i i*i+i i E::=i E *i+i E*i+i E* i+i E*i+i E*i +i E*i+i i E::=i E*E +i E*E+i E*E E::=E*E E +i E+i E+i E+i i E::=i E+E E+E E+E E::=E+E E 例子的解释 当栈中的符号的栈顶部分还不能形成句柄时，进行移入操作。 一旦发现栈顶部分形成了句柄的时候，对该句柄进行归约。将句柄出栈，然后将归约得到的非终结符号压栈。 如果输入是句子，则栈中的符号（从底到上）和未处理的符号组成句型。 在例子中，发现句柄和归约是人为干预的结果。所以移入-归约不是实际可运行的技术，而是技术的模板。 基本问题 如何找出进行直接归约的简单短语？即如何知道栈顶符号串已形成了句柄？ 将找到的简单短语归约到哪个非终结符号？即如何选取适当的产生式进行归约? 6.2 两种优先分析法 简单优先分析法： 求出该文法所有符号（终结符和非终结符）之间的优先关系，按照这种关系确定归约过程中的句柄。 规范归约。 分析准确规范，但效率低，不实用。 算符优先分析法： 规定算符之间的优先关系，即只考虑终结符之间的优先关系，而不考虑非终结符的优先关系。 不是规范归约。 分析速度快，适用于表达式的分析。 简单优先分析法 思路： 每次察看句型中相邻的两个符号。通过两个符号的关系判定出前一个符号是句柄的尾。然后，反向找出句柄的头。这样我们就找到了一个句柄。 优先关系 和书上的写法不一样。 等同：Si 〓 Sj 先于：Si ?Sj 后于：Si?Sj 注意：〓，?和?不同于=，和。 由Si?Sj不能导出Sj?Si。 简单优先分析技术(思路续） 我们要通过两个相邻符号SiSi+1之间的关系来找到句柄： SiSi+1在句柄内：必然有规则U→ ?SiSi+1? Si在句柄内部，但是Si+1在句柄之后：必然有规则U→?Si，且存在规范句型?USi+1?。 如果Si+1在句柄内，而Si在句柄外，那么必然存在规范句型?SiU?，且 U→Si+1?。 优先关系的定义 Sj = Si：当且仅当G中有规则 U → ?SjSi ? Sj ? Si：当且仅当 U → ?SjV?，且 + V == Si?； Sj ? Si：当且仅当 U → ?VW?， 其中V和W分别满足 + V == ?Sj * W == Si ? 且 Si为终结符号。 优先关系的例子 文法：S→bAb A→(B | a B→Aa) 语言：{bab, b(aa)b, b((aa)a)b, ?} 可以从语法树里面导出部分优先关系。 优先矩阵 可以将优先关系填写到一个矩阵，得到优先矩阵。(将矩阵作为关系的表示形式） 识别过程(例子续) 优先关系的构造 根据优先关系的构造性的定义（定义6.1），我们立刻可以得到构造算法。 (1) =的构造：直接对每个规则右部处理，对