《编译原理第010章》由会员分享，可在线阅读，更多相关《编译原理第010章（133页珍藏版）》请在金锄头文库上搜索。
1、第十章 自下而上语法分析u概述u算符优先分析法uLR分析法语法分析内容回顾u什么是语法分析？u自上而下分析方法：前提条件：提取公共左因子、消除左递归u缺陷只适合部分文法、效率较低第十章 自下而上语法分析第一节 概述 自下而上分析： 从输入串出发，寻找归约序列，逐步进行归约，直至开始符号S 方法：采用栈， 移进-归约基本方法:移进-归约基于下推自动机1)采用栈，将输入符号移进栈中2)如果栈顶（一个或多个符号） 形成某个非终结符号的候选式3)则进行归约:将候选式出桟；归约后的非终 结符号移进栈4)重复进行上述过程，直到输入串 扫描结束。 5)如果栈内只剩下开始符号S，则输入串是文法合法的句子。例1
2、0-1文法G：SSASSbAccAAa 输入串bccab的归约过程为：bSc Sc c Sa c c SA c c SA Sb A SS A SSG(S)：SSASSbAccAAa输入串bccab符号栈b Scca AAb SS历史记录语法分析过程可以用分析树的形成过程来表示SSSAbccAbaSbAAcacAaSb串bccab分析树的形成语法分析过程也可以用语法树的修剪过程来表示u语法树的剪枝过程：SSSAbccAba冲突归约与归约的冲突移进与归约的冲突自下而上分析可能遇到的问题如何判断栈顶符号串已经形成可归约串如何进行归约自下而上分析的关键问题对可归约串的不同的定义形成不同的语法分析方法：
3、算符优先分析法：最左素短语LR分析法：句柄1.短语:是无关文法G的一个句型, 如果有S*A并且A+则称是句型的一个短语(关于非终结符A的短语) 短语、句柄和规范归约2.直接短语（简单短语）A = 3.句柄：句型的最左直接短语。4.素短语:是短语，至少包含一个终结符,且 不再含更小的素短语 5.最左素短语:句型中最左的素短语。例: G(E) EE+T|TTT*F|FF(E)|I 求T*F+i的短语、直接短语、句柄EE+TT+TT*F+TT*F+FT*F+iT*F+i是关于E的短语T*F是关于E的短语句型：推导树端末结点自左至右连接 短语：子树的边缘是相对于根的短语 直接短语：有且仅有两层的子树的
4、边 缘是相对于根的直接短语 句柄：位于最左的有且仅有两层的子 树的边缘推导树确定短语EET+TTFFi*例: G(E) EE+T|TTT*F|FF(E)|I 求T*F+i的短语、直接短语、句柄是文法的句子, 序列n,n-1,0满足下述条件时的归约称为规范归约 (1)n= (2)0为文法的开始符, 即0=S(3) 对i, 0bG有P. . .Qb. . . 且Q+. . .a 或Q+aR2. 相邻的2个终结符之间的优先关系(1)a=b P.ab.或P.aQb.PbaQ推广u一个候选式中的所有终结符的 优先关系都相等 (2)ab G中有P.Qb. 且Q+.a或Q+aRPabQLASTVT集合LAS
5、TVT(Q)=a|Q+.a 或 Q+aRaVT,R VN3. 算符优先文法若算符文法G的任何终结符a、b 之间的优先关系至多只有=、ai+1Pai+1QNiaiNi+1 NjajNj+1aj-1栈顶待归约的最左素短语与对应的产生式结构一致即长度一致, 对应的终结符一致而非终结符可以不一致。归约最左素短语的方法-结构归约根据优先关系的定义，可以得到 终结符之间的所有优先关系。 G（E）:EE+T|TTT*F|FF(E)|i+*ii()# =算符优先关系表思考u特殊符号#的优先关系如何确定 ?对文法进行改造，得： G（S）:S #E#EE+T|TTT*F|FF(E)|i(1)相同终结符的优先关系未
6、必是=(2)有aa(3)a、b之间未必一定有优先关系 注意思考两个终结符之间若没有优先关系则表示?二. 算符优先分析算法设a为栈顶终结符初始化: #栈a=b=#ab归约最左素短语:最左素短语出栈, 左部符号入栈b入栈结束出错YN YYN N读一符号bk:=1; Sk:=#; repeata:=下一输入符号；if SkVT then j:=k else j:=k-1;while Sja dobeginrepeatQ:=Sj;if Sj-1VT then j:=j-1 else j:=j-2until Sj+, 用Fi归约#F +i*i#*, 用Fi归约 #F+F *i#+#, 用Fi归约*#,
7、用TT*F归约+#, 用EE+T归约结束#F+F*F#F+T#EEET+FTii*FTiFi+i*i F+i*i F+F*i F+F*F F+T E(1)FIRSTVT集FIRSTVT(P)=a|P+a 或 P+Qa三、优先关系表的构造若Pa或PQa 则aFIRSTVT(P)若PQ 则FIRSTVT(Q)FIRSTVT(P)直至FIRSTVT(P)不再增大。(2)LASTVT集 LASTVT(P)=a|P+.a 或 P+aQ若P.a或PaQ 则aLASTVT(P)若P.Q 则LASTVT(Q)LASTVT(P)直至LASTVT(P)不再增大。例 G(E) EE+TTTT*FFF(E) iET
8、FFIRSTVTLASTVT ( i + *( i) i + * ) i *) i( i *（3）求FIRSTVT集的矩阵规则 若Pa 或 PQa则MP,a:=1 若PQ 则对所有的MQ,a=1置MP,a:=1重复上述两步，直到矩阵不再变化(4)求LASTVT集的矩阵规则 若Pa 或 PaQ则MP,a:=1; 若PQ则对所有的MQ,a=1置MP,a:=1重复上述两步，直到矩阵不再变化例 G(E) EE+TTTT*FFF(E) iFIRSTVTLASTVTETFETF * i （ ） * i （ ） * i （ ）11111 11 1 111111 11 1 1FOR 每条产生式PX1X2Xn
9、DOFOR i:=1 TO n-1 DOBEGINIF Xi和Xi+1均为终结符 THEN Xi= Xi+1; /abIF ib END例 G(E) EE+TTTT*FFF(E) iETFFIRSTVTLASTVT( i + *( i) i + *) i *) i( i *+*ii()# =算符优先关系表第三节 LR分析法一. LR(K) 分析法LR分析法从左向右扫描输入串分析栈中符号及向前搜索K个输入符号以确定是否已在栈顶形成句柄从而决定应采取的动作。LR(K)分析法只考虑K=0、1的情况。s0sm-1smaia1控制程序其组成为:栈,控制程序,分析表,输入串输入串分析栈 输出actiong
10、oto分析表. . .存放状态初始时,置初始状态0;栈里的每个状态概括了从分析开始到目前已进行的分析工作。1. 分析栈包括action和goto两个子表(1)actions,a在状态s下, 当前输入符号为a时应采取的分析动作: 移进, 归约,接收, 出错。 2. 分析表(2) gotos,A表状态及非终结符的二维矩阵在状态s下, 针对归约后的符号A的入栈状态。(0)S E(1)EE+T(2)ET(3)TT*F(4)TF(5)F(E)(6)Fi LR分析表为例 G0(E)11LR分析表状 态 0 1 2 3 4 5 6 7 8 9 10actiongoto i+*()ETF s5s4123 s6
11、acc r2s7r2r2 r4r4r4r4 s5s4823 r6r6r6r6 s5s493 s5s410 s6s11 r1s7r1r1 r3r3r3r3 r5r5r5r5(1) actions,a=sj则将状态j移进栈顶, 输入指针指向下一输入符号;3. 控制程序的工作- actions,a(2) actions,a=rj按第j个产生式A归约分析栈栈顶上托|个状态出栈, 目前 栈顶的状态为i, 则根据i及A, 查goto表, gotoi,A=k, 则将状态k压入分析栈栈顶。(3)actions,a=acc, 则结束分析,输入串被接收。 (4)若actions,a或gotos,A为空转出错处理程
12、序。123 456789分析栈符号栈输入串动作(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,6 i*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,7 i)移进0,4,8,6,9,7,5 )归约0,4,8,6,9,7,10 )归约0,4,8,6,9 )归约0,4,8 )移进0,4,8,11 归约0,3归约0,2 归约0,1 接受(续表
13、)123 456789分析栈符号栈输入串动作(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
14、,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 接受(续表)EET+FTii*FTiF(i+i*i) (F+i*i) (T+i*i) (E+i*i) (E+F*i) (E+T*i) (E+T*F) (E+T) (E) F T E SF()S4. 几种LR分析法及其比较LR(0)、 SLR(1)LR(1)、 LALR(1)分析能力，LR(1)最强，LALR(1)次之，LR(0)最弱。LOOKAHEADScent它们的分析表的形式和控制程 序都是相同的差别在于分析表的内容。LR分析表可能存在冲突在状态S下，当前输入符为a时，采取的分析动作有移进和归约。 LR分析表在某些状态下的动作既 有移进又有归约或者有两个以上不同的归约 移进-归约或归约-归约冲突。LR(0)采取简单的方法构造分析 表，分析表不大，分析简单，但 只对无冲突的文法有效。SLR(1) 解决一类文法的冲突，分 析能力强于LR
