Sự khác biệt chính 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 thực hiện phân tích cú pháp từ biểu tượng dấu sao đến 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 đến ký hiệu 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 dẫn xuất bên trái nhất và phân tích cú pháp từ dưới xuống sử dụng dẫn xuất bên phải.
Ngôn ngữ cấp cao giúp viết các 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 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 của con người sang mã máy có thể đọc được của máy. Một chương trình trải qua một số bước để chuyển đổi sang 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 biên dịch. 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 tác vụ phân tích cú pháp.
Phân tích cú pháp từ trên xuống là gì?
Mọi ngôn ngữ lập trình đều có một bộ quy tắc để đại diện cho ngôn ngữ đó. Trình phân tích cú pháp hoặc trình phân tích cú pháp lấy chuỗi đầu vào và kiểm tra xem nó có tuân theo quy trình ngữ pháp hay không. Nói cách khác, ngữ pháp phải 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, việc phân tích cú pháp diễn ra từ ký hiệu 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: Phân tích cú pháp Cây 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 a b. Chuỗi là cabd. Nó không phải là chuỗi bắt buộc. Vì vậy, cần phải thực hiện backtracking, tức là sử dụng các giải pháp thay thế khác.
Tương tự, S tạo ra c A d. Áp dụng phương án khác cho A sẽ cho a. Bây giờ nó đưa ra chuỗi bắt buộc. 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: Cây phân tích cú pháp 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
Trong phân tích cú pháp từ trên xuống, 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 biến nhiều nhất bên trái trước rồi đến vị trí bên phải tiếp theo, v.v. Do đó, nó tuân theo một phương pháp dẫn xuất bên trái nhất. Hơn nữa, điều quan trọng là phải quyết định chọn quy tắc sản xuất nào khi có một biến số.
Phân tích cú pháp từ dưới lên là gì?
Phân tích cú pháp 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 tạo ngữ pháp sau và đặt 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 với cách phân tích cú pháp từ dưới lên
Chuỗi đã cho là cad. A được tạo ra bởi A. Các c, A và d kết hợp để có đượ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 cú pháp từ dưới lên, S -> aABe (Thay thế B ->d)
S -> aAde (Thay thế A -> Abc)
S -> aAbcde (Substuting A -> b)
S -> abbcde
Thay thế bắt đầu với biến bên phải nhất đầu tiên và sau đó chuyển sang vị trí bên trái tiếp theo, v.v. Do đó, nó tuân theo một phương pháp dẫn xuất mot trái.
Sự khác biệt giữa phân tích cú pháp từ trên xuống và từ dưới lên là gì?
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 mà đầu tiên nhìn vào cấp cao nhất của cây phân tích cú pháp và xử lý cây phân tích cú pháp bằng cách sử dụng các quy tắc của 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 mà đầu tiên nhìn vào cấp thấp nhất của cây phân tích cú pháp và điều chỉnh cây phân tích cú pháp bằng cách sử dụng các quy tắc của 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 quá trình 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, trong phân tích cú pháp từ dưới lên.
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 để tạo chuỗi trong khi quyết định chính trong phân tích cú pháp từ dưới xuống là chọn thời điểm sử dụng quy tắc sản xuất để giảm chuỗi xuống 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 dẫn xuất bên trái và phân tích cú pháp từ dưới xuống sử dụng hầu hết các dẫn xuất bên phải.
Tóm tắt - Phân tích cú pháp từ trên xuống so với từ dưới lên
Sự khác biệt 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 thực hiện phân tích cú pháp từ biểu tượng dấu sao đến 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 đến biểu tượng bắt đầu.
