编译原理第三章语法分析.ppt

《编译原理第三章语法分析.ppt》由会员分享，可在线阅读，更多相关《编译原理第三章语法分析.ppt（63页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章 语法分析语法分析器的作用语法分析器的作用词法分析器词法分析器语法分析器语法分析器前端其他部分前端其他部分符号表符号表管理器管理器出错出错处理器处理器源程序源程序记号流记号流分析树分析树中间表示中间表示上下文无关文法（上下文无关文法（CFG）定义：上下文无关文法是一个四元组定义：上下文无关文法是一个四元组G=(N,T,P,S)G=(N,T,P,S)N N是非终结符的有限集合；是非终结符的有限集合；T T是终结符的有限集合，且是终结符的有限集合，且NTNT；P P是产生式的有限集合；是产生式的有限集合；S S是非终结符，是文法的开始符号。是非终结符，是文法的开始符号。例：定义上下文无关文法

2、例：定义上下文无关文法G=(N,T,P,S)G=(N,T,P,S)如下：如下：N=E T=+,*,(,),-,id S=EN=E T=+,*,(,),-,id S=EP:EE+EP:EE+E EE*E EE*E E(E)E(E)E-E E-E Eid Eid所有出现在产生式所有出现在产生式左边符号的集合左边符号的集合所有所有不不出现在产生出现在产生式左边符号的集合式左边符号的集合缩写为：缩写为：EE+E|E*E|(E)|-E|id EE+E|E*E|(E)|-E|id形式语言分类形式语言分类定义：若文法定义：若文法G=(N,T,P,S)G=(N,T,P,S)的每个产生式的每个产生式中，均有中，

3、均有 (NT)(NT)*N(NT)N(NT)*,且至少含有一个非终结符，且至少含有一个非终结符，(NT)(NT)*,则称则称G G为为0 0型型文法（短语文法）。文法（短语文法）。1 1型型文法（上下文有关文法）：文法（上下文有关文法）：G G的任何产生式的任何产生式(S(S除外除外)均满足均满足|(|x|(|x|表示表示x x中文法符号的个数中文法符号的个数)；2 2型型文法（上下文无关文法）：文法（上下文无关文法）：G G的任何产生式形如的任何产生式形如A A，其，其中中ANAN，(NT)(NT)*；3 3型型文法（正规文法、线性文法）：文法（正规文法、线性文法）：G G的任何产生式形如的

4、任何产生式形如A Aaa或者或者AaB(AaB(或者或者ABaABa）,其中其中A,BN,aTA,BN,aT*。正规式与上下文无关文法正规式与上下文无关文法正规式所描述的语言结构均可以用正规式所描述的语言结构均可以用CFGCFG描述，反之不一定。描述，反之不一定。例：正规式例：正规式r=(a|b)*abbr=(a|b)*abb的的CFGCFG描述如下描述如下 AHT AHT H H|aH|bH|aH|bH Tabb Tabb往往采用正规式而不是往往采用正规式而不是CFGCFG描述词法。描述词法。正规式适合描述正规式适合描述线性线性结构；结构；CFGCFG适合描述具有嵌套（层次）性质的适合描述具

5、有嵌套（层次）性质的非线性非线性结构。结构。CFG产生语言的基本方法产生语言的基本方法推导推导定义：将产生式定义：将产生式AA的右部代替文法符号序列的右部代替文法符号序列AA 中的中的A A得到得到的过程，称为的过程，称为AA直接推导直接推导 出出，记作：，记作：AA。11nn为零步或多步推导；为零步或多步推导；11nn为零步推导；为零步推导；任何文法符号序列可以推导出它自身，任何文法符号序列可以推导出它自身，；推导具有传递性，推导具有传递性，,则则*定义：由定义：由CFG GCFG G所产生的语言所产生的语言 L(G)=L(G)=|S|S and T and T*称为称为上下文无上下文无关语

6、言关语言，称为句子。若称为句子。若S S,(NT),(NT)*,则称则称为为G G的一个句型。的一个句型。只含终结符的句型是句子。只含终结符的句型是句子。定义：在推导中，若每次直接推导均替换句型中最左定义：在推导中，若每次直接推导均替换句型中最左边的非终结符，则称为边的非终结符，则称为最左推导最左推导，产生的句型称为，产生的句型称为左句型左句型。最右推导也称为最右推导也称为规范推导规范推导。+*例：例：已知已知G(E),EE+E|E*E|(E)|-E|idG(E),EE+E|E*E|(E)|-E|id id+(id*id)id+(id*id)的推导过程：的推导过程：最左推导：最左推导：E E

7、E+E E+E id+E id+E id+(E)id+(E)id+(E*E)id+(E*E)id+(id*E)id+(id*E)id+(id*id)id+(id*id)最右推导：最右推导：E E E+E E+E E+(E)E+(E)E+(E*E)E+(E*E)E+(E*id)E+(E*id)E+(id*id)E+(id*id)id+(id*id)id+(id*id)定义：定义：设设 是上下文无关文法是上下文无关文法G G的一个句型的一个句型,如果有如果有S S AA,并且并且A A,则称则称是句型是句型 关于非终结符关于非终结符A A的一个短语的一个短语,或称或称是句型是句型 的一个短语。的一

8、个短语。直接短语（简单短语）：直接短语（简单短语）：A A句柄：一个句型的最左直接短语。句柄：一个句型的最左直接短语。素短语素短语:含有终结符的短语含有终结符的短语,但不存在也具有相同性质的真子串但不存在也具有相同性质的真子串短语：以非终结符为根的子树中所有从左到右排列的叶子；短语：以非终结符为根的子树中所有从左到右排列的叶子；直接短语：只有父子关系的树中所有从左到右排列的叶子（树高为直接短语：只有父子关系的树中所有从左到右排列的叶子（树高为2 2）；）；句柄：最左边父子关系树中所有从左到右排列的叶子（句柄是唯一的）。句柄：最左边父子关系树中所有从左到右排列的叶子（句柄是唯一的）。素短语素短语

9、:子树末端结点组成的符号串含终结符子树末端结点组成的符号串含终结符,且在该子树中不再有包含且在该子树中不再有包含 含有终结符的更小子树含有终结符的更小子树*+短语与语法树短语与语法树例：例：G(E)G(E)：EE+T|TEE+T|T TT*F|F TT*F|F F(E)|i F(E)|i句型：句型：i*i+ii*i+i的短语、直接短语、句柄和素短语的短语、直接短语、句柄和素短语 短语：短语：i i1 1*i*i2 2+i+i3 3,i,i1 1*i*i2 2,i,i1 1,i,i2 2,i,i3 3 直接短语：直接短语：i i1 1,i,i2 2,i,i3 3 句柄：句柄：i i1 1 素短语

10、素短语:i:i1 1，i i2 2，i i3 3E E +T T FT *F i3 F i2i1分析树：分析树：根由开始符号标记；根由开始符号标记；每个叶子由一个终结符、非终结符或每个叶子由一个终结符、非终结符或标记；标记；每个内部结点由一个非终结符标记；每个内部结点由一个非终结符标记；若若AX1X2XnAX1X2Xn是一个产生式，则标记为是一个产生式，则标记为A A的内部结的内部结 点从左到右有子结点点从左到右有子结点X1X1，X2X2，XnXn；若若AA，则，则必是叶结点，且它是必是叶结点，且它是A A的唯一子结点。的唯一子结点。例：例：E E E+EE id+EE id+E (E )E

11、id+E (E )E *EE id+E (E )E *E id EE id+E (E )E *E id id语法树：语法树：根与内部结点由表达式中的操作符标记；根与内部结点由表达式中的操作符标记；叶子由表达式中的操作数标记；叶子由表达式中的操作数标记；用于改变运算优先级和结合性的括弧，被隐含在语法树用于改变运算优先级和结合性的括弧，被隐含在语法树的结构中；的结构中；例：例：语法树只反映句型的结构，忽略了推导句型的过程。语法树只反映句型的结构，忽略了推导句型的过程。+id *id id二义性与二义性的消除二义性与二义性的消除定义：若文法定义：若文法G对同一个句子产生不止一棵分析树，对同一个句子产

12、生不止一棵分析树，则称则称G是二义的。是二义的。例：例：id+id*id原因是文法中缺少对文法符号优先级和结合性的规定原因是文法中缺少对文法符号优先级和结合性的规定E id +EE *E id idE E *EE +E id id id自上而下语法分析自上而下语法分析自上而下语法分析法：从文法开始符号出发自上而下语法分析法：从文法开始符号出发,找最左推找最左推导；或从根开始导；或从根开始,构造推导树。构造推导树。1.回溯分析法：回溯分析法：(不确定性不确定性)例：例：SxAy Aaba 输入串为输入串为xay,说明分析过程说明分析过程S x A ySa b x A ySa x A y2.存在的

13、问题存在的问题(1)回溯回溯公共左因子的存在公共左因子的存在 A1|2(2)左递归左递归 AA 或或 AA提取左因子，以避免回溯；提取左因子，以避免回溯；消除左递归，以避免陷入死循环。消除左递归，以避免陷入死循环。消除左递归消除左递归(1)直接左递归的消除直接左递归的消除 AA 改写为：改写为：AA AA一般地一般地 AA1|A2|Am|1|2|n （i，j不以不以A开头）开头）改写为：改写为：A1A|2A.|nA A 1A|2A.|mA|例：消除直接左递归例：消除直接左递归 EE+T|T EE+T|T TT*F|F TT*F|F F(E)|-F|id F(E)|-F|id消除后消除后 ETE

14、 ETE E+TE|E+TE|TFT TFT T*FT|T*FT|F(E)|-F|id F(E)|-F|id(2)间接左递归的消除间接左递归的消除例：例：SQcc QRbb RSaa 按按S,Q,R排列排列,或或R,Q,S排列排列按按S、Q、R排列排列,代入后代入后 按按R、Q、S排列排列,代代入后入后 SQcc RSaa QRbb QSababb R Rbcabcacaa SSabcabc bcc 消除消除R中的直接左递归中的直接左递归 消除消除S中的直接左递中的直接左递归归 R bcaRcaRaR SabcSbcScS R bcaR SabcS 提取左因子提取左因子(回溯回溯)A A1 1

15、|2 2|.|.|n n|改写为：改写为：AA|AA|A A 1 1|2 2|.|.|n n 例：例：SiCtS|iCtSeS|aSiCtS|iCtSeS|a Cb Cb消除左因子：消除左因子：SiCtSS|a SiCtSS|a SeS|SeS|Cb Cb 当一个文法中既有左递归又含左因子时，先消除左递归。当一个文法中既有左递归又含左因子时，先消除左递归。文法文法3.2:ETEETEE+TE|E+TE|TFTTFTT*FT|T*FT|F(E)|iF(E)|i 输入串输入串i*(i+i)i*(i+i)的语法分析的语法分析递归下降程序递归下降程序:void match(token t)if(loo

16、kahead=t)lookahead=nexttoken;else error();void E()T();E();void E()if(lookahead=+)match(+);T();E();void T()F();T();void T()if(lookahead=*)match(*);F();T();递归下降程序递归下降程序:void F()if(lookahead=i)match(i);else if(lookahead=()match();E();if(lookahead=)match();else error();else error();#E#ET#ET#ETF#ETF#ETE#

17、ETET#ETETF#ETET#ETE#ETET#ETETF#ETET#ETE#ET#E#匹配匹配*匹配匹配()匹配匹配i匹配匹配i匹配匹配匹配匹配+匹配匹配i匹配匹配匹配匹配匹配匹配匹配匹配预测分析器预测分析器(LL(1)分析法分析法)构成：下推栈构成：下推栈,预测分析表预测分析表,控制程序控制程序,输入串输入串分析方法：分析方法：初始时初始时,和开始符入栈和开始符入栈,输入指针指向第一个符号输入指针指向第一个符号,然后根据下推栈栈顶符然后根据下推栈栈顶符x和当前输入符和当前输入符a进行工作进行工作:x=a=,成功成功 x=a,匹配匹配 xN,查预测分析表查预测分析表构造预测分析表构造预测分

18、析表1 1FIRSTFIRST集集(1)(1)定义：文法符号序列定义：文法符号序列A A的的FIRSTFIRST集合集合 FIRST(A)FIRST(A)a|Aa|A a.,aT,a.,aT,若若A A,则则FIRST(A)FIRST(A)若若x x是终结符，则是终结符，则FIRST(x)=x;FIRST(x)=x;若若A A是非终结符且是非终结符且AA，则加入，则加入到到FIRST(A);FIRST(A);若若A A是非终结符且是非终结符且AYAY1 1Y Y2 2YYk k,并且并且Y Y1 1Y Yj-1j-1都能推导都能推导出出,则对所有则对所有j(1jk),j(1jk),若若aFIR

19、ST(YaFIRST(Yj j),),加入加入a a到到FIRST(A)FIRST(A)。*例：例：LE;L|LE;L|ETE ETE E+TE|-TE|E+TE|-TE|TFT TFT T*FT|/FT|modFT|T*FT|/FT|modFT|F(E)|id|num F(E)|id|num 非终结符的非终结符的FIRSTFIRST集集 FIRST(F)=(,id FIRST(F)=(,id，numnum FIRST(T)=*,/,mod FIRST(T)=*,/,mod，FIRST(T)=FIRST(F)=(,id FIRST(T)=FIRST(F)=(,id，numnum FIRST(E

20、)=+,-,FIRST(E)=+,-,FIRST(E)=FIRST(T)=(,id FIRST(E)=FIRST(T)=(,id，numnum FIRST(L)=,(,id FIRST(L)=,(,id，numnum1 1FOLLOWFOLLOW集集(1)(1)定义：非终结符定义：非终结符A A的的FOLLOWFOLLOW集合集合 FOLLOW(A)FOLLOW(A)a|Sa|SAa,aT,Aa,aT,若若S SA,A,则则#FOLLOW(A),#FOLLOW(A),其中其中S S为开始符号为开始符号#FOLLOW(S);#FOLLOW(S);ABC:ABC:将将FIRST(C)-FIRST(

21、C)-加入加入FOLLOW(B);FOLLOW(B);ABAB或或ABCABC且且FIRST(C),FIRST(C),则将则将FOLLOW(A)FOLLOW(A)加加入入FOLLOW(B)FOLLOW(B)。*例：例：LE;L|LE;L|ETE ETE E+TE|-TE|E+TE|-TE|TFT TFT T*FT|/FT|modFT|T*FT|/FT|modFT|F(E)|id|num F(E)|id|num 非终结符的非终结符的FOLLOWFOLLOW集集 FOLLOW(L)=#FOLLOW(L)=#FOLLOW(E)=;,)FOLLOW(E)=;,)FOLLOW(E)=;,)FOLLOW(

22、E)=;,)FOLLOW(T)=+,-,;,)FOLLOW(T)=+,-,;,)FOLLOW(T)=+,-,;,)FOLLOW(T)=+,-,;,)FOLLOW(F)=*,/,mod,+,-,;,)FOLLOW(F)=*,/,mod,+,-,;,)构造算法：构造算法：对每个产生式对每个产生式AA对对FIRST(A)FIRST(A)的每个终结符的每个终结符a a，加入，加入到到MA,aMA,a；若若FIRST(A),FIRST(A),则对则对FOLLOW(A)FOLLOW(A)的每个终结符的每个终结符b b（包括（包括#），），加入加入到到MA,bMA,b；MM中其他没有定义的条目均为中其他没有

23、定义的条目均为errorerror。ididnumnum+-*/modmod();#L LE;LE;LE;LE;LE;LE;LE ETETETETETETEEE+TE+TE-TETET TFTFTFTFTFTFTTT*FT*FT/FT/FTmodFTmodFTF Fididnumnum(E)(E)例：例：id+id*id;的分析过程的分析过程步骤步骤下推栈下推栈输入串输入串动作动作查分析表查分析表1 1#L#Lid+id*id;#id+id*id;#pop(L),push(E;L)pop(L),push(E;L)LE;LLE;L2 2#L;E#L;Eid+id*id;#id+id*id;#po

24、p(E),push(TEpop(E),push(TE)ETEETE3 3#L;ET#L;ETid+id*id;#id+id*id;#pop(T),push(FTpop(T),push(FT)TFTTFT4 4#L;ETF#L;ETFid+id*id;#id+id*id;#pop(F),push(id)pop(F),push(id)FidFid5 5#L;ETid#L;ETidid+id*id;#id+id*id;#pop(id),next(ip)pop(id),next(ip)匹配匹配idid6 6#L;ET#L;ET+id*id;#+id*id;#pop(T)pop(T)TT7 7#L;E#

25、L;E+id*id;#+id*id;#pop(E),push(+Tpop(E),push(+TE)E)E+TEE+TE8 8#L;ET+#L;ET+id*id;#+id*id;#pop(+),next(ip)pop(+),next(ip)匹配匹配+9 9#L;ET#L;ETid*id;#id*id;#pop(T),push(FTpop(T),push(FT)TFTTFT1010#L;ETF#L;ETFid*id;#id*id;#pop(F),push(id)pop(F),push(id)FidFid1111#L;ETid#L;ETidid*id;#id*id;#pop(id),next(ip)

26、pop(id),next(ip)匹配匹配idid步骤步骤下推栈下推栈输入串输入串动作动作查分析表查分析表1212#L;ET#L;ET*id;#*id;#pop(T),push(*Fpop(T),push(*FT)T)T*FTT*FT1313#L;ETF*#L;ETF*id;#*id;#pop(*),next(ip)pop(*),next(ip)匹配匹配*1414#L;ETF#L;ETFid;#id;#pop(F),push(id)pop(F),push(id)FidFid1515#L;ETid#L;ETidid;#id;#pop(id),next(ip)pop(id),next(ip)匹配匹配

27、idid1616#L;ET#L;ET;#;#pop(T)pop(T)TT1717#L;E#L;E;#;#pop(E)pop(E)EE1818#L;#L;#;#pop(;),next(ip)pop(;),next(ip)匹配；匹配；1919#L#L#pop(L)pop(L)LL2020#正确结束正确结束LL(1)LL(1)文法文法例：例：SiCtSS|aSiCtSS|a SeS|SeS|Cb CbFIRST(C)=b FIRST(S)=e,FIRST(C)=b FIRST(S)=e,FIRST(S)=i,aFIRST(S)=i,aFOLLOW(S)=e,#FOLLOW(S)=e,#FOLLOW(

28、C)=tFOLLOW(S)=e,#FOLLOW(S)=e,#FOLLOW(C)=t任何二义文法、含左递归和左因子的文法都不是任何二义文法、含左递归和左因子的文法都不是LL(1)LL(1)文法。文法。a ab be ei it t#S SSaSaSiCtSSSiCtSSSSSSSeSeS SSSC CCbCb 一个文法一个文法G G是是LL(1)LL(1)文法，当且仅当文法，当且仅当G G的任何两个产生式的任何两个产生式AA|,|,满足下列条件：满足下列条件：对任何终结符对任何终结符a a，和和不能同时推导出以不能同时推导出以a a开始的串；开始的串；和和最多有一个可以推导出最多有一个可以推导出

29、；若若,则则不能推导出以不能推导出以FOLLOW(A)FOLLOW(A)中的终结符开始的任中的终结符开始的任 何串。何串。*自下而上语法分析法：从输入串开始自下而上语法分析法：从输入串开始,归约归约,直至直至 文法开始符。文法开始符。定义：若定义：若 是文法是文法G G的一个句子的一个句子,序列序列 n n,n-1n-1,0 0满足下述条件时称为最左规约（满足下述条件时称为最左规约（规范归约规范归约）。）。n n=;=;0 0为文法的开始符为文法的开始符,即即 0 0=S;=S;对对任任何何i(0ii(0in),n),i-1i-1是是从从 i i经经把把句句柄柄替替换换为为相相应产生式的左部非

30、终结符而得到的。应产生式的左部非终结符而得到的。自下而上语法分析自下而上语法分析例例1:G(E)EE+TT TT*FF F(E)i i+i*i的规范规约过程的规范规约过程i+i*iE+i*iE+T*iE+T*FE+TEEET+FTii*FTiF例例2:G(S)SaAcBe AAb|b Bd abbcde的规范规约过程的规范规约过程Sa A c B e A b d babbcdeaAbcdeaAcdeaAcBeS算符优先分析法算符优先分析法 适合于分析程序语言中的各类表达式。适合于分析程序语言中的各类表达式。所谓算符优先分析所谓算符优先分析,就是依照算术表达式的四则运就是依照算术表达式的四则运算

31、过程来进行语法分析算过程来进行语法分析,预先规定终结符之间的优先关预先规定终结符之间的优先关系和结合性质系和结合性质,以确定句型的以确定句型的”可规约串可规约串”来进行规约。来进行规约。它不是一种规范规约它不是一种规范规约,在整个过程中起决定作用的在整个过程中起决定作用的是相继两个终结符的优先关系。是相继两个终结符的优先关系。1.算符文法算符文法 上下文无关文法上下文无关文法G,没有形如没有形如P或或P.QR.的的产生式产生式,则称则称G为为算符文法算符文法2.终结符之间的优先关系终结符之间的优先关系 对算符文法对算符文法G,a,bT 定义定义(1)a=b:G中有中有P.ab.或或P.aQb.

32、的产生式的产生式(2)ab:G中有中有P.Rb.且且R.a或或R aQ3.算符优先文法算符优先文法 若算符文法若算符文法G的任何终结符的任何终结符a,b之间的优先关系至多有之间的优先关系至多有=、=算符优先关系表算符优先关系表从上表可知从上表可知:(1)相同终结符之间的优先关系未必是相同终结符之间的优先关系未必是=(2)有有aa(3)a、b之间未必一定有优先关系之间未必一定有优先关系 故故=、不同于关系运算符不同于关系运算符“等于等于”、“小于小于”、“大于大于”算符优先分析方法算符优先分析方法 设设a a为栈顶终结符为栈顶终结符初始化初始化:#栈栈读一符号读一符号ba=b=#ab归约最左素短

33、语归约最左素短语,最左素短语出栈最左素短语出栈,左部符号入左部符号入栈栈结束结束b入栈入栈出错出错YNYYNNi+i*ii+i*i的算符优先分析过程的算符优先分析过程步骤步骤1234567891011下推栈下推栈输入串输入串动作动作#i+i*i#+,用用Fi归约归约#F+i*i#+,移进移进+#F+i*i#+*,用用Fi归约归约#F+F *i#+*,移进移进*#F+F*i#*#,用用Fi归约归约*#,用用TT*F归约归约+#,用用EE+T归约归约结束结束#F+F*F#F+T#ELR分析法分析法LR(K)分析法：分析法：自下而上的自下而上的LR分析法是指从左向右扫描输入串分析法是指从左向右扫描输

34、入串,每每次分析由分析栈中符号及向前搜索次分析由分析栈中符号及向前搜索K个输入符号个输入符号,以确以确定作为产生式右部的短语定作为产生式右部的短语(句柄句柄)是否已在分析栈的栈是否已在分析栈的栈顶形成顶形成,从而决定应采取的动作。这种分析方法称为从而决定应采取的动作。这种分析方法称为LR(K)分析法。一般只考虑分析法。一般只考虑K1的情况。的情况。识别活前缀识别活前缀活前缀：规范句型的不含句柄之后任何符号的一个前缀。活前缀：规范句型的不含句柄之后任何符号的一个前缀。亦即亦即:若若AA是文法的一个产生式是文法的一个产生式,且有且有S SA A则则的任何前缀都是规范句型的任何前缀都是规范句型的活前

35、缀。的活前缀。项项项项 目目目目:在在产产生生式式右右部部添添加加一一个个圆圆点点,如如AA、AA 、AA 归约项目：形如归约项目：形如AA 移进项目：形如移进项目：形如AA aa，a a T T待约项目：形如待约项目：形如AA BB，B B N N接受项目：形如接受项目：形如SS ，S S为开始符为开始符拓拓广广文文法法：增增加加产产生生式式SSSS，从从而而SSSS成成为为唯唯一一的的接接受受项项目。目。*识别活前缀的识别活前缀的DFA项目集项目集I I的闭包的闭包closure(I)closure(I)：对对i i I,I,都有都有i i closure(I);closure(I);若若

36、A AB Bclosure(I),closure(I),B B为为非非终终结结符符，且且B B为为文文法法G G的一个产生式的一个产生式,则则B B closure(I)closure(I)；重复重复直至直至closureclosure不再增大。不再增大。定义：对所有属于项目集定义：对所有属于项目集I I、且形如、且形如 A AX X 的项目，令的项目，令 XNT,XNT,则则goto(I,X)goto(I,X)是所有形如是所有形如 A AX X 的项目。的项目。LR分析器组成：分析栈分析器组成：分析栈,控制程序控制程序,分析表分析表,输入串输入串输入串输入串分析栈分析栈驱动程序驱动程序输出输

37、出actionactiongotogoto分析表分析表s s0 0.s sm-1m-1s sm ma a1 1a ai i#.分析栈：分析栈：存放状态存放状态;初始时初始时,置初始状态置初始状态s0;栈里的每一状态栈里的每一状态概括了从分析开始到某一时刻已进行的分析工作。概括了从分析开始到某一时刻已进行的分析工作。分析表：分析表：由由actions,a和和gotos,A两个子表组成。两个子表组成。actions,a定义了在状态定义了在状态s下下,当前输入符号为当前输入符号为a时时应应 采取的分析动作：移进采取的分析动作：移进,归约归约,接受接受,出错。出错。goto表是一个状态及非终结符的二维

38、矩阵表是一个状态及非终结符的二维矩阵,gotos,A定义了在状态定义了在状态s下下,面对文法符号面对文法符号A时的时的状态转换。状态转换。C=IC=I0 0,I,I1 1,I,In n,I,Ii i对应状态对应状态i,Ii,I0 0=closure(S=closure(SS)S)为唯一初态为唯一初态;对每个对每个I Ii i,n若若A Aa aI Ii i,且且go(go(I Ii i,a,a)=)=I Ij j,则则actioni,aactioni,a=sjsj;n若若A AI Ii i,A A为第为第j j个产生式个产生式,则则actioni,aactioni,a=rjrj;n若若SSS

39、SI Ii i,则则actioniactioni,=acc;=acc;若若go(Igo(Ii i,A,A)=)=I Ij j,则则gotoi,Agotoi,A=j;=j;凡不能用规则凡不能用规则、登记的表项均为登记的表项均为“错误错误”。LR(0)分析表的构造分析表的构造 假定假定LR(0)LR(0)文法规范族的每个项目集不含冲突项目，按文法规范族的每个项目集不含冲突项目，按下述方法构造的分析表是一张下述方法构造的分析表是一张LR(0)LR(0)表，使用表，使用LR(0)LR(0)表的分析表的分析器叫做器叫做LR(0)LR(0)分析器。分析器。例：试构造该文法的例：试构造该文法的LR(0)LR

40、(0)分析表分析表 GS:SBB GS:SBB BaB|b BaB|b拓广为：拓广为：GS:(0)SSGS:(0)SS (1)SBB (1)SBB (2)BaB (2)BaB (3)Bb (3)Bb构造构造GSGS的的LR(0)LR(0)项目集规范族：项目集规范族：计算初态，计算初态，I0I0closure(S.S)closure(S.S)I0 I0：S.S S.S S.BB S.BB B.aB B.aB B.b B.b计算初态下的每个可能状态转移计算初态下的每个可能状态转移closure(goto(I0,x)closure(goto(I0,x)I1 I1：SS.SS.I2 I2：SB.B I

41、3 SB.B I3：Ba.B I4 Ba.B I4：Bb.Bb.B.aB B.aB B.aB B.aB B.b B.b B.b B.b计算下一状态的每个可能状态转移计算下一状态的每个可能状态转移closure(goto(Ii,x)closure(goto(Ii,x)I5 I5：SBB.SBB.I6 I6：BaB.BaB.构造构造DFA:DFA:S SI0I0：S.S S.S S.BB S.BB B.aB B.aB B.b B.bI1I1：SS.SS.I2I2：SB.B SB.B B.aB B.aB B.b B.b I3I3：Ba.B Ba.B B.aB B.aB B.b B.bI4I4：Bb.

42、Bb.I5I5：SBB.SBB.I6I6：BaB.BaB.B Ba ab bB BB Ba ab ba ab bLR(0)分析表分析表状状态态0123456actiongotoab#SBS3S41accr3r3r32S3S45S3S46r1r1r1r2r2r2例：为文法构造识别活前缀的例：为文法构造识别活前缀的DFADFA。(0)EE (0)EE (1)EE-T (2)ET (1)EE-T (2)ET (3)TT*F (4)TF (3)TT*F (4)TF (5)F-F (6)Fid (5)F-F (6)Fid 计算计算DFADFA初态，初态，I0I0closure(E.E)closure(E

43、.E)I0:I0:E.EE.EE.E-TE.E-TE.TE.TT.T*FT.T*FT.FT.FF.-FF.-FF.idF.idSLR分析表的构造分析表的构造计算初态下的每个可能状态转移计算初态下的每个可能状态转移closure(goto(I0,x)closure(goto(I0,x)E.EE.EE.E-TE.E-TE.TE.TT.T*FT.T*FT.FT.FF.-FF.-FF.idF.idI0I0EE.EE.EE.-TEE.-TE EI1I1ET.ET.TT.*FTT.*FT TTF.TF.F FFid.Fid.I2I2I3I3I4I4ididF-.FF-.FF.-FF.-FF.idF.id-

44、I5I5计算下一状态的每个可能状态转移计算下一状态的每个可能状态转移closure(goto(Ii,x)closure(goto(Ii,x)E.EE.EE.E-TE.E-TE.TE.TT.T*FT.T*FT.FT.FF.-FF.-FF.idF.idI0I0EE.EE.EE.-TEE.-TE EI1I1ET.ET.TT.*FTT.*FT TTF.TF.F FFid.Fid.I2I2I3I3I4I4ididF-.FF-.FF.-FF.-FF.idF.id-I5I5EE-.TEE-.TT.T*FT.T*FT.FT.FF.-FF.-FF.idF.idI6I6-TT*.FTT*.FF.-FF.-FF.i

45、dF.idI7I7*F-F.F-F.I8I8F F-EE-T.EE-T.TT.*FTT.*FT TI9I9*F Fidid-TT*F.TT*F.F F-ididI10I10ididSLRSLR方法：方法：当某个项目集形如当某个项目集形如I=XI=Xb b,A,A,B,B 时时,出现了出现了移进移进-归约冲突归约冲突和和归约归约-归约冲突归约冲突,可用如可用如下方法解决下方法解决,该方法称为该方法称为SLRSLR方法。方法。C=IC=I0 0,I,I1 1,I,In n,I,Ii i对应状态对应状态i,Ii,I0 0=closure(S=closure(SS)S)为唯为唯一初态一初态;对每个对每

46、个I Ii i,n若若A Aa aI Ii i,且且go(Igo(Ii i,a)=I,a)=Ij j,则则actioni,a=sj;actioni,a=sj;n若若A AI Ii i,A A为第为第j j个产生式个产生式,则则任何任何b b FOLLOW(A),FOLLOW(A),actioni,b=rj;actioni,b=rj;n若若SSS SI Ii i,则则actioni,actioni,=acc;=acc;若若go(Igo(Ii i,A)=I,A)=Ij j,则则gotoi,A=j;gotoi,A=j;凡不能用规则凡不能用规则、登记的表项均为登记的表项均为“错误错误”。FOLLOW(

47、E)=-,#FOLLOW(T)=-,*,#FOLLOW(F)=-,*,#状状态态012345678910actiongotoid-*#ETFS4S5123S6accS7r2r4r6S4S5893S4S510S4S5r5r1S7r3r2r4r4r6r6r5r5r1r3r3SLR(1)分析表分析表例：例：idid*id的分析过程的分析过程步骤步骤栈内容栈内容输入串输入串动作动作查分析表查分析表1 1#0#0id-id*id#id-id*id#移进移进s4s42 2#0id4#0id4-id*id#-id*id#归约归约r6(r6(Fid)Fid)3 3#0F3#0F3-id*id#-id*id#归

48、约归约r4(Tr4(TF)F)4 4#0T2#0T2-id*id#-id*id#归约归约r2(Er2(ET)T)5 5#0E1#0E1-id*id#-id*id#移进移进s6s66 6#0E1-6#0E1-6-id*id#-id*id#移进移进s5s57 7#0E1-6-5#0E1-6-5id*id#id*id#移进移进s4s48 8#0E1-6-5id4#0E1-6-5id4*id#*id#归约归约r6(r6(Fid)Fid)9 9#0E1-6-5F8#0E1-6-5F8*id#*id#归约归约r5(r5(F-F)F-F)1010#0E1-6F3#0E1-6F3*id#*id#归约归约r4(

49、Tr4(TF)F)1111#0E1-6T9#0E1-6T9*id#*id#移进移进s7s7步骤步骤栈内容栈内容输入串输入串动作动作查分析表查分析表1212#0E1-6T9*7#0E1-6T9*7id#id#移进移进s4s41313#0E1-6T9*7id4#0E1-6T9*7id4#归约归约r6(r6(Fid)Fid)1414#0E1-6T9*7F10#0E1-6T9*7F10#归约归约r3(Tr3(TT*F)T*F)1515#0E1-6T9#0E1-6T9#归约归约r1(Er1(EE-T)E-T)1616#0E1#0E1#接收接收accacc二义文法不是二义文法不是SLR(1)SLR(1)文

50、法文法例：例：GS:GS:(0)SS (0)SS (1)SL=R (1)SL=R (2)SR(2)SR(3)L*R(3)L*R(4)Li(4)Li(5)RL(5)RL证明该文法既不是证明该文法既不是LR(0)LR(0)文法，也不是文法，也不是SLR(1)SLR(1)文法。文法。LR(0)LR(0)项目集规范族项目集规范族:I0:I0:S.SS.S S.L=R S.L=R S.R S.R L.*R L.*R L.i L.i R.L R.L I1:I1:SS.SS.I2:I2:SL.=R SL.=R RL.RL.I3:I3:SR.SR.I4:I4:L*.R L*.R R.L R.L L.*R L.