एक रिकर्सिव डेटा स्ट्रक्चर में पार्सिंग

Question

मैं एफ # का उपयोग कर एक रिकर्सिव डेटा स्ट्रक्चर में स्ट्रिंग को पार्स करना चाहता हूं। इस सवाल में मैं एक सरलीकृत उदाहरण पेश करने जा रहा हूं जो कि मैं जो करना चाहता हूं उसके मूल में कटौती करता हूं।

मैं रिकॉर्ड प्रकार के लिए नेस्टेड वर्ग कोष्ठक की एक स्ट्रिंग पार्स करने के लिए करना चाहते हैं:

type Bracket = | Bracket of Bracket option 

तो:

• "[]" ->Bracket None
• "[[]] "->Bracket (Some (Bracket None))
• " [[[]]] "->Bracket (Some (Bracket (Some (Bracket None))))

मैं FParsec लाइब्रेरी में पार्सर संयोजकों का उपयोग करके ऐसा करना चाहता हूं। यहाँ मैं अब तक है:

let tryP parser = 
    parser |>> Some 
    <|> 
    preturn None 

/// Parses up to nesting level of 3 
let parseBrakets : Parser<_> = 

let mostInnerLevelBracket = 
    pchar '[' 
    .>> pchar ']' 
    |>> fun _ -> Bracket None 

let secondLevelBracket = 
    pchar '[' 
    >>. tryP mostInnerLevelBracket 
    .>> pchar ']' 
    |>> Bracket 

let firstLevelBracket = 
    pchar '[' 
    >>. tryP secondLevelBracket 
    .>> pchar ']' 
    |>> Bracket 

firstLevelBracket 

मैं भी कुछ Expecto परीक्षण: बेशक कैसे संभाल करने के लिए नहीं मिल पाता की मनमानी के स्तर का

open Expecto 

[<Tests>] 
let parserTests = 
[ "[]", Bracket None 
    "[[]]", Bracket (Some (Bracket None)) 
    "[[[]]]", Bracket (Some (Bracket (Some (Bracket None)))) ] 
|> List.map(fun (str, expected) -> 
    str 
    |> sprintf "Trying to parse %s" 
    |> testCase 
    <| fun _ -> 
    match run parseBrakets str with 
    | Success (x, _,_) -> Expect.equal x expected "These should have been equal" 
    | Failure (m, _,_) -> failwithf "Expected a match: %s" m 
) 
|> testList "Bracket tests" 

let tests = 
[ parserTests ] 
|> testList "Tests" 

runTests defaultConfig tests 

समस्या है - केवल उपरोक्त कोड अप के लिए काम करता 3 स्तर तक। कोड मैं तरह लिखने के लिए होता है:

let rec pNestedBracket = 
    pchar '[' 
    >>. tryP pNestedBracket 
    .>> pchar ']' 
    |>> Bracket 

लेकिन एफ # इस अनुमति नहीं है।

क्या मैं इसे हल करने के तरीके से गलत पेड़ को पूरी तरह से भौंक रहा हूं (मैं समझता हूं कि इस विशेष समस्या को हल करने के आसान तरीके हैं)?

Answer 1

आप FParsecs createParserForwardedToRef विधि की तलाश में हैं। क्योंकि पार्सर्स मूल्य हैं और काम नहीं करते हैं, ऐसा करने के लिए पारस्परिक रूप से रिकर्सिव या स्वयं रिकर्सिव पार्सर्स बनाना असंभव है, आपको इसे समझने से पहले एक पार्सर घोषित करना होगा।

आपकी अंतिम कोड इस

let bracketParser, bracketParserRef = createParserForwardedToRef<Bracket>() 
bracketParserRef := ... //here you can finally declare your parser 
    //you can reference bracketParser which is a parser that uses the bracketParserRef 

की तरह कुछ के लिए देख इसके अलावा, मैं पार्सर combinators की बुनियादी समझ के लिए यह लेख की सिफारिश करेंगे खत्म हो जाएगा। https://fsharpforfunandprofit.com/posts/understanding-parser-combinators/। JSON पार्सर पर अंतिम अनुभाग createParserForwardedToRef विधि के बारे में बात करता है।

Answer 2

createParserForwardedToRef का उपयोग करने के उदाहरण के रूप में, यहां हाल ही में लिखे गए एक छोटे पार्सर से स्निपेट है। यह ब्रैकेट्स के बीच अंतरिक्ष से अलग पूर्णांक की सूचियों को पार्स करता है (और सूचियों को नेस्टेड किया जा सकता है), और "पूर्णांक" 1+2 या 3*5 जैसे छोटे अंकगणितीय अभिव्यक्ति हो सकते हैं।

type ListItem = 
    | Int of int 
    | List of ListItem list 

let pexpr = // ... omitted for brevity 

let plist,plistImpl = createParserForwardedToRef() 

let pListContents = (many1 (plist |>> List .>> spaces)) <|> 
        (many (pexpr |>> Int .>> spaces)) 

plistImpl := pchar '[' >>. spaces 
         >>. pListContents 
         .>> pchar ']' 

पीएस मैं इसे थॉमस डेवर्स के जवाब पर टिप्पणी के रूप में रखता, लेकिन एक टिप्पणी में अच्छी तरह से स्वरूपित कोड नहीं हो सकता है। आगे बढ़ें और उसका जवाब स्वीकार करें; मेरा इरादा सिर्फ उसका मांस बनाना है।