Thiết kế trình biên dịch - Các loại phân tích cú pháp
Bộ phân tích cú pháp tuân theo các quy tắc sản xuất được xác định bằng ngữ pháp không có ngữ cảnh. Cách thực hiện các quy tắc sản xuất (dẫn xuất) chia phân tích cú pháp thành hai loại: phân tích cú pháp từ trên xuống và phân tích cú pháp từ dưới lên.
Phân tích cú pháp từ trên xuống
Khi trình phân tích cú pháp bắt đầu xây dựng cây phân tích cú pháp từ biểu tượng bắt đầu và sau đó cố gắng chuyển đổi biểu tượng bắt đầu thành đầu vào, nó được gọi là phân tích cú pháp từ trên xuống.
Recursive descent parsing: Đây là một dạng phân tích cú pháp từ trên xuống phổ biến. Nó được gọi là đệ quy vì nó sử dụng các thủ tục đệ quy để xử lý đầu vào. Phân tích cú pháp gốc đệ quy bị backtracking.
Backtracking: Có nghĩa là, nếu một dẫn xuất của một sản xuất không thành công, trình phân tích cú pháp sẽ khởi động lại quy trình bằng cách sử dụng các quy tắc khác nhau của cùng một sản xuất. Kỹ thuật này có thể xử lý chuỗi đầu vào nhiều lần để xác định sản xuất phù hợp.
Phân tích cú pháp từ dưới lên
Như tên cho thấy, phân tích cú pháp từ dưới lên bắt đầu với các ký hiệu đầu vào và cố gắng xây dựng cây phân tích cú pháp lên đến ký hiệu bắt đầu.
Example:
Chuỗi đầu vào: a + b * c
Quy tắc sản xuất:
S → E
E → E + T
E → E * T
E → T
T → idHãy để chúng tôi bắt đầu phân tích cú pháp từ dưới lên
a + b * cĐọc đầu vào và kiểm tra xem có sản phẩm nào khớp với đầu vào không:
a + b * c
T + b * c
E + b * c
E + T * c
E * c
E * T
E
S