Parser combinators (brevemente explicados)

Los parser combinators te permiten crear parser más complejos a partir de otros más sencillos, combinándolos como si fuesen operadores aritméticos.

Perfectamente definido queda en Wikipedia:

En programación funcional, un parser combinator es una función de orden superior que acepta múltiples parsers como entrada y devuelve un nuevo parser como salida. En este contexto, un parser es una función que acepta strings como entrada y devuelve una cierta estructura como salida, típicamente un árbol de parseo o un conjunto de índices que representan las localizaciones en el string donde el parser paró satisfactoriamente. Los parser combinators habilitan una estrategia recursiva descendente de parseo, estrategia que facilita la construcción y testeo modular. Esta técnica de parseo se denomina parseo combinatorio.

Los operadores aritméticos que puedes usar son:

  • a ~ b Parseo de una sequencia compuesta de ‘a’ y después ‘b’
  • a | b Parser alternativo de ‘a’ o ‘b’
  • a? Parser opcional de ‘a’
  • a* Parser opcional y repetible
  • a+ Parser repetible
  • a ~> b Como el operador ~ pero ignorando el miembro izquierdo (a)
  • a <~ b Como el operador ~ pero ignorando el miembro derecho (b)

Y en esencia, eso es lo que necesitas saber sobre parser combinators 🙂
Un parser muy sencillo podría ser:

import scala.util.parsing.combinator._
import scala.util.matching.Regex
val parser = new RegexParsers {
  def mySuperSimpleParser= """\s*_end_$""".r ^^ { _.toString }
}

Debería reconocer cualquier string que termine con cero o más espacios y la cadena “_end_”, y devolver el string.

Lo que se encuentra entre llaves es la semántica, la acción se va a ejecutar cuando nos encontremos con un elemento parseado.

Así que básicamente,

a ^^ f

parseará a (sintáxis), y aplicará la función f al resultado(semántica).

Para parsear un string simplemente haríamos como sigue:

parse(myParser, "my input string           _end_") match {
  case Success(matched,_) =>
    matched match{
      case "hello"=>
        println "hello world"
      case listOfArgs@h::t=> 
        MyParserHelper.executeAction(listOfArgs)
      case _=> 
        println( s"string $matched has been recognized, but I don't know what to do with it" )
    }
  case Failure(msg,_) =>   
    println("FAILURE PARSING STRING " + msg)
}

Hasta ahora, no hemos cominado mySuperSimpleParser con nada, así que compliquémoslo un poco más.
Un ejemplo (todavía simple) podría ser:

def myParser = 
  (pHelp | pThreeArgs) <~ mySuperSimpleParser

donde mySuperSimpleParser encajaría (como vimos antes) con cualquier string que termina en cero o más espacio y la cadena “_end_”, pero no haría nada con ello y continuaría con la parte izquierda en el input, parseando pHelp o pThreeArgs.

pHelp podría ser algo como:

def pHelp=  
  "(help|helpMe)".r ^^ { _=> HelpCommand }

HelpCommand es una case class que, for cuestión de simplicidad, no definiremos aquí, pero que se podría sustituir por:

def pHelp = 
  "(help|helpMe)".r ^^ { _=>"the recogniced command is help" }

Incluso no necesitaríamos añadir ninguna semántica si no es necesario:

def pHelp = 
  "(help|helpMe)".r

Nos falta ahora definir el parser pThreeArgs. Este parser reconocerá una secuencia de tres palabras y las pondrá secuencialmente en una lista (la cual devolveremos):

def pThreeArgs: Parser[List[Any]] = {
  var paramsCtx=mutable.ListBuffer[String]()
  pListParam(paramsCtx) ~> pListParam(paramsCtx) ~> pListParam(paramsCtx) ^^ {_.toList}
}

Nótese que he creado un ListBuffer mutable, que actuará como un contexto “global” para cada uno de los tres parsers que estamos combinando, de manera que solo se tengan que ocupar de parsear un parámetro y almacenarlo en el contexto global que han recibido como parámetro de la función (estos parsers son funciones).
Al final, la lista completa se devuelve conteniendo los tres parámetros 🙂

¿Se os ocurre de una mejor (o al menos más funcional) forma de resolverlo? 😉
pListParam sería algo del estilo:

def pListParam(l:mutable.ListBuffer[String])= 
  """\S+""".r ^^ {l+=_.toString}

Para un ejemplo más complejo, visitad el siguiente enlace.

Anuncios

2 thoughts on “Parser combinators (brevemente explicados)

  1. creo que este fue el tema que me sacó del curso de haskell… los parsers xD y me siguen echando humo las orejas….

    Tengo una duda, tal vez por mi inexperiencia en Scala: en este caso, como actuan los operadores “” que usas?

    Quitando casos de reconocimiendo de comandos (y gramaticas en general que es el ejemplo más clásico), te/os ha surgido la necesidad de parsers para otras cosas?

    Me gusta

  2. En mi caso, yo quería tener un pequeño intérprete de comandos, donde pudiera hacer varias cosas:
    Por ejemplo:

    def myParser = (pHelp |pUser | pRole | pVersion |pDownload | pReplace | pScheduler) <~ pEnd

    El intérprete espera una de estas instrucciones (una, u otra, u otra, o la otra, o la otra…) y el final (pEnd).
    Cada una de estas instrucciones o comandos (porque en mi caso lo que quiero es interpretar comandos), es a su vez, otro parser, que puede estar compuesto de varias opciones (uno, u otro, u otro) o de una secuencia (uno y luego otro), o de uno que se repite varias veces.

    Así podríamos ir profundizando e irnos metiendo por las ramas, hasta definir una gramática completa.

    Esta es la única necesidad que he tenido (que es para lo que sirven estas cosas): generar gramáticas que generan lenguajes (podrías hacer un compilador si quisieras, pero lo mío era mucho más sencillo, y como puedes ver, es bastante rápido de hacer).

    Le gusta a 1 persona

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s