Tại sao ngữ pháp LR (1) này không phải là LALR (1)?

Question

Đây không phải là bài tập về nhà của tôi, tôi đang cố gắng hiểu LALR (k) ngữ pháp. Vì vậy, tôi tìm thấy this

S -> aEa | bEb | aFb | bFa 
E -> e 
F -> e 

tôi đã thực hiện một phân tích (có sẵn dưới dạng PDF trong git repo như LR1notLARL1.pdf

Nhưng tôi không thể tìm ra, tại sao LR ngữ pháp này không LALR? Can bất cứ ai giúp đỡ của tôi ? tôi Cảm ơn bạn

Answer 1

Hãy bắt đầu bằng việc xây dựng LR bộ (1) configurating cho ngữ pháp:

(1) 
S' -> .S [$] 
S -> .aEa [$] 
S -> .aFb [$] 
S -> .bFa [$] 
S -> .bEb [$] 

(2) 
S' -> S. [$] 

(3) 
S -> a.Ea [$] 
S -> a.Fb [$] 
E -> .e [a] 
F -> .e [b] 

(4) 
E -> e. [a] 
F -> e. [b] 

(5) 
S -> aE.a [$] 

(6) 
S -> aEa. [$] 

(7) 
S -> aF.b [$] 

(8) 
S -> aFb. [$] 

(9) 
S -> b.Fa [$] 
S -> b.Eb [$] 
E -> .e [b] 
F -> .e [a] 

(10) 
E -> e. [b] 
F -> e. [a] 

(11) 
S -> bF.a [$] 

(12) 
S -> bFa. [$] 

(13) 
S -> bE.b [$] 

(14) 
S -> bEb. [$] 

Nếu yo thông báo u'll, tiểu bang (4) và (10) có lõi tương tự, vì vậy trong LALR (1) automaton chúng tôi muốn kết hợp chúng với nhau để tạo trạng thái mới

(4, 10) 
E -> e. [a, b] 
F -> e. [a, b] 

Mà bây giờ có một giảm/giảm xung đột trong nó (tất cả các xung đột trong LALR (1) mà không có trong LR (1) phân tích cú pháp được giảm/giảm, bằng cách này). Điều này giải thích tại sao ngữ pháp là LR (1) nhưng không phải là LALR (1).

Hy vọng điều này sẽ hữu ích!