Encuentro 7 - 25/8/2012 - Parsers

TALLER DE LENGUAJES: 07 (25/08/12)

Parsers

  Un parser es una función que transforma un input en un output. ¬¬
 
  El input será un string (aunque podría ser una cadena de otra cosa).

  El auput será un AST (Abstract Sintax Tree).

  Los parsers suelen estar divididos en distintos niveles:
 
    * Lexical: Transforma una lista de caracteres en una lista de tokens.
    * ? : Transforma el resultado del Lexical en un AST.

    Tipos Básicos de Tokens:
      * Literales: constantes asociadas a un tipo (1, "hola", etc.)
      * Keywords: tienen un significado asociado al lenguaje (public, class, etc.)
      * Identificadores: palabras que se usan.
      * Delimitadores: elementos puramente sintácticos. No aparecen en el AST ({,(,etc.)

  Veamos el siguiente código java:

    public class Bleh {
      int foo;
      int bar() {
println("hola" + 1);
      }
    }

    Literales: "hola", 1
    Keywords: public, class
    Identificadores: Bleh, foo, bar, println, +
    Delimitadores: {, }, (, )

    Notar que las lineas:

int foo;
int bar() {

    Arrancan igual, pero definen cosas distintas. Entonces va a hacer falta manejar alguna clase de backtracking u otro mecanismo para ir cambiando a medida que avanza.


  A medida que va avanzando, el parser tiene que ir consumiendo la entrada. El Parser le pide al Lexical a medida que va necesitando.

  <Ver ejemplos de Parsers>

 Parser Combinators

  Son funciones que reciben un parser y devuelven otro.

    p ~ q: ejecuta p y q en secuencia. q recibe el resultado de p. Devuelve ambos resultados en una tupla.

    p ~> q : ejecuta p ~ q pero ignora el resultado de p.

    p <~ q : ejecuta p ~ q pero ignora el resultado de q.

    p ~! q : p ~ q, pero sin backtracking.

    p ||| q : parsea p o q tratando de consumir la mayor cantidad de caracteres.

    p ^^ f : parsea con p y le aplica f al resultado.

    p ^^^ v : parsea con p y devuelve la constante v.

    p* : parsea 0+ veces p.

    p * q : parsea 0+ veces p combinando los resultados con el resultado de aplicar el parser q al separador. Hace algo así como "foldear"...

    p+ : parsea 1+ veces p.

    p? : parsea p 0 o 1 vez.
Comments