Ejemplo 540. Parser de Json #

Enunciado #

Requisitos #

En este apartado se hará un parser de JSON. Se mostrará así que las técnicas vistas en esta asignatura no son específicas para hacer compiladores, sino que pueden ser aplicadas para procesar cualquier tipo de entrada estructurada.

El ejercicio se dividirá en tres tareas:

1. Hacer la gramática libre de contexto con ANTLR4. Deberá detectar entradas que no sean JSON válido.
2. Hacer la gramática abstracta que describa los nodos de los AST necesarios para modelar cualquier JSON en forma de árbol.
3. Añadir las acciones a la gramática del punto 1 para que se forme un árbol mediante los nodos del punto 2.

Resumen de JSON #

Un fichero en JSON está formado por uno de los siguientes values:

Nótese que, aunque lo habitual es que el JSON sea un objeto o un array, la especificación permite que sea cualquier valor. Por ejemplo, los siguientes son ejemplos válidos de JSON:

true

"hello"

Los arrays tienen la siguiente forma:

Los object, la estructura más común, tienen la siguiente forma:

Finalmente, se muestran alguno ejemplos válidos de JSON:

{
    "id" : 25,
    "ciudades" : [ "Santander", "Oviedo"],
    "updated" : false,
    "reference" : null,
    "marker" : { "north" : "43.3", "west" : "5.65" }
}

{
    "menu" : {
        "name" : "File",
        "menuitems" : [
           {  “text" : "New", "onclick" : "Create()" },
           {  “text" : "Close", "onclick" : "Close()" }
        ]
    }
}

[ "Santander", "Oviedo"]

Para más detalle, aunque no será necesario para este ejercicio, se puede consultar la especificación de JSON.

Soluciones #

Gramática en ANTLR #

grammar Grammar;
import Lexicon;

start: valor EOF
	;

valor: STRING
	| NUMBER
	| 'true'
	| 'false'
	| 'null'
	| '[' valores ']'
	| '{' atributos '}'
	;

valores: (valor (',' valor)*)?
	;

atributos: (atributo (',' atributo)*)?
	;

atributo: STRING ':' valor
	;

lexer grammar Lexicon;

NUMBER: [0-9]+;
STRING: '"' (~[\r\n"])* '"';

WHITESPACE: [ \t\r\n]+ -> skip;

Nótese cómo la gramática ha ido formándose siguiendo las construcciones para la creación de gramáticas:

• start, valor y atributo son secuencias.
• valores y atributos son listas. Concretamente, siguen el patrón de listas de 0+cs.

Cabe destacar, de nuevo, la importancia de crear gramáticas limpias siguiendo las construcciones. Nuestro cerebro procesará más fácil una nueva gramática si encuentra estructuras que le son conocidas. En el caso anterior, dado que las listas son siempre iguales, serán ignoradas y se podrá centrar en las secuencias, que son más sencillas. Eso hará más fácil de entender cualquier gramática.

Gramática Abstracta #

Ahora, hay que determinar los nodos mínimos qué serán necesarios para modelar cualquier entrada válida de JSON.

Estos nodos serán:

numero: valor -> string ;
cadena: valor -> string ;
true: valor -> ;
false: valor -> ;
null: valor -> ;
array: valor ->  valor* ;
objeto: valor -> atributo*;

atributo -> string valor;

Nótese que, a diferencia de las descripciones abstractas para lenguajes de programación, aquí realmente no hace falta una clase raíz (program). El parser, en el caso de JSON, deberá devolver un valor y esté será aquel que corresponda con lo que se encuentre a la entrada (un array, un object, ...). Dependiendo de la entrada, cualquiera de los nodos valor puede ser el nodo raíz del árbol.

Parser Finalizado #

Queda ahora añadir las acciones al fichero de ANTLR para que se cree el árbol. El fichero completo quedaría así:

grammar Grammar;

import Lexicon;

@parser::header {
    import ast.*;
}

start returns[Valor ast]
	: valor EOF { $ast = $valor.ast; }
	;

valor returns[Valor ast]
	: STRING			{ $ast = new Cadena($STRING.text); }
	| NUMBER			{ $ast = new Numero($NUMBER.text); }
	| 'true'			{ $ast = new True(); }
	| 'false'			{ $ast = new False(); }
	| 'null'			{ $ast = new Null(); }
	| '[' valores ']'	{ $ast = new Array($valores.list); }
	| '{' atributos '}'	{ $ast = new Objeto($atributos.list); }
	;

valores returns[List<Valor> list = new ArrayList<Valor>()]
	: (valor { $list.add($valor.ast); } (',' valor { $list.add($valor.ast); })*)?
	;

atributos returns[List<Atributo> list = new ArrayList<Atributo>()]
	: (atributo { $list.add($atributo.ast); } (',' atributo { $list.add($atributo.ast); })*)?
	;

atributo returns[Atributo ast]
	: STRING ':' valor { $ast = new Atributo($STRING.text, $valor.ast); }
	;

De nuevo, si se han seguido las construcciones, el añadir las acciones será más sencillo.

• Las listas se implementa siempre igual, ya que cada patrón de lista tiene su patrón de implementación correspondiente.
• Las secuencias son siempre un new.