ऐसा क्यों लगता है कि पारसी चॉइस ऑपरेटर पार्सर्स के आदेश पर निर्भर करता है?

Question

मैं एक बहुत ही साधारण भाषा का विश्लेषण करने की कोशिश कर रहा हूं जिसमें केवल दशमलव या बाइनरी संख्याएं होंगी। उदाहरण के लिए, यहाँ कुछ मान्य इनपुट हैं: <|>:

#b1 
#d1 
#b0101 
#d1234 

मैं Parsec की पसंद ऑपरेटर का उपयोग में समस्या हो रही। ट्यूटोरियल के मुताबिक: Write yourself a Scheme in 48 hours:

[पसंद ऑपरेटर] पहले पार्सर की कोशिश करता है, फिर यदि यह विफल हो जाता है, तो दूसरा प्रयास करता है। यदि या तो सफल होता है, तो यह उस पार्सर द्वारा लौटाए गए मान को वापस कर देता है ..

लेकिन मेरे अनुभव में, मुझे लगता है कि पार्सर्स के आदेश ने मामलों की आपूर्ति की।

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 

यहाँ कैसे मैं इस कार्यक्रम चला रहा हूँ है: यहाँ मेरी कार्यक्रम है

स्थापित कर रहा है निर्भरता

$ cabal sandbox init 
$ cabal install parsec 

संकलन

$ cabal exec ghc Main 

भागो

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

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

,210

इस प्रकार अगर मैं पारसर्स के आदेश को बदल:

parseExp = (dec <|> bin) 

उसके बाद ही द्विआधारी संख्या का पता चलता है और इस कार्यक्रम दशमलव संख्या की पहचान करने में विफल रहता है।

मेरे द्वारा किए गए परीक्षणों के साथ, मुझे लगता है कि यह समस्या केवल तभी होती है जब एक पार्सर्स ने इनपुट को पार्स करना शुरू कर दिया हो। यदि एक हैश चरित्र # पाया जाता है, तो बिन पार्सर सक्रिय होने में सक्रिय हो रहा है क्योंकि अगली वर्ण अपेक्षित है b और d नहीं। ऐसा लगता है कि ऐसा कुछ प्रकार का बैकट्रैक होना चाहिए जो होना चाहिए, जिसे मुझे पता नहीं है।

सहायता की सराहना करें!

Answer 1

पारसेक में दो प्रकार की "विफलता" है: ऐसी विफलताएं हैं जो इनपुट का उपभोग करती हैं, और विफलताएं नहीं होती हैं। बैकट्रैकिंग से बचने के लिए (और इसलिए आवश्यक से लंबे समय तक इनपुट पर पकड़ना/आमतौर पर कचरा कलेक्टर के लिए असभ्य होना), (<|>) जैसे ही यह इनपुट का उपभोग करता है, पहले पार्सर में होता है; ताकि यदि इसका पहला तर्क इनपुट का उपभोग करता है और विफल रहता है, तो इसका दूसरा पार्सर कभी सफल होने का मौका नहीं देता है। आप स्पष्ट रूप से try साथ व्यवहार उलटे पांव लौटने से, इस प्रकार अनुरोध कर सकते हैं:

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" 

दुर्भाग्य से, try कुछ बहुत कष्टप्रद प्रदर्शन दंड, जिसका अर्थ है कि यदि आप एक performant पार्सर चाहते हैं, आप अपने व्याकरण थोड़ा refactor करना होगा है। मुझे लगता है कि इस तरह से करना होगा ऊपर पार्सर के साथ:

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

आपके मामले में, आप इसी तरह से "#" निशान को अलग करने की आवश्यकता होगी।

Answer 2

को ध्यान से पढ़ें:

[विकल्प ऑपरेटर] पहले पार्सर की कोशिश करता है, तो अगर यह विफल रहता है, दूसरी कोशिश करता है। या तो सफल होता है, तो यह कि पार्सर द्वारा लौटाए गए मान देता है ..

इसका मतलब है कि पहले पार्सर पहले की कोशिश की है, और अगर यह सफल होता है, दूसरा पार्सर बिल्कुल की कोशिश की नहीं है! इसका मतलब है कि पहले पार्सर की उच्च प्राथमिकता है, इसलिए <|> सामान्य रूप से कम्यूटिव नहीं है।

एक साधारण काउंटररेक्स नमूना कुछ हमेशा सफल पार्सर्स के साथ तैयार किया जा सकता है, उदाहरण के लिए

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

ऊपर return True के बराबर है: के बाद से पहली सफल होता है, दूसरा सारहीन है।

---

उस पर, पारसी को पहली शाखा में जल्दी से प्रतिबद्ध करने के लिए डिज़ाइन किया गया है जब उसने कुछ इनपुट सफलतापूर्वक खा लिया है। यह डिजाइन दक्षता के लिए सही nondeterminism बलिदान। अन्यथा, पारसी को अक्सर सभी फाइलों को स्मृति में रखने की आवश्यकता होती है, क्योंकि अगर एक पार्स त्रुटि होती है, तो कुछ नए विकल्प की कोशिश की जानी चाहिए।

उदाहरण के लिए,

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

के रूप में एक उम्मीद कर सकते हैं काम नहीं करेगा। जैसे ही 'a' पहली शाखा द्वारा सफलतापूर्वक उपभोग किया जाता है, परसेक इस पर काम करता है। इसका मतलब है कि यदि 'c' निम्नानुसार है, तो पहली शाखा विफल हो जाएगी लेकिन दूसरे की कोशिश करने में बहुत देर हो चुकी है। पूरा पार्सर बस विफल रहता है।

इसे हल करने के लिए सामान्य उपसर्ग को कारक बना सकते हैं, उदा।

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

या try को सहारा,

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

try मूल रूप से पारसेक बताता शाखा के लिए प्रतिबद्ध करने के लिए नहीं है जब तक try के तहत पूरे पार्सर सफल होता है। यदि दुर्व्यवहार किया जाता है, तो यह फ़ाइल के बड़े हिस्से को स्मृति में रखने के लिए पार्ससी का कारण बन सकता है, लेकिन उपयोगकर्ता पर कम से कम कुछ नियंत्रण होता है। सैद्धांतिक रूप से, <|> की पूरी बाएं शाखा में हमेशा try जोड़कर सही नोडेटर्मिनिज्म पुनर्प्राप्त किया जा सकता है। हालांकि इसकी अनुशंसा नहीं की जाती है, क्योंकि यह प्रोग्रामर को स्मृति समस्या के कारण दोनों एक अक्षम पार्सर लिखने में प्रोडक्ट करता है और तथ्य यह है कि कोई आसानी से व्याकरण लिख सकता है ताकि सफलतापूर्वक पार्स करने के लिए बैकट्रैक की घातीय संख्या की आवश्यकता हो।