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

编译原理

从初态出发, 从初态出发,经读出活 前缀γ 前缀γ后,而到达的项 目集称为活前缀 活前缀γ 目集称为活前缀γ的 有效项目集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→ …… 此处隐藏：2129字，全部文档内容请下载后查看。喜欢就下载吧 ……