LALR vs LL parser

Question

Tôi đã sử dụng lex/yacc và bây giờ tôi đang cố chuyển sang ANTLR. Mối quan tâm chính là ANTLR là một trình phân tích cú pháp LL (*) không giống yacc là LALR. Tôi đã từng suy nghĩ từ dưới lên và tôi không biết chính xác lợi thế của ngữ pháp LL là gì. Mọi người nói rằng ngữ pháp LL dễ hiểu hơn và phổ biến hơn trong những ngày này. Nhưng có vẻ như các trình phân tích cú pháp LR mạnh hơn, ví dụ: Các trình phân tích cú pháp LL không có khả năng xử lý các cuộc truy tìm trái, mặc dù dường như có một số cách giải quyết.

Câu hỏi đặt ra là lợi thế của ngữ pháp LL đối với LALR là gì? Tôi sẽ đánh giá cao nếu ai đó có thể cho tôi một số ví dụ. Liên kết đến các bài viết hữu ích cũng sẽ tuyệt vời.

Cảm ơn sự giúp đỡ của bạn trước!

(Tôi thấy đây là một nguồn lực lớn:. What advantages do LL parsers have over LR parsers?, nhưng nó sẽ đã tốt hơn với một số ví dụ)

Answer 1

Lợi thế lớn nhất tôi thấy để LL phân tích cú pháp là họ rất dễ hiểu và thực hiện! Bạn có thể viết tay recursive descent trình phân tích cú pháp có mã phù hợp chặt chẽ với ngữ pháp.

LR thường được coi là mạnh hơn và nhanh hơn cũng nhiều nhưng có một vài sự đánh đổi thương mại mà tôi biết:

• parsers LR chỉ có thể sử dụng thuộc tính tổng hợp; họ không thể vượt qua các thuộc tính kế thừa.
• Các hành động trong ngữ pháp LR có thể gây ra tính không xác định ngữ pháp nhưng không phải trong LL.

Tuy nhiên, bạn sẽ thấy rằng LL (*) cũng rất mạnh.

Answer 2

Trình phân tích cú pháp LR mạnh hơn các trình phân tích cú pháp LL, và ngoài ra, các trình phân tích cú pháp LALR có thể chạy trong O (n) giống như các trình phân tích cú pháp LL. Vì vậy, bạn sẽ không tìm thấy bất kỳ lợi thế chức năng của LL trên LR. Vì vậy, lợi thế duy nhất của LL là các máy trạng thái LR khá phức tạp và khó hiểu hơn, và các trình phân tích cú pháp LR không phải là trực quan đặc biệt. Mặt khác, mã phân tích cú pháp LL được tạo tự động có thể rất dễ hiểu và gỡ lỗi.