@alu0101040288/pegjs-infix2egg

Parser en PEG.js para una versión ligeramente distinta de PL/0

Este pequeño parser hecho con PEG.js es capaz de parsear una versión ligeramente modificada del lenguaje PL/0. El AST generado por el parser es directamente ejecutable por la máquina virtual de Egg.

Detalles de implementación

La gramática puede encontrarse en grammar/pl0.pegjs.

PEG.js no permite la declaración separada de elementos terminales y no terminales, por lo que el parser y el lexer deben ir juntos en un mismo archivo. En mi caso, los he separado con comentarios para mejorar un poco la legibilidad.

Los tokens están declarados de manera que admitan espacios delante y detrás. Por ejemplo:

END       = _ ('END'       / 'end')       _
CALL      = _ ('CALL'      / 'call')      _
CONST     = _ ('CONST'     / 'const')     _
VAR       = _ ('VAR'       / 'var')       _
PROCEDURE = _ ('PROCEDURE' / 'procedure') _

COMPARISON_OP   = _ op:('!=' / '<=' / '>=' / '=' / '<' / '>') _ { return makeWord(op); }
ADD_SUB_OP      = _ op:('+' / '-') _                            { return makeWord(op); }
MULT_DIV_MOD_OP = _ op:('*' / '/' / '%') _                      { return makeWord(op); }

Una pequeña diferencia entre los parsers PEG y otros como los generados por ANTLR es que el caracter para representar un OR es distinto (| por /), y también vale la pena mencionar que PEG sigue una evaluación de cortocircuito (short-circuit evaluation) que los otros parsers no, en el sentido en que en un OR, si la primera expresión encaja el parser seguirá por ahí, sin comprobar el resto de posibles opciones. Con respecto al ejemplo anterior:

COMPARISON_OP   = _ op:('!=' / '<=' / '>=' / '=' / '<' / '>') _ { return makeWord(op); }

Si el operador en cuestión es !=, no se molestará en comprobar el resto de operadores. Esto implica que no habrá ambiguedades aunque la gramática sea ambigua.

---

Con respecto al parser, la regla de comienzo es program, que admite un bloque o más, siendo un bloque un conjunto de declaraciones de variables, constantes, procedimientos y una posible sentencia. Un ejemplo:

VAR x, y;

PROCEDURE square
BEGIN
   x := x * 2;
END;

BEGIN
   x := 2;
   y := 0;
   WHILE y < 10 DO
   BEGIN
      call print(x);
      call square();
      y := y + 1;
   END;
   x := x;
END;

Los elementos terminales y no terminales usados en las reglas del parser escritas en PEG permiten ser capturadas anteponiendo un identificador y dos puntos delante de ellas. La ventaja de esto es que luego se pueden realizar acciones semánticas para generar el AST. Por ejemplo:

procedure
    = PROCEDURE id:ID BEGIN block:block END
    {
         return makeApply("def",
                          id,
                          makeApply("fun", block));
    }

En este caso, la regla procedure está compuesta de la palabra clave PROCEDURE, seguida de un identificador y la palabra clave BEGIN, seguida de un bloque y la palabra clave END.

Como lo que nos interesa es el nombre del procedimiento y el bloque, es lo que capturamos. Con ello luego podemos crear una acción semántica que genera un apply de Egg que define una función con el ID del procedimiento como el primer argumento y un conjunto de sentencias (que sería el bloque capturado) como el segundo argumento.