compiler-construction - que - f# vs c#

Analizador de descenso recursivo y programación funcional. (5)

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?

¡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

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

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:

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 #:

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

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

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.