Tại sao dường như toán tử Parsec Choice phụ thuộc vào thứ tự của các trình phân tích cú pháp?

Question

Tôi đang cố gắng phân tích một ngôn ngữ rất đơn giản chỉ bao gồm các số thập phân hoặc số nhị phân. Ví dụ: dưới đây là một số thông tin nhập hợp lệ:

#b1 
#d1 
#b0101 
#d1234 

Tôi gặp sự cố khi sử dụng toán tử lựa chọn của Parsec: <|>. Theo hướng dẫn: Write yourself a Scheme in 48 hours:

[Toán tử lựa chọn] thử trình phân tích cú pháp đầu tiên, nếu không, hãy thử trình phân tích thứ hai. Nếu một trong hai thành công, thì nó trả về giá trị được trả về bởi trình phân tích cú pháp đó.

Nhưng theo kinh nghiệm của tôi, tôi thấy thứ tự của các trình phân tích cú pháp đã cung cấp vấn đề. Đây là chương trình của tôi:

import System.Environment 
import Text.ParserCombinators.Parsec 

main :: IO() 
main = do 
    (x:_) <- getArgs 
    putStrLn ("Hello, " ++ readExp x) 

bin :: Parser String 
bin = do string "#b" 
     x <- many(oneOf "01") 
     return x 

dec :: Parser String 
dec = do string "#d" 
     x <- many(oneOf "") 
     return x 

-- Why does order matter here? 
parseExp = (bin <|> dec) 

readExp :: String -> String 
readExp input = case parse parseExp "test" input of 
         Left error -> "Error: " ++ show error 
         Right val -> "Found val" ++ show val 

đây là làm thế nào tôi đang chạy chương trình:

phụ thuộc Cài đặt

$ cabal sandbox init 
$ cabal install parsec 

Biên soạn

$ cabal exec ghc Main 

Run

$ ./Main "#d1" 
Hello, Error: "test" (line 1, column 1): 
unexpected "d" 
expecting "#b" 

$ ./Main "#b1" 
Hello, Found val"1" 

.210

Nếu tôi thay đổi thứ tự của các phân tích cú pháp như sau:

parseExp = (dec <|> bin) 

sau đó chỉ số nhị phân được phát hiện và chương trình thất bại trong việc xác định các số thập phân.

Với các thử nghiệm mà tôi đã thực hiện, tôi thấy vấn đề này chỉ xảy ra khi một trong các trình phân tích cú pháp đã bắt đầu phân tích cú pháp đầu vào, ví dụ: nếu tìm thấy ký tự băm #, trình phân tích cú pháp bin được kích hoạt sẽ kết thúc khi không thành công như ký tự tiếp theo được mong đợi là b và không phải là d. Nó có vẻ như có một số loại backtracking mà nên xảy ra, mà tôi không nhận thức được.

Đánh giá cao sự trợ giúp!

Answer 1

Parsec có hai loại "lỗi": có lỗi thất bại tiêu thụ đầu vào và lỗi không thực hiện. Để tránh backtracking (và do đó giữ đầu vào lâu hơn cần thiết/nói chung không thân thiện với bộ thu gom rác), (<|>) cam kết với trình phân tích cú pháp đầu tiên ngay sau khi nó tiêu thụ đầu vào; để nếu đối số đầu tiên của nó tiêu thụ đầu vào và không thành công, trình phân tích thứ hai của nó sẽ không bao giờ có cơ hội thành công. Bạn có thể yêu cầu một cách rõ ràng backtracking hành vi với try, như sau:

Text.Parsec> parse (string "ab" <|> string "ac") "" "ac" 
Left (line 1, column 1): 
unexpected "c" 
expecting "ab" 
Text.Parsec> parse (try (string "ab") <|> string "ac") "" "ac" 
Right "ac" 

Thật không may, try có một số hình phạt hiệu suất khá khó chịu, điều đó có nghĩa rằng nếu bạn muốn có một phân tích cú pháp performant, bạn sẽ phải cấu trúc lại ngữ pháp của bạn một chút. Tôi sẽ làm điều đó với trình phân tích cú pháp ở trên theo cách này:

Text.Parsec> parse (char 'a' >> (("ab" <$ char 'b') <|> ("ac" <$ char 'c'))) "" "ac" 
Right "ac" 

Trong trường hợp của bạn, bạn sẽ cần đánh dấu dấu "#" tương tự.

Answer 2

Đọc kỹ:

[Nhà điều hành lựa chọn] cố gắng phân tích cú pháp đầu tiên, sau đó nếu nó không thành công, cố gắng thứ hai. Nếu một trong hai thành công thì nó sẽ trả về giá trị trả về bởi phân tích cú pháp mà ..

này ngụ ý rằng phân tích cú pháp đầu tiên là cố gắng đầu tiên, và nếu nó thành công, phân tích cú pháp thứ hai là không cố gắng ở tất cả! Điều này có nghĩa là trình phân tích cú pháp đầu tiên có mức độ ưu tiên cao hơn, vì vậy, tổng quát, <|> không giao hoán.

Một ví dụ đơn giản có thể được tạo bằng một số trình phân tích cú pháp luôn thành công, ví dụ:

dummy :: Parser Bool 
dummy = return True <|> return False 

Ở trên tương đương với return True: kể từ lần đầu tiên thành công, thứ hai là không quan trọng.

---

Ngày đầu đó, parsec được thiết kế để cam kết sớm trên nhánh đầu tiên khi đã tiêu thụ thành công một số đầu vào. Thiết kế này hy sinh tính không xác định hoàn hảo cho hiệu quả. Nếu không, parsec thường sẽ cần phải giữ trong bộ nhớ tất cả các tập tin được phân tích cú pháp, bởi vì nếu một lỗi phân tích xảy ra, một số thay thế mới cần phải được thử.

Ví dụ,

p = (char 'a' >> char 'b' >> ...) <|> 
    (char 'a' >> char 'c' >> ...) 

sẽ không làm việc như người ta có thể mong đợi. Ngay sau khi 'a' được tiêu thụ thành công bởi chi nhánh đầu tiên, parsec cam kết trên đó. Điều này có nghĩa là nếu 'c' theo sau, thì nhánh đầu tiên sẽ thất bại nhưng đã quá muộn cho lần thử thứ hai được thử. Toàn bộ trình phân tích cú pháp đơn giản là không thành công.

Để giải quyết vấn đề này có thể tạo ra tiền tố chung, ví dụ:

p = char 'a' >> ((char 'b' >> ...) <|> (char 'c' >> ...)) 

hoặc khu nghỉ mát để try,

p = (try (char 'a' >> char 'b') >> ...) <|> 
    (char 'a' >> char 'c' >> ...) 

try cơ bản cho parsec không cam kết chi nhánh cho đến khi toàn bộ phân tích cú pháp dưới try thành công. Nếu bị lạm dụng, nó có thể làm cho parsec giữ trong bộ nhớ một phần lớn của tệp, nhưng người dùng ít nhất có một số điều khiển trên đó. Về mặt lý thuyết, tính không xác định hoàn hảo có thể được phục hồi bằng cách luôn thêm try vào toàn bộ nhánh trái của <|>. Tuy nhiên, điều này không được khuyến khích, vì nó khuyến khích lập trình viên viết một trình phân tích cú pháp không hiệu quả, cả do vấn đề bộ nhớ và thực tế là người ta có thể dễ dàng viết một ngữ pháp yêu cầu số lượng các rãnh quay để phân tích cú pháp thành công.