编译原理第八章.

第八章自下而上的语法分析第一节引言自下而上分析：从输入串出发，归约，直至开始符方法：采用栈，在移进的过程中，观察栈顶是否形成某个产生式的一个候选一.分析树G(S)：SSASSbAccAAa看输入串bccab的归约过程bScSccSaccSAccSASbASSASSG(S)：SSASSbAccAAa输入串bccab符号栈输入串bccab分析树的形成：SSSAbccAbaSbAcAacAaSb语法树的剪枝过程：SSSAbccAbaSSSAccAbaSSSAccAbSSSAccAbSSSAbSSSA关键问题：如何判断栈顶符号串是否形成可归约串、如何归约？当对不同的归约串进行归约，即形成了不同的自下而上语法分析方法二.短语、句柄和规范归约1.短语:设αβ是上下文无关文法G的一个句型,如果有SαA,并且Aβ,则称β是句型αβ关于非终结符A的一个短语,或称β是句型αβ的一个短语2.直接短语（简单短语）：Aβ3.句柄：一个句型的最左直接短语*+例:G(E)E→E+T|TT→T*F|FF→(E)|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*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|TT→T*F|FF→(E)|i求T*F+i的短语、直接短语、句柄SSSAbccAbaSSSAccAbaSSSAccAbSSSAccAbSSSAbSSSA5.规范归约（最左归约）假定是文法G的一个句子,序列n,n-1,…,0满足下述条件时称为规范归约。(1)n=α;(2)0为文法的开始符,即0=S;(3)对i,0in,i-1是从i经把句柄替换为相应产生式的左部符号而得到的。例:G(E)E→E+T│TT→T*F│FF→(E)│ii+i*i的分析过程EET+FTii*FTiFi+i*iF+i*iT+i*iE+i*iE+F*iE+T*iE+T*FE+TEEET+FTii*FTFEET+FTii*FTiFEET+FTii*FTEET+FTii*FEET+FTi*FEET+FTi*EET+FT*EET+E例:G(S)S→aAcBeA→Ab|bB→dabbcde的分析过程SaAcBeAbdbabbcdeaAbcdeaAcdeaAcBeSSaAcBeAbdbSaAcBeAbdSaAcBedSaAcBeS第二节算符优先分析法一.算符优先文法1.算符文法上下文无关文法G,没有形如P→ε或P→...QR...的产生式,则称G为算符文法2.终结符之间的优先关系对算符文法G,a,bVT定义(1)a=b:G中有P→...ab...或P→...aQb...(2)ab:G中有P→...aQ...且Qb…或QRb...(3)ab:G中有P→...Qb...且Q...a或Q…aR++++3.算符优先文法若算符文法G的任何终结符a,b之间的优先关系至多有=、、中的一个,则G为一算符优先文法。据定义，构造下述文法G的优先关系表G（E）:E→E+T|TT→T*F|FF→(E)|i++**ii(())##==算符优先关系表从上表可知:(1)相同终结符之间的优先关系未必是=(2)有ab，未必有ba(3)a、b之间未必一定有优先关系故=、、不同于关系运算符“等于”、“小于”、“大于”二.算符优先分析算法设a为栈顶终结符初始化:#栈读一符号ba=b=#ab或a=bab归约最左素短语,最左素短语出栈,左部符号入栈结束b入栈出错YNYYNN素短语：至少含有一个终结符号，且除它自身之外不再含有更小的素短语最左素短语：在具有多个素短语的句型中处于最左边的那个素短语归约最左素短语的方法:这是一种结构归约,处于栈顶待归约的最左素短语与对应的产生式在结构上应一致,即长度一致,对应的终结符一致,而非终结符可以不一致。若句型的一般形式为：#N1a1N2a2…NnanNn+1#最左素短语是满足如下条件的最左子串NjajNj+1…NiaiNi+1，其中aj-1ajaj=aj+1,…,ai-1=aiaiai+1分析算法如下：k:=1;S[k]:=‘#’;repeata:=下一输入符号；ifS[k]VTthenj:=kelsej:=k-1;whileS[j]adobeginrepeatQ:=S[j];ifS[j-1]VTthenj:=j-1elsej:=j-2untilS[j]Q;把S[j+1]…S[k]归约为某个N;k:=j+1;S[k]:=Nendofwhile;ifS[j]aorS[j]=athenbegink:=k+1;S[k]:=aendelseerroruntila=‘#’;例G(E)E→E+T│TT→T*F│FF→(E)│ii+i*i的分析过程步骤1234567891011下推栈输入串动作#i+i*i##i,移进i#i+i*i#i+,用Fi归约#F+i*i##+,移进+#F+i*i#+i,移进i#F+i*i#i*,用Fi归约#F+F*i#+*,移进*#F+F*i#*i,移进i#F+F*i####i#,用Fi归约*#,用TT*F归约+#,用EE+T归约结束#F+F*F#F+T#EEET+FTii*FTiFEET+FTii*FTFEET+FT*FTFEET+FTi*FTFEET+TFEET+FTii*FTiFi+i*iF+i*iT+i*iE+i*iE+F*iE+T*iE+T*FE+TE三.优先关系表的构造(1)FIRSTVT集FIRSTVT(P)={a|Pa…,或PQa…,aVT,QVN}若Pa…或PQa…,则aFIRSTVT(P);若PQ…,则FIRSTVT(Q)FIRSTVT(P);直至FIRSTVT(P)不再增大。++(2)LASTVT集LASTVT(P)={a|P...a,或P…aQ,aVT,QVN}若P...a或P…aQ,则aLASTVT(P);若P...Q,则LASTVT(Q)LASTVT(P);直至LASTVT(P)不再增大。++例G(E)E→E+T│TT→T*F│FF→(E)│iETFFIRSTVTLASTVT(i+*(i)i+*)i*)i(i*（3）求FIRSTVT集的矩阵规则若Pa…或PQa…,则M[P,a]:=1;若PQ…,则对所有的M[Q,a]=1置M[P,a]:=1;重复上述两步，直到M矩阵不再变化。（4）求LASTVT集的矩阵规则若P…a或P…aQ,则M[P,a]:=1;若P…Q,则对所有的M[Q,a]=1置M[P,a]:=1;重复上述两步，直到M矩阵不再变化。例G(E)E→E+T│TT→T*F│FF→(E)│iFIRSTVTLASTVTETFETFETF＋*i（）＋*i（）＋*i（）111111111111111111(5)构造优先关系表的算法FOR每条产生式PX1X2…XnDOFORi:=1TOn-1DOBEGINIFXi和Xi+1均为终结符THENXi=Xi+1;IFi=n-2且Xi和Xi+2均为终结符但Xi+1VNTHENXi=Xi+2;IFXiVT,Xi+1VNTHENaFIRSTVT(Xi+1)Xia;IFXiVN,Xi+1VTTHENaLASTVT(Xi)aXi+1END;例G(E)E→E+T│TT→T*F│FF→(E)│iETFFIRSTVTLASTVT(i+*(i)i+*)i*)i(i*考察E→E+T中的E和+、+和T考察T→T*F中的T和*、*和F考察F→(E)中的(和E、(和)、E和)++**ii(())##==算符优先关系表一.LR(K)分析法自底向上的LR分析法是指从左向右扫描输入串,每次分析由分析栈中符号及向前搜索K个输入符号,以确定作为产生式右部的短语(句柄)是否已在分析栈的栈顶形成,从而决定应采取的动作。这种分析方法称为LR(K)分析法。一般只考虑K1的情况。第三节LR分析法其组成为:分析栈,控制程序,分析表,输入串输入串分析栈驱动程序输出actiongoto分析表s0...sm-1sma1ai＃......1.分析栈存放状态;初始时,置初始状态s0;栈里的每一状态概括了从分析开始到某一时刻已进行的分析工作。2.分析表由action[s,a]和goto[s,x]两个子表组成。(1)action[s,a]定义了在状态s下,当前输入符号为a时应采取的分析动作:移进,归约,接受,出错。(2)goto表是一个状态及非终结符的二维矩阵,goto[s,x]定义了在状态s下,面对文法符号x时的状态转换。例G0(E)(1)E→E+T(2)E→T(3)T→T*F(4)T→F(5)F→(E)(6)F→i的LR分析表如后LR分析表状态01234567891011actiongotoi+*()＃ETFs5s4123s6accr2s7r2r2r4r4r4r4r4s5s4823r6r6r6r6s5s493s5s410s6s11r1s7r1r1r3r3r3r3r5r5r5r53.控制程序的工作据action[s,a]进行:(1)若action[s,a]=sj,则将状态j推入栈顶,输入指针指向下一输入符号;(2)若action[s,a]=rj,则按第j个产生式A归约,设||=t,应在分析栈栈顶上托t个状态出栈,呈现栈顶的状态设为si,则根据si及归约后的非终结符A,查goto表,goto[si,A]=j,则将状态j下推入分析栈栈顶。(3)若action[s,a]=acc,则结束分析,输入串被接受。(4)若action[s,a]或goto[s,A]不是上述情况,转出错处理程序。123456789分析栈符号栈输入串动作＃(i+i*i)＃移进＃,(,i+i*i)＃移进00,40,4,5＃,(i+i*i)＃归约0,4,3＃,(,F+i*i)＃归约0,4,2＃,(,T+i*i)＃归约0,4,8＃,(,E+i*i)＃移进0,4,8,6＃,(,E,+i*i)＃移进0,4,8,6,5＃,(,E,+,i*i)＃归约0,4,8,6,3＃,(,E,+,F*i)＃归约例:(i+i*i)的分析过程101112131415161718190,4,8,6,9＃,(,E,+,T*i)＃移进0,4,8,6,9,7＃,(,E,+,T,*i)＃移进0,4,8,6,9,7,5＃,(,E,+,T,*,i)＃归约0,4,8,6,9,7,10＃,(,E,+,T,*,F)＃归约0,4,8,6,9＃,(,E,+,T)＃归约0,4,8＃,(,E)＃移进0,4,8,11＃,(,E,)＃归约0,3＃,F＃归约0,2＃,T＃归约0,1＃,E＃接受(续表)123456789分析栈符号栈输入串动作(i+i*i)＃移进+i*i)＃移进00,40,4,5i+i*i)＃归约0,4,3+i*i)＃归约0,4,2+i*i)＃归约0,4,8+i*i)＃移进0,4,8,6i*i)＃移进0,4,8,6,5*i)＃归约0,4,8,6,3*i)＃归约例:(i+i*i)的分析过程101112131415161718190,4,8,6,9*i)＃移进0,4,8,6,9,7i)＃移进0,4,8,6,9,7,5)＃归约0,4,8,6,9,7,10)＃归约0,4,8,6,9)＃归约0,4