Construyendo el compilador Parte I: ANTLR V4 (ya van 4 versiones, increible), café y una miradita a los parser y lexer generados con Java

La satisfacción como gasolina mental

 En ocasiones, filosofamos sobre la dificultad de tener la capacidad de realizar ciertas tareas. Por ejemplo, la subestimación provoca que demos menos, y en ocasiones una alta autoestima provoca que no sea de la mayor calidad.
Leí un paper interesante que habla sobre un estado de "ansiedad productiva". Este estado se debe a que en ocasiones, nuestro ambiente es demasiado blando, amigable, lindo. Esta "lindura" ambiental, es un pesticida para la productividad porque no salimos de la zona de confort. Tiene lógica y a la vez no. Por ende, soy fan de que las cosas que cuestan provocan satisfacción al ser realizadas.
Ahora bien, ¿por qué hablo de estos temas de psicología cuando este blog es de COMPILADORES?

Buena pregunta querido lector.

Quiero que entiendas que la satisfacción viene del trabajo duro, y cuando lo has dominado, no hay nada que pare esa felicidad. ANTLR vino a darle satisfacción a mi vida en algunso aspectos que creía olvidados, o más bien, ocultos o escondidos. Vamos, en ocasiones todos necesitamos eso.

ANTLR es según su página oficial: ANTLR (ANother Tool for Language Recognition) is a powerful parser generator for reading, processing, executing, or translating structured text or binary files. It's widely used to build languages, tools, and frameworks. From a grammar, ANTLR generates a parser that can build and walk parse trees.

Entonces, ANTLR provee una base para generar parser. ¿Por qué me causa tanta satisfacción? Porque hace apenas unos meses, yo sufrí en carne propia el crear un parser y un analizador léxico desde cero en Python. Este sufrimiento y que funcionara me hizo sentir realizado, alegre y sobre todo: satisfecho conmigo mismo.
En nuestro proceso de crear el compilador necesitamos una base sobre la cual pararnos: un parser y un lexer. ANTLR los genera en lenguaje JAVA por nosotros (tambien se puede en otros). Y estoy feliz, porque entiendo lo que hay detrás y comprendo la maravillosidad que es este lenguaje al hacer lo que me costó tantos meses. 
ANTLR, ejemplitos
En simples pasos, hace lo siguiente:
Debemos tener un lenguaje target, en este caso JAVA.
Debemos saber el lenguaje que queremos generar. En este caso, es DECAF, y necesitamos su gramática. La gramática incluye tokens, declaraciones, etc. 
Una vez consolidada la gramática se pasa a sintaxis de ANTLR. Ejecutamos comandos y WALA. 
ANTLR genera los files. Otras cositas lindas que hace, es tener la capacidad de tomar un ejemplo del lenguaje generado (un holamundo.decaf) y generar un arbol sintáctico que detecte el lenguaje. Si todo va bien, se genera un gráfico bastante guapo. 
ANTLR permite la creación de archivos de parser y lexer en JAVA. ¿Cómo?

Veamos la gramática de DECAF en ANTLR

grammar decafV2;

// ************ DEFINITIONS *******************

fragment LETTER: ('a' ..'z' | 'A' ..'Z');

fragment DIGIT: '0' ..'9';

// *************TOKENS *********************

CHAR2: LETTER;

ID: LETTER ( LETTER | DIGIT)*;

NUM: DIGIT (DIGIT)*;

COMMENTS: '//' ~('\r' | '\n')* -> channel(HIDDEN);

WS: [ \t\r\n\f]+ -> channel(HIDDEN);

// ********** PARSER *****************

program: 'class' 'Program' '{' (declaration)* '}';

declaration:

    structDeclaration

    | varDeclaration

    | methodDeclaration;

varDeclaration: varType ID ';' | varType ID '[' NUM ']' ';';

structDeclaration: 'struct' ID '{' (varDeclaration)* '}';

varType:

    'int'

    | 'char'

    | 'boolean'

    | 'struct' ID

    | structDeclaration

    | 'void';

methodDeclaration:

    methodType ID '(' (parameter (',')?)* ')' block;

methodType: 'int' | 'char' | 'boolean' | 'void';

parameter: parameterType ID | parameterType ID '[' ']';

parameterType: 'int' | 'char' | 'boolean';

block: '{' (varDeclaration)* (statement)* '}';

statement:

    'if' '(' expression ')' block ('else' block)?

    | 'while' '(' expression ')' block

    | 'return' (expression)? ';'

    | methodCall ';'

    | block

    | location '=' expression

    | (expression)? ';';

location: (ID | ID '[' expression ']') ('.' location)?;

expression:

    location

    | methodCall

    | literal

    | expression op expression

    | '-' expression

    | '!' expression

    | '(' expression ')';

methodCall: ID '(' (arg (',')?)* ')';

arg: expression;

op: arith_op | rel_op | eq_op | cond_op;

arith_op: '+' | '-' | '*' | '/' | '%';

rel_op: '<' | '>' | '<=' | '>=';

eq_op: '==' | '!=';

cond_op: '&&' | '||';

literal: int_literal | char_literal | bool_literal;

int_literal: NUM;

char_literal: '\'' CHAR2 '\'' | '"' CHAR2 '"';

bool_literal: 'true' | 'false';

Una vez teniendo la gramática en ANTLR, podemos generar files y probar el siguiente archivo de prueba. Un example.decaf

class Program {

  struct Cow

  {

    char  name[50];

    char  owner[50];

    int height;

    int weight;

  }

  int Eat(int weight)

  {

    weight = weight * 2 + 5 % 100;

    return weight;

  }

  void Moo(boolean moo)

  {

    char message;

    message = 'o';

    if (moo)

    {

      makeSound(message);

    }

    else

    {

      doNothing();

    }

  }

  void main() {

    struct Cow betsy;

    betsy.height = 5;

    betsy.weight = 10;

    besty.name = 'b';

    Moo(true);

    betsy.weight = Eat(betsy.weight);

  }

}

Usaremos el comando grun gramatica program example.decaf -gui para generar un gráfico de la gramática.

Espero hayan sido sorprendidos.

Y espero la próxima vez, todos valores el valor de la satisfacción