文法与语法分析(下).ppt

第04章 文法与语法分析,主要内容： LR(1)分析方法 LALR(1)分析方法 进行语法分析的几种方法 语法错误处理,4.5.6 LR(1)方法,前两种的不足之处： 1）LR(0)方法：不依赖输入流，直接判定归约，容易出现冲突。 2）SLR(1)方法：简单的把非终极符的follow集做为可归约的依据，不区分相同符号的不同出现，故并不精确。 LR(1)基本思想：对非终极符的每个不同出现求其后继符集（展望符集Reducelookup），故减少了移入/归约冲突。,例：下列文法的部分LRSM如右图： Z E E (L,E) E S L L,E L E S id S (S),注：因为： Follow(E)=)、#Follow(L)=)、#、, 所以，状态3有冲突 ，故不能用SLR(1)方法。,为什么要LR(1)分析？,LR(1)分析中的相关定义,LR(1)归约活前缀：定义为三元组(,p,ss)形式，其中是活前缀，p是产生式号，ss是展望符集。 LR(1)归约活前缀定理：设 ZS# 为增广产生式，则定理可描述如下： 1 (S,0,#)是LR(1)归约活前缀； 2 若(A,p,ss)是LR(1)归约活前缀，A是Q产生式，First2(,ss)=ss1，则(,Q,ss1)也是LR(1)归约活前缀。 LR(1)项目：定义为A,ss，其中A是项目的心，而ss为展望符集。,LR(1)项目的产生途径： 1 发射：AX,a AX,a 2 扩展：AB,a B,b 其中B是产生式 , bFirst(a) 展望符的计算原理：设ZS为增广产生式，#为结束符，(A)为A的后继符，则： 1 (Z)=# 2 若(A)=ss，AB，则 (B)=First2(,ss) 其中，当时，First2(,ss)=First()- ss；否则First2(,ss)=First(）,shift函数：假设给定项目集IS，则： shift(IS)=AX,a|AX,aIS 它表示IS中“”右移一位所得的项目集。 LR(1)项目集的闭包：假设IS是LR(1)项目集，则称下面close_lr(IS)为IS的闭包集： 1 ISclose_lr(IS)； 2 若AB,ssclose_lr(IS), BG, First2(,ss)=ss1， 则B,ss1close_lr(IS)； goto函数：假设给定项目集IS，则： goto(IS,X)=close_lr(shift(project(IS,X) 它表示IS状态的X输出边所指向状态的项目集闭包。,例：已知文法GZ： Z S , S L= R , S R , L aR , L b , R L 设：IS = ZS ，# 则： close_lr ( IS ) =ZS ，# ，SL=R，# ， SR ，# ，LaR ， = ， Lb ，= ，RL ，# ,LR(1)状态机的构造,1初始化：ss0=close(ZS#,); AllStateSet=ss0; UnHandledStateSet=ss0; 2判断结束：若UnHandledStateSet空，则结束，否则转3； 3从UnHandledStateSet选择一个状态ss，并做对每个符号a 做下面动作： 1) 求ss1 = goto(ss,a)，若ss1空，则TTss,a=空； 2) 否则，检查在AllStateSet中有无ss1; 若无，则把ss1追加到UnHandledStateSet和 AllStateSet中，并构造ss(a)ss1； 否则，构造ss(a)ss1； 4从UnHandledStateSet中删除状态ss，并转向步骤2。,L,a,a,a,LR(1)分析表的构造,Action表 Action(S,a)= Shift j 当S有到Sj的a输出边 Action(S,a)= Reduce p .当S是p-归约状态 Action(S,#)= Accept 当S是接受状态 Action(S,a)= Error .其他情形 GOTO表 Goto(S,A)= S 当S有到S的A输出边，A为非终极符,例：上例自动机的LR(1)分析表与分析过程,状态栈 符号栈 输入串 Action GoTo 0 # aab=b# S5 0,5 # a ab=b# S5 0,5,5 #aa b=b# S4 0,5,5,4 # aab =b# R5 11 0,5,5,11 #aaL =b# R6 10 0,5,5,10 #aaR =b# R4 11 0,5,11 #aL =b# R6 10 0,5,10 #aR =b# R4 2 0,2 #L =b# S6 0,2,6 #L= b# S12 0,2,6,12 #L=b # R5 9 0,2,6,9 #L=L # R6 7 0,2,6,7 #L=R # R2 1 0,1 #S # Acc,例： 串aab=b的分析过程。,ZS SL=R SR LaR Lb RL,例：设文法GS为： SAS | A aA | b 证明GS是LR(1)文法；构造它的LR(1)分 析表；给出符号串abab#的分析过程。,4.5.7 LALR(1)方法,特点： 1）它具有SLR(1)的状态数少的优点和LR(1)的适用范围广的优点； 2）LALR(1)方法的功能介于SLR(1)和LR(1)之间； 3）LALR(1)状态机的状态个数和LR(0)状态机的状态个数相同，而其展望符则即不采用SLR(1)的Follow集方法，也不采用LR(1)的完全精确法。,LALR(1)的思想来源,来源是因为： 1）LR(1)状态机和LR(0)状态机从它们所表示的自动机角度来看是等价的 ； 2）自动机可通过合并等价状态来减少状态个数。 LALR(1)状态机的定义方式： 1）用LR(1)状态机来定义； 2）用LR(0)状态机来定义。,相关的术语,项目的心：假设A, b是LR(1)项目，则称其中的LR(0)项目部分A为该项目的心。用Core(S)表示状态S的心。 同心状态：如果LR(1)状态机中的两个状态S1和S2具有相同的心，即Core(S1)=Core(S2)，则称它们为同心状态。用SameCoreState( S)表示与S同心的状态集，用Merge(S1, S2)表示S1与 S2中同心状态项目的合并。,例：假设在LR(1)状态机中有状态S1和S2： S1 = A,a1，B,b1, S2 = A,a2，B,b2 Core(S1)= A, B , Core(S2)= A, B ， SameCoreState( S1 )= S 1, S2 Merge(S1, S2) = A, a1, a2， B, b1 ,b2,LALR(1)状态机的构造方法,有两种方法： 1）先构造LR(1)状态机，后构造LALR(1)状态机，按LR(1)状态机的方式构造，但发现同心状态时不产生新状态，而是采用合并状态的方法。 2）先构造LR(0)状态机，而后用传播方式求出每个项目的展望符集。,由LR(1)构造LALR(1)的算法,初始化：LR_State:=LR(1)_DFA_State；LALR_State:=； 构造LALR(1)的状态集： while (LR_State ) ssc=SameCoreState(OneStateOf(LR_State)； ssm=Merge(ssc); LR_State =LR_State - ssc； LALR_State=LALR_State ssm； 确定LALR状态给的转向边：对于SS1,SS2 LALR_State，当存在S1SS1和S2SS2，使得S1 (a) S2 (LR(1)状态机)，则令在LALR(1)_DFA中有边： SS1 (a) SS2 。 确定LALR的初始和终止状态：假设SSLALR_State，SSS,若SLA_StartState，则SS为初始状态，若SLA_FinishState，则SS为终止状态。,例：p128图4.5.28变为p131图4.5.31,方法：1）合并同心集；2）画出自动机。,注：LALR(1)自动机见p131,LALR(1)分析表的构造,Action表 Action(S,a)= Shift j 当S有到Sj的a输出边 Action(S,a)= Reduce p .当S包含p-归约状态 Action(S,#)= Accept 当S包含接受状态 Action(S,a)= Error .其他情形 GOTO表 Goto(S,A)= S 当S有到S的A输出边，A为非终极符,展望符传播算法： 1构造LR(0)状态机时，对于每个项目(Si,Ij)构造其传播表。 2初始化：令所有网点N:(P,i,L)的展望符集L为。 3计算自生展望符： 顺次扫描下一项目(S ,I ) ； 若AX,L(发射)AX,L ,则把L追加到L； 若AD,L(扩展)D,L ,则把First(L)追加 到L,其中若L=a1,a2,an,则有 First(L)= First(a1)First(a2)First(an) ； 4重复上述过程，直至全扫描完为止。,LALR(1)的传播构造方法,带传播的LR(0)状态机,4.5.8 二义性文法的处理,任何语法分析方法都拒绝二义性，会引 起分析动作的不确定。 解决二义性的方法： 改变文法，消除二义性； 增加额外的规则。 功能：有时利用二义性能简化语法分析。,例1：条件语句定义 i S if E then S else S j S if E then S 例2：表达式文法 E E + E E E * E E id E ( E ),4.5.9 简单优先分析方法,特点： 1）一种shift-reduce分析方法； 2）根据文法符号的优先关系确定句柄。 文法符号的优先关系的确定。,简单优先分析中的三种关系,X Y ：当且仅当存在一个产生式AXY X Y ：当且仅当存在一个产生式AXB 并有B+ Y 。 X Y ：当且仅当存在一个产生式ABY 并有B+ X 。 如何确定两个文法符号之间的优先关系？,三种关系的计算方法,FIRST(B) =X | B + X ，X(VNVT) LAST(B) =X | B + X ，X(VNVT) X Y ：当且仅当存在一个产生式AXB 并有 YFIRST(B) 。 X Y ：当且仅当存在一个产生式ABY 并有 XLAST(B) 。 文法G为简单优先文法如果满足： 对于任意两个语法符号X和Y，至多成立一种 优先关系； 任意两个产生式都具有不同的右部。,例： Z bMb M a M (L L Ma),简单优先分析算法要点,找第一个使SjSj+1的Sj 从Sj开始往前(左)找第一个使Si-1Si的Si 用SiSi+1Sj去查产生式的右部，并用相应的左部符号代替句柄SiSi+1Sj (归约) 。 重复上述过程，直至输入符结束。如果归约出文法的开始符号则成功，否则失败。,简单优先分析实例,文法Z： Z bMb M a M (L L Ma),第四章 总结,上下文无关文法(CFG) ： (VN,VT,S,P) 语法分析树：二义性文法，句柄。 文法分析算法：三个集合的定义及求法。 语法分析作用：目的是判定输入串是否为文法所接受的语言。,自顶向下分析： 思想：从文法开始符出发，适当选择产生 式，力图推导出输入串。 关键问题：产生式的选择。 主要方法： 1）递归下降法 2）LL(1)分析方法 等价变换:消除公共前缀，消除左递归。,分析条件 分析方法 分析过程,自底向上分析： 思想：从输入串出发，从左到右进行归约， 直至归约出文法的开始符。 关键问题：何时归约、归约产生式的选择。 主要分析方法 1）LR分析方法： LR(0) SLR(1) LR(1) LALR(1) 2）简单优先分析方法 ：优先关系矩阵。,LRSM的构造（展望符的计算）； 判断分析条件； 构造分析表； 分析过程；,LR分析方法的比较,状态数： LR(0)=SLR(1)=LALR(1)LR(1) 展望符的确定： LR(0)无展望符；SLR(1)利用Follow集解 决冲突；LR(1)针对不同位置确定展望符， LALR(1)利用合并/传播方法计算展望符。 分析能力： LR(0) SLR(1) LALR(1) LR(1) 应