编译原理第八章ppt课件.ppt

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

1、第八章自下而上的语法分析第一节引言自下而上分析：从输入串出发，归约，直至开始符方法：采用栈，在移进的过程中，观察栈顶是否形成某个产生式的一个候选一.分析树G(S)：SSASSbAccAAa看输入串bccab的归约过程bScSccSaccSAccSASbASSASSG(S)：SSASSbAccAAa输入串bccab符号栈输入串bccab分析树的形成：SSSAbccAbaSbAcAacAaSb语法树的剪枝过程：SSSAbccAbaSSSAccAbaSSSAccAbSSSAccAbSSSAbSSSA关键问题：如何判断栈顶符号串是否形成可

2、归约串、如何归约？当对不同的归约串进行归约，即形成了不同的自下而上语法分析方法二.短语、句柄和规范归约1.短语:设αβ是上下文无关文法G的一个句型,如果有SαA,并且Aβ,则称β是句型αβ关于非终结符A的一个短语,或称β是句型αβ的一个短语2.直接短语（简单短语）：Aβ3.句柄：一个句型的最左直接短语*+例:G(E)E→E+T

3、TT→T*F

4、FF→(E)

5、i求T*F+i的短语、直接短语、句柄EE+TT+TT*F+TT*F+FT*F+i因为E=E且ET*F+i，所以T*F+i是关于E的短语因为ET＋i且TT*F，所以T

6、*F是关于T的短语、直接短语、句柄因为EE＋i且ET*F，所以T*F是关于E的短语因为ET*F+T且Ti，所以i是关于T的短语因为ET*F+F且Fi，所以i是关于F的短语、直接短语******4.由推导树确定短语等句型：推导树的叶结点的自左至右连接短语：任何子树的边缘是相对于根的短语直接短语：有且仅有两层的子树的边缘是相对于根的直接短语句柄：位于最左的有且仅有两层的子树的边缘EET+TTFFi*例:G(E)E→E+T

7、TT→T*F

8、FF→(E)

9、i求T*F+i的短语、直接短语、句柄SSSAbccAbaSSSAccAbaSSSAccAb

10、SSSAccAbSSSAbSSSA5.规范归约（最左归约）假定是文法G的一个句子,序列n,n-1,…,0满足下述条件时称为规范归约。(1)n=α;(2)0为文法的开始符,即0=S;(3)对i,0

11、ET+FTi*FEET+FTi*EET+FT*EET+E例:G(S)S→aAcBeA→Ab

12、bB→dabbcde的分析过程SaAcBeAbdbabbcdeaAbcdeaAcdeaAcBeSSaAcBeAbdbSaAcBeAbdSaAcBedSaAcBeS第二节算符优先分析法一.算符优先文法1.算符文法上下文无关文法G,没有形如P→ε或P→...QR...的产生式,则称G为算符文法2.终结符之间的优先关系对算符文法G,a,bVT定义(1)a=b:G中有P→...ab...或P→...aQb...(2)a

13、QRb...(3)a>b:G中有P→...Qb...且Q...a或Q…aR++++3.算符优先文法若算符文法G的任何终结符a,b之间的优先关系至多有=、>、<中的一个,则G为一算符优先文法。据定义，构造下述文法G的优先关系表G（E）:E→E+T

14、TT→T*F

15、FF→(E)

16、i++**ii(())##>>><><<<<>>><<<<<<<<>>>>>>>>==算符优先关系表从上表可知:(1)相同终结符之间的优先关系未必是=(2)有aa(3)a、b之间未必一定有优先关系故=、<、>不同于关系运算符“等于”、“小于”、“大于”二.

17、算符优先分析算法设a为栈顶终结符初始化:#栈读一符号ba=b=#ab归约最左素短语,最左素短语出栈,左部符号入栈结束b入栈出错YNYYNN素短语：至少含有一个终结符号，且除它自身之外不再含有更小的素短语最左素短语：在具有多个素短语的句型中处于最左边的那个素短语归约最左素短语的方法:这是一种结构归约,处于栈顶待归约的最左素短语与对应的产生式在结构上应一致,即长度一致,对应的终结符一致,而非终结符可以不一致。若句型的一般形式为：#N1a1N2a2…NnanNn+1#最左素短语是满足如下条件的最左子串NjajNj+1…NiaiNi+

18、1，其中aj-1ai+1分析算法如下：k:=1;S[k]:=‘#’;repeata:=下一