《语法分析自底向上分析》由会员分享，可在线阅读，更多相关《语法分析自底向上分析（71页珍藏版）》请在金锄头文库上搜索。
1、第五章 语法分析自底向上分析,5.1 基本问题 方法 从句子出发，反复利用产生式做归约 （用产生式的左部替代右部），逐步构造语法分析树，最后得到文法的开始符号 核心 寻找句型与句柄的匹配,分析方法,例 5-1： S a A c B e A A bb B d 分析过程: abbcde aAbcde aAcde aAcBe S,语法分析树的生成,a b b c d e,A,A,B,S,A b,A A b,B d,S a A c B e,句柄：最左直接短语,短语： 设文法T，N， 若 =* 且 =+ ， 则称是句型相对于非终结符的短语若=* 且=，则称是直接短语。,规范归约的定义,设 为文法 G 的
2、句子，称序列 n，.，1，0 为 的规范归约，其中 1) n = 2) 0 = （开始符号） 3) 对每个 i (1 = i B .ab = BaB . = BB . = S .,LR(0) 项目,目的 用产生式中的符号分割位置(有限） 来表示分析位置(无限) 定义 右部某个位置上标有园点的产生式 坐标表示( x, y ) 表示 x 号产生式的 y 号位置的 LR(0) 项目,文法的改写,文法 G 的拓广文法 G： 扩充识别符号 S S （G 的识别符号 ) 例 5-5 0) S S 1) S B B 2) B a B 3) B b,LR(0) 项目例(0,0) S . S (2,1) B a
3、 . B(3,1) B b .,用状态近似表示分析位置,分析位置对应多个 LR(0) 项目，状态应是 LR(0) 项目集合。 状态计算：从一个分割位置出发，考虑向前分析中可能处于同一分析位置的分割位置。, . B ,A,. ,状态的计算,求核心位置的闭包 closure( I ) J := I; repeatJ = J B .A .B J until J 不再扩大 例： closure（(0,0)）= (0,0),(1,0),(2,0),(3,0),状态转移的计算：,确定在某状态遇到一个文法符号后的状态转移目标,A,状态 I,核心 J, . X ,状态转移函数,当前状态 I 文法符号 X 下一状态go( I, X ) = closure( J ) 其中 J = A X. A .X I ,计算状态集合（P105) 即：LR(0)项目集规范族,beginI := closure( S .S ); C := I ;repeatfor C 中的每一状态 I 和每一文法符号 Xif go(I, X)非空并且 go(I,X) 不在 C 中将状态 go(I, X) 加入到 C 中until 不出现新的状态 end.,
