GrammGen en C# (1) Primeros Conceptos

Published on Author lopezLeave a comment

Siguiente Post

He trabajado mucho escribiendo lexers y parsers, ver por ejemplo:

https://github.com/ajlopez/AjSharp
https://github.com/ajlopez/AjTalk
https://github.com/ajlopez/AjTalkJs
https://github.com/ajlopez/Mass
https://github.com/ajlopez/AjLispJava

y otros más. Hace dos años me encontré con Ian Piumarta en la Smalltalks 2011, en la Universidad de Quilmes (ver AjSoda). El me propuso que trabajara en la implementación de un PEG

http://en.wikipedia.org/wiki/Parsing_expression_grammar

Traté el año pasado de escribir algo en JavaScript, pero este año me dediqué a escribir dos implementaciones, que no sé si llegan en un PEG, pero se acercan. Por un lado en JavaScript tengo funcionando:

https://github.com/ajlopez/SimpleGrammar

que lo estoy consumiendo (dog fooding!) en:

https://github.com/ajlopez/PageJs

con bastante buen resultado. Pero hoy quería presentar que tengo algo implementando en C#:

https://github.com/ajlopez/GrammGen

Es una solución armada con TDD (librería de clases y tests):

La idea es tener un parser que tenga una lista de reglas. Las reglas sirven para reconocer series de caracteres y patrones:

var rule = Rule.Get("0-9").OneOrMore().Generate("Integer");

Esta regla reconocerá una serie de dígitos, produciendo un elemento no terminal llamado “Integer” (se nombran con la primera letra en mayúscula). Ver que hay una interfaz fluent, y que el método Generate agrupa el resultado obtenido hasta ese momento (un string de caracteres) bajo un elemento con nombre “Integer”.

Lo interesante es que el generate también permite generar algo con nombre “Integer”, pero en vez de string, tener asociado un objeto nuestro:

Rule.Get("0-9").OneOrMore().Generate("Integer", 
    x => int.Parse((string)x));    

En este caso, asocia al elemento reconocido un valor que es un entero, y un nombre “Integer”.

Uno puede tener una lista de reglas:

var rules = new Rule[] {
    // ...
    Rule.Get("Term", Rule.Or('*', '/'), "Factor").Generate("Term", MakeBinaryOperatorExpresion),
    Rule.Get("Factor").Generate("Term"),
    Rule.Get("Integer").Generate("Factor"),
    // ...
}

y con ellas, armar un objeto Parser:

var parser = new Parser("1+2", rules);

Uno puede pedirle al parser un elemento por nombre:

var element = parser.Parse("Expression");
var expression = (IExpression)element.Value;

El que el elemento a retornar tenga un valor IExpression, es parte nuestra: IExpression debería ser una interfaz de nuestro programa, no es parte de GrammGen. Cada elemento que devuelve GrammGen tiene un valor y un tipo (un string). El valor lo vamos armando nosotros, en los métodos .Generate, donde decimos qué queremos obtener. Ver los tests y el ejemplo de Calculator, para ver más detalles (como left recursion, y precedencia de operadores).

Hoy completé un pequeño ejemplo de consola, con TDD:

Parsea un string, con una expresión aritmética de enteros:

Pero podría usarser GrammGen para proyectos más ambiciosos, como el armado de un AST (Abstract Syntax Tree) para un lenguaje bien definido.

Nos leemos!

Angel “Java” Lopez

http://www.ajlopez.com

http://twitter.com/ajlopez

Leave a Reply

Your email address will not be published. Required fields are marked *