PPT《编译原理与技术》

根据当前栈顶状态S和当前输入符号a,查action表,由action[S,a]决定分析动作:? si-输入符a移入栈顶top(push a );

状态i移入栈顶top(push i).? rj -按第j个产生式(A??)进行归约,首先将从栈顶top往栈中的|?|个状态和|?|个符号(计2*|?|个)弹出分析栈;

设此时栈顶状态为T,再将符号A和状态S'

=GOTO[T,A] 依次移入分析栈(S'

在栈顶top)? acc - 输入串被接受,分析成功!? error - 输入串有错,调错误恢复程序 e.g.21 表达式文法G2的LR分析表 文法G2:(1)E?E + T(2)E?T(3)T?T * F(4)T?F(5)F?( E )(6)F? id e.g.21 表达式文法G2的LR分析表

3 9 s4 s5

6 r6 r6 r6 r6

5 3

2 8 s4 s5

4 r4 r4 r4 r4

3 r2 r2 s7 r2

2 acc s6

1 3

2 1 s4 s5

0 F T E $ ) ( * + id goto action 状态 e.g.21 表达式文法G2的LR分析表(续) r5 r5 r5 r5

11 r3 r3 r3 r3

10 r1 r1 s7 r1

9 s11 s6

8 10 s4 s5

7 F T E $ ) ( * + id goto action 状态 e.g.21 id*(id+id)$的移进-归约分析过程 分析栈 输入串 输出

0 id*(id+id)$ 0id5 *(id+id)$ s5:移进id 0F3 *(id+id)$ r6:F?id 0T2 *(id+id)$ r4:T?F 0T2*7 (id+id)$ s7:移进* 0T2*7(4 id+id)$ s4:移进( 0T2*7(4id5 +id)$ s5:移进id e.g.21 id*(id+id)$的移进-归约分析过程 输入串 输出 分析栈 +id)$ s5:移进id 0T2*7(4id5 +id)$ r6:F?id 0T2*7(4F3 +id)$ r4:T?F 0T2*7(4T2 +id)$ r2:E?T 0T2*7(4E8 id)$ s6:移进+ 0T2*7(4E8+6 0T2*7(4E8+6id5 )$ s5:移进id 0T2*7(4E8+6F3 )$ r6:F?id e.g.21 id*(id+id)$的移进-归约分析过程 输入串 输出 分析栈 0T2*7(4E8+6F3 )$ r6:F?id 0T2*7(4E8+6T9 )$ r4:T?F 0T2*7(4E8 )$ r1:E?E+T 0T2*7(4E8)11 $ s11:移进) 0T2*7F10 $ r5:F?(E) 0T2 $ r3:T?T*F 0E1 $ r2:E?T 0E1 $ acc 活前缀(viable prefix)是规范(右)句型的前缀,它不包含句柄后的任何符号(即活前缀的长度不会超过句柄的最右端).若A???∈P,有如下规范推导, 则,???的前缀为右句型????的活前缀. 识别活前缀的DFA 活前缀与句柄移进-归约分析过程中,分析栈内的符号串构成活前缀(这表明已扫描过的输入串没有语法错误;

事实上,也只有形成活前缀的符号才会被移入分析栈;

分析的实质就是判断剩余输入串能否继续形成活前缀)? 活前缀不包含或部分包含句柄- 此时期待着 匹配 句柄的输入串并将之移入栈顶;

? ? ? $ bottom ? ? 活前缀与句柄? 活前缀已完全包含句柄- 此时句柄位于栈顶,需要进行归约. ? ? ? $ bottom ? 句柄 A ? ? $ bottom 识别活前缀的DFA LR(0)项目产生式右部加 的左部表示已 看见 (分析识别过)的部分;

而右部则是期望 看到 的部分.如:产生式A???∈P,其LR(0)项目有:A???? 期望看到??产生的串(移进项目) A???? 已分析?期望看到?产生的串(移进项目) A???? ?、?都分析完了 ( 归约项目)特别的,空产生式A?? 的LR(0)项目只有一个: A? ? ( 归约项目) 识别活前缀的NFA 拓展文法引入新产生式S'

?S , S'

为新的开始符号NFA的状态:各个产生式的LR(0)项目;

初态:S'

??S 终态(唯一) : S'

?S?NFA的状态转换 i: A???X? j: A??X?? X h: A???B? k: B ?? ? ? ? ? X∈VT?VN B∈VN 采用子集构造法转换上述的NFA到DFA-闭包 closure(I) // I:NFA的状态子集即LR(0)项目集合1)I ? closure(I)2)若项目A???B?∈I,B??∈P,则项目 B??? ∈ closure(I)3)重复2)直至closure(I)不再增大 -转移 goto(I,X)X∈VT?VNJ=goto(I,X)=closure({A??X??| A???X? ∈I}) DFA识别的活前缀-从DFA初态I0到任一状态Ij的路径上所 读过 的符号串?.状态Ij可以指示下一步的 动作 .该DFA识别所有的活前缀;