compiler-construction - que - f# vs c#

Analizador de descenso recursivo y programación funcional.

Question

Así que últimamente he estado trabajando en escribir un compilador simple para comprender mejor los conceptos del compilador. Al ser un lector diligente de stackoverfolow, parece que existe un consenso de que escribir un compilador en un lenguaje funcional es más fácil que uno imperativo. Con este fin, pensé que intentaría matar dos pájaros y escribir un compilador en F # para aprender un lenguaje funcional y escribir un compilador al mismo tiempo.

He estado leyendo el libro del dragón y decidí comenzar con un analizador de descenso recursivo escrito a mano en F #. El libro del dragón, sin embargo, tiene casi todas las muestras de código en un estilo imperativo. Por ejemplo, la función de token de coincidencia realiza una parte importante de su trabajo a través de un efecto secundario.

Entonces, mi pregunta es ¿qué aspecto tendría un enfoque funcional más tradicional para analizar (es decir, algunos efectos secundarios)? Sé que el compilador Haskell (GHC) está escrito en Haskell, pero apreciaría un ejemplo de código algo más pequeño y más fácil de comprender.

En segundo lugar, ¿vale la pena probar y adoptar un enfoque funcional para el análisis, o es realmente en optimizaciones al código intermedio que los lenguajes funcionales brillan y simplemente no he llegado todavía? Es decir, ¿debería repasar el análisis en F # utilizando un estilo imperativo y cambiar a un enfoque más funcional más adelante?

Answer 1

¡Los combinadores de analizadores son realmente hermosos! FParsec es una biblioteca de combinadores de analizadores monádicos muy hábil que deberías revisar. Si desea comenzar con algo simple y aún puramente funcional, puede disfrutar del tokenizer / parser del intérprete Scheme en la serie F # aquí (mi blog): http://blogs.msdn.com/b/ashleyf/archive/2010/09/24/fscheme-0-0-0.aspx

Answer 2

He estado trabajando en un compilador ECMAScript en F # por un tiempo, así que estoy en el mismo barco que tú. Quizás algo de mi trabajo pueda ser de utilidad para ti. Aquí hay una biblioteca simple de combinadores de analizadores en la que he estado trabajando y que uso en combinación con FParsec. No está cerca de ser perfecto, pero debería brindarte algo lo suficientemente simple como para estudiar para que puedas pasar a cosas más avanzadas. Si terminas usando FParsec, puedes notar que muchas de las cosas aquí se inspiraron en él.

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

NOTA: Necesitará PowerPack para el tipo LazyList .

Ejemplo:

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)
    }

Answer 3

Respuesta derivada de este artículo del blog :

Entonces, mi pregunta es ¿qué aspecto tendría un enfoque funcional más tradicional para analizar (es decir, algunos efectos secundarios)?

Parece que necesita separar funcional (como en Lisp, Scheme, Standard ML, CAML, OCaml, F #) de la pureza (ausencia de efectos secundarios, como en Haskell) y las características del lenguaje incidental (tipos de datos algebraicos, comparación de patrones).

Gracias a los tipos de datos algebraicos, la coincidencia de patrones y las funciones de orden superior, F # es bueno para el análisis y excelente para las transformaciones y la generación de código, pero la mayoría de los analizadores de producción escritos en F # no son puros. Históricamente, la familia de idiomas de F # se deriva principalmente de (los MetaLanguages ​​o MLs) fueron creados específicamente para este tipo de metaprogramación.

Aquí hay un conjunto muy simple de patrones activos recursivos que analizan y evalúan expresiones matemáticas compuestas de dígitos simples, operadores + - * y subexpresiones entre corchetes:

> let rec (|Term|_|) = function
    | Factor(e1, t) ->
        let rec aux e1 = function
          | ''+''::Factor(e2, t) -> aux (e1 + e2) t
          | ''-''::Factor(e2, t) -> aux (e1 - e2) t
          | t -> Some(e1, t)
        aux e1 t
    | _ -> None
  and (|Factor|_|) = function
    | ''-''::Factor(e, t) -> Some(-e, t)
    | Atom(e1, ''*''::Factor(e2, t)) -> Some(e1 * e2, t)
    | Atom(e, t) -> Some(e, t)
    | _ -> None
  and (|Atom|_|) = function
    | c::t when ''0''<=c && c<=''9'' -> Some(int(string c), t)
    | ''(''::Term(e, '')''::t) -> Some(e, t)
    | _ -> None;;
val ( |Term|_| ) : char list -> (int * char list) option
val ( |Factor|_| ) : char list -> (int * char list) option
val ( |Atom|_| ) : char list -> (int * char list) option

Aquí hay un ejemplo de cómo se usa para analizar y evaluar una expresión:

> let (Term e) = List.ofSeq "1+2*(3-4)*-5";;
val e : int * char list = (11, [])

Esa es una solución pura que utiliza la coincidencia de patrones sobre las listas con los patrones activos de F #. En realidad, querrá definir un tipo para su árbol de sintaxis abstracta y devolver un valor de ese tipo. Esto es realmente fácil en F #:

type expr =
  | Int of int
  | Neg of expr
  | Add of expr * expr
  | Sub of expr * expr
  | Mul of expr * expr

  static member (~-) f = Neg f
  static member (+) (f, g) = Add(f, g)
  static member (-) (f, g) = Sub(f, g)
  static member (*) (f, g) = Mul(f, g)

let rec (|Term|_|) = function
  | Factor(e1, t) ->
      let rec aux e1 = function
        | ''+''::Factor(e2, t) -> aux (e1 + e2) t
        | ''-''::Factor(e2, t) -> aux (e1 - e2) t
        | t -> Some(e1, t)
      aux e1 t
  | _ -> None
and (|Factor|_|) = function
  | ''-''::Factor(e, t) -> Some(-e, t)
  | Atom(e1, ''*''::Factor(e2, t)) -> Some(e1 * e2, t)
  | Atom(e, t) -> Some(e, t)
  | _ -> None
and (|Atom|_|) = function
  | c::t when ''0''<=c && c<=''9'' -> Some(Int(int(string c)), t)
  | ''(''::Term(e, '')''::t) -> Some(e, t)
  | _ -> None

let (Term e) = List.ofSeq "1+2*(3-4)*-5"

Tenga en cuenta que solo se requirió un cambio menor en el analizador porque el AST también se puede construir utilizando los operadores + , - y * .

En segundo lugar, ¿vale la pena probar y adoptar un enfoque funcional para el análisis, o es realmente en optimizaciones al código intermedio que los lenguajes funcionales brillan y simplemente no he llegado todavía?

Estás hablando de pureza, no de programación funcional. La pureza no es particularmente útil en el contexto del análisis de texto y, de hecho, puede ser un verdadero obstáculo (por ejemplo, internar símbolos es una pesadilla en Haskell). Sin embargo, F # tiene muchos otros beneficios que lo hacen bueno para este conjunto de problemas. En particular, aunque otros lenguajes como OCaml tienen herramientas mucho mejores para analizar, creo que F # es el mejor lenguaje .NET en este contexto.

Es decir, ¿debería repasar el análisis en F # utilizando un estilo imperativo y cambiar a un enfoque más funcional más adelante?

Depende completamente de lo que quieras hacer funcional. Usaría fslex y fsyacc con código puro para construir AST en las acciones pero impurezas para cualquier cosa, como el hash, o la generación de ID únicas.

Puede apreciar los siguientes artículos que he escrito sobre este tema en este blog (nota paywall):

• "Análisis de texto con Lex y Yacc" (30 de septiembre de 2007).
• "Optimización de un intérprete de bytecode simple" (31 de octubre de 2007).
• "Combinadores de analizadores" (30 de noviembre de 2007).
• "Programación orientada al lenguaje: el intérprete de nivel de término" (31 de diciembre de 2007).
• "Programación orientada al lenguaje: reescritura de términos" (16 de agosto de 2008).
• "Generación de código en tiempo de ejecución usando System.Reflection.Emit " (31 de agosto de 2008).
• "Análisis y visualización de datos binarios del Sistema de Información Geográfica" (30 de noviembre de 2009).

Answer 4

Una estrategia para el análisis funcional es combinadores de analizadores monádicos. Puedes leer algo sobre esto here (y seguir enlaces) o usar una biblioteca como FParsec . Sin embargo, no recomiendo este enfoque si solo está aprendiendo / iniciando F # / compiladores.

Otro enfoque con F # es usar FsLex / FsYacc (en el PowerPack ). Detesto un poco la tecnología Lex / Yacc, así que tampoco lo recomiendo.

Creo que deberías escribir un analizador decente recursivo a mano. No tengo fuertes sentimientos con respecto a un tokenizador, pero simplemente tokeninizar todo el archivo en una lista (n inmutable) de tokens y luego hacer un descenso recursivo (y aprovechar algún patrón de coincidencia) es una buena manera de lidiar con el análisis. Y, por supuesto, querrá usar uniones discriminadas para representar la salida AST del analizador (a la here ).

No he leído el libro del dragón en mucho tiempo, pero aparentemente soy la única persona en el planeta que no le gusta. Consideraría abandonar ese texto en favor de un libro que discute sobre compiladores que usan algún lenguaje basado en ML, aunque no puedo recomendar uno de antemano.

EDITAR

No he hecho uno de estos en un tiempo, así que me tomé unos minutos para codificar una pequeña muestra.

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

(Esperemos que no haya errores graves).

Answer 5

Una respuesta más simple que las otras buenas respuestas:

Un analizador en un lenguaje de función toma un flujo de token en un árbol de análisis y el resto del flujo de token. Es decir, tiene tipo.

 token list -> ast * token list

Un analizador decente recursivo usualmente tiene un gran número de funciones de este tipo que come la secuencia de token y luego construye una pequeña parte del árbol de análisis. Al llamar a estos recursivamente (decente recursivo), obtienes lo que quieres.

El siguiente paso es utilizar analizadores de orden superior: analizadores que funcionan con otros analizadores. Esto es lo que hacen las bibliotecas de parser combinator. Quizás podría comenzar con un esquema de recursión simple y luego actualizarlo a combinadores de analizador.