Chapter4 Syntax Analysis

Presentation on theme: "Chapter4 Syntax Analysis"— Presentation transcript:

1 Chapter4 Syntax Analysis
语法分析概述 （An overview of parsing） 自顶向下分析（Top-down Parsing） 自底向上分析（Bottom-up Parsing） 算符优先分析 （Operator-precedence Parsing） LR 分析（LR Parser） 2018/9/18

2 4.5 LR分析 LR（k）分析技术： L 指从左至右扫描输入符号串 R 指构造一个最右推导的逆过程（最左归约）
2018/9/18

3 4.5 LR分析 LR分析器的逻辑结构：P217 Fig4.29 input stack output a1 ... ai an $ Sm
Xm Sm-1 Xm-1 . S1 X1 S0 LR Parsing Algorithm stack output Action Table Goto Table 2018/9/18

4 4.5 LR分析 LR分析器的逻辑结构： LR分析程序——固定不变的 分析表——动作表（action）、状态转移表（goto）
栈——状态符号、文法符号 输入缓冲 输出——产生式序列 2018/9/18

5 4.5 LR分析 LR分析器运行： 根据当前栈顶状态符号与输入符号查分析表决定下一步动作
假设当前 （s0X1s1X2s2…Xmsm, aiai+1…an$） 1、action [sm, ai] = shift s （s0X1s1X2s2…Xmsmais, ai+1…an$） 2、action [sm, ai] = reduce A→β （s0X1s1X2s2…Xm-rsm-rAs, aiai+1…an$） 2018/9/18

6 4.5 LR分析 LR分析算法： P 218-219 关键步骤: s : top of stack a : current input
1. If action[s,a]=“accept” halt, accept, success If action[s,a]=“reduce by production A β” do the following: 2a. Pop 2*|β| elements from the stack. 2b. Push A 2c. Push goto[s*,A] If action[s,a]=“shift and goto state s*” Shift; push s* 2018/9/18

7 4.5 LR分析 LR分析算法： LR分析的关键问题是如何构造分析表，不同的构造方法形成不同的分析方法，主要有 LR（0）、SLR、LR（1）、LALR 2018/9/18

8 a b c d e A B S a b c d e A B S 例子： 分析句子：abbcde
文法G[S]： (1) S → aAcBe (2) A → b (3) A → Ab (4) B → d 例子： 分析句子：abbcde a b c d e A B S a b c d e A B S 2018/9/18

9 4.5 LR分析 ACTION GOTO a c e b d $ S A B S2 1 Acc 2 S4 3 S5 S6 4 R2 5 S8
S2 1 Acc 2 S4 3 S5 S6 4 R2 5 S8 7 6 R3 S9 8 R4 9 R1 LR(0)分析表 2018/9/18

10 4.5 LR分析 对 abbcde$ 的分析过程 步骤 栈 输入串 ACTION GOTO 1 abbcde$ S2 2 0a2
abbcde$ S2 2 0a2 bbcde$ S4 3 0a2b4 bcde$ R2 4 0a2A3 S6 5 0a2A3b6 cde$ R3 6 S5 7 0a2A3c5 de$ S8 8 0a2A3c5d8 e$ R4 9 0a2A3c5B7 S9 10 0a2A3c5B7e9 $ R1 11 0S1 Acc 2018/9/18

11 4.5 LR分析 LR分析过程中的性质与特点： 栈中的文法符号串并上剩余的输入串构成一个右句型（规范句型）
当该右句型的句柄出现在栈顶时，归约，否则，移进 栈中的文法符号串是当前句型的前缀，该前缀不包含句型句柄后面的符号，称之为活前缀（Viable Prefixes） 2018/9/18

12 4.5 LR分析 活前缀：上例 aAbcde  , a , aA , aAb 可归前缀：包含完整句柄的活前缀 2018/9/18

13 4.5 LR分析 只要每一时刻栈中的文法符号串是某规范句型的活前缀，则说明已分析的部分是正确的 α β $ α’ S α’ β’ αβ’ 
$ α’ S α’ β’ αβ’ 2018/9/18

14 4.5 LR分析 分析过程可以看作是识别文法规范句型活前缀的过程。
一个文法的规范句型的所有活前缀构成一个语言，而且是正规语言，可以用一个 DFA 来识别 2018/9/18

15 4.5 LR分析  例子： 文法G[S]： (1) S → aAcBe (2) A → b (3) A → Ab (4) B → d 1
* 1 4 S b  a A b 2 3 6 c B e 5 7 9 d 8 2018/9/18

16 4.5 LR分析  每个状态都是活前缀的识别态，双圈状态是可归前缀（句柄）识别态，标识了*的状态是句子识别态 1 4 2 3 6 5 7
S b 每个状态都是活前缀的识别态，双圈状态是可归前缀（句柄）识别态，标识了*的状态是句子识别态  a A b 2 3 6 c B e 5 7 9 d (1) S → aAcBe (2) A → b (3) A → Ab (4) B → d 8 2018/9/18

17 4.5 LR分析 构造识别活前缀的DFA 拓广文法：增加产生式 S’→S，S’作为新的开始符号 文法等价
确保文法的开始符号只在产生式的左部出现 为了在分析过程中区别是归约到了文法的最初开始符号还是产生式右边出现的开始符号 2018/9/18

18 4.5 LR分析 LR（0）项目（item） 在文法产生式右部的适当位置添加圆点构成项目 例： A→XYZ
A→·XYZ A→X·YZ A→XY·Z A→XYZ· 例： A→ε A→· 2018/9/18

19 4.5 LR分析 项目的含义：圆点的左部表示分析过程中的某时刻用该产生式归约时句柄已识别过的部分，圆点右部表示待识别部分
移进项目：A →α· aβ 待约项目：A →α· Bβ 归约项目： A →α· 接受项目： S’ →S · 2018/9/18

20 4.5 LR分析 项目集的闭包（closure） I 在 closure(I) 中
若 A→α·Bβ在 closure(I)，且 B→γ是产生式，将 B→·γ添加到 closure(I) 中 例： 求 closure ( { E’  ·E } ) E’  E E  E + T | T T  T * F | F F  ( E ) | id 2018/9/18

21 4.5 LR分析 goto 函数 goto ( I, X ) goto ( I, X ) = closure (A→αX·β)，其中 A→α·Xβ在 I 中 例： 求 goto ( { E’  E·， E  E ·+ T } , +) E’  E E  E + T | T T  T * F | F F  ( E ) | id 2018/9/18

22 4.5 LR分析 构造规范的 LR（0）项目集族 算法 P 224 C = { closure ( { S’  ·S }) }
C = C ∪ goto ( I, X ) 例子：P 2018/9/18

23 I0: I1: E  ·E E   E· E  ·E + T E  E· + T E  ·T T  ·T * F
F  ·(E) F  ·id I1: E   E· E  E· + T I2: E  T· T T· * F I3: T  F· 2018/9/18

24 I0: I4: E  ·E F  (·E ) E  ·E + T E  ·E + T E  ·T E  ·T
T  ·T * F T  ·T * F T  ·F T  ·F F  ·(E) F  ·(E) F  ·id F  ·id I5: F  id · 2018/9/18

25 I1: E   E· E  E·+ T I6 : EE + ·T T ·T * F T ·F I2: F ·(E) E T·
F ·id I2: E T· TT·*F I7: TT *·F F ·(E) F ·id 2018/9/18

26 I4: I8: F  (·E ) F (E·) E  ·E + T E  E·+ T E  ·T T  ·T *F T  ·F
F  ·id I9: … I10: I11: 2018/9/18

27 4.5 LR分析 构造识别文法所有活前缀的 DFA 项目集作为状态，项目集族作为状态集 goto ( I, X ) 作为状态转换函数
例子：P 226 2018/9/18

28 E + T * I0 I1 I6 I9 to I7 F to I3 ( to I4 id to I5 T * F I2 I7 F F
) I4 I8 I11 + ( T to I6 to I2 F to I3 id id I5 2018/9/18

29 4.5 LR分析 每个状态都是识别态，识别的是从初态到该状态的通路上标记的文法符号构成的活前缀 活前缀的有效项目（Valid items）集
初态是活前缀 ε 的有效项目集 活前缀γ的有效项目集是从初态出发经过γ道路所到达的那个状态所代表的项目集 2018/9/18

30 4.5 LR分析 例：文法G’ S’ E E  T + E E  T T  int * T T  int T  (E)
2018/9/18

31 E ® T + . E E ® .T E ® .T + E T ® .(E) T ® .int * T T ® .int 7 E ® T + E. E T 2 5 + S’ ® E . E ® T. E ® T. + E ( 6 T int E T ® (. E) E ® .T E ® .T + E T ® .(E) T ® .int * T T ® .int 1 T ® int. * T T ® int. T ( S’ ® . E E ® . T E ® .T + E T ® .(E) T ® .int * T T ® .int int int 4 3 int * T ® int * T. E T ® int * .T T ® .(E) T ® .int * T T ® .int T T ® (E.) 8 9 ) T ® (E). 11 10 ( 2018/9/18 (

32 4.5 LR分析 例：文法G’ (0)S’ S (1)S  aA (2)S  bB (3)A  cA (4)A  d (5)B  cB (6)A  d 2018/9/18

33 (0)S’ S (1)S  aA (2)S  bB (3)A  cA (4)A  d (5)B  cB
(6)B  d I4: A → c•A A → •cA A → •d A I8: A → cA• d I10: A → d• c d I2: S → a•A A → •cA A → •d A I6: S → aA• a I0: S‘ → •S S → •aA S → •bB S I1: S‘ → S• I3: S → b•B B → •cB B → •d B b I7: S → bB• d I11: B → d• c d I5: B → c•B B → •cB B → •d c B I9: B → cB• 2018/9/18

34 accd <= acA <= aA <= S <= S’
有了识别活前缀的 DFA 可以分析句子： accd <= acA <= aA <= S <= S’ 步骤 栈 输入串 ACTION GOTO 1 accd$ S2 2 0a2 ccd$ S4 3 0a2c4 cd$ 4 0a2c4c4 d$ S10 5 0a2c4c4d10 $ R4 8 6 0a2c4c4A8 R3 7 0a2c4A8 0a2A6 R1 9 0S1 Acc 2018/9/18

35 4.5 LR分析  有了识别活前缀的 DFA 可以分析句子： 含有归约项目的状态是可归前缀识别态，处于此状态可归约
β α  含有接受项目的状态是句子识别态，归约后完成分析 2018/9/18

36 4.5 LR分析   处于含有移进项目的状态可移进 处于含有待约项目的状态可以等待归约（A  β），然后状态转移 b α β α A
处于含有待约项目的状态可以等待归约（A  β），然后状态转移 β α  A 2018/9/18

37 4.5 LR分析 构造 LR（0）分析表： 若 goto (Ik，a)= Ij，则 action[k，a]= Sj
若 goto (Ik，A)= Ij，则 goto[k，A]= j 若 Ik 包含 A→α· ，则 aciton[k，a]= rj，a为任何终结符号或 $，j为产生式 A→α的编号（含有归约项目的状态是可归前缀识别态） 若 Ik 包含 S’→S · ，则 action[k，$]= acc 2018/9/18

38 (0)S’ S (1)S  aA (2)S  bB (3)A  cA (4)A  d (5)B  cB
(6)B  d I4: A → c•A A → •cA A → •d A I8: A → cA• d I10: A → d• c d I2: S → a•A A → •cA A → •d A I6: S → aA• a I0: S‘ → •S S → •aA S → •bB S I1: S‘ → S• I3: S → b•B B → •cB B → •d B b I7: S → bB• d I11: B → d• c d I5: B → c•B B → •cB B → •d c B I9: B → cB• 2018/9/18

39 LR（0）分析表 a b c d $ S A B S2 S3 1 acc 2 S4 S10 6 3 S5 S11 7 4 8 5 9 r1
ACTION GOTO a b c d $ S A B S2 S3 1 acc 2 S4 S10 6 3 S5 S11 7 4 8 5 9 r1 r2 r3 r5 10 r4 11 r6 2018/9/18

40 4.5 LR分析 项目集合中的冲突 移进-归约冲突 归约-归约冲突 项目集合中若存在冲突，LR（0）分析表中存在多重定义入口
项目集合中同时含有形如 A→α · aβ和 B→γ·的项目 归约-归约冲突 项目集合中同时含有形如 A→α· 和 B→ β· 的项目 项目集合中若存在冲突，LR（0）分析表中存在多重定义入口 2018/9/18

41 文法G’： (0) S’ S (1) S  rD (2) D D,i (3) D  i
I6: D →D,i • 文法G’： (0) S’ S (1) S  rD (2) D D,i (3) D  i I3: S → rD • D →D •,i i I1: S‘ → S • , I5: D → D,•i D S I2: S → r•D D → •D,i D → • i I0: S‘ → • S S → •rD r i I4: D → i • LR(0)分析表 2018/9/18

42 4.5 LR分析 如果文法 G 的规范 LR（0）项目集族中不含有移进-归约冲突和归约-归约冲突，则称文法 G 为 LR（0）文法
构造分析表时没有向前看，或者说向前看了 0 个符号 基于 LR（0）分析表的 LR 分析称为 LR（0）分析 2018/9/18

43 4.5 LR分析 对于规范 LR（0）项目集族中有冲突的项目集合，有的可以通过向前看一个符号（考察当前正在扫描的符号）来解决冲突
当存在冲突时才向前看一个符号，因此是一种简单的 LR（1）分析方法，称为 SLR 分析 2018/9/18

44 4.5 LR分析 解决方法： 假设一个LR（0）项目集规范族中有如下项目集合： {X → α·bβ，A → γ·，B → δ·}
即存在移进-归约冲突和归约-归约冲突 2018/9/18

45 4.5 LR分析 如果FOLLOW（A）∩ FOLLOW（B）∩ {b} =ф，则可以如下来解决冲突（假设当前符号是 a ）：
1、若 a = b，则移进 2、若 a∈ FOLLOW（A），则用产生式 A → γ归约 3、若 a∈ FOLLOW（B），则用产生式 B → δ归约 4、否则，报错 2018/9/18

46 文法G’： (0) S’ S (1) S  rD (2) D D,i (3) D  i
I0: S‘ → • S S → •rD I2: S → r•D D → •D,i D → • i I3: S → rD • D →D •,i I4: D → i • I5: D → D,•i I1: S‘ → S • I6: D →D,i • S r i D , 文法G’： (0) S’ S (1) S  rD (2) D D,i (3) D  i SLR(1)分析表 2018/9/18

47 4.5 LR分析 如果文法 G 的规范 LR（0）项目集族中的移进-归约冲突和归约-归约冲突可以用上述方法解决，则称文法 G 为 SLR（1）文法。 构造分析表中的归约项时，考察了产生式左边非终结符号的 FOLLOW 集，这样形成的分析表称为 SLR 分析表 基于 SLR 分析表的 LR 分析称为 SLR 分析 2018/9/18

48 The End! 2018/9/18