Sự khác biệt giữa phân tích từ trên xuống và từ dưới lên
Share
Các sự khác biệt chính giữa phân tích từ trên xuống và từ dưới lên là từ trên xuống phân tích cú pháp thực hiện phân tích cú pháp từ biểu tượng nhìn chằm chằm vào chuỗi đầu vào trong khi phân tích cú pháp từ dưới xuống thực hiện phân tích cú pháp từ chuỗi đầu vào sang biểu tượng bắt đầu. Hơn nữa, một sự khác biệt quan trọng khác giữa phân tích cú pháp từ trên xuống và từ dưới lên là phân tích cú pháp từ trên xuống sử dụng hầu hết các dẫn xuất trái và phân tích từ dưới lên sử dụng hầu hết các dẫn xuất bên phải.
Ngôn ngữ cấp cao giúp viết chương trình máy tính. Chúng dễ hiểu hơn bởi lập trình viên nhưng không phải bởi máy tính. Do đó, chương trình cấp cao chuyển đổi thành mã máy. Nhiệm vụ của trình biên dịch là chuyển đổi mã nguồn có thể đọc được thành mã máy có thể đọc được. Một chương trình trải qua một số bước để chuyển đổi thành mã máy. Toàn bộ quá trình này được gọi là Hệ thống xử lý ngôn ngữ. Một trong số đó là phần tổng hợp. Trình phân tích cú pháp hoặc trình phân tích cú pháp nằm trong trình biên dịch và nó thực hiện nhiệm vụ phân tích cú pháp.
NỘI DUNG
1. Tổng quan và sự khác biệt chính
2. Phân tích cú pháp từ trên xuống là gì
3. Phân tích từ dưới lên là gì
4. So sánh cạnh nhau - Phân tích từ trên xuống và từ dưới lên dưới dạng bảng
5. Tóm tắt
Phân tích từ trên xuống là gì?
Mỗi ngôn ngữ lập trình có một bộ quy tắc để đại diện cho ngôn ngữ. Bộ phân tích cú pháp hoặc phân tích cú pháp lấy chuỗi đầu vào và kiểm tra xem nó có theo các sản phẩm ngữ pháp hay không. Nói cách khác, ngữ pháp sẽ tạo ra chuỗi đó bằng cách sử dụng cây phân tích cú pháp.
Trong phân tích cú pháp từ trên xuống, phân tích cú pháp xảy ra từ biểu tượng bắt đầu và sẽ đến chuỗi đầu vào đã cho. Hãy xem xét các quy tắc sản xuất ngữ pháp sau đây. Chuỗi đầu vào (w) là cad.
S -> cAd
A -> ab / a
Cây phân tích cú pháp sau khi thực hiện phân tích cú pháp từ trên xuống như sau.
Hình 01: Parse Tree 1 với phân tích cú pháp từ trên xuống
S tạo ra c A d và A tạo ra b. Chuỗi là cabd. Nó không phải là chuỗi yêu cầu. Vì vậy, cần phải thực hiện quay lui, đó là sử dụng các phương án khác.
Tương tự, S tạo ra c A d. Áp dụng tùy chọn khác cho A sẽ cho a. Bây giờ nó đưa ra chuỗi yêu cầu. Do đó, trình phân tích cú pháp chấp nhận chuỗi đầu vào này. Cây phân tích cú pháp sau khi thực hiện phân tích cú pháp từ trên xuống như sau.
Hình 02: Parse Tree 2 với phân tích cú pháp từ trên xuống
Khi chuỗi đầu vào (w) là abbcde
Hãy xem xét các quy tắc sản xuất ngữ pháp sau đây.
S -> aABe
A -> Abc / b
B -> d
Từ trên xuống phân tích cú pháp,
S -> aABe (Thay thế A -> Abc)
S -> aAbcBe (Thay thế A -> b)
S -> abbcBe (Thay thế B -> d)
S -> abbcde
Thay thế bắt đầu với hầu hết các biến trái đầu tiên và sau đó đến vị trí bên phải tiếp theo và như vậy. Do đó, nó tuân theo một phương pháp phái sinh trái nhất. Hơn nữa, điều quan trọng là phải quyết định nên chọn quy tắc sản xuất nào khi có biến.
Phân tích từ dưới lên là gì?
Trong phân tích từ dưới lên xảy ra theo cách khác. Việc phân tích cú pháp xảy ra từ chuỗi đầu vào đến ký hiệu bắt đầu. Hãy xem xét các quy tắc sản xuất ngữ pháp sau đây và để chuỗi đầu vào là w ɛ cad
S -> cAd
A -> ab / a
Cây phân tích cú pháp sau khi thực hiện phân tích cú pháp từ dưới lên như sau.
Hình 03: Cây phân tích cú pháp phân tích từ dưới lên
Chuỗi đã cho là cad. A được tạo bởi A. Kết hợp c, A và d để có ký hiệu bắt đầu S.
Khi chuỗi đầu vào (w) là abbcde
Hãy xem xét các quy tắc sản xuất ngữ pháp sau đây.
S -> aABe
A -> Abc / b
B -> d
Trong phân tích từ dưới lên,
S -> aABe (Thay thế B -> d)
S -> aAde (Thay thế A -> Abc)
S -> aAbcde (Thay thế A -> b)
S -> abbcde
Thay thế bắt đầu với hầu hết các bên phải đầu tiên và sau đó di chuyển đến vị trí bên trái tiếp theo và như vậy. Do đó, nó tuân theo một phương pháp phái sinh trái.
Sự khác biệt giữa phân tích từ trên xuống và từ dưới lên?
Phân tích cú pháp từ trên xuống là một chiến lược phân tích cú pháp đầu tiên nhìn vào cấp độ cao nhất của cây phân tích và làm việc với cây phân tích bằng cách sử dụng các quy tắc của một ngữ pháp chính thức. Phân tích cú pháp từ dưới lên là một chiến lược phân tích cú pháp đầu tiên nhìn vào mức thấp nhất của cây phân tích và làm việc với cây phân tích bằng cách sử dụng các quy tắc của một ngữ pháp chính thức. Việc phân tích cú pháp xảy ra từ ký hiệu bắt đầu đến chuỗi đầu vào, trong phân tích cú pháp từ trên xuống. Mặt khác, phân tích cú pháp xảy ra từ chuỗi đầu vào đến ký hiệu bắt đầu, từ dưới lên phân tích cú pháp.
Hơn nữa, quyết định chính trong phân tích cú pháp từ trên xuống là chọn quy tắc sản xuất nào sẽ sử dụng để xây dựng chuỗi trong khi quyết định chính trong phân tích cú pháp từ dưới lên là chọn khi nào nên sử dụng quy tắc sản xuất để giảm chuỗi để lấy ký hiệu bắt đầu. Hơn nữa, phân tích cú pháp từ trên xuống sử dụng hầu hết các công cụ phái sinh bên trái và phân tích cú pháp từ dưới lên sử dụng hầu hết các công cụ phái sinh bên phải.
Tóm tắt - Phân tích từ trên xuống và từ dưới lên
Sự khác biệt giữa phân tích từ trên xuống và từ dưới lên là phân tích cú pháp từ trên xuống thực hiện phân tích cú pháp từ biểu tượng nhìn chằm chằm sang chuỗi đầu vào trong khi phân tích từ dưới xuống thực hiện phân tích cú pháp từ chuỗi đầu vào sang biểu tượng bắt đầu.
Tài liệu tham khảo:
1. Bài giảng Thiết kế Trình biên dịch 5 - Giới thiệu về Trình phân tích cú pháp và LL (1) Phân tích cú pháp. Trình biên dịch thiết kế bài giảng 5 - Giới thiệu về phân tích cú pháp và LL (1) Phân tích cú pháp, Bài giảng Gate của Ravindrababu Ravula, ngày 22 tháng 5 năm 2014. Có sẵn tại đây
