再帰的な降下構文解析プログラムをゼロから書くには？

Question

純粋に学問的な演習として、ANTLRまたはlex/yaccを使用せずに、再帰的降下パーサをゼロから作成しています。

数式を同等のASTに変換する簡単な関数を書いています。

// 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] 

この時点で、私は、演算子の優先順位についてのASTにトークンストリームをマッピングしたいと思います：

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

しかし、私は空白を描いています。私はパーサーを一から書いたことが一度もありませんし、原則としてどのように始めるべきかも分かりません。

トークンストリームを代表的なASTに変換するにはどうすればよいですか？

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 
... 

うまくいけば、あなたが見ます基本的な考え。これは、「次のトークンを見る」と「次のトークンを消費する」の両方を可能にするグローバルな変更可能なトークンストリームを前提としています。

Answer 2

私はアイデアは次のように式ツリーを構築することだった大学の授業から覚えている場合：その後、

  exp 
     exp op  exp 
    5  +  and so on 

：

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

あなたが建設あなたの木完全を持っていたら、そのようにあなたのような何かを得ますあなたは、あなたが答えを得るまで、式を計算するツリーに再帰的に降下する別のプログラムを通して完成したツリーを実行します。パーサがツリーを理解できない場合は、構文エラーが発生します。希望が役立ちます。