资源描述：
《同济大学编译原理第五章语法分析自下而上分析ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第五章语法分析——自下而上分析概述自下而上分析法就是从输入串开始，逐步进行“归约”，直至归约到文法的开始符号。从语法树的末端，步步向上“归约”，直到根结。自上而下分析法:开始符号S⇒输入串α（推导）自下而上分析法:输入串α⇒开始符号S（归约）**内容线索自下而上分析基本问题算符优先分析方法规范归约LR分析方法归约移进-归约法使用一个符号栈，把输入符号逐一移进栈，当栈顶形成某个产生式右部时，则将栈顶的这一部分替换（归约）为该产生式的左部符号。例.给定文法G：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d输入串abbcde是否为句子？归约过程如下：abbcdeb
2、abcdeAabcdebAacdeAacdecAadedcAaeabbcdeeBcAaSBcAae例.给定文法G：(1)S→aAcBe(2)A→b(3)A→Ab(4)B→d输入串abbcde是否为句子？归约过程如下：步骤：动作：1.进aa2.进bba3.归(2)4.进b5.归(3)6.进c7.进d8.归(4)10.归(1)9.进eAabAaAacAadcAaBcAaeBcAaS分析树:用树表示“移进-归约”过程bdbaceSABA符号栈的使用实现移进-归约分析的一个方便途径是用一个栈和一个输入缓冲区，用#表示栈底和输入的结束栈输入串#w#栈输入串#S#初始最终例.G:E
3、→E+E│E*E│(E)│i给出i1*i2+i3的移进归约过程步骤栈输入串动作0#i1*i2+i3#预备1#i1*i2+i3#移进2#E*i2+i3#归约E→i3#E*i2+i3#移进4#E*i2+i3#移进5#E*E+i3#归约E→i6#E+i3#归约E→E*E7#E+i3#移进8#E+i3#移进9#E+E#归约E→i10#E#归约E→E+E11#E#接受语法分析的操作移进下一输入符号移进栈顶,读头后移；归约检查栈顶若干个符号能否进行归约，若能，就以产生式左部替代该符号串，同时输出产生式编号；接收移进－归约的结局是栈内只剩下栈底符号和文法开始符号，读头也指向语句的结束
4、符；出错发现了一个语法错,调用出错处理程序注:可归约的串在栈顶,不会在内部语法树的表示——穿线表方法:在移进-归约过程中自下而上构造句子的语法树移进符号a时，构造表示端末结a的数据结构，其地址与a同时进栈a0An.....符号儿子数左部非终结符儿子数指向子结点的指针指向子结点的指针符号栈符号结点地址用A→X1X2…Xn归约时，构造新结A的数据结构，其地址与A同时进栈接受时，语法树已经构成，S及根地址在栈中例.i*i+i的语法树EE...3...E1.E1.i0*0i0+0i0E1.3自下而上分析的基本问题X→·bβA→·B→·如何找出或确定可规约串？对找出的可规约
5、串替换为哪一个非终结符号？内容线索自下而上分析基本问题算符优先分析方法规范归约LR分析方法算符优先分析方法算符优先分析法是自下而上进行句型归约的一种分析方法。定义终结符（算符）的优先关系，按终结符（算符）的优先关系控制自下而上语法分析过程（寻找“可归约串”和进行归约）。分析速度快，适于表达式的语法分析。优先关系任何两个可能相继出现的终结符a和b（它们之间可能插有一个非终结符）的优先关系：aba的优先级高于b注：这三种关系不同于数学中的<,=,>关系。算符文法一个文法，如果它的任一产生式右部都不含两个相继（并列）的非终结符，即
6、不含如下形式的产生式右部：…QR…,Q,R∈VN则称该文法为算符文法。算符优先关系设G为算符文法且不含ε-产生式，a,b∈VT,算符间的优先关系定义为：a=b当且仅当G含有产生式P→…ab…或P→…aQb…ab当且仅当G含有产生式P→…Rb…且R⇒…a或R⇒…aQ++++算符优先文法如果一个算符文法G中的任何终结符对(a,b)至多满足下述关系之一ab例.给定文法G：E→E+E
7、E*E
8、(E)
9、i其中：VT={+,*,i,(,)}。G是算符文法G是算符优先文法吗？考察终结
10、符对(+,*)（1）因为E→E+E，且E⇒E*E，所以+<*（2）因为E→E*E，且E⇒E+E，所以+>*G不是算符优先文法例.文法G:(1)E→E+T│T(2)T→T*F│F(3)F→P↑F│P(4)P→(E)│i算符优先关系为：由(4):P→(E)∴(=)由(1)(2):E→E+T,T⇒T*F∴+<*由(2)(3):T→T*F,F⇒P↑F∴*<↑由(1):E→E+T,E⇒E+T∴+>+由(3):F→P↑F,F⇒P↑F∴↑<↑由(4):P→(E),E⇒E+T∴(<+,+>)...∴G为算符优先文法（＃看作终结符号，作为句子括号）优先关系
