Lợi ích của phân tích cú pháp ứng dụng qua phân tích cú pháp đơn thuần là gì?

Question

Dường như có một sự đồng thuận rằng bạn nên sử dụng Parsec như một ứng dụng chứ không phải là một đơn nguyên. Lợi ích của phân tích cú pháp ứng dụng qua phân tích cú pháp đơn thuần là gì?

• phong cách
• hiệu suất
• trừu tượng

là monadic phân tích ra?

Answer 1

Sự khác biệt chính giữa phân tích cú pháp đơn và ứng dụng là cách xử lý thành phần tuần tự. Trong trường hợp của một trình phân tích cú pháp, chúng tôi sử dụng (<*>), trong khi với một đơn nguyên, chúng tôi sử dụng (>>=).

(<*>) :: Parser (a -> b) -> Parser a -> Parser b 
(>>=) :: Parser a -> (a -> Parser b) -> Parser b 

Cách tiếp cận đơn giản linh hoạt hơn, vì ngữ pháp của phần thứ hai phụ thuộc vào kết quả đầu tiên, nhưng chúng tôi hiếm khi cần thêm tính linh hoạt trong thực tế.

Bạn có thể nghĩ rằng có một số tính linh hoạt bổ sung không thể làm tổn thương, nhưng thực tế nó có thể. Nó ngăn cản chúng tôi làm phân tích tĩnh hữu ích trên một trình phân tích cú pháp mà không cần chạy nó. Ví dụ: giả sử chúng tôi muốn biết liệu trình phân tích cú pháp có thể khớp với chuỗi trống hay không và những ký tự đầu tiên có thể có trong kết quả trùng khớp. Chúng tôi muốn chức năng

empty :: Parser a -> Bool 
first :: Parser a -> Set Char 

Với trình phân tích cú pháp, chúng tôi có thể dễ dàng trả lời câu hỏi này. (Tôi đang gian lận một chút ở đây. Hãy tưởng tượng chúng tôi có một nhà xây dựng dữ liệu tương ứng với (<*>) và (>>=) trong phân tích cú pháp ứng cử viên của chúng tôi "ngôn ngữ").

empty (f <*> x) = empty f && empty x 
first (f <*> x) | empty f = first f `union` first x 
       | otherwise = first f 

Tuy nhiên, với trình phân tích cú pháp đơn thuần, chúng tôi không biết ngữ pháp của phần thứ hai là gì mà không biết đầu vào.

empty (x >>= f) = empty x && empty (f ???) 
first (x >>= f) | empty x = first x `union` first (f ???) 
       | otherwise = first x 

Bằng cách cho phép nhiều hơn, chúng tôi có thể giải thích ít hơn. Điều này tương tự như sự lựa chọn giữa các hệ thống kiểu động và tĩnh.

Nhưng điểm này là gì? Chúng ta có thể sử dụng kiến ​​thức tĩnh bổ sung này để làm gì? Ví dụ, chúng ta có thể sử dụng nó để tránh backtracking trong LL (1) phân tích cú pháp bằng cách so sánh các ký tự tiếp theo để first thiết lập của mỗi thay thế. Chúng tôi cũng có thể xác định tĩnh cho dù điều này có thể mơ hồ hay không bằng cách kiểm tra xem first có hai lựa chọn thay thế trùng lặp hay không.

Ví dụ khác là nó có thể được sử dụng để phục hồi lỗi, như được hiển thị trong giấy Deterministic, Error-Correcting Combinator Parsers bởi S. Doaitse Swierstra và Luc Duponcheel.

Thông thường, tuy nhiên, sự lựa chọn giữa phân tích cú pháp ứng dụng và đơn lẻ đã được thực hiện bởi các tác giả của thư viện phân tích mà bạn đang sử dụng. Khi một thư viện như Parsec trưng ra cả hai giao diện, sự lựa chọn cái nào để sử dụng hoàn toàn là một phong cách. Trong một số trường hợp, mã ứng dụng dễ đọc hơn mã đơn điệu và đôi khi nó là một cách khác.

Answer 2

Với Parsec lợi ích của việc sử dụng Applicative chỉ là phong cách. Monad có lợi thế là nó mạnh hơn - bạn có thể triển khai thực hiện phân tích ngữ cảnh nhạy cảm.

Phân tích UU của Doaitse Swierstra hiệu quả hơn nếu chỉ được sử dụng.

Answer 3

Đơn vị quảng cáo hoàn toàn là trừu tượng chi tiết hơn so với Đơn đăng ký. Bạn có thể viết

instance (Monad m) => Applicative m where 
    pure = return 
    (<*>) = ap 

Nhưng không có cách nào để viết

instance (Applicative a) => Monad a where 
    return = pure 
    (>>=) = ??? 

Vì vậy, có, nó thực chất là một vấn đề của phong cách. Tôi tưởng tượng nếu bạn sử dụng return và ap, thì phải có không bị mất hiệu suất khi sử dụng pure và <*>. Vì ứng dụng là giao diện nhỏ hơn nghiêm ngặt so với Monad, điều này có nghĩa là <*> đôi khi có thể được tối ưu hóa cao hơn ap. (Nhưng với quy tắc viết lại GHC thông minh, người ta thường có thể đạt được cùng một sự tối ưu hóa bất kể.)

Phân tích đơn thuần có phải không?

Vì Monads là tập hợp con của các ứng dụng, tôi sẽ kết luận rằng phân tích cú pháp ứng dụng là tập con của phân tích cú pháp đơn thuần.

Answer 4

Lý do chính tôi có thể thấy để thích phân tích cú pháp đơn trên trình phân tích cú pháp đơn thuần là lý do chính để ưu tiên mã đơn trên mã đơn lẻ trong bất kỳ ngữ cảnh nào: ít mạnh mẽ hơn, các ứng dụng đơn giản hơn.

Đây là ví dụ về nguyên tắc kỹ thuật tổng quát hơn: sử dụng công cụ đơn giản nhất để thực hiện công việc. Không sử dụng thang nâng khi một dolly sẽ làm. Không sử dụng cưa bàn để cắt các phiếu giảm giá. Đừng viết mã số IO khi nó có thể thuần khiết. Giữ nó đơn giản.

Nhưng đôi khi, bạn cần công suất bổ sung là Monad. Một dấu hiệu chắc chắn của điều này là khi bạn cần phải thay đổi quá trình tính toán dựa trên những gì đã được tính toán cho đến nay. Trong phân tích cú pháp, điều này có nghĩa là xác định cách phân tích cú pháp những gì tiếp theo dựa trên những gì đã được phân tích cú pháp cho đến nay; nói cách khác bạn có thể xây dựng ngữ pháp ngữ cảnh nhạy cảm theo cách này.

Answer 5

Nếu trình phân tích cú pháp hoàn toàn là ứng dụng, có thể phân tích cấu trúc của nó và "tối ưu hóa" cấu trúc đó trước khi chạy. Nếu một trình phân tích cú pháp là monadic, về cơ bản nó là một chương trình Turing-complete, và thực hiện hầu như bất kỳ phân tích thú vị nào của nó tương đương với việc giải quyết vấn đề dừng (ví dụ, không thể).

Oh, và có, có sự khác biệt về phong cách quá ...