语法(二)介绍.ppt

machunyan 西北工业大学软件与微电子学院 * LR(1)分析表构造规则： 对于文法G[S]，其LR(1)分析表的构造规则为： 1. 对于[A?α.x?, a]?状态i,且GO(i，x)=j. 若x?VT,则置Action[i，x]=Sj 若x?VN ,则置Goto[i，x]=j 2. 对于[A?α. , a]?状态i，若A?α是文法的第j个产生式，则置 Action[i，a]=rj 3.对于[S?α.，$]?状态i，则action[i，$]=acc 4.其它情况置错。 machunyan 西北工业大学软件与微电子学院 * 根据文法A→(A)|a 的 LR(1)项目集合的DFA ，构造其对应的LR(1)分析表: 给产生式编号： (0) A’→A (1) A→(A) (2) A→ a machunyan 西北工业大学软件与微电子学院 * [A’→.A , $] [A→.(A), $] [A→.a, $] 0 [A’→A. , $] 1 A [A→a. , $] 3 a [A→(.A) , $] [A→.(A), )] [A→.a , )] 2 ( [A→(A.), $] 4 A ( [A→(.A) , )] [A→.(A), )] [A→.a , )] 4 a [A→a. , )] 6 a ) [A→(A)., $] 7 ( [A→(A.), )] 8 A ) [A→(A)., )] 9 machunyan 西北工业大学软件与微电子学院 * 状态 Action Goto ( ) a $ A 0 S2 S3 1 1 acc 2 S4 S6 4 3 r2 4 S7 4 S4 S6 8 6 r2 … machunyan 西北工业大学软件与微电子学院 * 用LR(1)分析算法对输入串(a)的分析步骤： 步骤 状态栈S 符号栈X 动作 输入符号 1 0 $ S2 (a)$ 2 02 $( S6 a)$ 3 026 $(a r2(A?a) )$ 4 024 $(A S7 )$ 4 0247 $(A) r1(A→(A)) $ 6 01 $A acc $ machunyan 西北工业大学软件与微电子学院 * (0)E?E (1)E?(L) (2)E? a (3)L?L,E (4)L?E 构造下面文法的LR(1)分析表： 首先构造其LR(1)项目的DFA machunyan 西北工业大学软件与微电子学院 * (0)E?E (1)E?(L) (2)E? a (3)L?L,E (4)L?E [E’? .E , $] [E? .(L) , $] [E?.a , $] 0 E [E’? E.,$] 1 ( 2 [E ? a. , $ ] 3 a L E ( a [E? (.L) , $] …… machunyan 西北工业大学软件与微电子学院 * [E? (.L) , $] [L? .E ，)] [L? .L,E , )] [E? .(L) , )] [E?. a , )] [L? .L,E ，, ] [L? .E ，,] [E? .(L) ， ,] [E?. a ，,] 2 (0)E?E (1)E?(L) (2)E? a (3)L?L,E (4)L?E [E? (.L) ， $] [L? .L,E ， )/,] [L? .E ，)/,] [E? .(L)， )/,] [E?. a ，)/,] 2 machunyan 西北工业大学软件与微电子学院 * (0)E?E (1)E?(L) (2)E? a (3)L?L,E (4)L?E [E’? .E , $] [E? .(L) , $] [E?.a , $] 0 E [E’? E. , $] 1 ( [E? (.L) , $] [L? .L,E , )/,] [L? .E ,)/,] [E? .(L) , )/,] [E?. a , )/,] 2 [E ? a . , $ ] 3 a L [E? (L.) , $] [L? L.,E , )/,] 4 E [L? E.,)/,] 4 ( [E? (.L) , )/,] [L? .L,E , )/,] [L? .E ,)/,] [E? .(L) , )/,] [E?. a , )/,] 6 a [E ? a . , )/, ] 7 ) [E? (L)., $] 8 , [L? L, .E , )/,] [E? .(L) , )/,] [E?. a