自底向上分析思想

自底向上分析思想第一页，共三十四页，2022年，8月28日6.1自底向上优先分析法概述优先分析法可分为：简单优先分析法算符优先分析法第二页，共三十四页，2022年，8月28日简单优先分析法基本思想:对一个文法按一定原则求出该文法所有符号之间的优先关系。按照这种关系确定规约过程中的句柄。这种规约实际上是一种规范规约。第三页，共三十四页，2022年，8月28日算符优先分析法基本思想:只规定算符之间的优先关系，即只考虑终极符之间的优先关系。由于不考虑非终极符之间的关系，在规约过程中只要找到句柄就规约，并不考虑规约到哪个非终极符，所以不是规范规约。第四页，共三十四页，2022年，8月28日6.2简单优先分析法6.2.1优先关系X=Y表示X和Y的优先关系相等。

(iffG中存在产生式A→…XY…）X<.Y表示X的优先性比Y的优先性小。

(iffG中存在产生式A→…XB…,

且B=>+Y…）X.>Y表示X的优先性比Y的优先性大。

(iffG中存在产生式A→…BD…,

且B=>+…X和D=>*Y）第五页，共三十四页，2022年，8月28日6.2.1优先关系例：若有文法G[S]1.S→bAb2.A→(B|a3.B→Aa)根据定义，可求得文法符号之间的优先关系：第六页，共三十四页，2022年，8月28日SSSS

bAbbAb

bAb

bAb（Ba(BAa)(BAa)(BaAa)优先关系实例第七页，共三十四页，2022年，8月28日表6.2文法的简单优先关系矩阵SbA(Ba)#S.>b1.>A11(<.<.1<.Ba1)#=.第八页，共三十四页，2022年，8月28日

简单优先关系矩阵从上表可看出：矩阵中元素要么只有一种关系，要么为空，元素为空时表示该文法的任何句型中不会出现该符号对的相邻关系。若出现，则为出错。

‘#’表示语句括号，‘#’的优先级<.所有符号的优先级，仅对所有与‘#’有相邻关系的文法符号而言。第九页，共三十四页，2022年，8月28日6.2.2简单优先文法的定义简单优先文法必须满足以下条件：（1）在文法符号集V中，任意两个符号之间最多只有一种优先关系成立。（2）在文法中任意两个产生式没有相同的右部。（若不满足会出现规约不唯一。）第十页，共三十四页，2022年，8月28日6.2.3简单优先分析法算法：首先构造优先关系矩阵。（1）将输入符号串a1a2..an#依次逐个存入符号栈S中，直到遇到栈顶符号ai的优先性.>下一个待输入符号aj时为止。（2）栈顶当前符号ai为句柄尾，由此向左在栈中找句柄的头符号ak,即找到ak-1<.ak为止。（3）由句柄akak+1…ai在文法的产生式中查找右部为akak+1…ai的产生式，若找到,则用相应左部代替句柄，若找不到则为出错，这时可断定输入串不是该文法的句子。（4）重复（1）（2）（3）直到归约完输入符号串，栈中只剩文法的开始符号为止。第十一页，共三十四页，2022年，8月28日6.3算符优先分析法算符优先分析法只考虑算符（广义为终结符）之间的优先关系，例如：（1）E→E+E(2)E→E-E(3)E→I对输入串i1+i2*i3的归约过程可表示如下：第十二页，共三十四页，2022年，8月28日表6.3对输入串i1+i2*i3的归约过程步骤栈S当前输入符输入串剩余部分动作1#i1+i2*i3#移进2#i1+i2*i3#归约（3）3#E+i2*i3#移进4#E+i2*i3#移进5#E+i2*i3#归约（3）6#E+E*i3#移进7#E+E*i3#移进8#E+E*i3#归约（3）9#E+E*E#归约（2）10#E+E#归约（1）11#E#接受第十三页，共三十四页，2022年，8月28日

直观算符优先分析法算符间的优先关系的表示：

a<.b表示a的优先性低于ba=.b表示a的优先性等于ba>.b表示a的优先性高于b我们可以对表达式的文法按公认的计算顺序规定优先级和结合性如下：第十四页，共三十四页，2022年，8月28日算符优先分析法表达式：

E→E+E|E-E|E*E|E/E|E^E|(E)|i（1）^优先级最高，遵循右结合。相当^<.^(2)*,/优先级其次，服从左结合。相当*>.**>.//>.//>.*(3)+,-优先级最低，服从左结合。相当

+>.++>.-->.-->.+

（4）对‘（’，‘）’规定括号的优先性大于括号外的运算符，小于括号内的运算符,内括号的优先性大于外括号。附加:对运算对象的终结符i其优先级最高。

‘#’

优先级最低。第十五页，共三十四页，2022年，8月28日算符优先关系表+-*/^()i#+>.>.>.<>.-<>.*>>>>><>./<>.^>>>><<><>.(>>>>><=.<)>>>>>>>.i>>>>>>>.#<<<<<<<=.第十六页，共三十四页，2022年，8月28日

算符优先文法的定义 定义1算符文法

:设有一文法G,如果G中没有形如A→

…BC…的产生式，其中B和C为非终结符，则称G为算符文法（OperaterGrammar)也称OG文法。第十七页，共三十四页，2022年，8月28日算符文法的性质性质1在算符文法中任何句型都不包含两个相邻的非终结符。性质2如果Ab或（bA)出现在算符文法的句型中，其中A∈VN，b∈VT,则该句型中任何含b的短语必含有A。第十八页，共三十四页，2022年，8月28日算符优先关系的定义定义2设G是一个不含ε产生式的算符文法，a和b是任意两个终结符，A、B、C是非终结符，算符优先关系=.、<.、.>定义如下：（1）a=.b当且仅当G中含有形如

A→

…ab…

或A→

…aBb…的产生式第十九页，共三十四页，2022年，8月28日算符优先关系的定义(2）a<.b当且仅当G中含有形如

A→

…aB…

的产生式且

B=>+b…或B=>+Cb…(3）a>.b当且仅当G中含有形如

A→

…Bb…的产生式且

B=>+…a或B=>+…aC第二十页，共三十四页，2022年，8月28日算符优先文法的定义定义3:设G是一个不含ε产生式的算符文法，如果对任意两个终结符对a，b之间，至多只有=.、<.、.>三种关系的一种成立，则称G是一个算符优先文法。（OperatorPrecedenceGrammar)即OPG文法。第二十一页，共三十四页，2022年，8月28日6.3.3算符优先关系表的构造（1）由定义直接构造（通过算法实现）（2）由关系图法构造（手工构造）第二十二页，共三十四页，2022年，8月28日

LR分析法

自底向上分析的最终目的是：试图将输入串归约为文法的开始符号。分析过程实际上是一种移进—归约过程，即当被分析的（栈顶）符号串形成句柄时就采取归约动作，自底向上分析的关键问题就是如何确定句柄。LR分析法就是一种自底向上分析法。LR分析法的归约过程是规范推导的逆过程，所以LR分析过程是一种归范归约过程。第二十三页，共三十四页，2022年，8月28日LR（K）的含义LR（K）分析法是1965年Knuth先生提出的，括号内的K表示向右查看输入串中符号的个数。“L”表示从左（L）向右扫描输入串，“R”表示自下而上地建立它的最右（R）推导。第二十四页，共三十四页，2022年，8月28日LR分析法的优点LR文法是非歧义文法中能够自底向上进行确定分析的最大文法类。这种方法比起自顶向下的LL（K）分析方法和自底向上的优先分析方法对文法的限制要少得多。也就是说：凡是能够用LL分析的文法都能用LR进行分析，LR分析器可以识别大多数用非歧义上下文无关文法描述的语言。因此，LR方法的适用范围比LL方法更加广泛。具有速度快、准确即时指错的优点。

第二十五页，共三十四页，2022年，8月28日LR分析LR分析器的构造工作量相当大，实现相当困难。目前真正实用的编译器，其LR分析器大多采用美国Bell实验室1974年推出的“一个编译器的编译器——YACC”来实现。它能接受一个用BNF描述的满足LALR（1）的上下文无关文法并将自动构造出LALR（1）语法分析器。第二十六页，共三十四页，2022年，8月28日LR分析我们主要介绍K≤1时，LR分析器的基本构造原理和方法。其中LR（0）分析器在分析时不需向右查看输入符号，因而对文法的限制较大，但它是构造其它LR分析器的基础；当K=1时，已能满足大多数高级语言编译程序的需要。首先，了解一下LR分析法的基本概念。第二十七页，共三十四页，2022年，8月28日LR方法的一般概念LR分析器也是下推自动机的特例（图4.8）。它是一个带有下推栈的有穷自动机。输入带存放被分析的串，带的右端（即串尾）总是放上一个界限符“#”。

下推栈分为两部分：状态栈和文法符号栈。

分析器的控制器由一个总控（驱动）程序和一张分析表组成。

第二十八页，共三十四页，2022年，8月28日一个LR分析器的组成：

（1）总控程序

对所有的LR分析器都是一样的，易于实现。（2）分析表（或分析函数）

对不同的文法是不同的。分析表由两部分组成：动作表（ACTION）和状态转换表（GOTO），都可用二维数组表示。动作表f(S,a)规定了当状态S遇到输入符号a时应采取的行动；转换表g(S,X)规定了状态S遇到非终极符X时应进入的下一个状态。（3）分析栈

包括文法符号栈和相应的状态栈，它们都是后进先出栈。第二十九页，共三十四页，2022年，8月28日LR分析器分析器的动作就是由栈顶状态和当前输入符号决定的LR（0）分析器不需向前查看输入符号。第三十页，共三十四页，2022年，8月28日LR分析器工作过程

LR分析器按下列方式动作：假定当前栈为状态栈S0S1…Sm，文法符号栈X0X1…Xm。任一时刻栈顶状态Sm与当前输入符号a都决定了分析器的下一步动作，这个动作是由动作表的f(Sm,a)所决定。动作表f的表项可规定下列4种动作之一：第三十一页，共三十四页，2022年，8月28日动作表f可规定的四种动作（1）移进如果f(Sm,a)=Si，则分析器首先把a移入到文法符号栈，再把状态Si压入状态栈顶。（i为状