资源描述：
《编译原理-南京大学-自下而上语法分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第五章语法分析——自下而上分析本章内容自下而上分析基本问题直观算符优先分析法算符优先分析LR分析法自下而上分析法从输入串开始，逐步进行“归约”，直至归约到文法的开始符号；一、自下而上分析基本问题1、归约利用栈，输入符号移进栈，当栈顶形成P的候选式时，就归约为它的左P符号例5.1文法G2:S->aAcBeA->bA->AbB->d输入串：abbcde自下而上法，即“移进-归约”法最右推导：aabaAaAbaAaAcaAcdaAcBaAcBeS12345678910栈S=>aAcBe=>aAcde=>aAbcde=>abbcdeS->aAcBe输入串：abbcdeA->AbB->dA->b
2、SaAcBeAbdb分析树最左归约：=>S=>aAcBe=>aAcde=>aAbcdeabbcdeS->aAcBe输入串：abbcdeA->AbB->dA->b2规范归约短语:令G是一个文法，S是文法的开始符号，若αβδ是文法G的一个句型，如果有SαAδ且Aβ，则称β是句型αβδ相对于非终结符A的短语。句柄：一个句型的最左直接短语称为该句型的句柄。直接短语：如果有Aβ，则称β是句型αβδ相对于规则A－>β的直接短语规范推导：即最右推导；规范句型：由规范推导所得的句型称为规范句型；规范归约：是关于句型α的一个最右推导的逆过程，也称最左归约。例5.2文法GE—＞T
3、E+TT—＞F
4、T*FF
5、—＞i
6、（E）的一个句型i1*i2+i3语法树TFEEFF+T*iiiTTFEEFF+T*i1i2i3Ti1,i2,i3,i1*i2,i1*i2+i3i1,i2,i3i1短语:直接短语:句柄:3符号栈的使用规范归约用来作语法分析需要解决的问题：①如何在句型中找出句柄?②在相同的右部有不止一个产生式时,选哪一个?①实现移进-归约分析的一个方便途径是用一个栈和一个输入缓冲区,用#表示栈底和输入的结束栈输入#w#②分析程序的动作移进:下一输入符号移进栈顶归约:把句柄按产生式的左部进行归约接收:分析程序报告成功出错:发现了一个语法错,调用出错处理程序注意:可归约的串在栈顶,不会在内部二直观算符
7、优先分析法1定义:任二个相继出现的终结符a与b(可能中间有VN),可能有以下优先关系:aba的优先性低于baba的优先性等于baba的优先性高于b2例5.3文法G:E—>E+E
8、E*E
9、E↑E
10、(E)
11、i的终结符的优先关系见下表。+*↑i（）#+*↑i（）#优先表E—>E+E
12、E*E
13、E↑E
14、(E)
15、i3使用如上分析表，构造分析算法（直观算符优先分析法）记号使用说明：#：语句括号（栈底w后）θ：现行栈顶符a：刚读入字符OPTR：运算符栈OPND：操作符栈分析算法步骤：①下一个输入符号读至a中；②若a为i，则a—>OPND，转第一步；③若θa，则调用关于θ的处理程序（语义程序），处理子表
16、达式:E（1）θE（2）；然后重新进入第3步；（其中，E（1）、E（2）分别为OPND栈的次栈顶和栈顶）aOPTROPND#θ………E（1）E（2）E（3）=>④若θa，则若θ=‘(’,a=‘)’,则逐出OPTR栈顶的‘(’,放弃a中的‘)’,转第1步;若θ=a=‘#’,分析成功结束；⑤若θa，a—>OPTR栈，转第1步；⑥θ与a不存在优先关系，则输入串错误，调出错处理)OPTROPND#(………E（1）E（2）aθ#成功！2例5.4由文法G:E—>E+E
17、E*E
18、E↑E
19、(E)
20、i的终结符的优先关系表及上述分析算法分析算术表达式i1+i2*i3#的过程。OPTROPND分析过程①OP
21、ND栈为空，‘#’->OPTR栈②i1->OPND‘#’<‘+’，‘+’->OPTRi2->OPND#+i1i2i3*te输入串:i1+i2*i3#‘+’<‘*’，‘*’->OPTRi3->OPND‘*’>‘#’，‘*’弹出OPTR栈；i2*i3=t->OPND⑤‘+’>‘#’，‘+’弹出OPTR栈；t+i1=e->OPND⑥‘#’=‘#’，分析成功；e为整个表达式的结果aθ1算符优先文法①定义一如果一个文法的任何产生式右部都不含两个相继（并列）的非终结符，即不含有如下形式的产生式右部：…QR…则我们称该文法为算符文法。三算符优先分析②定义二假定G是一个不含ε-产生式的算符文法。对于任
22、何一对终结符a、b，我们说：ab，当且仅当文法G中含有形如P->…ab…或P->…aQb…的产生式；（如：（E），则（））ab，当且仅当G中含有形如P->…aR…的产生式，而Rb…或RQb…；ab，当且仅当G中含有形如P->…Rb…的产生式，而R…a或R…aQ。③定义三如果一个算符文法G中的任何终结符对（a，b）至多只满足下述三种关系之一：ab，ab，ab则称G是一个算符优先文法。2从算符优先文法构造优先关系表①构造优先关系表，就是要找出所有V
