编译原理5.3.3-SLR分析表的构造

发布时间：2024-09-25

编译原理

从初态出发, 从初态出发,经读出活前缀γ 前缀γ后,而到达的项目集称为活前缀活前缀γ 目集称为活前缀γ的有效项目集a I0: S'→E → E→ aA → E→ bB →

I4:A→cA → c A→ cA → A→ d → c I2:E→aA → A→ cA → A→ d → I1: S' → E

A d d A

I8:A→c A → I10:A→ d → I6:E→aA →

E b c

I3: E→bB B → B→ cB → B→ d → d d B

I7:E→bB →

识别文法活前缀的DFA 活前缀的DFA 图5.7 p106

I5: B→cB → → c B→ cB B→ d →

I11:B→ d → I9:B→cB →

编译原理

有效项目

* ω 如果存在规范推导 S' αAω αβ1β2ω R R

有效的。则项目A→ 则项目 →β1β2 对活前缀 αβ1 是有效的。 o 如果β2 ≠ ε,应该移进应该用产生式 → o 如果β2 = ε,应该用产生式A→β1归约 LR分析理论的一条基本定理: 在任何时候， LR分析理论的一条基本定理: 在任何时候，分析理论的一条基本定理分析栈中的活前缀X 分析栈中的活前缀X1X2...Xm的有效项目集正是栈顶状态S 所代表的那个集合。是栈顶状态Sm所代表的那个集合。

编译原理

G': S'→E E→aA|bB A→cA|d B→cB|d a

I4:A→cA → c A→ cA → A→ d → c I0: S'→E → E→ aA → E→ bB → I2:E→aA → A→ cA → A→ d → I1: S' → E

A d d A

I8:A→c A → I10:A→ d → I6:E→aA →

项目集I 项目集I5 对活前缀 bc有效有效考虑如下规范推导

E b

(1) S′ E bB bcB ′ c (2) S′ E bB bcB bccB ′ I5: B→cB → (3) S′ E bB bcB bcd ′ → c B→ cB B→ d →

I3: E→bB B → B→ cB → B→ d → d d B

I7:E→bB →

I11:B→ d → I9:B→cB →

编译原理

同一个项目可能对好几个活前缀都有效a G': S'→E E→aA|bB A→cA|d B→cB|d I0: S'→E → E→ aA → E→ bB →

I4:A→cA → c A→ cA → A→ d → c I2:E→aA → A→ cA → A→ d → I1: S' → E

A d d A

I8:A→c A → I10:A→ d → I6:E→aA →

E b c

I3: E→bB B → B→ cB → B→ d → d d B

I7:E→bB →

I5: B→cB → → c B→ cB B→ d →

I11:B→ d → I9:B→cB →

编译原理

同一个活前缀，同一个活前缀，可能存在若干个项目对它都是有效的而且告诉我们应做的事情各不相同，相互冲突。 ,而且告诉我们应做的事情各不相同，相互冲突。这种冲突通过向前多看几个输入符号, 这种冲突通过向前多看几个输入符号, 或许能够获得解决。解决。

编译原理

5.3.3 SLR分析表的构造分析表的构造SLR(1)分析法的引入分析法的引入: 分析法的引入

LR(0)文法的活前缀识别自动机的每一状态文法的活前缀识别自动机的每一状态(项目集都不含冲突性的项目项目集)都不含冲突性的项目项目集

大多数的程序设计语言的文法不能满足大多数的程序设计语言的文法不能满足LR(0)文法的条件

用向前查看一个符号的办法解决冲突

编译原理

例：设文法的LR(0)项目集规范族中含有如设文

法G的项目集规范族中含有如下一个项目集(状态)I: 下一个项目集(状态) : I = { X→δ bβ /*移进项目移进项目*/ 移进-归约冲突 → β 移进项目移进- A→α →α /*归约项目归约项目*/ 归约-归约冲突 →α 归约项目归约- B→γ /*归约项目 } 归约项目*/ → 归约项目解决冲突策略 (1)若a=b,则移进 ) , (2)若a∈Follow(A), 则用 A→α 归约 ) ∈ →α (3)若a∈Follow(B), 则用 B→γ归约 ) ∈ → 归约 (4)此外，报错 )此外，

编译原理

用SLR(1)方法解决冲突方法解决冲突假定LR(0)规范族的一个项目集I中含有m个移进项目: 假定LR(0)规范族的一个项目集I中含有m个移进项目: LR(0)规范族的一个项目集 A1→αa1β1,A2→αa2β2,…,Am→αamβm 同时含有n个归约项目: 同时含有n个归约项目: B1→α1, B2→α2, …, Bn→αn 如果集合{ }、FOLLOW(B 如果集合{a1,…,am}、FOLLOW(B1)、…、FOLLOW(Bn) 两两不相交，是现行输入符号，两两不相交，a是现行输入符号，则: 是某个a i=1,2,…,m,则移进； (1)若a是某个ai,i=1,2,…,m,则移进； i=1,2,…,n, (2)若a∈FOLLOW(Bi),i=1,2,…,n, 则用产生式B 进行归约；则用产生式Bi→αi进行归约；此外，报错。 (3)此外，报错。

编译原理

文法5.8) 考虑下面的拓广文法 (文法文法 (0) S′ E ) (1) E E+T ) (2) E T ) (3) T T*F ) (4) T F ) (5) F (E) ) (6) F I ) 构造其LR(0)项目集规范族构造其项目集规范族

例5.11 p111

编译原理

I0 : S′→ E ′→ E → E + T E → T T → T * F T → F F → (E) F → i I1 : S ′→ E E→E+T I2 : E→T T→T*F

I3 : T→F I4 : F → ( E) E → E + T E → T T → T * F T → F F → (E) F → i I5 : F→i

I6 : E→E+T T → T * F T → F F → (E) F → i I7 : T→T*F F → (E) F → i I8 : F → (E ) E→E+T

DFA 图5.8 p112 移进-归约移进归约冲突I9 : E→E+T T→T*F I10: T→T*F I11: F → (E )

移进-接受冲突移进接受冲突接受移进-归约冲突移进归约冲突归约

编译原理

SLR(1) 解决方法(0) S′ ) (1) E ) (2) E ) (3) T ) (4) T ) (5) F ) (6) F ) E E+T T T*F F (E) I

I1: S′→ E ′→ E→E+T

FOLLOW(S′) = { # }, {#}∩{+}=φ,因此 1中的冲 = ,因此I突可解决。突可解决。遇 ‘+’移进，遇 ‘#’接受移进接受其它情况则报错。其它情况则报错。

编译原理

(0) S′ ) (1) E ) (2) E ) (3) T ) (4) T ) (5) F ) (6) F )

E E+T T T*F F (E) I

I2: E→T T→T*F

FOLLOW(E) = { +, ) , # } FOLLOW(E)∩{*}= φ,因此 2中因此I 因此的冲突可解决。的冲突可解决。

编译原理

(0) S′ (1) E (2) E (3) T (4) T (5) F (6) F

E E+T T T*F F (E) I

I9: E→E+T T→T*F

FOLLOW(E) = { + , ) , # } FOLLOW(E)∩{*}= φ,因此 9中因此I 因此的冲突可解决。的冲突

可解决。

编译原理

更正

构造SLR(1)分析表构造SLR(1)分析表 SLR(1)

(1)若属于I (1)若 A→αaβ 属于Ik , 且GO(Ik, a)=Ij , 则置 ACTION[k, a] 为 sj (2)若属于I (2)若 A→α 属于Ik,a∈FOLLOW(A) , 则置 ACTION[k,a] 为 rj 是产生式A→α A→α的编号 j是产生式A→α的编号。 (3)若 ′→S属于I →S属于 ACTION[k,#]为 (3)若 S′→S属于Ik, 则置 ACTION[k,#]为 acc (4)若 A]=j (4)若 GO(Ik,A)=Ij , 则置 GOTO[k, A]=j (5)凡不能用规则(1)~(4)填入的空白格均置为“出错 (5)凡不能用规则(1)~(4)填入的空白格均置为“ 凡不能用规则(1)~(4)填入的空白格均置为标志” 标志”。

编译原理

Follow(S′)={#} ′ Follow(E)={# , ) , +}

状态 1 2

ACTION i + s6 r2 s7 r2 * ( s4 acc r2 ) #

GOTO E T F 1 2 3

0 s5

(0) S′ (1) E (2) E (3) T (4) T (5) F (6) F

E E+T T T*F F (E) I

编译原理

状态 i

ACTION + * ( )

# acc r2 r4