Sự khác nhau giữa các trình phân tích cú pháp LR, SLR và LALR là gì?

Question

Sự khác nhau thực sự giữa các trình phân tích cú pháp LR, SLR và LALR là gì? Tôi biết rằng SLR và LALR là các loại trình phân tích cú pháp LR, nhưng sự khác biệt thực sự như xa như các bảng phân tích cú pháp của chúng là gì?

Và cách hiển thị ngữ pháp là LR, SLR hoặc LALR? Đối với một ngữ pháp LL, chúng ta chỉ cần cho thấy rằng bất kỳ ô nào của bảng phân tích cú pháp không được chứa nhiều quy tắc sản xuất. Bất kỳ quy tắc tương tự cho LALR, SLR và LR?

Ví dụ, làm thế nào chúng ta có thể thấy rằng ngữ pháp

S --> Aa | bAc | dc | bda 
A --> d 

là LALR (1) nhưng không phải SLR (1)?

---

EDIT (ybungalobill): Tôi đã không nhận được một câu trả lời thỏa đáng cho sự khác biệt giữa LALR và LR là những gì. Vì vậy, các bảng của LALR có kích thước nhỏ hơn nhưng nó chỉ có thể nhận ra một tập con của các ngữ pháp LR. Ai đó có thể xây dựng thêm về sự khác biệt giữa LALR và LR không? LALR (1) và LR (1) sẽ đủ cho câu trả lời. Cả hai người trong số họ sử dụng 1 mã thông báo nhìn về phía trước và cả hai đều được điều khiển theo bảng! Chúng khác nhau như thế nào?

Answer 1

Máy phân tích cú pháp SLR, LALR và LR đều có thể được thực hiện bằng cách sử dụng chính xác cùng một máy theo bảng.

Về cơ bản, các thuật toán phân tích cú pháp thu thập đầu vào tiếp theo thẻ T, và tư vấn tình trạng S hiện tại (và liên lookahead, GOTO, và bảng giảm) để quyết định những việc cần làm:

• SHIFT: Nếu hiện tại bảng nói đến SHIFT trên mã thông báo T, cặp (S, T) được đẩy lên ngăn xếp phân tích cú pháp, trạng thái được thay đổi theo những gì bảng GOTO nói cho mã thông báo hiện tại (ví dụ, GOTO (T)), một mã thông báo đầu vào khác T 'được tìm nạp và quá trình lặp lại
• GIẢM: Mỗi trạng thái có 0, 1 hoặc nhiều lần giảm có thể xảy ra trong tiểu bang. Nếu trình phân tích cú pháp là LR hoặc LALR, mã thông báo được kiểm tra đối với các bộ lookahead cho tất cả các phép cắt hợp lệ cho trạng thái. Nếu mã thông báo khớp với tập hợp lookahead để giảm quy tắc ngữ pháp G = R1 R2 .. Rn, giảm và thay đổi ngăn xếp xảy ra: hành động ngữ nghĩa cho G được gọi, ngăn xếp được bật n (từ Rn) lần, cặp (S, G) được đẩy lên ngăn xếp, trạng thái S mới được đặt thành GOTO (G) và chu trình lặp lại với cùng mã thông báo T. Nếu trình phân tích cú pháp là trình phân tích cú pháp SLR, có nhiều nhất một quy tắc giảm cho nhà nước và vì vậy hành động giảm có thể được thực hiện một cách mù quáng mà không cần tìm kiếm để xem mức giảm nào được áp dụng. Nó rất hữu ích cho một trình phân tích cú pháp SLR để biết liệu có là giảm hay không; điều này rất dễ dàng để biết liệu mỗi tiểu bang có ghi lại rõ ràng số lượng giảm liên quan đến nó hay không, và số đó là cần thiết cho các phiên bản L (AL) R trong thực tế.
• L ERI: Nếu không thể thực hiện cả SHIFT lẫn REDUCE, lỗi cú pháp sẽ được khai báo.

Vì vậy, nếu tất cả chúng đều sử dụng cùng một máy móc, thì vấn đề là gì?

Giá trị mục tiêu trong SLR là tính đơn giản của nó trong việc triển khai; bạn không phải quét qua các bộ kiểm tra có thể cắt giảm có thể do có nhiều nhất, và đây là hành động khả thi duy nhất nếu không có SHIFT thoát khỏi tiểu bang. Mức giảm nào được áp dụng có thể được gắn riêng cho tiểu bang, do đó, máy phân tích cú pháp SLR không phải tìm kiếm nó. Trong thực tế, các trình phân tích cú pháp R (AL) R xử lý một tập hợp langauges có ích hơn và rất ít công việc để thực hiện không ai thực hiện SLR ngoại trừ một bài tập học thuật.

Sự khác biệt giữa LALR và LR phải làm với bảng máy phát điện. Máy phát điện phân tích LR theo dõi tất cả các giảm có thể từ các trạng thái cụ thể và bộ nhìn chính xác của chúng; bạn kết thúc với các trạng thái trong đó mọi giảm được kết hợp với bộ nhìn chính xác của nó từ ngữ cảnh bên trái của nó. Điều này có xu hướng xây dựng các bộ trạng thái khá lớn. Các trình tạo trình phân tích cú pháp LALR sẵn sàng kết hợp các trạng thái nếu các bảng GOTO và các bộ đầu để cắt giảm tương thích và không xung đột; điều này tạo ra số lượng nhỏ hơn đáng kể các trạng thái, với mức giá không thể phân biệt các chuỗi ký hiệu nhất định mà LR có thể phân biệt. Vì vậy, các trình phân tích cú pháp LR có thể phân tích một bộ ngôn ngữ lớn hơn các trình phân tích cú pháp LALR, nhưng có các bảng phân tích cú pháp lớn hơn rất nhiều. Trong thực tế, người ta có thể tìm thấy các ngữ pháp LALR đủ gần với các langau đích mà kích thước của máy trạng thái đáng được tối ưu hóa; những nơi mà trình phân tích cú pháp LR sẽ được xử lý tốt hơn bằng cách kiểm tra đặc biệt bên ngoài trình phân tích cú pháp.

Vì vậy: Cả ba đều sử dụng cùng một máy móc. SLR là "dễ dàng" trong ý nghĩa rằng bạn có thể bỏ qua một chút nhỏ của máy móc, nhưng nó chỉ là không có giá trị rắc rối. LR phân tích một tập hợp các langauges rộng hơn nhưng các bảng trạng thái có xu hướng khá lớn. Điều đó khiến LALR trở thành sự lựa chọn thực tế.

Có nói tất cả điều này, nó là giá trị biết rằng GLR parsers có thể phân tích bất kỳ bối cảnh ngôn ngữ miễn phí, sử dụng máy móc thiết bị phức tạp hơn nhưng chính xác các bảng cùng (bao gồm cả phiên bản nhỏ hơn được sử dụng bởi LALR). Điều này có nghĩa là GLR mạnh hơn LR, LALR và SLR; khá nhiều nếu bạn có thể viết một ngữ pháp BNF chuẩn, GLR sẽ phân tích theo nó. Sự khác biệt trong máy móc là GLR sẵn sàng thử nhiều phân tích cú pháp khi có xung đột giữa bảng GOTO và các bộ lookahead. (Làm thế nào GLR thực hiện điều này một cách hiệu quả là thiên tài tuyệt đối [không phải của tôi] nhưng sẽ không phù hợp trong bài SO này).

Điều đó đối với tôi là một thực tế vô cùng hữu ích. Tôi xây dựng các trình phân tích chương trình và các trình biến đổi mã và trình phân tích cú pháp là cần thiết nhưng "không quan tâm"; công việc thú vị là những gì bạn làm với kết quả được phân tích cú pháp và do đó trọng tâm là làm công việc hậu phân tích cú pháp. Sử dụng GLR có nghĩa là tôi có thể tương đối dễ dàng xây dựng các ngữ pháp làm việc, so với việc hack một ngữ pháp để có được dạng LALR có thể sử dụng được. Điều này rất quan trọng khi cố gắng đối phó với các ngôn ngữ không học thuật như C++ hoặc Fortran, nơi bạn thực sự cần hàng nghìn quy tắc để xử lý toàn bộ ngôn ngữ, và bạn không muốn dành cả cuộc đời để cố gắng thực hiện các quy tắc ngữ pháp đáp ứng các giới hạn của LALR (hoặc thậm chí LR).

Như một loại ví dụ nổi tiếng, C++ được coi là cực kỳ khó phân tích ... bởi những kẻ làm phân tích cú pháp LALR. C++ là đơn giản để phân tích cú pháp bằng cách sử dụng máy móc GLR sử dụng khá nhiều quy tắc được cung cấp ở mặt sau của hướng dẫn tham khảo C++. (Tôi có trình phân tích cú pháp chính xác như vậy, và nó xử lý không chỉ vani C++, mà còn có nhiều phương ngữ của nhà cung cấp. Điều này chỉ có thể thực hiện được vì chúng tôi đang sử dụng trình phân tích cú pháp GLR, IMHO).

[EDIT tháng 11 năm 2011: Chúng tôi đã mở rộng trình phân tích cú pháp của mình để xử lý tất cả C++ 11. GLR giúp dễ dàng hơn nhiều.]

Answer 2

Trình phân tích cú pháp LALR hợp nhất các trạng thái tương tự trong ngữ pháp LR để tạo ra các bảng trạng thái phân tích có cùng kích thước với ngữ pháp SLR tương đương, thường có độ lớn nhỏ hơn thuần túy Bảng phân tích LR. Tuy nhiên, đối với các ngữ pháp LR quá phức tạp để là LALR, các trạng thái hợp nhất này dẫn đến xung đột phân tích cú pháp hoặc tạo ra một trình phân tích cú pháp không nhận thức đầy đủ ngữ pháp LR ban đầu.

BTW, tôi đề cập đến một vài điều về điều này trong thuật toán bảng phân tích cú pháp MLR (k) của tôi here.

Phụ Lục

Câu trả lời ngắn gọn là các bảng LALR phân tích cú pháp có kích thước nhỏ, nhưng máy móc thiết bị phân tích cú pháp là như nhau. Một ngữ pháp LALR đã cho sẽ tạo ra các bảng phân tích lớn hơn nhiều nếu tất cả các trạng thái LR được tạo ra, với rất nhiều trạng thái dư thừa (gần giống hệt).

Bảng LALR nhỏ hơn vì các trạng thái tương tự (dư thừa) được hợp nhất với nhau, loại bỏ hiệu quả thông tin ngữ cảnh/tra cứu mà các trạng thái riêng biệt mã hóa. Ưu điểm là bạn nhận được nhiều bảng phân tích cú pháp nhỏ hơn cho cùng một ngữ pháp.

Hạn chế là không phải tất cả các ngữ pháp LR có thể được mã hóa thành các bảng LALR vì các ngữ pháp phức tạp hơn có các lookaheads phức tạp hơn, dẫn đến hai hoặc nhiều trạng thái thay vì một trạng thái hợp nhất.

Sự khác biệt chính là thuật toán tạo các bảng LR mang nhiều thông tin hơn giữa các chuyển tiếp từ trạng thái này sang trạng thái khác trong khi thuật toán LALR thì không. Vì vậy, thuật toán LALR không thể biết liệu một trạng thái hợp nhất đã cho có thực sự được để lại dưới dạng hai hoặc nhiều trạng thái riêng biệt hay không.

Answer 3

Sự khác biệt cơ bản giữa các bảng phân tích cú pháp được tạo với SLR vs LR, là các hành động giảm được dựa trên các giá trị đặt cho các bảng SLR. Điều này có thể quá hạn chế, cuối cùng gây ra một cuộc xung đột giảm thiểu sự thay đổi.

Một trình phân tích cú pháp LR, mặt khác, các căn cứ chỉ giảm các quyết định trên tập hợp các thiết bị đầu cuối mà thực sự có thể thực hiện theo các thiết bị đầu cuối không bị giảm. Tập hợp các thiết bị đầu cuối này thường là một tập hợp con thích hợp của tập hợp Follows của một thiết bị phi đầu cuối như vậy, và do đó ít có cơ hội xung đột với các hành động thay đổi.

Trình phân tích cú pháp LR mạnh hơn vì lý do này. Tuy nhiên, các bảng phân tích LR có thể rất lớn.

Trình phân tích cú pháp LALR bắt đầu với ý tưởng xây dựng bảng phân tích LR, nhưng kết hợp các trạng thái được tạo theo cách dẫn đến kích thước bảng ít hơn đáng kể. Nhược điểm là một cơ hội nhỏ của xung đột sẽ được giới thiệu cho một số ngữ pháp mà một bảng LR nếu không có thể tránh được.

Trình phân tích cú pháp LALR hơi kém mạnh hơn các trình phân tích cú pháp LR, nhưng vẫn mạnh hơn các trình phân tích cú pháp SLR. YACC và các trình tạo phân tích cú pháp khác có xu hướng sử dụng LALR vì lý do này.

P.S. Đối với ngắn gọn, SLR, LALR và LR trên thực sự có nghĩa là SLR (1), LALR (1), và LR (1), do đó, một lookahead mã thông báo được ngụ ý.

Answer 4

Một câu trả lời khác (YAA). Các thuật toán phân tích cú pháp cho SLR (1), LALR (1) và LR (1) giống hệt như Ira Baxter cho biết,
tuy nhiên, các bảng phân tích cú pháp có thể khác nhau do thuật toán tạo phân tích cú pháp.

Trình tạo trình phân tích cú pháp SLR tạo ra máy trạng thái LR (0) và tính toán các giao diện từ ngữ pháp (bộ FIRST và FOLLOW). Đây là một cách tiếp cận đơn giản và có thể báo cáo xung đột không thực sự tồn tại trong máy trạng thái LR (0).

Trình tạo trình phân tích cú pháp LALR tạo một máy trạng thái LR (0) và tính toán các giao diện từ máy trạng thái LR (0) (thông qua các chuyển tiếp đầu cuối). Đây là một cách tiếp cận đúng, nhưng đôi khi báo cáo xung đột sẽ không tồn tại trong một máy trạng thái LR (1).

Trình tạo phân tích cú pháp LR của Canon tính toán máy trạng thái LR (1) và các giao diện đã là một phần của máy trạng thái LR (1). Các bảng phân tích cú pháp này có thể rất lớn.

Máy phát phân tích LR tối thiểu tính toán máy trạng thái LR (1), nhưng hợp nhất các trạng thái tương thích trong quá trình, sau đó tính toán các điểm nhìn từ máy trạng thái LR (1) tối thiểu. Các bảng phân tích cú pháp này có cùng kích thước hoặc lớn hơn một chút so với các bảng phân tích cú pháp LALR, đưa ra giải pháp tốt nhất.

LRSTAR 8.0 có thể tạo các trình phân tích cú pháp LALR (1), LR tối thiểu (1) và LR (k) trong C++.

Answer 5

Trình phân tích cú pháp SLR nhận dạng một tập hợp con ngữ pháp thích hợp được nhận dạng bởi LALR (1) phân tích cú pháp, từ đó nhận ra tập hợp con ngữ pháp thích hợp được nhận dạng bởi các trình phân tích cú pháp LR (1).

Mỗi trong số này được xây dựng như một máy trạng thái, với mỗi trạng thái đại diện cho một số bộ quy tắc sản xuất ngữ pháp (và vị trí trong mỗi) khi phân tích cú pháp đầu vào.

Các Dragon Book ví dụ về một LALR (1) ngữ pháp đó không phải là SLR là thế này:

S → L = R | R 
L → * R | id 
R → L 

Đây là một trong những quốc gia về ngữ pháp này:

S → L•= R 
R → L• 

Các • chỉ ra vị trí của trình phân tích cú pháp trong mỗi sản phẩm có thể có. Nó không biết sản phẩm nào thực sự cho đến khi nó kết thúc và cố gắng giảm.

Tại đây, trình phân tích cú pháp có thể thay đổi = hoặc giảm R → L.

Một SLR (aka LR (0)) phân tích cú pháp sẽ xác định xem nó có thể giảm bằng cách kiểm tra nếu các biểu tượng đầu vào tiếp theo là trong làm theo thiết của R (ví dụ, các thiết lập của tất cả các thiết bị đầu cuối trong ngữ pháp mà có thể làm theo R). Vì = cũng nằm trong tập hợp này, trình phân tích cú pháp SLR gặp phải một cuộc xung đột giảm dần.

Tuy nhiên, một LALR (1) phân tích cú pháp sẽ sử dụng các thiết lập của tất cả các thiết bị đầu cuối có thể làm theo sản xuất này đặc biệt của R, đó là chỉ $ (ví dụ, cuối đầu vào). Vì vậy, không có xung đột.

Như những người nhận xét trước đã lưu ý, LALR (1) trình phân tích cú pháp có cùng số trạng thái như trình phân tích cú pháp SLR. Thuật toán tuyên truyền lookahead được sử dụng để tack lookaheads vào sản phẩm trạng thái SLR từ các trạng thái LR (1) tương ứng. Trình phân tích cú pháp LALR (1) có thể đưa ra các xung đột giảm thiểu không có trong trình phân tích cú pháp LR (1), nhưng nó không thể giới thiệu các xung đột giảm-giảm.

Trong ví dụ của bạn, các LALR sau (1) nhà nước gây ra một cuộc xung đột shift-giảm trong một thực hiện SLR:

S → b d•a/$ 
A → d•/c 

Biểu tượng sau / là sau bộ đối với từng sản xuất trong LALR (1) phân tích cú pháp. Trong SLR, theo dõi (A) bao gồm a, cũng có thể được dịch chuyển.

Answer 6

Một câu trả lời đơn giản là tất cả các ngôn ngữ LR (0) là LALR (1) Ngữ pháp. So với LR (1), LALR (1) có nhiều trạng thái hơn trong DFA liên quan (gần như hai trạng thái). Và đó là lý do chính cho LALR (1) ngữ pháp mất nhiều thời gian hơn để hiển thị lỗi hơn LR (1) ngữ pháp. Và một điều quan trọng nữa cần biết về hai ngữ pháp này là trong LR (1) Grammars chúng ta không thể tìm thấy shift/reduce hoặc reduce/reduce conflicts.But trong LALR (1) có khả năng giảm/giảm xung đột.

Answer 7

Giả sử một trình phân tích cú pháp mà không có một lookahead đang phân tích cú pháp các chuỗi cho ngữ pháp của bạn.

Sử dụng ví dụ nhất định của bạn, nó đi qua một chuỗi dc, nó sẽ làm gì? Liệu nó có làm giảm nó thành S, bởi vì dc là một chuỗi hợp lệ được tạo ra bởi ngữ pháp này? HOẶC có lẽ chúng tôi đang cố gắng phân tích cú pháp bdc bởi vì ngay cả đó là một chuỗi có thể chấp nhận được?

Vì con người chúng ta biết câu trả lời là đơn giản, chúng ta chỉ cần nhớ nếu chúng ta vừa phân tích cú pháp b hay không. Nhưng máy vi tính là ngu ngốc :)

Vì một trình phân tích cú pháp (LR) có sức mạnh bổ sung trên LR (0) để thực hiện một điều tra, chúng tôi biết rằng bất kỳ số tiền nào không thể cho chúng tôi biết phải làm gì trong trường hợp này; thay vào đó, chúng ta cần nhìn lại quá khứ của mình. Vì vậy, đến trình phân tích cú pháp LR chuẩn để giải cứu. Nó ghi nhớ bối cảnh trong quá khứ.

Cách thức ghi nhớ ngữ cảnh này là nó tự kỷ luật, bất cứ khi nào nó gặp phải b, nó sẽ bắt đầu đi trên con đường hướng tới việc đọc bdc, như một khả năng. Vì vậy, khi nó nhìn thấy một d nó biết liệu nó đã đi bộ một con đường. Do đó, trình phân tích cú pháp CLR (1) có thể làm những việc mà một trình phân tích cú pháp SLR (1) không thể!

Nhưng bây giờ, vì chúng tôi phải xác định rất nhiều đường dẫn, các trạng thái của máy sẽ rất lớn!

Vì vậy, chúng tôi hợp nhất các đường dẫn tìm kiếm giống nhau, nhưng theo dự kiến, điều đó có thể dẫn đến các vấn đề về sự nhầm lẫn. Tuy nhiên, chúng tôi sẵn sàng chấp nhận rủi ro với chi phí giảm kích thước.

Đây là trình phân tích cú pháp LALR (1) của bạn.

---

Bây giờ, làm cách nào để thực hiện thuật toán.

Khi bạn vẽ các bộ cấu hình cho ngôn ngữ trên, bạn sẽ thấy một xung đột giảm-giảm ở hai trạng thái. Để loại bỏ chúng, bạn có thể muốn xem xét một SLR (1), trong đó có quyết định xem xét một theo, nhưng bạn sẽ quan sát thấy rằng nó vẫn sẽ không thể. Vì vậy, bạn sẽ vẽ các tập cấu hình một lần nữa nhưng lần này với một hạn chế mà bất cứ khi nào bạn tính toán việc đóng, các sản phẩm bổ sung được thêm phải có (các) sự theo dõi nghiêm ngặt. Tham khảo bất kỳ sách giáo khoa về những gì nên làm theo được.