Phương pháp Simple LR (SLR)

1. Phương pháp phân tích cú pháp dưới lên

1.3. Phương pháp Simple LR (SLR)

 Cấu tạo:

Kết quả

$ a0 a1

ai …

Buffer

Bộ phân tích Stack

$ S0 x0 … Si-1 Xi-1 Si

Bảng SLR Action Goto

168

CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)

 Cấu tạo:

- Stack: $s0x0 s1x1…si-1xi-1si st: trạng thái; xt∈(Σ∪Δ)

- Buffer: aiai-1…a0$ ; với at ∈Σ

- Bảng SLR gồm 2 phần: action và goto

• Chỉ số hàng: trạng thái St

169

CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)

 Cấu tạo:

• Chỉ số cột

Phần action: ai∈Σ Phần goto: X∈Δ

• Action[Si,ai]=Shift j (Sj)

• Action[Si,ai]=Reduce Aα (RJ)

170

CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)

 Cấu tạo:

• Action[Si,ai]=Accept

• Action[Si,ai]=rỗng

• Goto[Si,X]=j

171

CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)

 Hoạt động:

Tại một thời điểm bộ phân tích đọc trạng thái Si ở đỉnh stack và ký hiệu vào ai ở đỉnh buffer và tra trong bảng SLR ở phần Action một giá trị. Nếu:

- Action[Si,ai]=Shift j (Sj)

 D/c ai từ Buffer Stack

 Đẩy j vào stack

172

CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)

 Hoạt động:

- Action[Si,ai]=Reduce Aα (RJ)

 Lấy 2*r phần tử ra khỏi stack. Với r=|α|

 Đẩy A vào stack

 Đẩy j vào stack với j=goto[Si-r,A]

173

CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)

 Hoạt động:

- Action[Si,ai]=Accept

 Xâu x đúng cp của vpG - Action[Si,ai]=rỗng

 Báo lỗi x không cú pháp của vpG

174

CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)

 Thuật toán:

Sử dụng: 1 stack, 1 buffer, bảng SLR Khởi tạo: - stack: $0

- Buffer: x$

Lặp: {g/sử ở đỉnh stack là Si, đỉnh buffer là a}

If (Action[Si,a]=accept) then - x đúng cp và dừng vòng lặp

175

CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)

 Thuật toán:

Else If (Action[Si,a]=Sj) then - D/c a từ buffer  stack - Đẩy j vào stack

Else IF (Action[Si,a]=Reduce Aα) then - Lấy 2*r phần tử ra khỏi stack

176

CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)

 Thuật toán:

- Đẩy A vào stack

- Đẩy j vào stack. Với j=goto[Si-r,A]

Else {Action[Si,a]=rỗng}

- Báo lỗi x không đúng cp của G - Dừng vòng lặp

177

CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)

 Ví dụ: Cho vp G E  E + T | T T  T * F | F F  (E) | id

Xâu x: id*(id+id)

(1) (2) (3) (4) (5) (6)

178

CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)

T/

thái Action Goto

id + * ( ) $ E T F

0 S5 S4 1 2 3

1 S6 Accept

2 R2 S7 R2 R2

3 R4 R4 R4 R4

4 S5 S4 8 2 3

5 R6 R6 R6 R6

6 S5 S4 9 3

179

CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)

T/

thái Action Goto

id + * ( ) $ E T F

7 S5 S4 10

8 S6 S11

9 R1 S7 R1 R1

10 R3 R3 R3 R3

11 R5 R5 R5 R5

180

CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)

 Ví dụ:

Stt Stack Buffer Hành động

0 $0 id*(id+id)$ S5

1 $0 id 5 *(id+id)$ R6(Fid)

2 $0 F 3 *(id+id)$ R4(TF)

3 $0 T 2 *(id+id)$ S7

4 $0 T 2 * 7 (id+id)$ S4

5 $0 T 2 * 7 ( 4 id+id)$ S5

181

CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)

 Ví dụ:

Stt Stack Buffer Hành động

6 $0 T 2 * 7 ( 4 id 5 +id)$ R6(Fid)

7 $0 T 2 * 7 ( 4 F 3 +id)$ R4(TF)

8 $0 T 2 * 7 ( 4 T 2 +id)$ R2(ET)

9 $0 T 2 * 7 ( 4 E 8 +id)$ S6

10 $0 T 2 * 7 ( 4 E 8 + 6 id)$ S5

11 $0 T 2 * 7 ( 4 E 8 + 6 id 5 )$ R6(Fid)

182

CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)

 Ví dụ:

Stt Stack Buffer Hành động

12 $0 T 2 * 7 ( 4 E 8 + 6 F 3 )$ R4(TF) 13 $0 T 2 * 7 ( 4 E 8 + 6 T 9 )$ R1(EE+T)

14 $0 T 2 * 7 ( 4 E 8 )$ S11

15 $0 T 2 * 7 ( 4 E 8 ) 11 $ R5(F(E))

16 $0 T 2 * 7 F 10 $ R3(TT*F)

17 $0 T 2 $ R2(ET)

183

CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)

 Ví dụ:

Stt Stack Buffer Hành động

18 $0 E 1 $ Accept

184

CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)

 Xây dựng bảng SLR - Văn phạm gia tố G’

G’=G ∪ {S’S}

Ví dụ: G: S  0S | 1S|0|1 G’: S’  S

S  0S | 1S|0|1

185

CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)

 Xây dựng bảng SLR

- Thực thể: Sx thêm dấu chấm ở bất kỳ vị trí của vế phải.

Ví dụ: A xyz

thì A .xyz Ax.yz Axy.z A  xyz. là các thực thể

186

CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)

 Xây dựng bảng SLR

- Hàm tính bao đóng Closure(Ii): 2 qui tắc

(1) Đưa tất cả các thực thể trong Ii vào closure(Ii) (2) Cứ mỗi thực thể có dạng

Aα.Bβ∈closure(Ii) mà Bγ thì thêm B.γ vào closure(Ii) với B.γ ∉ closure(Ii)

187

CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)

 Ví dụ: Xác định tập closure(I) của VP G’

E’ E

E  E + T | T T  T * F | F F  (E) | id

I={E’.E}

188

CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)

 Xây dựng bảng SLR - Hàm tính goto

Goto(Ii,x)=closure({Aαx.β}) với {Aα.xβ} ⊂ Ii ; x∈(Σ∪Δ)

189

CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)

 Ví dụ: Tìm tất cả các tập goto(I,X) có thể của VP G

I={ E’.E E.E+T E.T

T.T*F } X: E, T

Goto(I,E) và Goto(I,T)

E’ E

E  E + T | T

T  T * F |

F F  (E) | id

Goto(I,E)=closure({E’E

. ; EE.+T})

Goto(I,T)=closure({ET.

; TT.*F})

190

CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)

 Xây dựng bảng SLR - Tập thực thể LR(0)

I0=closure({S’.S})

- Tính tất cả các goto(Ii,x) của tất cả các tập thực thể ta sẽ được tập LR(0).

- Tính hết goto(Ii,x) mà không sinh được Ii+1 thì dừng.

191

CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)

 Xây dựng bảng SLR

- Qui tắc xác định hành động

(1)∃ Aα.aβ ∈ Ii và goto(Ii,a)=Ij với a ∈Σ thì: Action[i,a]= Sj

(2)∃ Aα.Xβ ∈ Ii và goto(Ii,X)=Ij với X ∈Δ thì: goto[i,X]= j

192

CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)

 Xây dựng bảng SLR

- Qui tắc xác định hành động

(3)∃ S’S. ∈ Ii thì: Action[i,$]= accept

(4)∃ Aα. ∈ Ii thì Action[i,a]= Reduce Aα với a∈ Follow(A); A<>S’

- Qui tắc xác định Follow Follow(A)={(t∈Σ|

S⇒+αAtβ)∪(t=$|S⇒+ αA)}

193

CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)

 Ví dụ: Cho vp G E  E + T | T T  T * F | F F  (E) | id

Xây dựng bảng SLR cho VP G

194

CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)

 Ví dụ:

- Xác định G’

- Tạo tập thực thể LR(0) - Xác định các hành động

195

CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)

 Ví dụ:

- VP gia tố G’

E’  E

E  E + T | T T  T * F | F F  (E) | id

196

CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)

 Ví dụ:

- Tạo tập thực thể LR(0)

I0=closure({E’.E}) E’.E

E.E+T E.T T.T*F

T.F F.(E) F.id

I1=goto(I0,E) E’E.

EE.+T

197

CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)

 Ví dụ:

- Xác định các hành động

198

CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)

Bài tập:

(1)cho VPG: A A or B | B B  B and C | C

C  not C | (A) | true | false Hỏi xâu x: true and false or (not true) có được

sinh ra từ VPG? c/m bằng PP SLR

199

CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG

1. Phương pháp phân tích cú pháp dưới lên 1.3. Phương pháp Simple LR (SLR)

Bài tập:

(2)Cho VPG: S AS| b A  SA| a

Xây dựng bảng SLR cho VP G?

200

CHƯƠNG 4. CÁC PHƯƠNG PHÁP PHÂN TÍCH CÚ PHÁP

TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG