！ 温故知新 上下文无关文法 最左推导 最右推导 自上而下 自下而上 句柄 归约 移进-归约冲突 移进-归约分析 递归下降预测分析

Presentation on theme: "！ 温故知新 上下文无关文法 最左推导 最右推导 自上而下 自下而上 句柄 归约 移进-归约冲突 移进-归约分析 递归下降预测分析"— Presentation transcript:

1 ！ 温故知新 上下文无关文法 最左推导 最右推导 自上而下 自下而上 句柄 归约 移进-归约冲突 移进-归约分析 递归下降预测分析
1。句柄与某个产生式的右部符号串相同 2。句柄是句型的一个子串 3。把句柄归约成非终结符代表了最右推导逆过程的一步 上下文无关文法 ！ 最左推导 最右推导 自上而下 自下而上 句柄 归约 移进-归约冲突 移进-归约分析 递归下降预测分析 归约-归约冲突 LL(1)文法 输入 LR分析程序 输出 栈 LR分析器的模型 action goto sm Xm sm-1 Xm-1 … s0 a1 ai an $ 非递归的预测分析 LR文法 2个函数 活前缀 右句型的前缀，该前缀不超过最右句柄的右端 简单的LR方法（SLR） 规范的LR方法 向前看的LR方法(LALR） 1/41

2 given point in the parsing process.
3.5 LR Parser 3.5.3 Constructing SLR Parse Table LR(0) item (item for short) a production of G with a dot at some position of the body Ex：AXYZ has four items A  ·XYZ A  X·YZ A  XY·Z A  XYZ· Ex：A has only one item A  · Intuitively , an item indicates ho w much of a production we have seen at a given point in the parsing process.

3 S  aABe A  Abc | b B  d $ a b b c d e $ S0 S  ·aABe

4 S  aABe A  Abc | b B  d A  · Abc S  a · ABe A  · b S  a · ABe
Two possibilities b b c d e $ $ a S0 S1 A  · Abc S  a · ABe A  · b 通过实例来说明加点项含义 S  a · ABe A  · Abc A  · b action(1,b)=S2

5 S  aABe A  Abc | b B  d S1 S  a · ABe A  · Abc A  · b S2
$ a b b c d e $ S0 S1 S2 S2 achieved by shifting b from S1 S1 S  a · ABe A  · Abc A  · b A  · b becomes A  b · S2 A  b · Next, reduce

6 S  aABe A  Abc | b B  d S  a A · Be S1 S  a · ABe A  A ·bc
$ a A b c d e $ S0 S1 S3 Check: from S1, after seeing A, where to go? S  a A · Be Two possibilities S1 S  a · ABe A  · Abc A  · b A  A ·bc S3 S  a A · Be A  A ·bc B  ·d

7 S  aABe A  Abc | b B  d S3 S4 S  a A · Be A  A b · c A  A ·bc
$ a A b c d e $ S0 S1 S3 S4 After shifting b becomes S3 S  a A · Be A  A ·bc B  ·d S4 A  A b · c

8 S  aABe A  Abc | b B  d S4 A  A b · c S5 A  A b c · becomes
$ a A b c d e $ S0 S1 S3 S4 S5 becomes S4 A  A b · c Next, reduce S5 A  A b c ·

9 S  aABe A  Abc | b B  d S3 S  a A · Be A  A ·bc B  ·d becomes
$ a A d e $ S0 S1 S3 becomes Next? S3 S  a A · Be A  A ·bc B  ·d

10 S  aABe A  Abc | b B  d S2 S  a A · Be A  A · bc B  · d S6
$ a A d e $ S0 S1 S3 S6 S2 S  a A · Be A  A · bc B  · d becomes S6 B  d · Next, reduce

11 S  aABe A  Abc | b B  d S3 S  a A · Be A  A · bc B  · d S7
$ a A B e $ S0 S1 S3 S7 S3 S  a A · Be A  A · bc B  · d becomes S7 S  a AB · e

12 S  aABe A  Abc | b B  d S7 S  a AB · e Next, reduce S8
$ a A B e $ S0 S1 S3 S7 S7 S  a AB · e becomes Next, reduce S8 S  a AB e ·

13 S  aABe A  Abc | b B  d $ S $ S0 OK Accept

14 3.5 LR Parser Two steps of constructing SLR Parse table
1. Construct a DFA to recognize the viable prefixes 2. Construct the parse table with respect to the DFA

15 3.5 LR Parser Constructing the DFA 1. Augmented Grammar E   E
acceptance occurs when and only when the parser is about to reduce b y E   E Constructing the DFA 1. Augmented Grammar E   E E  E + T | T T T * F | F F ( E ) | id id + id F + id T+id E+id E+F E+T E E rmE+T rm E+F rm E+id rm T+id rm F+id rm id+id

16 3.5 LR Parser Constructing the DFA
E   E E  E + T | T T T * F | F F ( E ) | id Constructing the DFA 2. Construct the canonical LR(0) collection I0: E  ·E closure(I) 1、 add every item in I to closure(I) 2、If Aα·Bβ is in closure(I), and Bγ is a production, then add B ·γ to closure(I) if it’s not there E  ·E + T E  ·T T  ·T * F T  ·F F  ·(E) F  ·id 5/41

17 and those items in which dot not at the left end
3.5 LR Parser E   E E  E + T | T T T * F | F F ( E ) | id Constructing the DFA 2. Construct the canonical LR(0) collection I0: E  ·E (Kernel items) E  ·E + T E  ·T (Nonkernel items， T  ·T * F could be obtained by T  ·F computing the closure F  ·(E) function of kernel items) F  ·id E’·E and those items in which dot not at the left end

18 3.5 LR Parser Constructing the DFA
E   E E  E + T | T T T * F | F F ( E ) | id Constructing the DFA 2. Construct the canonical LR(0) collection I0: I1: E  ·E E   E· E  ·E + T E  E· + T E  ·T T  ·T * F T  ·F F  ·(E) F  ·id

19 3.5 LR Parser Constructing the DFA
E   E E  E + T | T T T * F | F F ( E ) | id Constructing the DFA 2. Construct the canonical LR(0) collection I0: I1: E  ·E E   E· E  ·E + T E  E· + T E  ·T T  ·T * F I1 := goto ( I0, E ) T  ·F F  ·(E) F  ·id

20 3.5 LR Parser Constructing the DFA
E   E E  E + T | T T T * F | F F ( E ) | id Constructing the DFA 2. Construct the canonical LR(0) collection I0: I1: E  ·E E   E· E  ·E + T E  E· + T E  ·T T  ·T * F I2: T  ·F E  T· F  ·(E) T T· * F F  ·id

21 3.5 LR Parser Constructing the DFA
E   E E  E + T | T T T * F | F F ( E ) | id Constructing the DFA 2. Construct the canonical LR(0) collection I0: I1: E  ·E E   E· E  ·E + T E  E· + T E  ·T T  ·T * F I2: T  ·F E  T· F  ·(E) T T· * F F  ·id I3: T  F· 10/41

22 3.5 LR Parser I0: I4: E  ·E F  (·E ) E  ·E + T E  ·E + T
E  E + T | T T T * F | F F ( E ) | id 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

23 3.5 LR Parser I0: I4: E  ·E F  (·E ) E  ·E + T E  ·E + T
E  E + T | T T T * F | F F ( E ) | id 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·

24 3.5 LR Parser I1 I0 E I3 I2 I4 I5 T F ( id

25 3.5 LR Parser I1: E   E· E  E·+ T E E   E I0 I1 E  E + T | T
F ( id E   E E  E + T | T T T * F | F F ( E ) | id I1: E   E· E  E·+ T

26 3.5 LR Parser I1: E   E· E  E·+ T I6 : EE + ·T T ·T * F T ·F
( id E   E E  E + T | T T T * F | F F ( E ) | id I1: E   E· E  E·+ T I6 : EE + ·T T ·T * F T ·F F ·(E) F ·id 15/41

27 3.5 LR Parser I2: E T· TT·*F I7: TT *·F F ·(E) F ·id E E   E I0
E  E + T | T T T * F | F F ( E ) | id I2: E T· TT·*F I7: TT *·F F ·(E) F ·id

28 3.5 LR Parser I3: T  F· E E   E I0 I1 E  E + T | T T T * F | F
( id E   E E  E + T | T T T * F | F F ( E ) | id I3: T  F·

29 3.5 LR Parser I4: F  (·E ) E  ·E + T E  ·T T  ·T *F T  ·F
id E   E E  E + T | T T T * F | F F ( E ) | id I4: F  (·E ) E  ·E + T E  ·T T  ·T *F T  ·F F  ·( E ) F  ·id

30 3.5 LR Parser I4: I8: F  (·E ) F (E·) E  ·E + T E  E·+ T E  ·T
id I4: I8: F  (·E ) F (E·) E  ·E + T E  E·+ T E  ·T T  ·T *F T  ·F F  ·( E ) F  ·id E   E E  E + T | T T T * F | F F ( E ) | id

31 3.5 LR Parser I4: I8: F  (·E ) F (E·) E  ·E + T E  E·+ T E  ·T
id I4: I8: F  (·E ) F (E·) E  ·E + T E  E·+ T E  ·T T  ·T *F I2: T  ·F E T· F  ·( E ) TT·*F F  ·id E   E E  E + T | T T T * F | F F ( E ) | id 20/41

32 3.5 LR Parser I4: I8: F  (·E ) F (E·) E  ·E + T E  E·+ T E  ·T
id I4: I8: F  (·E ) F (E·) E  ·E + T E  E·+ T E  ·T T  ·T *F I2: T  ·F E T· F  ·( E ) TT·*F F  ·id I3: TF· E   E E  E + T | T T T * F | F F ( E ) | id

33 3.5 LR Parser I4: I8: F  (·E ) F (E·) E  ·E + T E  E·+ T E  ·T
id I4: I8: F  (·E ) F (E·) E  ·E + T E  E·+ T E  ·T T  ·T *F I2: T  ·F E T· F  ·( E ) TT·*F F  ·id I3: TF· I4: F (·E ) . . . E   E E  E + T | T T T * F | F F ( E ) | id

34 3.5 LR Parser I4: I8: F  (·E ) F (E·) E  ·E + T E  E·+ T E  ·T
E  E + T | T T T * F | F F ( E ) | id I1 I0 E I3 I2 I4 I5 T F ( id I4: I8: F  (·E ) F (E·) E  ·E + T E  E·+ T E  ·T T  ·T *F I2: T  ·F E T· F  ·( E ) TT·*F F  ·id I3: TF· I4: I5: F (·E ) F id· . . .

35 3.5 LR Parser I5: F id· E E   E I0 I1 E  E + T | T T T * F | F
( id E   E E  E + T | T T T * F | F F ( E ) | id I5: F id·

36 3.5 LR Parser E + E   E E  E + T | T T T * F | F F ( E ) | id I0
25/47 I5

37 3.5 LR Parser I1 I0 + To I7 E I6 I9 I3 I2 I4 I11 I8 I7 * T I5 To I4
F ( id )

38 3.5 LR Parser Properties of the constructed DFA Definition：valid item
If S*rm Aw rm 12w，we say item A1·2 is valid for a viable prefix 1 In general, an item will b e v alid for man y viable prefixes S*rm AAw rm A12w rm  1212w For any viable prefix 1, suppose A1·2is valid If 2 , should shift If 2 = , should reduce by A1

39 3.5 LR Parser Properties of the constructed DFA Definition：valid item
If S*rm Aw rm 12w，we say item A1·2 is valid for a viable prefix 1 In general, an item will b e v alid for man y viable prefixes A viable prefix may have multiple valid items The valid items of a viable prefix  is the item set (state) reached by the path 

40 3.5 LR Parser Ex E + T * is a viable prefix. After reading it, DFA reaches I7 I7: TT *·F, F ·(E ), F ·id E   E E   E E   E  E+T  E+T  E+T  E+T * F  E+T * F  E+T * F  E+T * id  E+T * (E )  E+T* id  E+T * F * id Definition：Valid item If S*rm Aw rm 12w，we say item A1·2 is valid for viable prefix 1

41 3.5 LR Parser Two steps of constructing SLR Parse table
1. Construct a DFA to recognize the viable prefixes 2. Construct the parse table with respect to the DFA 30/41

42 3.5 LR Parser Construct SLR Parse table from DFA
For state i from Ii，its action function defined as： If [A·a] in Ii，and goto(Ii, a ) = Ij，then action[i, a] is sj。 If [A·] in Ii，then for all a in FOLLOW(A) ，place action[i, a] with rj, where j is the id of A If [SS·] in Ii，action[ i, $ ] is acc。 If conflict occurs, the grammar is not SLR(1)

43 3.5 LR Parser Construct SLR Parse table
State I constructed from Ii, its action function defined as follows . . . Construct goto function as follows： For all nonterminalA, ifgoto(Ii, A) = Ij, then goto[i, A] = j。

44 3.5 LR Parser Construct SLR Parse table
State I constructed from Ii, its action function defined as follows . . . Construct goto function as follows： Set other entries as error

45 3.5 LR Parser Construct SLR Parse table
State I constructed from Ii, its action function defined as follows . . . Construct goto function as follows： Set other entries as error The state that contains [S·S] is the initial state

46 3.5 LR Parser 例 I2: E  T· T  T· * F 因为FOLLOW(E) = {$, +, )}, 所以
E   E E  E + T | T T T * F | F F ( E ) | id 例 I2: E  T· T  T· * F 因为FOLLOW(E) = {$, +, )}, 所以 action[2, $]=action[2, +]=action[2, )]=r2 action[2, *] = s7 35/41

47 3.5 LR Parser S  V = E S  E V  * E V  id E  V I0 : S   · S
Ex Limitation of SLR(1) S  V = E S  E V  * E V  id E  V I0 : S   · S S  ·V = E S  · E V  · * E V  · id E  · V I2 : S  V · = E E  V · V

48 3.5 LR Parser Ex Limitation of SLR(1) S  V = E S  E V  * E V  id
S   · S S  ·V = E S  · E V  · * E V  · id E  · V I2 : S  V · = E E  V · V I2 the first item: action[2, = ] = s6

49 3.5 LR Parser Ex Limitation of SLR(1) S  V = E S  E V  * E V  id
S   · S S  ·V = E S  · E V  · * E V  · id E  · V I2 : S  V · = E E  V · V I2 the first item: action[2, = ] = s6 I2 the second item: action[2, = ] = r5 Reduce by EV In that = belongs to FOLLW(E)

50 3.5 LR Parser Ex Limitation of SLR(1) S  V = E S  E V  * E V  id
S   · S S  ·V = E S  · E V  · * E V  · id E  · V I2 : S  V · = E E  V · V I2 the first item: action[2, = ] = s6 I2 the second item: action[2, = ] = r5 Reduce by EV In that = belongs to FOLLW(E)

51 3.5 LR Parser Ex Limitation of SLR(1) S  V = E S  E V  * E V  id
S   · S S  ·V = E S  · E V  · * E V  · id E  · V I2 : S  V · = E E  V · V I2 the first item: action[2, = ] = s6 I2 the second item: action[2, = ] = r5 Reduce by EV In that = belongs to FOLLW(E) However, right sentential form never starts with E=… 40/41

52 习 题 3.19(a), 3.20(a), 3.23 41/41

53

54

55 课堂练习 例 构造以下文法的SLR(1)分析表 S  V = E S  E V  * E V  id E  V

56 课堂练习 1. 构造识别活前缀的DFA (1) 拓广文法 S’ S S  V = E S  E V  * E V  id

57 课堂练习 1. 构造识别活前缀的DFA (2) 构造项目集规范族 I6: S V=.E E .V V  .*E I4: V * .E
V  .id 1. 构造识别活前缀的DFA (2) 构造项目集规范族 I4: V * .E E .V V .*E V .id I1: S’ S . I0: S’ . S S  .V = E S  . E V  .* E V  .id E  .V I2: S V .=E E V. I7: V * E. I5: V id. I3: S E . I8: E V. I9: S V=E.

58 课堂练习 2. 从DFA构造分析表