[理学]第4章 语法分析3_自底向上分析方法LR分析.ppt

* 4.5 LR分析器 每个状态都是识别态，识别的是从初态到该状态的通路上标记的文法符号构成的活前缀 含有规约项目的是可归前缀识别态 含有 “S‘ → S?” 的是“句子”识别态 * 4.5 LR分析器 例：文法G’: (0) S’? S (1) S ? aA  (2) S ? bB (3) A ? cA  (4) A ? d  (5) B ? cB (6) B ? d (0) S’? S (1) S ? aA  (2) S ? bB (3) A ? cA  (4) A ? d  (5) B ? cB (6) B ? d I0:S‘ → ?SS → ?aA S → ?bB I4:A → c?AA → ?cA A → ?d I2:S → a?AA → ?cA A → ?d I5:B → c?BB → ?cB B → ?d I3:S → b?BB → ?cB B → ?d I1:S‘ → S? I8:A → cA? I10:A → d? I6:S → aA? I7:S → bB? I11:B → d? I9:B → cB? b a S c c c c A d d A B d d B * 4.5 LR分析器 初态是活前缀 ε 的有效项目集 活前缀的有效项目集 活前缀 γ 的有效项目集是从初态出发经过 γ 道路所到达的那个状态所代表的项目集 ** 根据当前活前缀的有效项目集确定下一步的分析动作 I0:S‘ → ?SS → ?aA S → ?bB I4:A → c?AA → ?cA A → ?d I2:S → a?AA → ?cA A → ?d I5:B → c?BB → ?cB B → ?d I3:S → b?BB → ?cB B → ?d I1:S‘ → S? I8:A → cA? I10:A → d? I6:S → aA? I7:S → bB? I11:B → d? I9:B → cB? b a S c c c A d d A B d d B (0) S’? S (1) S ? aA  (2) S ? bB (3) A ? cA  (4) A ? d  (5) B ? cB (6) B ? d c 步骤 栈 输入串 ACTION GOTO 1 0 accd$ S2 2 0a2 ccd$ S4 3 0a2c4 cd$ S4 4 0a2c4c4 d$ S10 5 0a2c4c4d10 $ R4 8 6 0a2c4c4A8 $ R3 8 7 0a2c4A8 $ R3 6 8 0a2A6 $ R1 1 9 0S1 $ Acc (0) S’? S (1) S ? aA  (2) S ? bB (3) A ? cA  (4) A ? d  (5) B ? cB (6) B ? d 有了识别活前缀的 DFA 可以分析句子： accd = accA = acA = aA = S = S’ * 每个状态识别其左边活前缀 步骤 栈 输入串 动作 1 $ accd$ 移进 2 $ a ccd$ 移进 3 $ a c cd$ 移进 4 $ a c c d$ 移进 5 $ a c c d $ 归约4 6 $ a c c A $ 归约3 7 $ a c A $ 归约3 8 $ a A $ 归约1 9 $ S $ Acc (0) S’? S (1) S ? aA  (2) S ? bB (3) A ? cA  (4) A ? d  (5) B ? cB (6) B ? d accd = accA = acA = aA = S = S’ * 4.5 LR分析器 有了识别活前缀的 DFA 可以分析句子： 处于含有移进项目的状态可移进（句子中下一个符号为 b） 0 α ? b * 4.5 LR分析器 含有归约项目（A ? β ? ）的状态是可归前缀识别态，处于此状态可归约（用 A ? β） * 含有接受项目的状态是句子识别态，归约后完成分析 0 α ? β * 4.5 LR分析器 处于含有待约项目（B ? α ? A γ ）的状态可以等待归约（用 A ? β），然后状态转移 0 α ? β A * 4.5 LR分析器 构造 LR（0）分析表： 若 goto (Ik，a)= Ij，则 action[k，a]= Sj 若 goto (Ik，A)= Ij，则 goto[k，A]= j 若 Ik 包含 S’→S · ，则 action [k，$] = acc 若 Ik 包含 A→α· ，则 aciton[k，a]= rj，a为任何终结符号或 $，j为产生式 A→α的编号（含有归约项目的状态是可归前缀识别态）