自底向上优先分析法.ppt

简单优先分析技术流程图(续)A寻找其右部和句柄匹配的规则存在这样的规则是句子？出错处理停止将句柄中的符号退去，将规则的左部入栈。B是是否否例子1#b?(aa)b#移入2#b(?aa)b#移入3#b(a?a)b#归约4#b(M=a)b#移入5#b(Ma=)b#移入7#b(L?b#归约8#bM=b#移入9#bMb?##归约10#Z##接受0#?b(aa)b#移入步骤栈关系Next余下部分动作6#b(Ma)?b#归约文法的适用范围小。虽然使用成层法可以使一些文法变成简单优先文法，但是成层法的技术非常复杂。当两个关系既有?又有?时，成层法无能为力。如果使用高阶矩阵，将使得算法的内存需求更加大。简单优先技术的局限性简单优先技术对字汇表中的所有符号之间建立优先关系。但是，有些情况下，不需要对所有两个符号之间建立优先关系。算符优先分析技术只在部分符号（终结符）之间建立优先关系。6.3算符优先分析法壹对于算术表达式，只需要按照操作符之间的优先关系，就可以确定运算的顺序。不需要考虑操作数就可以对表达式进行分析。贰例如：E+T*F。只需要知道*的优先级高于+，就可以知道T*F时句柄。叁在一般的文法中，终结符的地位相当于操作符。算符优先分析技术基本思想定义6.4：如果文法中没有形状如U::=?VW?的规则，则该文法称为算符文法。其中，U，V和W均为非终结符。算符文法定理6.5对于算符文法，不存在包含有相邻两个非终结符的句型。定理6.6如果TU出现在句型中，其中T为终结符，U为非终结符，那么包含T的短语也必然包含U.定理6.7如果UT出现在句型中，其中T为终结符，U为非终结符，那么包含T的短语也必然包含U.算符文法的性质定理6.5的证明只需要证明：如果x不包含两个相邻的非终结符，且x=y，那么y也不包含相邻的非终结符。假设x=wUv，而y=wuv。由于x不包含两个相邻的非终结符，那么w和v中没有不相邻的非终结符。根据算符文法的定义，u中也不包含相邻的非终结符。根据假设，w的结尾不是非终结符（否则，x中包含有相邻的非终结符）。同样，v的开始符也不是非终结符。综上所述：y中不存在相邻的非终结符。假设w=xvy是文法的句型，而v是相对于V的短语。那么xVy也是句型。如果w中有两个相邻的符号TU，且T在v中，而U不在v中。显然U是y的头符号。因此xVy中存在两个相邻的非终结符VU。和定理6.5矛盾。定理6.7的证明和定理6.6类似。定理6.6和6.7的证明定义6.5设文法G是一个算符文法，Tj和Ti是两个任意的终结符，而U,V,W∈VN，定义算符优先关系如下：≈：当且仅当文法G中存在以下形式的规则：U::=?TjTi?或者U::=?TjVTi?≮：当且仅当文法G中存在形如U::=?TjV?的规则，且V=Ti?或者V=WTi?≯：当且仅当文法G中存在形如U::=?VTi?的规则，且V=?Tj或者V=?TjW。1+2+3+4+5算符优先关系算符优先分析技术的基本思想是通过终结符之间的优先关系，确定句型的句柄。对于句型[N1]T1?[Ni-1]Ti-1[Ni]Ti?[Nj]Tj[Nj+1]Tj+1?[Nk]Tk[Nk+1]满足关系Ti-1≮Ti≈Ti+1≈?≈Tj≯Tj+1的最左子符号串就是要被归约的短语。算符优先关系的直观意义优先关系例子文法： Z::=E E::=T|E+T T::=F|T*F F::=(E)|i等同关系：（≈）只有左、右括号1对由推导Z→E→E+T→E+F→E+iZ→E→E+T→E+T*F→E+T*(E)→E+T*(E+T)Z→E→E+T→E+T+T→E+T+F→E+T+(E)得到以下关系：+≮i，+≮*，*≮(，(≮+，+≯)，+≯+，+≮(等优先关系的构造优先关系≈的构造，只需要按照定义，枚举各个规则的右部就可以得到。对于关系≮和≯的构造，我们需要引入两个辅助的关系：FIRSTTERM和LASTTERM。UFIRSTTERMT当且仅当存在规则U::=T?或者U::=VT?ULASTTERMT当且仅当存在规则U::=?T或者U::=?TV第6章自底向上优先分析法对待分析的符号串，自左向右逐个扫描，输入符号栈，一旦栈顶符号串形