Miguel Vilá

moon

Parseando con funciones

Nov 23 2016
Tags: Scala, Parsing, Functional Programming, Parser Combinators

Nota aparte (Click!)

Este post iba a ser originalmente el último de esta serie pero creo que terminé escribiendo algo que es más autocontenido. Tal vez con el tiempo escriba el último post de esa serie.

Sorry por el spanglish en este post.

¿Qué significa parsear? Es el proceso de tomar una secuencia de tokens (usualmente caracteres) y construir alguna estructura de datos. Esta estructura de datos usualmente tiene significado dentro del dominio de un programa. Por ejemplo puede ser un objeto JSON:

Una aproximación funcional

La idea de construir un parser siempre se me ha hecho intimidante. Es el tipo de problema al que no sabía como aproximarme. Pero gracias a un acercamiento funcional esa tarea se vuelve más accesible y entendible. Este acercamiento consiste en describir qué es un parser en terminos de funciones.

Intentémos describir cómo se vería una función que parsea alguna estructura de datos. Si nuestro objetivo es manipular números enteros entonces el tipo de nuestro parser podría ser:

String => Int

En cambio si nuestro objetivo es manipular Floats entonces podría ser:

String => Float

Refinando la definición

En general si nuestro objetivo es parsear algo de tipo A entonces el tipo de nuestro parser será:

String => A

Creemos un type alias para esto:

type Parser[A] = String => A

Pero esto no tiene en cuenta varias cosas. La primera es que esto no tiene en cuenta los errores que se pueden producir al intentar parsear alguna estructura que no tiene sentido. Podríamos usar un tipo como Either pero un acercamiento más simple es una lista que estará vacía si al intentar parsear se produjo un error. Nuestro tipo refinado será:

type Parser[A] = String => List[A]

Por último queremos combinar nuestros parsers para expresar parsers más complejos. Digamos que queremos parsear expresiones que son sumas. Por ejemplo cadenas como “123+456”. Y digamos que tenemos algo que parsea un número y algo que parsea el signo +. Entonces deberíamos poder combinar ambos de la siguiente forma: “Primero parsee el primer número, después parsee el signo más y por último parsee el segundo número”. Pero bajo nuestro esquema actual no hay forma de hacerlo por que nuestras funciones parseadoras hacen “demasiado”. La cosa funciona bien para una cadena que en su totalidad consiste de un número:

val parseNumber: Parser[Int] = ???
parseNumber("123")
//List(123)

Eso está bien, pero cuando le pasamos un String que al principio tiene un número entonces va a fallar:

val parseNumber: Parser[Int] = ???
parseNumber("123+456")
//List()

Falla justificadamente por que toda la cadena "123+456" no es un número. Más sin embargo el principio de la cadena sí es un número. Ahora mismo el significado de nuestro tipo Parser es demasiado estricto. Es “parsee toda la cadena de entrada y devuelva un valor si es posible”. Pero para poder “componer” con otros parsers quisieramos ejecutar ese parser para que identifique el primer número que pueda y una vez hecho eso disponer del resto de la cadena para que podamos parsear otras cosas. Podemos ajustar nuestra definición para que no necesariamente parsee toda la cadena de entrada y para que devuelva el resto de cadena que no fue utilizada durante el parseo. Ajustando el tipo tenemos lo siguiente:

type Parser[A] = String => List[(A,String)]

Nota aparte (Click!)

Este tipo también se puede leer en como una rima en inglés (Tomado de Programming in Haskell por Graham Hutton):

A parser for things

Is a function from strings

To lists of pairs

Of things and strings

Para facilitarnos la cosa un poco no vamos a hacer que nuestro tipo Parser sea un alias sino que esté contenido como el atributo de una clase:

case class Parser[A](run: String => List[(A,String)]) extends AnyRef {

}

Esto nos permitirá agregar métodos.

Un parser muy básico

Uno de los parsers más básicos que podemos escribir es el que consume el primer caracter de una cadena, si es que existe:

val parseChar: Parser[Char] = 
    Parser { str =>
        if(str.isEmpty)
            List.empty
        else
            List( (str.head, str.tail) )
    }

Pero si queremos reconocer un solo dígito necesitamos reconocer si un caracter es o no un número. Podemos agregar una función filter que nos permita filtrar los resultados de un parseo:

case class Parser[A](run : String => List[(A,String)]) extends AnyRef { self => //(1)
                                                                       
    def filter(f: A => Boolean): Parser[A] = 
        Parser { str => //(2)
            self.run(str).filter { case (value,_) => //(3)
                f(value)
            }
        }
        
}

Vamos por partes: en (1) ponemos el nombre self a la instancia actual para podernos referir a ella desde otras instancias de Parser. En (2) iniciamos una nueva instancia de Parser. Esta instancia deberá leer un String y retornar algo de tipo List[(B,String)]. En (3) ejecutamos el parser inicial (para esto hacemos self.run), lo que nos retorna una lista de List[(A,String)] que a su vez filtramos conservando las tuplas cuyo primer elemento cumpla el predicado que recibimos como argumento.

Podríamos entonces tener un parser de dígitos así:

val parseDigit: Parser[Char] =
    parseChar.filter { c => '0' <= c && c <= '9' }

Pero tal vez quisieramos que el valor reconocido por el parser sea por ejemplo el número 1 y no el caracter '1'. Entonces necesitamos una forma de transformar el valor reconocido por el parser. Es decir una función que nos permita transformar el valor parseado:

case class Parser[A](run : String => List[(A,String)]) extends AnyRef { self =>

    def map[B](f: A => B): Parser[B] =
        Parser { str =>
            self.run(str).map { case (value,rest) =>
                (f(value),rest)
            }
        }

}

Así podemos volver a escribir nuestro parser de dígitos (nótese que ahora el tipo es Parser[Int] y no Parser[Char]):

val parseDigit: Parser[Int] =
    parseChar
        .filter { c => '0' <= c && c <= '9' }
        .map { c => c - '0' }

Parseando alternativas

En ocasiones vamos a necesitar describir un parser como el resultado de múltiples alternativas. Por ejemplo:

val parseTrue  = parseChar.filter( c => c == 't' ).map( _ => true )
val parseFalse = parseChar.filter( c => c == 'f' ).map( _ => false )
val parseBoolean = ???

Para hacer esto podemos tomar dos parsers, ejecutar el primero sobre la cadena de entrada y si eso arroja un resultado retornarlo, de lo contrario retornar lo que devuelva ejecutar el segundo parser:

case class Parser[A](run : String => List[(A,String)]) extends AnyRef { self =>

    def or(other: => Parser[A]): Parser[A] = Parser { str =>
        val firstResult = self.run(str)
        if(!firstResult.isEmpty) {
            firstResult
        } else {
            other.run(str)
        }
    }

}

Y así podemos describir el anterior parser como:

val parseBoolean = parseTrue or parseFalse

Secuenciando parsers

Digamos que en nuestra aplicación nuestros ids consisten de un dígito y de un caracter en mayúsculas:

case class Id(n: Int, char: Char)

Guardamos en algún lado los ids como String y quisieramos parsear esos Strings para convertirlos en objetos de tipo Id. El formato con el que los guardamos es primero el dígito concatenado con el caracter. Por ejemplo “5A”. Podríamos hacer algo como lo siguiente:

val idParser: Parser[Id] = Parser { str =>
  if(str.length() < 2) {
    List.empty
  } else {
    val nchar = str(0)
    if(isDigit(nchar)) {
      val n: Int = nchar - '0'
      val char = str(1)
      if( 'A' <= char && char <= 'Z') {
        List((Id(n,char), str.substring(2)))
      } else {
        List.empty
      }
    } else {
      List.empty
    }
  }
}

Pero acá estamos repitiendo mucho de lo que hicimos antes: no estamos aprovechando el hecho de que ya definimos un parseDigit y un parseChar. El patrón general que estamos buscando es el siguiente: ejecutamos un parser, con lo que queda de cadena sin procesar ejecutamos otro parser y si ambos son exitosos combinamos los valores parseados de alguna forma. La firma de la función que podríamos estar buscando es algo como:

(Parser[A], Parser[B], (A,B) => C) => Parser[C]

Creo que usualmente esta operación se llama map2. La podríamos implementar así:

def map2[A,B,C](p1: Parser[A], p2: Parser[B], f: (A,B) => C): Parser[C] = 
  Parser { str =>
    for {
      (a, rest1) <- p1.run(str)
      (b, rest2) <- p2.run(rest1)
    } yield (f(a,b), rest2)
  }

Aquí estamos aprovechando que run retorna una lista para realizar un for comprehension. También cabe notar como estamos pasando los argumentos rest1 y rest2. Esto es importante para conservar el significado de parser: usamos partes de la cadena y siempre retornamos el pedazo de cadena que no procesamos.

Ahora podemos reescribir idParser así:

val idParser: Parser[Id] = 
    map2(parseDigit, parseChar.filter(isUpperCase), (n: Int, c: Char) => Id(n,c) )

Mucho más conciso así, ¿no?

Todas estas funciones que tomán uno o más Parsers y retornan uno nuevo son denominadas combinadoras. Aquí yace la riqueza del acercamiento funcional: en vez de describir explícitamente paso a paso lo que el Parser debe hacer podemos usar funciones combinadoras y poco a poco expresamos lo que deseamos.

Una algebra con un constructor base

Hasta ahora pareciera que estamos construyendo una algebra que nos permite combinar valores de tipo Parser. Como es usual nos puede servir una función que coja un valor cualquiera y lo encierre como un valor dentro de la algebra. Podemos llamar esta función succeed por que es como construir un parser que siempre será exitoso con el valor que le pasemos:

def succeed[A](value: A): Parser[A] = Parser { str => (value,str) }

Está función nos servirá más adelante para definir ciertos casos base.

Repeticiones

Ahora queremos parsear no solamente un caracter sino una repetición de caracteres. Por ejemplo podríamos querer parsear las cadenas de texto que empiezan por cero o más As.

def rep[A](pa: Parser[A]): Parser[List[A]] = ???

val charA = parseChar.filter(_ == 'A')
val parseAs = rep(charA)

parseAs.run("AAAAxxx")
// List( (List('A','A','A','A'), "xxx") )

parseAs.run("xxx")
// List( (List(), "xxx") )

Podríamos intentar primero parsear una A, si eso falla, como en el segundo ejemplo retornamos una lista vacía. Si logramos parsear una A cogemos el resto de la cadena e intentamos parsear una repetición de As sobre esa cadena (es decir: ¡recursión!) y por último cogemos lo que retorne ese parseo y lo combinamos con la primera A que parseamos.

Resulta que para hacer lo anterior YA tenemos los suficientes ingredientes:

def rep[A](pa: Parser[A]): Parser[List[A]] = 
    map2(pa, rep(pa), (a:A, tl: List[A]) => a :: tl ) or succeed(List.empty)

Esto funciona así:

El primer parser (lo que va antes del or) se encarga de parsear una lista no vacía de caracteres. Si ese primer parser falla el or se encargará de reintentar con el segundo que siempre va a ser exitoso con una lista vacía. El primer parser funciona parseando una sola instancia (el argumento pa), después recursivamente parsea otra lista de repeticiones del resto de la cadena y une los dos resultados concatenándolos.

Pero resulta que si intentamos usar rep vamos a obtener un overflow de la pila de ejecución. Esto es por que la definición recursiva se está expandiendo indefinidamente:

rep(charA) == map2(charA, rep(charA), ...) or (...)
           == map2(charA, map2(charA, rep(charA), ...) or (...), ...) or (...)
           == etc...

El problema es que antes de que se ejecute map2 se deben evaluar sus argumentos. Esto se puede solucionar haciendo que el segundo argumento de map2 sea call by name de forma tal que las invocaciones no lo evaluan inmediatamente:

def map2[A,B,C](p1: Parser[A], p2: => Parser[B], f: (A,B) => C): Parser[C] = ...

Cuando el contexto importa

Digamos que tenemos que reconocer las cadenas que empiezan por un número y después de las que hay tantas `X’s como ese número. Por ejemplo “1X” o “2XX” o “3XXX”, etc… Primero construyamos un parser para repeticiones fijas de un parser:

def repN[A](p: Parser[A], n: Int): Parser[List[A]] = 
    if(n == 0) {
        succeed(List.empty)
    } else {
        map2(p, repN(p,n-1), (head: A, tail: List[A]) => head :: tail)
    }

Eso funciona cuando sabemos cuantas repeticiones queremos:

val twoXs = repN(parseChar.filter(_ == 'X'), 2)
twoXs.run("XXA")
// List((List('X', 'X'), "A"))

Con esto podríamos construir un parser para el caso especial de cuando el número es 2:

map2(
    parseChar.filter(_ == '2'),
    repN(parseChar(_ == 'X'), 2), 
    (c: Char, reps: List[Char]) => (c,reps)
)

Pero queremos generalizar esto para cualquier entero que se nos pueda aparecer. El problema es que tenemos 2 parsers y el segundo tiene un pedazo de información que depende del resultado del primero. Más concretamente el parámetro n del segundo parser depende de lo que aparezca al principio de la cadena: si parseamos un caracter '3' entonces en el momento de construir el segundo parser el parámetro n deberá ser el número 3. El patrón que estamos buscando es el siguiente:

Llamemos a esta operación andThen por que dice sirve para “secuenciar” resultados. Podría tener una firma como la siguiente:

def andThen[A,B](first: Parser[A], f: A => Parser[B]): Parser[B]

Recibe un primer parser y una función que construye un nuevo parser usando el resultado del primero. Al final devuelve lo que devuelva ese segundo parser que construimos. Implementémosla:

def andThen[A,B](first: Parser[A], f: A => Parser[B]): Parser[B] = Parser { str =>
   first.run(str).map { case (a, rest1)  =>
          f(a).run(rest1)
      }.flatten
   }

Y podemos ver este nuevo combinador en acción:

val parseNandReps = 
  andThen(
    parseDigit,
    { n: Int => 
      repN(parseChar.filter(_ == 'X'), n) 
    }
  )
  
parseNandReps.run("2XX")
// List((List('X', 'X'), ""))
parseNandReps.run("3XX")
// List()

Este es un ejemplo de algo que las expresiones regulares no pueden hacer: interpretar el resultado de un parseo parcial para continuar parseando.

Solo el principio

Con estas bases se pueden construir parsers para cosas más complejas: por ejemplo expresiones aritméticas, JSON objects o incluso podemos construir el árbol de sintáxis de un lenguaje de programación. Incluso para cosas más simples pueden reemplazar expresiones regulares y pueden servir para terminar con código más entendible.

Por ejemplo para parsear expresiones aritméticas en una hoja de cálculo escribí esto. Son ménos de 60 líneas de código y usan la librería estándar de parser combinators de Scala. Esa librería tiene muchas más funciones de las que describí acá, pero la idea base es la misma.

Así que si algún día necesitan parsear algo pueden usar esta aproximación. Es fácil de entender y el código resultante suele ser legible.

Fuentes y otros enlaces

Este post está basado en lo que aprendí leyendo varias fuentes:

Varias librerias que implementan de formas distintas la misma idea:

Una forma alternativa (no funcional) de parsear es esta.