编译原理5.3.3-SLR分析表的构造
时间:2025-07-06
时间:2025-07-06
编译原理
从初态出发, 从初态出发,经读出活 前缀γ 前缀γ后,而到达的项 目集称为活前缀 活前缀γ 目集称为活前缀γ的 有效项目集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
下一篇:高考语文古典诗词鉴赏真题及答案