OCaml

Question

का उपयोग कर व्याकरण को पार्स करना मेरे पास ओकैम का उपयोग करके एक (खिलौना) व्याकरण के लिए एक (खिलौना) पार्सर लिखने का कार्य है और यह सुनिश्चित नहीं है कि इस समस्या को कैसे शुरू करें (और आगे बढ़ें)। कुछ टुकड़े पार्स करने के लिए है

type ('nonterm, 'term) symbol = N of 'nonterm | T of 'term;; 

type awksub_nonterminals = Expr | Term | Lvalue | Incrop | Binop | Num;; 

let awksub_grammar = 
    (Expr, 
    function 
    | Expr -> 
     [[N Term; N Binop; N Expr]; 
      [N Term]] 
    | Term -> 
    [[N Num]; 
     [N Lvalue]; 
     [N Incrop; N Lvalue]; 
     [N Lvalue; N Incrop]; 
     [T"("; N Expr; T")"]] 
    | Lvalue -> 
    [[T"$"; N Expr]] 
    | Incrop -> 
    [[T"++"]; 
     [T"--"]] 
    | Binop -> 
    [[T"+"]; 
     [T"-"]] 
    | Num -> 
    [[T"0"]; [T"1"]; [T"2"]; [T"3"]; [T"4"]; 
     [T"5"]; [T"6"]; [T"7"]; [T"8"]; [T"9"]]);; 

और यहाँ:

यहां नमूने Awk व्याकरण है

let frag1 = ["4"; "+"; "3"];; 
let frag2 = ["9"; "+"; "$"; "1"; "+"];; 

क्या मैं के लिए देख रहा हूँ एक rulelist एक टुकड़ा पार्स करने का परिणाम है कि है, जैसे कि frag1 ["4" के लिए यह एक; "+"; "3"]:

[(Expr, [N Term; N Binop; N Expr]); 
    (Term, [N Num]); 
    (Num, [T "3"]); 
    (Binop, [T "+"]); 
    (Expr, [N Term]); 
    (Term, [N Num]); 
    (Num, [T "4"])] 

प्रतिबंध सूची अलावा अन्य किसी भी OCaml पुस्तकालयों का उपयोग नहीं करने के लिए है ...:/

Answer 1

मैं अगर आप विशेष रूप व्युत्पत्ति पेड़ की आवश्यकता होती है, या अगर यह है यकीन नहीं है पार्सिंग में बस एक पहला कदम। मैं उत्तरार्द्ध मान रहा हूँ।

आप प्रकारों को परिभाषित करके परिणामी अमूर्त वाक्यविन्यास पेड़ की संरचना को परिभाषित करके शुरू कर सकते हैं। यह कुछ ऐसा हो सकता है:

type expr = 
    | Operation of term * binop * term 
    | Term of term 
and term = 
    | Num of num 
    | Lvalue of expr 
    | Incrop of incrop * expression 
and incrop = Incr | Decr 
and binop = Plus | Minus 
and num = int 

तब मैं एक रिकर्सिव वंश पार्सर लागू करता। बेशक यह अगर तुम streams पूर्वप्रक्रमक camlp4of के साथ संयुक्त ...

इस्तेमाल कर सकते हैं वैसे बहुत अच्छे हो सकता है, वहाँ OCaml प्रलेखन here में गणित भाव के बारे में एक छोटा सा उदाहरण है।

Answer 2

ठीक है, तो सबसे पहले आपको लगता है कि आपको एक व्याख्यात्मक विश्लेषक लिखना चाहिए। यह फ़ंक्शन है जो ["3"; "-"; "("; "4"; "+"; "2"; ")"], जैसे 'कच्चे' इनपुट को लेता है और इसे टोकन की सूची में विभाजित करता है (यानी, टर्मिनल प्रतीकों का प्रतिनिधित्व)।

आप

type token = 
    | TokInt of int   (* an integer *) 
    | TokBinOp of binop  (* a binary operator *) 
    | TokOParen    (* an opening parenthesis *) 
    | TokCParen    (* a closing parenthesis *)  
and binop = Plus | Minus 

lexer समारोह के प्रकार string list -> token list होगा और

lexer ["3"; "-"; "("; "4"; "+"; "2"; ")"] 

के ouput होने के लिए एक टोकन परिभाषित कर सकते हैं होगा

कुछ की तरह

[ TokInt 3; TokBinOp Minus; TokOParen; TokInt 4; 
    TBinOp Plus; TokInt 2; TokCParen ] 

यह पार्सर को आसान लिखने का काम करेगा, क्योंकि आप नहीं करेंगे एक पूर्णांक क्या है, ऑपरेटर क्या है, आदि को पहचानने के बारे में चिंता करें

यह पहला, कठिन कदम नहीं है क्योंकि टोकन पहले ही अलग हो चुके हैं। सभी लेक्सर को उनकी पहचान करना है।

जब ऐसा होता है, तो आप प्रकार string -> token list का एक और अधिक यथार्थवादी शाब्दिक विश्लेषक,, कि एक वास्तविक कच्चे इनपुट जैसे "3-(4+2)" लेता है, और यह एक टोकन सूची में बदल जाता है लिख सकते हैं।

Answer 3

यहां एक मोटा स्केच है - सीधे व्याकरण में उतरें और क्रमशः प्रत्येक शाखा को आज़माएं। संभावित अनुकूलन: शाखा में एकल गैर टर्मिनल के लिए पूंछ रिकर्सन।

exception Backtrack 

let parse l = 
    let rules = snd awksub_grammar in 
    let rec descend gram l = 
    let rec loop = function 
     | [] -> raise Backtrack 
     | x::xs -> try attempt x l with Backtrack -> loop xs 
    in 
    loop (rules gram) 
    and attempt branch (path,tokens) = 
    match branch, tokens with 
    | T x :: branch' , h::tokens' when h = x -> 
     attempt branch' ((T x :: path),tokens') 
    | N n :: branch' , _ -> 
     let (path',tokens) = descend n ((N n :: path),tokens) in 
     attempt branch' (path', tokens) 
    | [], _ -> path,tokens 
    | _, _ -> raise Backtrack 
    in 
    let (path,tail) = descend (fst awksub_grammar) ([],l) in 
    tail, List.rev path