स्क्रैच से रिकर्सिव वंश पार्सर कैसे लिखें?

Question

पूरी तरह अकादमिक अभ्यास के रूप में, मैं एएनटीएलआर या लेक्स/वाईएसी का उपयोग किये बिना स्क्रैच से एक रिकर्सिव वंश पार्सर लिख रहा हूं।

मैं एक साधारण कार्य लिख रहा हूं जो गणित अभिव्यक्तियों को उनके समकक्ष एएसटी में परिवर्तित करता है।

// grammar 
type expr = 
    | Lit of float 
    | Add of expr * expr 
    | Mul of expr * expr 
    | Div of expr * expr 
    | Sub of expr * expr 

// tokens 
type tokens = 
    | Num of float 
    | LParen | RParen 
    | XPlus | XStar | XMinus | XSlash 

let tokenize (input : string) = 
    Regex.Matches(input.Replace(" ", ""), "\d+|[+/*\-()]") 
    |> Seq.cast<Match> 
    |> Seq.map (fun x -> x.Value) 
    |> Seq.map (function 
     | "+" -> XPlus 
     | "-" -> XMinus 
     | "/" -> XSlash 
     | "*" -> XStar 
     | "(" -> LParen 
     | ")" -> RParen 
     | num -> Num(float num)) 
    |> Seq.to_list 

तो, tokenize "10 * (4 + 5) - 1" रिटर्न निम्न टोकन धारा: मैं निम्नलिखित है

[Num 10.0; XStar; LParen; Num 4.0; XPlus; Num 5.0; RParen; XMinus; Num 1.0] 

इस बिंदु पर, मैं ऑपरेटर पूर्वता के संबंध में इसकी एएसटी को टोकन धारा मैप करने के लिए करना चाहते हैं:

Sub(
    Mul(
     Lit 10.0 
     ,Add(Lit 4.0, Lit 5.0) 
     ) 
    ,Lit 1.0 
    ) 

हालांकि, मैं एक खाली चित्रण कर रहा हूं। मैंने कभी भी खरोंच से एक पार्सर नहीं लिखा है, और मैं सिद्धांत में भी कैसे शुरू करना है, यह भी नहीं जानता।

मैं अपने प्रतिनिधि एएसटी को टोकन स्ट्रीम कैसे परिवर्तित करूं?

Answer 1

क्या आप भाषा व्याकरण के बारे में जानते हैं?

मान लें हां, तो आप लाइनों

... 
addTerm := mulTerm addOp addTerm 
     | mulTerm 

addOp := XPlus | XMinus 

mulTerm := litOrParen mulOp mulTerm 
     | litOrParen 
... 

जो (ब्राउज़र में कोड लिखने, संकलित कभी नहीं)

let rec AddTerm() = 
    let mulTerm = MulTerm() // will parse next mul term (error if fails to parse) 
    match TryAddOp with // peek ahead in token stream to try parse 
    | None -> mulTerm // next token was not prefix for addOp rule, stop here 
    | Some(ao) ->  // did parse an addOp 
     let rhsMulTerm = MulTerm() 
     match ao with 
     | XPlus -> Add(mulTerm, rhsMulTerm) 
     | XMinus -> Sub(mulTerm, rhsMulTerm) 
and TryAddOp() = 
    let next = tokens.Peek() 
    match next with 
    | XPlus | XMinus -> 
     tokens.ConsumeNext() 
     Some(next) 
    | _ -> None 
... 

उम्मीद है कि आप देख की तरह कोड में बदल समाप्त होता है के साथ नियमों के साथ एक व्याकरण है मूल विचार। यह एक वैश्विक म्यूटेबल टोकन स्ट्रीम मानता है जो 'अगले टोकन पर' चोटी और 'अगले टोकन का उपभोग' दोनों की अनुमति देता है।

  exp 
     exp op  exp 
    5  +  and so on 

तो: पूरी तरह से ताकि आप की तरह कुछ मिल

<program> --> <expression> <op> <expression> | <expression> 
<expression> --> (<expression>) | <constant> 
<op> --> * | - | + |/
<constant> --> <constant><constant> | [0-9] 

तो

एक बार आप निर्माण अपने पेड़ है:

Answer 2

अगर मैं कॉलेज की कक्षाओं से याद विचार की तरह अभिव्यक्ति के पेड़ का निर्माण करना था आप अपने पूरे पेड़ को किसी अन्य प्रोग्राम के माध्यम से चलाते हैं जो आपके पास उत्तर देने तक पेड़ की गणना करने वाले अभिव्यक्तियों में बार-बार उतरता है। यदि आपका पार्सर पेड़ को नहीं समझता है, तो आपके पास वाक्यविन्यास त्रुटि है। उम्मीद है की वो मदद करदे।