自上而下从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导（最左推导），若能推导出与输入字串相同的句子,则表示输入字符串是合法的；特点从文法开始符开始；推导中始终使用产生式的右部替换左边的非终结符；自下而上根据文法,对输入符号串进行归约,若能正确地归约为文法的初始符号,则表示输入字串是合法的。归约：在输入串中，寻找一条产生式的右部，如果找到用产生式的左边的非终结符替换右部。特点从输入串开始；归约中始终使用产生式的左部替换右边的候选式；5.1自下而上分析的基本问题---重点自下而上分析的基本思想、归约、规范归约、短语、直接短语、句柄等概念，规范归约———自下而上分析法5.2算符优先分析---重点难点算符优先文法、算符优先分析算法、优先表的构造、最左素短语、优先函数*5.3LR分析法5.4语法分析器的自动产生工具YACC---了解5.1自下而上分析的基本问题5.1自下而上分析的基本问题5.1自下而上分析的基本问题例5.1G[S]:S→aAcBeA→b|AbB→d分析句子abbcde是否为合法的句子分析栈动作源串分析栈动作源串5.1.1归约5.1.1归约5.1.1归约例5.2：文法G[S],其4条产生式如下：①S→aABe②A→b③A→Abc④B→d对句子abbcde的分析最右推导最左归约一个简单的归约过程5.1.1归约5.1.2规范归约简述5.1.2规范归约简述例5.4求P85.(5.2)文法的另一个句型E+T*F+i的短语。解：EE+TE+T+TE+T*F+TE+T*F+FE+T*F+i短语有4个：E+T*F+i(相对于E)；E+T*F(相对于E)；T*F(相对于T)；i(相对于T、F)。T*F和i为直接短语(相对于规则TT*F和Fi)。T*F为句柄。练习5.1.2规范归约简述例5.5文法G[S],①S→aABe②A→b③A→Abc④B→d求句子abbcde的规范归约。5.1.2规范归约简述5.1.2规范归约简述例5.6文法G[S],①S→aABe②A→b③A→Abc④B→d求对句子abbcde的规范归约。练习：文法G(S):S(L)|aS|aLL,S|S（1）指出句子(a,(a))的规范归约;（2）指出每次归约用的句柄。自下而上分析器结构移进归约：系统框架5.1.3符号栈的使用与语法树的表示移进归约例(5.1):分析输入串abbcde规范归约分析算法5.1.3符号栈的使用与语法树的表示例5.7i1*i2+i3的规范归约步骤(P88.)回顾：5.2算符优先分析例5.8表达式文法G[E]：E→E＋E|E-E|E*E|E/E|EE|(E)|i对这个二义文法可能会有好几个规范推导和归约，真正运算时也有几种不同结果。如果规定算符(终结符)的优先级从高到低为：乘幂运算符，乘、除运算符，加、减运算符；同级运算符服从左结合原则；有括号时，先括号内后括号外，那么，句子的归约过程就是唯一的。注：对所有的终结符定义某种优先关系，借助这种关系找出可归约的串，进行归约，达到自下而上分析的目的。如：i+i-i*(i+i)归约过程如下：1)i+i-i*(i+i)设算数级别最高，最先归约；E+i-i*(i+i)E+E-i*(i+i)＋，－同级，先归约左边“＋”E-i*(i+i)E-E*(i+i)－，×不同级，先归约右边“×”E-E*(i+i)×，（不同级，先归约右边“（”E-E*(i+i)E-E*(E+E)先算括号内，再算括号外E-E*(E)E-E*E先归约“×”，再归约“－”E-EE什么是算符优先分析法？所谓算符优先分析法是仿效四则运算的计算过程而构造的一种语法分析方法。算符优先分析法的特点：简单直观，特别方便于表达式分析，易于手工实现，是自下而上的归约过程，但未必按照句柄归约。算符优先分析法的关键：规定算符（终结符）的优先级而决定应采用的动作。5.2算符优先分析5.2.1算符优先文法及优先表的构造例5.9：文法G[E]:E→E＋E|E-E|E*E|E/E|EE|(E)|-E|i是算符文法，例5.10:文法E→EAE|(E)|-E|iA→＋|－|*|/|不是算符文法,算符优先关系的定义算符优先关系的定义算符优先文法算符优先表例5.11试说明下述文法G是算符文法，但不是算符优先文法。E→E+E∣E*E∣(E)∣i解:由于文法G的任一产生式右部都不含两个相邻的非终结符，故文法G是算符文法。(1)由于存在E→E+E，而E+E中第二个E可推出E*E，故有+<·*(2)由于存在E→E*E，而E*E中第一个E可推出E+E，即有+·>*可见,运算符+和*之间同时存在两种不同的优先关系，故文