《lr分析器》由会员分享，可在线阅读，更多相关《lr分析器（57页珍藏版）》请在金锄头文库上搜索。
1、1. 文法的句型中的短语、直接短语、句柄,句型的最左直接短语称为此句型的句柄。,短语定义分两部分,设文法G=(VN,VT,P,S),4.1 LR分析法,例，文法G的产生式为: ET|E+T TF|T*F F(E)|i,i1,句型i1*i2+i3的短语:,句型i1*i2+i3 的直接短语:,i1,E E+T,i2,i3,i1*i2,i1*i2+i3,i2+i3,i1,i2,i3,i1*i2,i1*i2+i3,句型i1*i2+i3的句柄:, E+F, E+i3, T+i3, T*F+i3, T*i2+i3, F*i2+i3, i1*i2+i3,由图不难看出:,利用句型的语法树，可以非常直观的寻找此
2、句型的短语和句柄。,F是句型E+F*i相对于T的直接短语；,i是句型E+F*i相对于F的直接短语；,F*i是句型E+F*i相对于T的短语；,E+F*i是句型E+F*i相对于E的短语。,F是句柄。,完整的最左二层子树的叶结点,句柄?,2. 句型的最右推导和最左规约,若在推导关系1n中，每次最先替换最右的非终结符，则称为最右推导?,S aBD ?,在上下文无关文法中(2型)，若在推导关系1n中，每次最先替换最右的非终结符，则称为最右推导!,S aAcBe aAcde aAbcde abbcde,最右推导,若在规约过程中，每次最先规约最左的非终结符，则称为最左规约?,在上下文无关文法中(2型)，若在
3、规约过程中，每次最先规约最左的非终结符，则称为最左规约?,S aAcBe,aAcde,aAbcde,abbcde,在上下文无关文法中(2型)，若在规约过程中，每次最先规约句柄，则称为最左规约!,句柄!,最左规约最右推导的逆过程,abbcde,在上下文无关文法中(2型)，句型的最右推导称为规范推导，最左规约称为规范归约，二者互为逆过程!,3. 句型的规范推导和规范规约,4.1 LR分析法,LR分析法是一种自底向上、自左向右的分析方法。,思想: 归范规约（最左规约）。,实现: 符号栈(移进归约) 。,i + i * i,句柄!,产生式的右部,i + i * i,规范规约,如何判断是否形成句柄？,#
4、 #,LR分析法的基本思想就是: 记住历史、展望未来、面对现实。,一方面记住已经移进的和规约的符号串，即记住“历史”；,另一方面根据所用的产生式，推测未来可能碰到的输入符号，即对未来进行“展望”。,最后根据所记载的“历史”和“展望”，与“现实”的输入符号进行比较，来确定下一步的操作是移进、规约还是出错。,在规范规约过程中，,如何记载历史和展望,LR分析器实质是一个带有符号栈的确定的有限状态自动机 DFA ；,将“历史”(已经移进或规约的符号串)及“展望”(推测可能遇见的符号)抽象为 “状态”；,将实际遇见的文法符号(“现实”)抽象成 “弧”。,“初态”抽象成为栈初始形态#。,“终态”抽象成为句
5、柄的识别状态。,例，文法 Sabc,输入串 abc#,S1,S2,S3,“状态”与符号栈当前状况一一对应,S4,状态栈中的栈顶状态概括了从分析开始到移进或规约的某一阶段的全部“历史”材料。,4.1.1 LR分析器,“动作”(ACTION)表: 二维数组，ACTIONk，a规定了当状态 k 面临输入符号 a 时应采取什么动作。,“状态转换”(GOTO)表: 二维数组，GOTOk，X规定了状态k面对文法符号(终结符或非终结符)时下一个状态是什么。,ACTIONK，a的值有四种情况:,2.规约: 设LR表中ACTIONmn，a=rj，其中，rj表示使用文法的第j个产生式A进行规约；mn表示LR表的栈
6、顶状态。,栈的状态可设为: m1 mn-p mn-p+1 mn,栈的符号可设为: x1 xn-p xn-p+1 xn,= xn-p+1 xn ，构成句柄,1. ACTIONmn，a = rj,2. GOTOmn-p ，A = m,m,状态栈 符号栈,例，输入串 i*i+i 的分析过程,EE+T ET,TT*F TF,F(E) Fi,例，输入串 i*i+i 的分析过程,EE+T ET,TT*F TF,F(E) Fi,LR文法,一个文法，如果能构造一张分析表，使得它的每个入口均是唯一确定的，则我们将这个文法称为LR文法。,一个LR分析器有时需要“展望”未来的k个输入符号才能决定采取什么样的“移进规
7、约”决策。,其相应的文法称为LR(k)文法。,根据“展望”的程度，一个LR分析器可以产生若干不同的分析方法。,LR(0) 基本LR分析法,SLR 简单LR分析法,LR(1) 规范LR分析法,4.1.2 LR(0)项目集规范族和LR(0)分析表,LR(0)描述了一种只概括“历史”信息而不包含预测性“展望”信息的“状态”。,LR(0)分析表的构造:,I. 先构造识别文法的活前缀的 NFA，然后确定化为 DFA，得到LR(0)项目集规范族。,II. 直接构造LR(0)项目集规范族。,构造LR(0)项目集规范族 DFA,构造LR(0)分析表,概念1 规范句型的活前缀,所谓活前缀是指规范句型的一个前缀，
8、这种前缀不含句柄之后的任何符号。,句型T*i2+i3的活前缀有,字的前缀是指该字的任意首部。,例，字abc的前缀有,；T；T*；T*i2,、a、ab、abc,E,意义?,概念2 文法的LR(0)项目,设文法G的某一产生式为Ax1x2xn，则Ax1xi xi+1xn 称为文法G的LR(0)项目。,其中，“”或在文法符号 xi 和 xi+1 之间；或在 x1 之前；或在 xn 之后。,A ?,A ,“ ” 的位置代表了什么含义呢？,项目A x1xi xn描述了识别当前句柄的初始状态。,项目Ax1xi xi+1xn移进xi+1后可到达项目Ax1xi+1 xi+2xn。,“ ” 每向后移动一个位置，表
9、示移进一个文法符号。,项目A x1xi xn 描述了当前句柄的识别状态。,文法的LR(0)项目分成如下四类:,A B 待归约项目，其中，BVN,A 归约项目,S 接收项目，其中，S是开始符号,A a 移进项目，其中，aVT,B c d e,B c d e,B c d e,B c d e ,A B ,(1) 构造识别文法句型最大活前缀的NFA,1. 对文法进行拓广，增加新的开始符号 S ，增加新的产生式 SE (E为原开始符号)，定义文法的每一个项目。,(1) SE (2) EaA (3) AcA (4) Ad,I,2. 定义文法的每一个项目作为 NFA 的状态； 字母表 = VNVT。,3.,
10、5. 文法的所有形如 A 的LR(0)项目构成的状态都是识别文法的规范句型的句柄的终态。,6. 文法的 SE 项目构成的状态是文法识别的接收终态。,例，文法G的识别规范句型最大活前缀的NFA,(2) NFA DFA,(3) 识别一个文法活前缀的DFA的项目集(状态)的全体称为该文法的LR(0)项目集规范族。,II. 直接构造,(1) 定义两个重要运算:,项目集闭包Closure(I) :,1. 若项目A I，则此项目Closure(I)；,2. 若项目A BClosure(I)，则B Closure (I)；,3. 重复(2)，直至Closure(I)不扩大为止。,状态转换函数GO(I，X):
11、,两部分!,I0 = Closure( S S ),GO（I0，S）,GO（I0，a）,LR(0)项目 :,S S S S ,S aBC S a BC S aB C S aBC ,B b B b ,C c C c ,= S S，S aBC ；,= S S = I1,= S a BC，B b = I2,例，文法,(1) SaBC (2) Bb (3) Cc,S S,S aBC,S S ,B b,S a BC,C c,S a B C,S aBC ,B b ,C c ,LR(0)项目集规范族如何确定归范规约?,例， #abc#,ACC !,给了文法G，将文法G拓广为文法G，假若文法G的项目集规范族已
12、经给出，其状态（项目集）为I0，I1In，则分析表的构造算法如下:,1. 若GO (Ii，a) =Ij，aVT，则Action (i，a) = S，Goto (i，a)=j ；,2. 若GO (Ii，X) =Ij，若XVN，则Goto (i，X) = j；,3. 若项目A ，A为非开始符号，则Action(i，a)=rk， rk 表示用第 k 个产生式 A进行归约； a 为任意终极符；,4. 若项目SS ，则Action（i，#）=“acc”；,5. 分析表中的空白表示出错。,S 2,1,acc,S 4,3,S 5,6,任给一文法，可按上述算法构造一张分析表，若表无重入口，则此分析表称为LR(
13、0)分析表，所给文法称为LR(0)文法，具有LR(0)分析表的分析器，称为LR(0)分析器。,a. 一个项目集Ii中，既含有移进项目，又含有归约项目，此时，Action(i，a)值不唯一。,Action(i，a) = S 或 r4，冲突。,若Action(i，a)值不唯一，我们称为语法动作冲突。通常为以下两种情况:,移进规约冲突,b. 一个项目集Ii中，存在两个或两个以上的归约项目，则Action(i，a)的值不唯一，其中，i 表示状态 Ii 。,Action(i，a)= r3或r4，冲突。,上述两种情况，有一部分动作冲突可用非终极符的后继符号集合FOLLOW(A)、FOLLOW(B)解决。下
14、面介绍SLR(1)分析表。,规约规约冲突,第一个项目告诉我们应该把下一个输入符号b移进；,第二个项目告诉我们应把栈顶的规约为A；,第三个项目告诉我们应把栈顶的规约为B；,三个项目动作互相冲突。,4.1.3 SLR(1)分析表,后继符号集FOLLOW(A)，AVN,考察FOLLOW(A)、FOLLOW(B)和b ，如果这三个集合互不相交，那么，当状态 I 面临任何输入符号 a 时，我们就可以采取如下的“移进规约”决策:,1. 若a = b，则移进；,2. 若aFOLLOW(A)，则用产生式A进行规约；,3. 若aFOLLOW(B)，则用产生式B进行规约；,4. 若a 为其它，出错；,项目集I3存在冲突:,可以用FOLLOW(B)=c解决冲突,Action (3，d) =S 4,Action (3，c) =r3 cFOLLOW(B),Action (3，x) =ERROR xVT#-d，c,Sab dD Bb ,I3,abdd abc abe,给了文法G，将文法G拓广为文法G，假若文法G的项目集规范族（识别句型的活前缀确定有限自动机）已经给出，其状态（项目集）为I0，I1In，则分析表的构造算法如下:,1. 若GO (Ii，a) =Ij，aVT，则置Action (i，a) = S j；,2. 若GO (Ii，X) =Ij，若XVN，则置Goto
