Ngữ pháp này LR (1) nhưng không phải là SLR (1)?

Question

Tôi có ngữ pháp sau đây, mà tôi đang nói là LR (1) nhưng không phải SLR (1):

S :: = a Một | b A c | d c | b d một

Một :: = d

Tôi không hiểu tại sao điều này là. Làm thế nào bạn sẽ chứng minh điều này?

Answer 1

Một cách để tìm ra điều này là cố gắng xây dựng các trình phân tích cú pháp LR (1) và SLR (1) cho ngữ pháp. Nếu chúng tôi tìm thấy bất kỳ thay đổi/giảm hoặc giảm/giảm xung đột nào trong quá trình làm như vậy, chúng tôi có thể cho thấy ngữ pháp đó không thuộc về một trong các loại ngôn ngữ đó.

Hãy bắt đầu với trình phân tích cú pháp SLR (1). Đầu tiên, chúng ta cần tính toán các bộ cấu hình LR (0) cho ngữ pháp. Chúng được thấy ở đây:

(1) 
S -> .aA 
S -> .bAc 
S -> .dc 
S -> .bda 

(2) 
S -> a.A 
A -> .d 

(3) 
S -> aA. 

(4) 
A -> d. 

(5) 
S -> b.Ac 
S -> b.da 
A -> .d 

(6) 
S -> bA.c 

(7) 
S -> bAc. 

(8) 
S -> bd.a 
A -> d. 

(9) 
S -> bda. 

(10) 
S -> d.c 

(11) 
S -> dc. 

Tiếp theo, chúng ta cần có các bộ THEO D forI cho tất cả các nonterminals. Này được thể hiện ở đây:

FOLLOW(S) = { $ } 
FOLLOW(A) = { $, c } 

Vì điều này, chúng ta có thể quay trở lại và nâng cấp LR bộ (0) configurating vào SLR (1) bộ configurating:

(1) 
S -> .aA [ $ ] 
S -> .bAc [ $ ] 
S -> .dc [ $ ] 
S -> .bda [ $ ] 

(2) 
S -> a.A [ $ ] 
A -> .d  [ $, c ] 

(3) 
S -> aA. [ $ ] 

(4) 
A -> d.  [ $, c ] 

(5) 
S -> b.Ac [ $ ] 
S -> b.da [ $ ] 
A -> .d  [ $, c ] 

(6) 
S -> bA.c [ $ ] 

(7) 
S -> bAc. [ $ ] 

(8) 
S -> bd.a [ $ ] 
A -> d.  [ $, c ] 

(9) 
S -> bda. [ $ ] 

(10) 
S -> d.c [ $ ] 

(11) 
S -> dc. [ $ ] 

Điều thú vị là đủ, không có xung đột đây! Xung đột thay đổi/giảm có thể xảy ra ở trạng thái (8), nhưng không có xung đột ở đây vì hành động dịch chuyển là a và mức giảm là trên $. Do đó, ngữ pháp này thực sự là là SLR (1). Vì bất kỳ ngữ pháp SLR (1) nào cũng là LR (1), điều này có nghĩa là ngữ pháp là cả SLR (1) và LR (1).

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

Answer 2

Tôi không có đủ nghiệp nhận xét về câu trả lời ở trên, và tôi là một hơi muộn cho câu hỏi này, nhưng ...

Tôi đã nhìn thấy ngữ pháp này là một ví dụ ở nơi khác và OP thực sự đã mắc lỗi đánh máy. Nó phải là:

S :: = A a | b A c | d c | b d một

Một :: = d

ví dụ, mệnh đề đầu tiên của S là 'Một a', không 'một Một'.

Trong trường hợp này, sau đặt ra cho A là {$, a, c} và có một cuộc xung đột SLR trong trạng thái 8.