Parser rekurencyjny i programowanie funkcyjne

Jedną ze strategii parsowania funkcjonalnego są monadyczne kombinatory parserów. Możesz poczytać o tym tutaj (i podążać za linkami) lub skorzystać z biblioteki typu FParsec. Nie polecam tego podejścia, jeśli dopiero uczysz się/uruchamiasz Kompilatory F#/.

Innym podejściem z F# jest użycie FsLex/FsYacc (w PowerPack ). Trochę nienawidzę technologii Lex / Yacc, więc nie polecam tego.

Myślę, że powinieneś napisać rekurencyjny porządny parser ręcznie. I nie masz silnych odczuć co do tokenizera, ale po prostu tokeninizowanie całego pliku do(n niezmiennego) list tokenów, a następnie rekurencyjne opadanie (i wykorzystanie niektórych dopasowań wzorców) jest dobrym sposobem na radzenie sobie z parsowaniem. I oczywiście, będziesz chciał użyć zniekształconych związków do reprezentowania wyjścia AST parsera (a la tutaj ).

Edytuj

// AST for tiny language
type Op = 
    | Plus 
    | Minus 
type Expr = 
    | Literal of int 
    | BinaryOp of Expr * Op * Expr // left, op, right 
type Stmt =
    | IfThenElse of Expr * Stmt * Stmt // cond, then, else; 0=false in cond 
    | Print of Expr

// sample program
let input = @"
    if 1+1-1 then 
        print 42 
    else 
        print 0"

// expected AST
let goal = 
    IfThenElse(
        BinaryOp( BinaryOp(Literal(1),Plus,Literal(1)), Minus, Literal(1)), 
        Print(Literal(42)), 
        Print(Literal(0))) 

////////////////////////////////////////////////////////////////////////////
// Lexer

type Token =
    | IF
    | THEN
    | ELSE
    | PRINT
    | NUM of int  // non-negative
    | PLUS
    | MINUS
    | EOF

let makeTokenizer (s:string) =
    let i = ref 0
    let keywords = [
        "if", IF 
        "then", THEN
        "else", ELSE
        "print", PRINT
        "+", PLUS
        "-", MINUS ]
    let rec getNextToken() =
        if !i >= s.Length then
            EOF
        elif System.Char.IsWhiteSpace(s.[!i]) then
            incr i
            getNextToken()
        elif System.Char.IsDigit(s.[!i]) then
            let mutable j = !i
            while j < s.Length && System.Char.IsDigit(s.[j]) do
                j <- j + 1
            let numStr = s.Substring(!i, j - !i)
            i := j
            NUM(System.Int32.Parse(numStr)) // may throw, e.g. if > MAXINT
        else 
            let keyword = keywords |> List.tryPick (fun (kwStr,kwTok) ->
                if s.IndexOf(kwStr, !i) = !i then
                    i := !i + kwStr.Length
                    Some(kwTok)
                else
                    None)
            match keyword with
            | Some k -> k
            | None -> 
                failwith "unexpected char '%c' at position %d" s.[!i] !i
    getNextToken

let tokens = 
    let nextToken = makeTokenizer input
    let t = ref(nextToken())
    [ 
        yield !t
        while !t <> EOF do
            t := nextToken()
            yield !t
    ]

printfn "%A" tokens // sanity check our tokenizer works

/////////////////////////////////////////////////////////////////////////
// Parser

let parseExpr toks =
    match toks with
    | NUM x :: rest ->
        let mutable rest = rest
        let mutable expr = Literal x
        while rest.Head = PLUS || rest.Head = MINUS do
            let op,y,r = 
                match rest with
                | PLUS::NUM y::t -> Plus, Literal y, t
                | MINUS::NUM y::t -> Minus, Literal y, t
                | _ -> 
                    failwith "parse error in expression, expected number"
            expr <- BinaryOp(expr, op, y)
            rest <- r
        expr, rest
    | _ -> failwith "parse error in expression, expected number"
let rec parseStmt toks =
    match toks with
    | PRINT :: rest -> 
        let e,rest = parseExpr(rest)
        Print(e), rest
    | IF :: rest ->
        let e,rest = parseExpr(rest)
        match rest with
        | THEN :: rest ->
            let s1,rest = parseStmt(rest)
            match rest with
            | ELSE :: rest ->
                let s2,rest = parseStmt(rest)
                IfThenElse(e,s1,s2), rest
            | _ -> 
                failwith "parse error after if branch, espected 'else'"
        | _ -> 
            failwith "parse error after if expression, expected 'then'"
    | _ -> failwith "parse error, expected statement"
let parseProgram toks =
    let s,rest = parseStmt toks
    match rest with
    | [EOF] -> s
    | _ -> failwith "parse error after statement, expected EOF"

let p = parseProgram tokens
printfn "%A" p
assert( p = goal )

(Mam nadzieję, że nie ma skandalicznych błędów.)

Kombinatory parserów są naprawdę piękne! FParsec jest bardzo zgrabną biblioteką monadic parser combinator, którą powinieneś sprawdzić. Jeśli chcesz zacząć od czegoś prostego i wciąż czysto funkcjonalnego, możesz cieszyć się tokenizerem / parserem z interpretera Scheme w serii F # tutaj (mój blog): http://blogs.msdn.com/b/ashleyf/archive/2010/09/24/fscheme-0-0-0.aspx

ODPOWIEDŹ prostsza od innych dobrych odpowiedzi:

Parser w języku funkcji pobiera strumień tokenu do drzewa parsowania, a resztę strumienia tokenu. Oznacza to, że ma typ

 token list -> ast * token list

Rekurencyjny Parser zwykle ma dużą liczbę funkcji tego typu, które zjadają strumień tokenu, a następnie budują niewielką część drzewa parsowania. Wywołując je rekurencyjnie (recursive decent) - dostajesz to, czego chcesz.

Następnym krokiem jest użycie wyższego rzędu parsery: parsery działające na innych parserach. To właśnie robią biblioteki kombinatorów parserów. Być może mógłbyś zacząć od prostego schematu rekurencji, a następnie uaktualnić go do kombinatorów parserów.

Pracuję nad kompilatorem ECMAScript W F# przez jakiś czas, więc jestem w tej samej łodzi co Ty. Może niektóre z moich prac mogą ci się przydać. Oto prosta biblioteka combinatora parserów, nad którą pracuję, której używam w połączeniu z FParsec. Nie jest to idealne miejsce, ale powinno dać ci coś prostego do nauki, abyś mógł przejść do bardziej zaawansowanych rzeczy. Jeśli skończy się korzystanie z FParsec można zauważyć, że wiele rzeczy tutaj zostały zainspirowane przez to.

module Tools =

    open System
    open System.Diagnostics
    open LazyList 

    [<Struct;DebuggerStepThrough>]
    type State<'a, 'b> (input:LazyList<'a>, data:'b) = //'
        member this.Input = input
        member this.Data = data

    type Result<'a, 'b, 'c> = //'
    | Success of 'c * State<'a, 'b>
    | Failure of list<string> * State<'a, 'b>    

    type Parser<'a, 'b, 'c> = //' 
        State<'a, 'b> -> seq<Result<'a, 'b, 'c>>

    let zero<'a, 'b, 'c> (state:State<'a, 'b>) = //'
        Seq.empty<Result<'a, 'b, 'c>>

    let item<'a, 'b> (state:State<'a, 'b>) = seq { //'
        match state.Input with
        | Cons (head, tail) ->
            yield Success(head, State (tail, state.Data))
        | Nil -> ()
    } 

    let result<'a, 'b, 'c> (value:'c) (state:State<'a, 'b>) = seq  { //'
        yield Success (value, state)
    }

    let run p i d =
        p (State(i, d)) 

    let (>>=) (m:Parser<'a, 'b, 'c>) (f:'c -> Parser<'a, 'b, 'd>) (state:State<'a, 'b>) = //'
        let rec run errors = seq {
            for r in m state do
                match r with
                | Success (v, s) ->
                    yield! f v s
                | Failure (ms, s) ->
                    yield! run (errors @ ms)
        }
        run []

    let (<|>) (l:Parser<'a, 'b, 'c>) (r:Parser<'a, 'b, 'c>) (state:State<'a, 'b>) = //'  
        let rec run p = seq {
            for result in p state do
                match result with
                | Success (_, _) ->
                    yield result
                | Failure (_, _) -> ()
        }
        Seq.append (run l) (run r)

    type ParseMonad() =        
        member this.Bind (f:Parser<'a, 'b, 'c>, g:'c -> Parser<'a, 'b, 'd>) : Parser<'a, 'b, 'd> = f >>= g //'     
        member this.Combine (f, g) = f <|> g      
        member this.Delay (f:unit -> Parser<'a, 'b, 'c>) (state:State<'a, 'b>) = f () state //'
        member this.Return x = result x
        member this.ReturnFrom p = p
        member this.Zero () = zero

    let parse = ParseMonad()

    let (|>>) (parser:Parser<'a, 'b, 'c>) (f:'c -> 'd) = parse { //'
        let! v = parser
        return f v   
    }

    let satisfy predicate = parse {
        let! value = item
        if predicate value then
            return value 
    }

    let maybe parser = parse {
        return! parser |>> Some <|> result None 
    }

    let choice (ps:seq<Parser<'a, 'b, 'c>>) (state:State<'a, 'b>) = seq { //'
        if not (LazyList.isEmpty state.Input) then
            for p in ps do
                yield! p state    
    }

    let between left right parser =
        parse {
            let! _ = left
            let! v = parser
            let! _ = right
            return v
        }

    let skip p = parse {
        let! v = p
        return ()
    }

    let many parser = 
        let rec many result = parse {
            let! v = parser
            let result = v::result
            return! many result
            return result    
        }
        many []

    let many1 parser = parse {
        let! r = many parser
        if not r.IsEmpty then
            return r
    }

    let manyFold parser start (f:_ -> _ -> _) = parse {
        let! r = many parser
        return r |> List.fold f start
    }

    let many1Fold parser start (f:_ -> _ -> _) = parse {
        let! r = many1 parser
        return r |> List.fold f start
    } 

    let isNotFollowedBy p =
        parse {
            let! v = maybe p
            match v with
            | Some _ -> ()
            | None -> return ()
        }

    let pipe2 (p1:Parser<'a, 'b, 'c>) (p2:Parser<'a, 'b, 'd>) (f:'c -> 'd -> 'e) = //' 
        parse {
            let! v1 = p1
            let! v2 = p2
            return f v1 v2
        }

    let pipe3 (p1:Parser<'a, 'b, 'c>) (p2:Parser<'a, 'b, 'd>) (p3:Parser<'a, 'b, 'e>) (f:'c -> 'd -> 'e -> 'f) = //' 
        parse {
            let! v1 = p1
            let! v2 = p2
            let! v3 = p3
            return f v1 v2 v3
        }

    let pipe4 (p1:Parser<'a, 'b, 'c>) (p2:Parser<'a, 'b, 'd>) (p3:Parser<'a, 'b, 'e>) (p4:Parser<'a, 'b, 'f>) (f:'c -> 'd -> 'e -> 'f -> 'g) = //' 
        parse {
            let! v1 = p1
            let! v2 = p2
            let! v3 = p3
            let! v4 = p4
            return f v1 v2 v3 v4
        }

    let pipe5 (p1:Parser<'a, 'b, 'c>) (p2:Parser<'a, 'b, 'd>) (p3:Parser<'a, 'b, 'e>) (p4:Parser<'a, 'b, 'f>) (p5:Parser<'a, 'b, 'g>) (f:'c -> 'd -> 'e -> 'f -> 'g -> 'h) = //' 
        parse {
            let! v1 = p1
            let! v2 = p2
            let! v3 = p3
            let! v4 = p4
            let! v5 = p5
            return f v1 v2 v3 v4 v5
        }

    let tuple2<'a, 'b, 'c, 'd, 'e> (p1:Parser<'a, 'b, 'c>) (p2:Parser<'a, 'b, 'd>) (f:'c * 'd -> 'e) = //' 
        parse {
            let! v1 = p1
            let! v2 = p2
            return f (v1, v2)
        }

    let tuple3 (p1:Parser<'a, 'b, 'c>) (p2:Parser<'a, 'b, 'd>) (p3:Parser<'a, 'b, 'e>) (f:'c * 'd * 'e -> 'f) = //' 
        parse {
            let! v1 = p1
            let! v2 = p2
            let! v3 = p3
            return f (v1, v2, v3)
        }

    let tuple4 (p1:Parser<'a, 'b, 'c>) (p2:Parser<'a, 'b, 'd>) (p3:Parser<'a, 'b, 'e>) (p4:Parser<'a, 'b, 'f>) (f:'c * 'd * 'e * 'f -> 'g) = //' 
        parse {
            let! v1 = p1
            let! v2 = p2
            let! v3 = p3
            let! v4 = p4
            return f (v1, v2, v3, v4)
        }

    let tuple5 (p1:Parser<'a, 'b, 'c>) (p2:Parser<'a, 'b, 'd>) (p3:Parser<'a, 'b, 'e>) (p4:Parser<'a, 'b, 'f>) (p5:Parser<'a, 'b, 'g>) (f:'c * 'd * 'e * 'f * 'g -> 'h) = //' 
        parse {
            let! v1 = p1
            let! v2 = p2
            let! v3 = p3
            let! v4 = p4
            let! v5 = p5
            return f (v1, v2, v3, v4, v5)
        }

    let createParserRef<'a, 'b, 'c> () = //'
        let dummyParser = fun state -> failwith "a parser was not initialized"
        let r = ref dummyParser
        (fun state -> !r state), r : Parser<'a, 'b, 'c> * Parser<'a, 'b, 'c> ref //'

Uwaga: będziesz potrzebował Fsharp PowerPack do typu LazyList.

Przykład:

and conditionalExpressionNoIn = 
    parse {
        let! e1 = logicalORExpressionNoIn
        return! parse {
            do! skip expectQuestionMark
            let! e2 = assignmentExpression
            do! skip expectColon
            let! e3 = assignmentExpressionNoIn
            return ConditionalExpressionNoIn (e1, e2, e3)
        }
        return ConditionalExpressionNoIn (e1, SourceElement.Nil, SourceElement.Nil)
    }