Dlaczego wydaje się, że operator parsektora zależy od kolejności analizatorów składni?

Question

Próbuję parsować bardzo prosty język, który składa się tylko z liczb dziesiętnych lub liczb binarnych. Na przykład, oto kilka ważnych Wejścia:

#b1 
#d1 
#b0101 
#d1234 

Mam problem za pomocą parsec operator wybór: <|>. Zgodnie z samouczkiem: Write yourself a Scheme in 48 hours:

[Operator wyboru] próbuje pierwszy parser, a jeśli się nie powiedzie, próbuje drugi. Jeśli się to uda, to zwróci wartość zwróconą przez ten analizator składni ..

Jednak z mojego doświadczenia wynika, że ​​kolejność parserów dostarczała spraw. Oto mój program:

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 

Oto jak używam programu:

Instalowanie zależnościami

$ cabal sandbox init 
$ cabal install parsec 

Kompilacja

$ cabal exec ghc Main 

Run

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

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

Jeśli zmienić kolejność parserami następująco: są wykrywane

parseExp = (dec <|> bin) 

wtedy tylko liczb binarnych, a program nie określa liczby dziesiętne.

Po przeprowadzonych testach widzę, że problem ten występuje tylko wtedy, gdy jeden z parserów rozpoczął analizowanie danych wejściowych, np. jeśli zostanie znaleziony znak skrótu #, parser bin jest aktywowany kończąc się niepowodzeniem, ponieważ oczekiwany następny znak to b, a nie . Wygląda na to, że powinno nastąpić coś w rodzaju powrotu, którego nie mam świadomości.

Doceń pomoc!

Answer 1

Parsek ma dwa rodzaje "niepowodzenia": są awarie, które zużywają dane wejściowe, i awarie, które nie. Aby uniknąć cofnięcia (a zatem wstrzymania wprowadzania dłuższych niż to konieczne/nieprzyjaznych ogólnie dla śmieciarza), (<|>) zatwierdza pierwszy parser, gdy tylko zużyje dane wejściowe; tak, że jeśli pierwszy argument pochłania dane wejściowe i kończy się niepowodzeniem, drugi parser nigdy nie ma szansy na powodzenie. Można wyraźnie zażądać backtracking zachowanie z try, a więc:

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" 

Niestety try ma kilka bardzo irytujące kary wydajności, co oznacza, że ​​jeśli chcesz wydajnych parser, trzeba będzie byłaby twoja gramatyka trochę. Chciałbym zrobić z powyższym parser ten sposób:

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

W twoim przypadku trzeba będzie czynnikiem zewnątrz znaku „#” podobnie.

Answer 2

Czytaj uważnie:

[Operator wybór] próbuje pierwszy parser, a następnie, jeśli to zawiedzie, próbuje drugiego. Jeśli któryś się powiedzie, to zwraca wartość zwróconą przez że parser ..

Oznacza to, że pierwszy parser jest spróbował najpierw, a jeśli to się uda, drugi parser NIE próbowali w ogóle! Oznacza to, że pierwszy parser ma wyższy priorytet, więc <|> nie jest ogólnie przemienny.

Prosty kontrprzykład może być wykonany z parami o zawsze następujących po sobie parametrach, np.

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

Powyższy odpowiada return True: od pierwszej przejmuje drugi jest nieistotna.

---

Co więcej, parsec ma za zadanie zatwierdzać wcześnie na pierwszym oddziale, gdy ten z powodzeniem zużył część danych wejściowych. Ten projekt poświęca doskonały niedeterminizm dla wydajności. W przeciwnym razie parsec często musiałby przechowywać w pamięci cały analizowany plik, ponieważ jeśli wystąpi błąd analizy, należy wypróbować nową alternatywę.

Na przykład

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

nie będzie działać, jak można by oczekiwać. Gdy tylko 'a' zostanie zużyty pomyślnie przez pierwszy oddział, parsec dokonuje na nim zatwierdzenia. Oznacza to, że jeśli nastąpi 'c', pierwsza gałąź zakończy się niepowodzeniem, ale jest już za późno na wypróbowanie drugiej. Cały parser po prostu zawiedzie.

Aby rozwiązać ten problem, można wziąć pod uwagę wspólny przedrostek, np.

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

lub ośrodek do try,

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

try zasadzie mówi parsec nie zobowiązać się do oddziału, aż cały parser pod try powiedzie. Jeśli zostanie nadużyty, może spowodować, że parsec pozostanie w pamięci dużej części pliku, ale użytkownik przynajmniej ma na to jakąś kontrolę. Teoretycznie doskonały niedeterminizm można odzyskać, dodając zawsze try do całej lewej gałęzi <|>. Nie jest to jednak zalecane, ponieważ zachęca on programistę do napisania nieefektywnego parsera, zarówno z powodu problemu z pamięcią, jak iz faktu, że można z łatwością napisać gramatykę wymagającą wykładniczej liczby ścieżek do pomyślnego przeanalizowania.