编译原理第010章.ppt

《编译原理第010章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十章自下而上语法分析概述算符优先分析法LR分析法语法分析内容回顾什么是语法分析？自上而下分析方法：前提条件：提取公共左因子、消除左递归缺陷只适合部分文法、效率较低第十章自下而上语法分析第一节概述自下而上分析：从输入串出发，寻找归约序列，逐步进行归约，直至开始符号S方法：采用栈，移进--归约基本方法:移进--归约基于下推自动机1)采用栈，将输入符号移进栈中2)如果栈顶（一个或多个符号）形成某个非终结符号的候选式3)则进行归约:将候选式出桟；归约后的非终结符号移进栈4)重复进行上述过程，直到输入串扫描结束。5)如果栈内只剩下开

2、始符号S，则输入串是文法合法的句子。例10-1文法G：SSASSbAccAAa输入串bccab的归约过程为：bScSccSaccSAccSASbASSASSG(S)：SSASSbAccAAa输入串bccab符号栈bSccaAAbSS历史记录语法分析过程可以用分析树的形成过程来表示SSSAbccAbaSbAAcacAaSb串bccab分析树的形成语法分析过程也可以用语法树的修剪过程来表示语法树的剪枝过程：SSSAbccAba冲突归约与归约的冲突移进与归约的冲突自下而上分析可能遇到的问题如何判断栈顶符号串已经形成

3、可归约串如何进行归约自下而上分析的关键问题对可归约串的不同的定义形成不同的语法分析方法：算符优先分析法：最左素短语LR分析法：句柄1.短语:αβ是无关文法G的一个句型,如果有S*αA并且A+β则称β是句型αβ的一个短语(关于非终结符A的短语)短语、句柄和规范归约2.直接短语（简单短语）A=>β3.句柄：句型的最左直接短语。4.素短语:是短语，至少包含一个终结符,且不再含更小的素短语5.最左素短语:句型中最左的素短语。例:G(E)E→E+T

4、TT→T*F

5、FF→(E)

6、I求T*F+i的短语、直接短语、句柄EE+T

7、T+TT*F+TT*F+FT*F+iT*F+i是关于E的短语T*F是关于E的短语…句型：推导树端末结点自左至右连接短语：子树的边缘是相对于根的短语直接短语：有且仅有两层的子树的边缘是相对于根的直接短语句柄：位于最左的有且仅有两层的子树的边缘推导树确定短语EET+TTFFi*例:G(E)E→E+T

8、TT→T*F

9、FF→(E)

10、I求T*F+i的短语、直接短语、句柄是文法的句子,序列n,n-1,…,0满足下述条件时的归约称为规范归约(1)n=(2)0为文法的开始符,即0=S(3)对i,0

11、柄归约得i-1规范归约（最左归约）E→E+T│TT→T*F│FF→(E)│ii+i*i的LR分析过程(按句柄归约)例:G(E)i+i*iF+i*iT+i*iE+i*iE+F*iE+T*iE+T*FE+TEEET+FTii*FTiF例:G(E)E→E+T│TT→T*F│FF→(E)│ii+i*i的算符优先分析过程（按照最左素短语进行归约）EET+FTii*FTiFi+i*iF+i*iF+F*iF+F*FF+TE注意：按最左素短语归约是结构归约：处于栈顶待归约的最左素短语与对应的产生式在结构上一致即长度一致,对应的终结符一致而

12、非终结符可以不一致。优点按照最左素短语进行的归约省略了A→的产生式的使用。其中：∈VN+(非终结符号串)缺点并不是任何文法都可以按照最左素短语进行归约。例如：S→ABA→aB→b结论部分文法可以进行算符优先分析;所有文法可以进行LR分析。S→aAcBeA→Ab

13、bB→dabbcde的LR和算符优先分析过程例:LR和算符优先分析一致SabbcdeaAbcdeaAcdeaAcBeSaS→aAcBeA→Ab

14、bB→dAcBeAbdb思考算符优先分析的条件?第二节算符优先分析法基于终结符号之间的归约顺序进行语法分析。在算术表达式

15、中，有运算符号的优先级和结合性的规定。算符优先分析法的实质就是仿效表达式的计算过程而设计的。一、算符优先文法1.算符文法上下文无关文法G如果没有形如P→ε或P→...QR...的产生式，则称G为算符文法。对算符文法G,a,bVT定义(1)a=bG有P→...ab...或P→...aQb...(2)abG有P→...Qb...且Q+...a或Q+…aR2.相邻的2个终结符之间的优先关系(1)a=bP→...ab...或P→...aQb...Pba…Q…推

16、广一个候选式中的所有终结符的优先关系都相等(2)a

17、Q+b…或Q+Rb…aVT,RVN}(3)a>bG中有P→...Qb...且Q+...a或Q+…aRPabQ………