第6章自底向上优先分析法从推导的角度，从输入符号出发，试图把它规约成识别符号。每一步都寻找特定的某个类型的短语（一般是简单短语）进行归约。在分析过程中，每次归约的都是最左边的简单短语（或其它短语）。从语法树的角度，以输入符号为树的叶子结点，试图向根结点方向往上构造语法树。基本问题自底向上分析过程的实现自底向上分析过程的实现（续）自底向上分析过程的实现（续）自底向上分析过程的实现（续）例子例子的解释6.2简单优先分析法简单优先分析技术(基本思想续）优先关系优先关系的定义优先关系的构造（2）◄的构造：由定义，Sj◄Si可以得到存在规则U→…SjV…，也就是Sj=V,+HEAD(V)＝{Sk|V==>Sk…}＝{Si1,Si2,…,Sin}。（3）►关系的构造：由定义，Sj►Si表示:存在规则U→…VW…其中V=W+TAIL(V)＝{Sl|V==>…Sl}＝{Sj1,Sj2,…,Sjm}。+HEAD(W)＝{Sk|W==>Sk…}＝{Si1,Si2,…,Sin}。优先矩阵=优先关系的冲突简单优先文法优先关系的例子定理6.4定理6.4的证明定理6.4的证明(续)定理6.4的证明(续)简单优先分析技术的实现简单优先分析技术流程图简单优先分析技术流程图(续)#b((aa)a)b#识别过程(例子续)例子例对文法G[E]：(1)S→aSb|P(2)P→bPc|bQc(3)Q→Qa|a请构造简单优先关系表，并说明该文法是否是简单优先文法？简单优先技术的局限性6.3算符优先分析法这种方法是效仿算术式的四则运算而建立起来的。对于算术表达式，只需要按照运算符之间的优先关系，就可以确定运算的顺序。不需要考虑操作数就可以对表达式进行分析。例如：E+T*F，只需要知道*的优先级高于+，就可以知道T*F是句柄。刚开始是对表达式文法进行分析，但是目前已不限于此。在一般的文法中，终结符号的地位相当于运算符号。人为确定：（0）i的优先级最高（1）优先级仅次于i，右结合（2）*和/优先级次之，左结合（3）+和-优先级最低，左结合（4）括号‘(’,‘)’的优先级大于括号外的运算符，小于括号内的运算符，左括号的优先性大于右括号（5）#的优先性低于与其相邻的运算符算符文法算符文法的性质定理6.5的证明定理6.6和6.7的证明算符优先关系首先定义如下两个集合：FIRSTVT(B)=｛b｜B=>b…或B=>Cb…｝LASTVT(B)=｛a｜B=>…a或B=>…aC｝按如下算法计算出给定文法中任何两个终结符对(a,b)之间的优先关系：1)‘〓‘关系直接看产生式的右部，若出现了A→…ab…或A→…aBb…,则a〓b2)’◄‘关系求出每个非终结符B的FIRSTVT(B)若A→…aB…,则b∈FIRSTVT(B),则a◄b3)’►’关系求出每个非终结符B的LASTVT(B)若A→…Bb…,则a∈LASTVT(B),则a►b例文法G[E]：(1)E→E+T(2)E→T(3)T→T*F(4)T→F(5)F→PF|P(6)P→(E)(7)P→iE→E+T(2)E→T(3)T→T*F(4)T→F(5)F→PF|P(6)P→(E)(7)P→i表达式文法G[E]的算符优先关表算符优先文法算符优先分析法的实现算符优先文法句型的识别素短语的例子定理6.8算符优先技术的说明识别算法流程图识别算法流程图(续)算符优先技术的实现语义处理子程序例:对符号串(i+i)*i的算符优先分析过程句型识别过程识别得到的语法树实际应用的算符优先分析技术对于某个优先关系矩阵M，如果存在两个函数f和g，它满足下列条件：1、当a〓b时,f(a)=g(b);2、当a◄b时,f(a)<g(b);3、当a►b时,f(a)>g(b)。那么f和g称为M的线性优先函数。于是a和b之间的优先关系可以由比较f(a)与g(b)的大小来决定。算法：从优先关系矩阵构造优先函数1.aVT{#},建立两个结点fa和ga;a，bVT，若a〓b,则从fa至gb和从gb至fa画一条弧；若a►b，则从fa至gb画一条弧；若a◄b，则从gb至fa画一条弧;3.若图中无环，则存在优先函数，f(a)和g(a)等于从fa和ga出发的所能到达的结点的个数。gi总结：1、不是所有的优先矩阵都有优先函数(P114例2)2、如果存在优先函数，优先函数的值不唯一；3、诊查错误的能力较弱，适用范围比较小；比如：两个没有关系的符号之间的优先函数值也有大小。算符优先文法的范围两种优先技术的比较