Ví dụ về ngữ pháp LR không thể được đại diện bởi LL?

Question

Tất cả các ngữ pháp LL là các ngữ pháp LR, nhưng không phải là cách khác, nhưng tôi vẫn đấu tranh để đối phó với sự khác biệt. Tôi tò mò về các ví dụ nhỏ, nếu có, các ngữ pháp LR không có biểu diễn LL tương đương.

Answer 1

Vâng, theo như ngữ pháp có liên quan, dễ dàng của nó - bất kỳ ngữ pháp đệ quy trái đơn giản nào là LR (có thể LR (1)) và không phải LL. Vì vậy, một danh sách ngữ pháp như:

list ::= list ',' element | element 

là LR (1) (giả định sản xuất cho phần tử) nhưng không phải LL. Những ngữ pháp như vậy có thể được chuyển đổi dễ dàng thành các ngữ pháp LL bằng cách thừa nhận trái và như vậy, do đó, điều này không quá thú vị.

Quan tâm nhiều hơn là NGÔN NGỮ không phải là LR mà không phải LL - đó là ngôn ngữ có ngữ pháp LR (1) nhưng không có ngôn ngữ LL (k) cho bất kỳ k nào. Một ví dụ là những thứ cần các kết quả phù hợp tùy chọn. Ví dụ: ngôn ngữ của bất kỳ số nào của a biểu tượng được theo sau bởi cùng một số hoặc ít hơn b biểu tượng, nhưng không nhiều hơn b s - {a^i b^j | i> = j}. Có một ngữ pháp LR (1) tầm thường:

S ::= a S | P 
P ::= a P b | \epsilon 

nhưng không có LL (k) ngữ pháp. Lý do là ngữ pháp LL cần quyết định xem có khớp cặp a + b hay kỳ quặc khi xem a, trong khi ngữ pháp LR có thể trì hoãn quyết định đó cho đến sau khi nó thấy b hoặc kết thúc của đầu vào.

This post trên cs.stackechange.com có ​​rất nhiều tài liệu tham khảo về điều này