Parser combinators (briefly explained)

Parser combinators allow you to create complex parsers from simpler ones, by combining them as if they were arithmetic operands.

As very well defined at Wikipedia:

In functional programming, a parser combinator is a higher-order function that accepts several parsers as input and returns a new parser as its output. In this context, a parser is a function accepting strings as input and returning some structure as output, typically a parse tree or a set of indices representing locations in the string where parsing stopped successfully. Parser combinators enable a recursive descent parsing strategy that facilitates modular piecewise construction and testing. This parsing technique is called combinatory parsing.

The arithmetic operators you can use are:

  • a ~ b parse a sequence made of a then b
  • a | b introduce an alternative parser that parses a or b
  • a? introduce an optional parser
  • a* introduce on optional and repeatable parser
  • a+ introduce a repeatable parser
  • a ~> b like ~ but ignore the left member (a)
  • a <~ b like ~ but ignore the right member (b)

And that’s pretty much everything you need to know about parser combinators!
A very simple parser could be:

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

(which would recognice any string that ends with zero or more blank spaces and _end_, and return that string)

Here, what is enclosed between the curly brackets is a semantic action that is going to be executed.

So basically

a ^^ f

will parse a, and apply function f to the result (semantic action)

To parse a string we would simply do this:

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

And will define myParser right now.

So far, we haven’t combined mySuperSimpleParser with anything, so let’s make it a little bit more complicated:
A still simple example coud be somethig like this:

def myParser = 
  (pHelp | pThreeArgs) <~ mySuperSimpleParser

where mySuperSimpleParser would (as we saw before) match any string ending in zero or more blanks plus the “_end_” string at the end of the input, but wouldn’t do anything with it, and would continue on the left side on the input either parsing pHelp or pThreeArgs:
pHelp could be something like this:

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

HelpCommand is a case class that, for the sake of simplicity we will not define here, but we could also do something like:

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

Or even:

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

We don’t even need to take any semantic action on it if we do not want to.

The only thing left now is the pThreeArgs parser. This parser will recognice a secuence of three words (first one word, then another, and then another) and put the three of them, sequencially into a list, and that list is what will be returned:

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

Note, that I created a mutable ListBuffer, which will act as a “global” context to each of the three parsers that we are combining, so that they only worry about parsing one parameter and storing it on the global context that they have received as a function parameter (these parsers are functions).
At the end, the whole List, containing the three parameters, will be returned 🙂

Can you think of a better (or more functional way of doing it? 😉 )
pListParam would be something like that:

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

For a more complete example, please look here

Anuncios

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.