[其它]第六章自底向上语法分析.ppt

第6章 自底向上优先分析法 基本知识点：自下而上语法分析的基本思想和面临的问题，简单优先分析法，算符优先分析法。 重点：算符优先关系矩阵的构造 难点：句型短语、句柄、最左素短语的寻找 自底向上优先分析法： 自底向上优先分析思想 简单优先分析法 算符优先分析法 自底向上分析思想： 任何时候栈中符号串和剩余符号串组成一个句型，当句柄出现在栈顶符号串中时，就用该句柄进行归约，这样一直归约到输入串只剩结束符、栈中符号只剩下开始符号，此时认为输入符号串是文法的句子，否则报错。 自底向上分析中的重要工作： 判断当前栈中符号串中哪些符号构成句柄 归约:构成句柄就归约 6.1 自底向上分析概述 自下而上分析法是一种“移进—归约”法，这是因为在自下而上分析过程采用了一个先进后出的分析栈。分析开始后，把输入符号自左至右逐个移进分析栈，并且边移入边分析，一旦栈顶的符号串形成某个句型的句柄时就进行一次归约，即用相应产生式的左部非终结符替换当前句柄。接下来继续查看栈顶是否形成新的句柄，若为句柄则再进行归约；若栈顶不是句柄则继续向栈中移进后续输入符号。不断重复这一过程，直到将整个输入串处理完毕。若此时分析栈只剩有文法的开始符号则分析成功，即确认输入串是文法的一个句子；否则，即认为分析失败。 优先关系分类: 简单优先分析法 算符优先分析法 简单优先分析法思路： 先确定文法中所有文法符号之间的优先关系，然后根据这种优先关系寻找句柄进行归约 其规约过程是规范规约 算符优先分析思想： 首先找出所有(算符)终结符之间的优先关系，然后根据优先关系对输入串进行分析，找到“句柄”就归约，但并不考虑归约到哪个非终结符名 因而不是规范规约 6.2 简单优先分析法 简单优先分析法是按照文法符号的优先关系确定句柄的 文法符号包括终结符和非终结符 6.2.1 优先关系： 优先关系：等于、小于、大于 优先关系表示如下： X Y： 表示X和Y 的优先关系相等 X Y： 表示X的优先性比Y 的优先性大 X Y： 表示X的优先性比Y 的优先性小 对已知文法中的任意两个文法符号X，Y按其在句型中可能出现的相临关系来确定它们的优先关系: X Y 当且仅当G中存在产生式规则 A?…XY..． X Y 当且仅当G中存在产生式规则 A?…XB…,且 B Y… X Y 当且仅当G中存在产生式规则 A ? …BD… 且有B …X 和D Y … 如何根据优先关系寻找符号串中的句柄？ 一个例子:6.2例 6.2.2 简单优先文法的定义： 简单优先文法必须满足以下条件： 在文法符号集中V，任意两个符号之间最多只有一种优先关系成立。 在文法中任意两个产生式没有相同的右部。 简单优先分析算法： 1.将输入符号串a1a2…an#依次存入符号栈S中，直到遇到栈顶符号ai的优先性大于下一个待输入符号aj时为止 2.栈顶当前符号ai为句柄尾，由此向左在栈中找句柄的头符号ak，即找到ak-1 ak的优先性为止 3.串ak …ai是句柄，在文法的产生式中查找右部为ak …ai的产生式，用该产生式的左部替代该句柄，若没找到合适的产生式则出错，此时断定输入串不是该文法的句子 4.重复1、2、3步直到归约完输入符号串、栈中只剩文法的开始符号为止 6.3 算符优先分析法 按照运算符的优先顺序和结合性，确定它们之间的优先关系。例如，乘法运算比加法运算优先，于是有 ﹡ + 和 + ﹡ ；加法运算是左结合的，所以 + +。 算符文法的定义（6.1定义） 若一文法G中没有形如A→…BC… （A、B、C∈VN）的产生式（即两个非终极符相邻），则称G为算符文法,也称OG文法。 算符文法的性质： 在算符文法中任何句型都不包含两个相邻的非终结符（性质1） 如果Ab（或bA）（A∈VN，b∈VT）出现在算符文法的句型?中，则?中任何含b的短语必含有A（性质2） 任意两终结符之间优先关系的定义(6.2)： 设G是一个不含?产生式的算符文法，a、b∈VT，A、B、C∈VN： a的优先性等于b的优先性是当G中含有 A→…ab…或A→…aBb… 产生式 a的优先性小于b的优先性当G中含有 A→…aB…，且B b…或B Cb… a的优先性大于b的优先性当G中含有 A→…Bb…，且B …a或B …aC 算符优先文法的定义（定义6.3） 对于某一文法G满足： 是算符文法 不含?产生式 任意a、b（ a、b∈VT）