Te damos la bienvenida a proyecto on line, ahora vas a encontrar la resolución de lo que estás buscando.
Solución:
Respuesta derivada de este artículo de blog:
Entonces, mi pregunta es ¿cómo sería un enfoque funcional más tradicional para el análisis sintáctico (es decir, pocos efectos secundarios)?
Parece que necesita separar funcional (como en Lisp, Scheme, Standard ML, CAML, OCaml, F #) de pureza (ausencia de efectos secundarios, como en Haskell) y características de lenguaje incidentales (tipos de datos algebraicos, coincidencia 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 sintáctico 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 lenguajes de los que se deriva principalmente F # (los MetaLanguages o ML) se crearon 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 un solo dígito, + - * 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 en listas con 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 usando el +, - y * operadores.
En segundo lugar, ¿vale la pena intentar adoptar un enfoque funcional para el análisis sintáctico, o es realmente en las optimizaciones para el código intermedio donde los lenguajes funcionales brillan y todavía no he llegado allí?
Estás hablando de pureza, no de programación funcional. La pureza no es particularmente útil en el contexto del análisis sintáctico de texto y, de hecho, puede ser un verdadero obstáculo (por ejemplo, intercalar 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 pasar por alto el análisis en F # usando 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 la conversión de hash o la generación de ID únicos.
Puede apreciar los siguientes artículos que he escrito sobre este tema en este blog (note 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).
- “Parser combinators” (30 de noviembre de 2007).
- “Programación orientada al lenguaje: el intérprete de nivel termino” (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 sintáctico funcional son los combinadores de analizadores sintácticos monádicos. Puede leer algo sobre esto aquí (y seguir los enlaces) o usar una biblioteca como FParsec. Sin embargo, no recomiendo este enfoque si solo está aprendiendo / iniciando compiladores de F # /.
Otro enfoque con F # es usar FsLex / FsYacc (en PowerPack). Detesto un poco la tecnología Lex / Yacc, así que tampoco recomiendo esto.
Creo que deberías escribir un analizador decente recursivo a mano. No tengo fuertes sentimientos con respecto a un tokenizador, simplemente tokeninizo todo el archivo en un (n inmutable) list de tokens y luego hacer un descenso recursivo (y aprovechar algunas coincidencias de patrones) es una buena manera de lidiar con el análisis. Y, por supuesto, querrá usar uniones discriminadas para representar la salida AST del analizador (como aquí).
No he leído el libro del dragón en mucho tiempo, pero aparentemente soy la única persona en el planeta a la que no le gusta. Consideraría abandonar ese texto en favor de un libro que analice los compiladores que utilizan algún lenguaje basado en ML, aunque no puedo recomendar uno de improviso.
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 )
(Con suerte, no hay errores atroces).
¡Los combinadores de analizadores son realmente hermosos! FParsec es una biblioteca de combinador de analizador monádico muy hábil que debe consultar. Si desea comenzar con algo simple y aún puramente funcional, puede disfrutar del tokenizador / analizador del intérprete de Scheme en la serie F # aquí (mi blog): http://blogs.msdn.com/b/ashleyf/archive/ 2010/09/24 / fscheme-0-0-0.aspx