第04章文法和语法分析(下).pptVIP

第04章 文法与语法分析;4.5.6 LR(1)方法; 例：下列文法的部分LRSM如右图： Z ? E E ? (L,E) E ? S L ? L,E L ? E S ? id S ? (S);LR(1)分析中的相关定义;LR(1)项目的产生途径： [1] 发射：[A→??X?,a] ? [A→?X??,a] [2] 扩展：[A→??B?,a] ? [B→??,b] 其中B→?是产生式 , b?First(?a)} 展望符的计算原理：设Z?S为增广产生式，#为结束符，?(A)为A的后继符，则： [1] ?(Z)={#} [2] 若?(A)=ss，A?αB?，则 ?(B)=First2(?,ss) 其中，当???时，First2(?,ss)=First(?)-{?} ∪ss；否则First2(?,ss)=First(?）; shift函数：假设给定项目集IS，则： shift(IS)={[A→?X??,a]|[A→??X?,a]?IS} 它表示IS中“·”右移一位所得的项目集。 LR(1)项目集的闭包：假设IS是LR(1)项目集，则称下面close_lr(IS)为IS的闭包集： [1] IS?close_lr(IS)； [2] 若[A→α?B?,ss]?close_lr(IS), B→??G, First2(β,ss)=ss1， 则[B→??,ss1]?close_lr(IS)； goto函数：假设给定项目集IS，则： goto(IS,X)=close_lr(shift(project(IS,X))) 它表示IS状态的X输出边所指向状态的项目集闭包。;例：已知文法G[Z]： Z → S , S → L= R , S → R , L → aR , L → b , R → L 设：IS = { [Z??S ，#]} 则： close_lr ( IS ) ={[Z??S ，#] ，[S??L=R，#] ， [S??R ，#] ，[L??aR ， =] ， [L??b ，=] ，[R??L ，#] } ;LR(1)状态机的构造 ;0;LR(1)分析表的构造;例：上例自动机的LR(1)分析表与分析过程;例：设文法G[S]为： S?AS | ? A ?aA | b 证明G[S]是LR(1)文法；构造它的LR(1)分 析表；给出符号串abab#的分析过程。;4.5.7 LALR(1)方法;LALR(1)的思想来源;相关的术语; 例：假设在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)状态机的构造方法;由LR(1)构造LALR(1)的算法;例：p128图4.5.28变为p131图4.5.31;LALR(1)分析表的构造;???望符传播算法： [1]构造LR(0)状态机时，对于每个项目(Si,Ij)构造其传播表。 [2]初始化：令所有网点N:(P,i,L)的展望符集L为{}。 [3]计算自生展望符： ?顺次扫描下一项目(S ,I ) ； ?若[A?α·Xβ,L]?(发射)[A?αX·β,L?] ,则把L追加到L?； ?若[A?α·Dβ,L]?(扩展)[D?·π,L?] ,则把First(βL)追加 到L?,其中若L={a1,a2,?,an},则有 First(βL)= First(βa1)∪First(βa2)∪?∪First(βan) ； [4]重复上述过程，直至全扫描完为止。;带传播的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