it-swarm-vi.com

Những ưu điểm và nhược điểm chính của phân tích LL và LR là gì?

Khi xây dựng một trình phân tích cú pháp thành ngôn ngữ lập trình những gì tôi kiếm được và những gì tôi đã mất khi chọn cái này hay cái khác?

29
Maniero

Tôi sẽ đối chiếu phân tích LL và LR cho một số tiêu chí:

Độ phức tạp

LL thắng đây, xuống tay. Bạn có thể dễ dàng viết tay một trình phân tích cú pháp LL. Trong thực tế, điều này thường được thực hiện: trình biên dịch Microsoft C # là một trình phân tích cú pháp gốc đệ quy viết tay (nguồn ở đây , hãy tìm một bình luận được thực hiện bởi Patrick Kristiansen - bài đăng trên blog cũng rất thú vị).

Phân tích cú pháp LR sử dụng một phương pháp khá trực quan để phân tích văn bản. Nó hoạt động, nhưng tôi phải mất một thời gian để xoay quanh cách nó hoạt động chính xác. Do đó, viết một trình phân tích cú pháp như vậy rất khó: bạn sẽ ít nhiều thực hiện trình tạo trình phân tích cú pháp LR.

Tính tổng quát

LR thắng ở đây: tất cả các ngôn ngữ LL là ngôn ngữ LR, nhưng có nhiều ngôn ngữ LR hơn ngôn ngữ LL (ngôn ngữ là ngôn ngữ LL nếu có thể được phân tích cú pháp bằng trình phân tích cú pháp LL và ngôn ngữ là ngôn ngữ LR nếu có thể được phân tích cú pháp một trình phân tích cú pháp LR).

LL có khá nhiều phiền toái mà will làm phiền bạn khi thực hiện bất kỳ ngôn ngữ lập trình nào. Xem tại đây để biết tổng quan.

Có những ngôn ngữ không rõ ràng không phải là ngôn ngữ LR, nhưng những ngôn ngữ này khá hiếm. Bạn gần như không bao giờ gặp phải những ngôn ngữ như vậy. Tuy nhiên, LALR có một vài vấn đề.

LALR ít nhiều là một hack cho các trình phân tích cú pháp LR để làm cho các bảng nhỏ hơn. Các bảng cho một trình phân tích cú pháp LR thường có thể phát triển rất lớn. Các trình phân tích cú pháp LALR từ bỏ khả năng phân tích tất cả các ngôn ngữ LR để đổi lấy các bảng nhỏ hơn. Hầu hết các trình phân tích cú pháp LR thực sự sử dụng LALR (mặc dù không bí mật, bạn thường có thể tìm thấy chính xác những gì nó thực hiện).

LALR có thể phàn nàn về xung đột giảm-giảm và giảm-giảm. Điều này được gây ra bởi hack bảng: nó gấp các mục tương tự lại với nhau, hoạt động vì hầu hết các mục đều trống, nhưng khi chúng không trống, nó sẽ tạo ra xung đột. Những loại lỗi này không tự nhiên, khó hiểu và các bản sửa lỗi thường khá kỳ lạ.

Lỗi trình biên dịch và khôi phục lỗi

LL thắng ở đây. Trong một phân tích LL, thường rất dễ phát ra các lỗi trình biên dịch hữu ích, đặc biệt là trong các trình phân tích cú pháp viết tay. Bạn biết những gì bạn đang mong đợi tiếp theo, vì vậy nếu nó không bật lên, bạn thường biết những gì đã sai và lỗi hợp lý nhất sẽ là gì.

Ngoài ra, trong phân tích LL, phục hồi lỗi dễ dàng hơn rất nhiều. Nếu một đầu vào không phân tích chính xác, bạn có thể cố gắng bỏ qua trước một chút và tìm hiểu xem phần còn lại của đầu vào có phân tích chính xác không. Ví dụ, nếu một số câu lệnh lập trình không đúng định dạng, bạn có thể bỏ qua và phân tích cú pháp tiếp theo, để bạn có thể bắt được nhiều hơn một lỗi.

Sử dụng một trình phân tích cú pháp LR điều này khó khăn hơn rất nhiều. Bạn có thể cố gắng tăng cường ngữ pháp của mình để nó chấp nhận lỗi nhập liệu và in lỗi trong các lĩnh vực xảy ra sự cố, nhưng điều này thường khá khó thực hiện. Cơ hội bạn kết thúc với một ngữ pháp không phải là LR (hoặc không phải LALR) cũng tăng lên.

Tốc độ

Tốc độ không thực sự là vấn đề với cách bạn phân tích cú pháp đầu vào (LL hoặc LR), mà là chất lượng của mã kết quả và việc sử dụng bảng (bạn có thể sử dụng bảng cho cả LL và LR). LL và LR do đó có thể so sánh về mặt này.

Liên kết

Ở đây là một liên kết đến một trang web cũng tương phản với LL và LR. Hãy tìm phần gần phía dưới.

Tại đây bạn có thể tìm thấy một cuộc trò chuyện liên quan đến sự khác biệt. Mặc dù vậy, đó không phải là một ý kiến ​​tồi để xem xét nghiêm túc các ý kiến ​​phát biểu ở đó, có một chút thánh chiến đang diễn ra ở đó.

Để biết thêm thông tin, tại đâytại đây là hai bài đăng của riêng tôi về trình phân tích cú pháp, mặc dù chúng không hoàn toàn về sự tương phản giữa LL và LR.

44
Alex ten Brink