Bài giảng Xây dựng chương trình dịch: Bài 7 - Nguyễn Thị Thu Hương

Bài giảng "Xây dựng chương trình dịch - Bài 7: Phân tích cú pháp tiền định" trình bày các nội dung: Phân tích tiền định, tính FOLLOW, bảng phân tích tiền định. Đây là một tài liệu tham khảo hữu ích dành cho các bạn sinh viên Công nghệ thông tin dùng làm tài liệu học tập và nghiên cứu.
Nội dung trích xuất từ tài liệu:
Bài giảng Xây dựng chương trình dịch: Bài 7 - Nguyễn Thị Thu Hương 21/1/2010 Phân tích tiền định „ Bài 7 Phân tích cú pháp tiền định „ „ Tư tưởng chính của phân tích cú pháp trên xuống : … Bắt đầu từ gốc, phát triển xuống các nút cấp dưới … Chọn một sản xuất và thử xem có phù hợp với xâu vào không … Có thể quay lui Có thể tránh được quay lui? … Cho sản xuất A → α | β bộ phân tích cú pháp cần chọn giữa α và β Làm thế nào? … Cho ký hiệu không kết thúc A và ký hiệu xem trước t, sản xuất nào của A chắc chắn sinh ra một xâu bắt đầu bởi t? 1 Phân tích tiền định 2 Phân tích tiền định Nếu có hai sản xuất: A→α⏐β , ta mong muốn có một phương pháp rõ ràng để chọn đúng sản xuất cần thiết „ Định nghĩa: „ „ … Nếu X là ký hiệu kết thúc FIRST(X)={X} … Nếu X→ε là một sản xuất thì thêm ε vào FIRST(X) … Nếu X là ký hiệu không kết thúc và X→Y1Y2...Yn là một sản xuất , thêm FIRST(Yi+1) vào FIRST(X) nếu FIRST(Yj) chứa ε α là một xâu chứa ký hiệu kết thúc và không kết thúc, x ∈ FIRST(α) nếu từ α có thể suy dẫn ra xγ (x chứa 0 hoặc 1 ký hiệu) … Với „ Nếu FIRST(α) và FIRST(β) không chứa ký hiệu chung ta biết phải chọn A→α hay A→β khi đã xem trước một ký hiệu Tính FIRST(X): 3 4 1 21/1/2010 Phân tích tiền định Tính FOLLOW Điều gì xảy ra nếu ta có sản xuất để chọn là A→α với α=ε hoặc α⇒*ε? „ Có thể mở rộng g nếu ta biết rằng g có một dạng g câu mà ký hiệu đang xét xuất ấ hiện sau A „ Định nghĩa: …FOLLOW(S) chứa EOF …Với các sản xuất dạng A→αBβ, mọi ký hiệu trong FIRST(β) trừ ε tham gia vào FOLLOW(B) …Với các sản xuất dạng A→αB hoặc A→αBβ trong đó FIRST(β) chứa ε, FOLLOW(B) chứa mọi ký hiệu của FOLLOW(A) „ … Với A là ký hiệu không kết thúc, x∈FOLLOW(A) nếu và chỉ nếu Scó thể suy dẫn ra αAxβ 5 Phân tích tiền định „ Bảng phân tích tiền định Với các khái niệm Dùng cho bộ sinh phân tích cú pháp „ Căn cứ … FIRST … FOLLOW „ „ „ 6 „ Ta có thể xây dựng bộ phân tích cú pháp mà không đòi hỏi quay lui Chỉ có thể xây dựng bộ phân tích cú pháp như vậy cho những văn phạm đặc biệt Loại văn phạm như vậy bao gồm văn phạm một số ngôn ngữ lập trình đơn giản, chẳng hạn KPL,PL/0, PÁSCAL-S … Ký hiệu đang xét … Ký hiệu đang ở đỉnh stack „ Quyết định … Thay thế ký hiệu không kết thúc con trỏ sang ký hiệu tiếp … Chấp nhận xâu … Chuyển 7 8 2 21/1/2010 Ví dụ „ Văn phạm: Bảng phân tích E→TE' E'→+TE'|ε T→FT' T'→*FT'|ε F→(E) F→id + E E' E'→+TE' T T'→ε T' F Đẩy + * ( ) id $ FIRST(E) = FIRST(T) = FIRST(F) = {(, id} FIRST(E') = {+, ε} FIRST(T') = {*, ε} FOLLOW(E) = FOLLOW(E') = {$, )} FOLLOW(T) = FOLLOW(T') = {+, $, )} FOLLOW(F) = {*, +, $, )} Văn phạm này có thể xây dựng bộ phân tích tiền định 9 * T'→*FT' ( E→TE' T→FT' T→FT F→(E) ) E'→ε T'→ε id E→TE' T→FT' T→FT F→id $ E'→ε T'→ε Đẩy Đẩy Đẩy Đẩy Nhận 10 Phân tích xâu vào id*id sử dụng bảng phân tích và stack Bước Stack 1 $E 2 $E'T $ 3 $E'T'F 4 $E'T'id 5 $E'T' 6 $T'F* 7 $T'F 8 $T'id 9 $T' 10 $ Xâu vào id*id$ id*id$ $ id*id$ id*id$ *id$ *id$ id$ id$ $ $ Hành động kế tiếp E→TE' T→FT' F→id đẩy id T'→*FT' đẩy * F→id đẩy id T'→ε nhận 11 3