自下而上的语法分析

自下而上的语法分析5.1自下而上的语法分析概述

从叶结点出发，步步向上归约。若能归约到根结点，说明输入串是文法的一个句子，否则输入串存在语法错误。比较：从文法的开始符号出发进行推导，最终推出确定的输入串（由单词种别构成的源程序）。

第2页,共58页，2024年2月25日，星期天5.1自下而上的语法分析概述

㈠概述实质上是一种移进归约法，设置一个栈，将输入串符号逐个移进栈内，一旦发现栈顶形成某个产生式的候选式时，立即将栈顶这一部分符号替换（归约）成该产生式的左部符号。第3页,共58页，2024年2月25日，星期天5.1自下而上的语法分析概述

例给定文法Ｇ：S→aAcBeA→b|AbB→d输入串abbcde第4页,共58页，2024年2月25日，星期天5.1自下而上的语法分析概述

移进归约过程如下所示

第5页,共58页，2024年2月25日，星期天5.1自下而上的语法分析概述

因最终归约到根结点，输入串abbcde是文法的一个句子。第6页,共58页，2024年2月25日，星期天5.1自下而上的语法分析概述

㈡问题从第④步到第⑤步有二种选择，可将b归约成A，栈顶成aAA；也可将Ab归成A，栈顶成aA，显然后者是正确的，故需精确定义可归约串。第7页,共58页，2024年2月25日，星期天5.1自下而上的语法分析概述

㈢句柄和规范归约①短语②直接短语（简单短语）第8页,共58页，2024年2月25日，星期天5.1自下而上的语法分析概述

③句柄句型aAbcde中存在三个短语，它们是Ab、d和aAbcde，其中Ab和d是直接短语，句柄是Ab。不能因为存在规则A→b，就断定b是这个句型的一个短语，b不是句柄，甚至连短语都不是。第9页,共58页，2024年2月25日，星期天5.1自下而上的语法分析概述

④规范归约（最左归约）⑤规范句型⑥规范推导⑦图解法第10页,共58页，2024年2月25日，星期天5.2算符优先文法1.算符文法比较简单，适合手工构造，特别适合算术表达式的语法分析2.算符优先分析法的优先关系P106第11页,共58页，2024年2月25日，星期天5.2算符优先文法3.算符优先文法的定义P107第12页,共58页，2024年2月25日，星期天5.2算符优先文法4.FIRSTVT集合定义P109LASTVT集合定义P109第13页,共58页，2024年2月25日，星期天5.2算符优先文法构造集合的规则第14页,共58页，2024年2月25日，星期天5.2算符优先文法5.构造算符优先文法分析表第15页,共58页，2024年2月25日，星期天5.3LR分析法的基本原理LR分析法适用范围广泛，适合自动生成，目前大多数编译程序的语法分析器都采用这种分析法第16页,共58页，2024年2月25日，星期天5.3LR分析法的基本原理㈠前缀—字的任意首部㈡活前缀—规范句型的一个前缀，不包含句柄后的任何符号。活就是其右部添加一些终结符后，就构成一个规范句型㈢LR分析法的基本思想把每个句柄的识别（产生式右部符号串）过程划分为若干状态，每个状态只识别句柄的一个符号，若干个符号就可识别句柄左端的一部分符号。识别了句柄这一部分就相当于识别了当前规范句型的左起部分，既规范句型的活前缀。第17页,共58页，2024年2月25日，星期天5.3LR分析法的基本原理对于文法G，可以构造一个有限自动机DFA，用它去识别给定文法的所有规范句型的活前缀，然后把这个DFA转换成LR分析表。因此，首先构造一个识别文法G所有活前缀的NFA，这个NFA的每个状态是下面定义的一个“项目”第18页,共58页，2024年2月25日，星期天5.3LR分析法的基本原理㈣LR(0)项目（简称项目）文法G的LR（0）项目定义为：在文法G每个产生式右部的某个位置添加一个园点“.”。如A→XYZ包含四个项目A→.XYZ A→X.YZA→XY.Z A→XYZ.特例，A→ε的项目为A→.。第19页,共58页，2024年2月25日，星期天5.3LR分析法的基本原理例文法0.

S'→E1.

E→aA2.

A→cA3.

A→d4.

E→d第20页,共58页，2024年2月25日，星期天5.3LR分析法的基本原理这个文法的项目有1S'→.E 2S'→E.3E→.aA 4E→a.A 5E→aA.6A→.cA 7A→c.A 8A→cA.9A→.d 10A→d.11E→.d 12E→d.第21页,共58页，2024年2月25日，星期天5.3LR分析法的基本原理㈤构造识别活前缀的NFA①将每个项目视为识别活前缀NFA的一个状态。②规定状态S'→.S为NFA的唯一初态，状态S'→S.为NFA的唯一接受态（S为原文法开始符号，S'为拓广文法开始符号）。第22页,共58页，2024年2月25日，星期天5.3LR分析法的基本原理③因在每个状态都可识别出一个活前缀（初态可识别出活前缀ε），故NFA的每个状态都是终态，终态又称为活前缀识别态。④如果状态i和状态j源自于同一产生式，而且状态i和状态j的园点位置相差一个文法符号，例状态i为

i:X→X1……Xi-1.XiXi+1……Xn

状态j为

j:X→X1……Xi-1Xi.Xi+1……Xn那么状态i和j之间存在一条弧，标记为Xi，表示在状态i读入Xi进入状态j。第23页,共58页，2024年2月25日，星期天5.3LR分析法的基本原理⑤若状态i园点之后的符号为非终结符（例i:X→α.Aβ），那么从状态i画一条ε弧到所有k:A→.γ状态,表示只有看到了从A推出的全部符号:状态i:X→α.Aβ才可经A弧进入状态j:X→αA.β。第24页,共58页，2024年2月25日，星期天5.3LR分析法的基本原理接上例，构造识别文法活前缀的NFA，如下所示：

其中1称为初态（含有S'→.E的项目），状态2、8、10、5和12称为句柄识别态（含有形如A→γ.的项目），其中2又称为接受态（含有S'→E.的项目）。

第25页,共58页，2024年2月25日，星期天5.3LR分析法的基本原理第26页,共58页，2024年2月25日，星期天5.3LR分析法的基本原理㈥构造识别活前缀的DFA其中0是初态，1为接受态，3、4、6和7是句柄识别态。第27页,共58页，2024年2月25日，星期天5.3LR分析法的基本原理第28页,共58页，2024年2月25日，星期天5.3LR分析法的基本原理㈦项目分类凡是圆点在最右端的项目称为归约项目，A→α.对文法开始符号S'的归约项目称为接受项目形如A→α.aβ的项目称为移进项目，a为终结符形如A→α.Bβ的项目称为待约项目，B为非终结符第29页,共58页，2024年2月25日，星期天5.3LR分析法的基本原理㈧LR(0)项目集规范族（简称项目集规范族）识别一个文法活前缀的DFA的项目集（状态）的全体㈨活前缀识别工作原理输入串acd第30页,共58页，2024年2月25日，星期天5.4项目集规范族的构造㈠文法拓广引进产生式S'→S㈡项目集I的闭包（CLOSURE(I)）P132㈢状态转换函数（GO(I,X)）P132㈣项目集规范族构造算法C={I0};//项目集的集合If(GO(Ii,XK)<>{}&&GO(Ii,XK)!∈C){j++;Ij=GO(Ii,XK);C=C∪Ij};第31页,共58页，2024年2月25日，星期天5.4项目集规范族的构造第32页,共58页，2024年2月25日，星期天5.5LR(0)分析表的构造㈠预备工作①引入产生式S'→S，将文法拓广成G'。②对G'的产生式进行编号。③构造文法G'的状态转换函数GO(I,X)和项目集规范族C。第33页,共58页，2024年2月25日，星期天5.5LR(0)分析表的构造㈡构造法设项目集规范族C={I0、I1、……In}，将I0、I1、……In视为分析表状态0、1、……n。LR(0)分析表存放在二维数组M中，第一维为状态，第二维为文法符号。①若移进项目A→α.aβ∈Ii且GO(Ii,a)=Ij，其中a∈VT，则置M[i][a]=sj（s表示移进）。第34页,共58页，2024年2月25日，星期天5.5LR(0)分析表的构造②若归约项目A→α.∈Ii，对于任何a∈VT∪{#}，置M[i][a]=rk（k是产生式A→α的编号，r表示归约）。③若接受项目S'→S.∈Ii，则置M[i]['#']=Acc（Acc表示接受）。④若待约项目A→α.Bβ∈Ii且GO(Ii,B)=Ij，其中B∈VN，则置M[i][B]=j。⑤分析表中的空白表示出错。第35页,共58页，2024年2月25日，星期天5.5LR(0)分析表的构造规则②若归约项目A→α.∈Ii，对于任何a∈VT∪{#}，置M[i][a]=rk（k是产生式A→α的编号，r表示归约）。某一个状态若含有归约项目，则在该状态下应执行归约操作，该规则简单处理为遇到任何符号都执行归约，而不考虑有些终结符出错的问题，这就是LR（0）分析法中0的含义，0表示没有任何展望。1表示有展望，向前看一个输入符号第36页,共58页，2024年2月25日，星期天5.5LR(0)分析表的构造例已知文法GE→aA|dA→cA|d 构造它的LR(0)分析表。第37页,共58页，2024年2月25日，星期天5.5LR(0)分析表的构造解：①预备工作1）引入产生式S'→E，将文法G拓广成G'。2）产生式编号如下：0.S'→E1.E→aA2.E→d3.A→cA4.A→d3）构造上述文法的状态转换函数GO(I,X)和项目集规范族。第38页,共58页，2024年2月25日，星期天5.5LR(0)分析表的构造②构造分析表（过程，手工完成）第39页,共58页，2024年2月25日，星期天5.5LR(0)分析表的构造总结若文法的项目集规范族中的每个项目集不存在以下情况：1.既含有移进项目又含有归约项目2.含有多个归约项目则称该文法是一个LR（0）文法即LR（0）文法的项目集规范族的任何一个项目集都不包含冲突项目，仅当一个文法是LR（0）文法时，才能构造出不含冲突的LR（0）分析表第40页,共58页，2024年2月25日，星期天5.6SLR(1)分析表的构造㈠SLR(1)分析法的引出例简单算术表达式文法G'：0.

S'→E 1.

E→E+T 2.

E→T 3.

T→T*F4.

T→F5.

F→(E) 6.

F→i 第41页,共58页，2024年2月25日，星期天5.6SLR(1)分析表的构造它的项目集规范族如下图所示：第42页,共58页，2024年2月25日，星期天5.6SLR(1)分析表的构造项目集规范族共有12个状态（I0-I11），根据项目集规范族构造LR(0)分析表，如下：第43页,共58页，2024年2月25日，星期天5.6SLR(1)分析表的构造因M[2]['*']=s7r2、M[9]['*']=s7r1，分析表含多重定义，故上述分析表不是LR(0)分析表。第44页,共58页，2024年2月25日，星期天5.6SLR(1)分析表的构造㈡SLR(1)分析法的基本思想假定I是项目集规范族的一个项目集I={X→α.bβ，A→α.，B→α.}若follow(A)∩follow(B)={}、follow(A)∩{b}={}、follow(B)∩{b}={}，则SLR(1)分析法处理如下：第45页,共58页，2024年2月25日，星期天5.6SLR(1)分析表的构造

①若当前输入符号t.code和b相等，则移进输入符号。②若当前输入符号t.code∈follow(A)，则用产生式A→α进行归约。③若当前输入符号t.code∈follow(B)，则用产生式B→α进行归约。④此外报错。第46页,共58页，2024年2月25日，星期天5.6SLR(1)分析表的构造㈢构造法SLR(1)分析表的构造是在LR(0)分析表基础上进行的，只要对LR(0)分析表的构造方法稍加修改，就可获得SLR(1)分析表的构造方法，修改部分如下所述：第47页,共58页，2024年2月25日，星期天5.6SLR(1)分析表的构造㈠预备工作①引入产生式②产生式编号③构造状态转换函数和项目集规范族④计算非终结符的follow集。㈡构造法①②若归约项目A→α.∈Ii，对于任何a∈follow(A)，置M[i][a]=rk（k是产生式A→α的编号，r表示归约）。③④⑤第48页,共58页，2024年2月25日，星期天5.6SLR(1)分析表的构造接上例，构造G的SLR(1)分析表。解：①预备工作1）文法拓广（同上）2）产生式编号（同上）3）构造状态转换函数GO(I,X)和项目集规范族（同上）4）计算非终结符的follow集folow(S')={#}、folow(E)={#,+,)}、folow(T)={#,+,),*}、folow(F)={#,+,),*}第49页,共58页，2024年2月25日，星期天5.6SLR(1)分析表的构造②构造分析表第50页,共58页，2024年2月25日，星期天5.7LR语法分析器的控制程序㈠数据结构①LR分析表②状态栈③符号栈④产生式右部符号串长度㈡手工模拟控制程序计算第51页,共58页，2024年2月25日，星期天5.7LR语法分析器的控制程序㈢算法描述分析表用二维数组M存储，栈顶状态用Stop表示，当前输入符号用t.code表示，控制程序的算法归纳如下：第52页,共58页，2024年2月25日，星期天5.7LR语法分析器的控制程序①移进若M[Stop][t.code]=sj，说明句柄尚未形成，应执行移进操作。s表示移进，j为状态号，将j移入状态栈，将t.code移入符号栈，j成为新的栈顶状态Stop。读下一个单词。第53页,共58页，2024年2月25日，