Phân Tích Trên Xuống & Dưới Lên | Hệ thống máy tính | Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội
Khi xây dựng cây cú pháp (hoặc bảng phân tích) bằng phương pháp Top-Down hoặc Bottom-Up, cần tiến hành qua các bước chung như sau: Bước 1: Xây dựng văn phạm tăng cường - Thêm một ký hiệu bắt đầu mới (ví dụ: S' → S) để hỗ trợ cho việc phân tích. - Xác định tập ký hiệu kết thúc (Σ) và tập ký hiệu chưa kết thúc (Δ). Tài liệu được sưu tầm và soạn thảo dưới dạng file PDF để gửi tới các bạn cùng tham khảo, ôn tập đầy đủ kiến thức, chuẩn bị cho các buổi học thật tốt. Mời bạn đọc đón xem!
Môn: Hệ thống máy tính (HUS) 10 tài liệu
Trường: Trường Đại học Khoa học tự nhiên, Đại học Quốc gia Hà Nội 687 tài liệu
Tác giả:
Preview text:
Xây dựng cây cú pháp bằng hai phương
pháp: Trên xuống và Dưới lên
Các bước giải chung Khi xây d n ự g cây cú pháp (ho c ặ b n ả g phân tích) b n ằ g ph n ươ g pháp Top-Down ho c ặ Bottom-Up, c n ầ ti n ế hành qua các b c ướ chung nh ư sau:
Bước 1: Xây dựng văn ph m ạ tăng c n ườ g - Thêm m t ộ ký hi u ệ b t ắ đ u ầ m i ớ (ví d : ụ S' → S) đ ể h ỗ tr ợ cho vi c ệ phân tích. - Xác đ n ị h t p ậ ký hi u ệ k t ế thúc ( ) Σ và t p ậ ký hi u ệ ch a ư k t ế thúc ( ) Δ . Bước 2: Xác đ n ị h các lu t ậ s n ả xu t ấ - Ghi rõ các lu t ậ sinh c a ủ văn ph m. ạ Bước 3: Xây dựng b n ả g phân tích (n u ế c n ầ ) ho c ặ ti n
ế hành phân tích cú pháp - Đ i ố v i ớ Top-Down: Suy di n ễ t ừ ký hi u ệ bắt đ u ầ theo chu i ỗ nh p ậ . - Đ i ố v i ớ Bottom-Up: Gi m ả t ừ chu i ỗ nh p ậ v ề ký hi u ệ b t ắ đ u ầ . Bước 4: Vẽ cây cú pháp - Cây th ể hi n
ệ quá trình phân tích, trong đó nút g c ố là ký hi u ệ b t ắ đ u ầ .
1. Phân tích cú pháp Trên Xuống (Top-Down Parsing) Ví dụ 1: Văn ph m: ạ (1) S → A a (2) A → B (3) B → b Chu i ỗ c n ầ phân tích: ba Giải:
Bước 1: Xây dựng văn ph m ạ tăng c n ườ g: (1') S' → S (2') S → A a (3') A → B (4') B → b T p ậ ký hi u ệ ch a ư kết thúc: Δ = {S', S, A, B} T p ậ ký hi u ệ k t ế thúc: Σ = {a, b} Bước 2: Phân tích chu i ỗ ba: - B t ắ đ u ầ t ừ S' → S - S → A a - A → B - B → b Cây cú pháp: S' | S / \ A a | B | b Ví dụ 2: Văn ph m: ạ (1) S → (S) | SS | a Chu i ỗ c n ầ phân tích: (a)a Giải:
Bước 1: Xây dựng văn ph m ạ tăng c n ườ g: (1') S' → S T p ậ ký hi u ệ ch a ư kết thúc: Δ = {S', S} T p ậ ký hi u ệ k t ế thúc: Σ = {(, ), a} Bước 2: Phân tích: - S' → S - S → (S) - S → a - Sau đó S → a Cây cú pháp: S' | S / | \ ( S ) | S | a Ví dụ 3: Văn ph m: ạ (1) E → E + T | T (2) T → T * F | F (3) F → (E) | id Chu i ỗ c n ầ phân tích: id + id * id Giải: Bước 1: Văn ph m ạ tăng c n ườ g: (1') E' → E Δ = {E', E, T, F} Σ = {+, *, (, ), id} Bước 2: Phân tích: - E → E + T - E → T - T → F - F → id Cây cú pháp: E' | E / | \ E + T | | T T | / \ F F * | | id id
2. Phân tích cú pháp Dưới Lên (Bottom-Up Parsing) Ví dụ 1: Văn ph m: ạ (1) S → A a (2) A → B (3) B → b Chu i ỗ : ba Giải: Bước 1: Văn ph m ạ tăng c n ườ g: (1') S' → S Δ = {S', S, A, B} Σ = {a, b} Bước 2: Phân tích t ừ d i ướ lên: - b → B - B → A - A a → S - S → S' Cây cú pháp: S' | S / \ A a | B | b Ví dụ 2: Văn ph m: ạ (1) S → (S) | SS | a Chu i ỗ : (a)a Giải: Bước 1: Văn ph m ạ tăng c n ườ g: (1') S' → S Bước 2: Phân tích: - a → S - (S) → S - S S → S - S → S' Cây cú pháp: S' | S / \ S S / | \ ( S ) | a Ví dụ 3: Văn ph m: ạ (1) E → E + T | T (2) T → T * F | F (3) F → (E) | id Chu i ỗ : id + id * id Giải: Bước 1: Văn ph m ạ tăng c n ườ g: (1') E' → E Bước 2: Phân tích: - id → F - F → T - id → F - F → T - T * T → T - id → F - F → T - T + T → E Cây cú pháp: E' | E / | \ E + T | | T T | / \ F F * | | id id