Creando nuestro propio lenguaje con ANTLR4

Esta página describe la creación de un lenguaje, ya sea de configuración o de programación, con ANTLR4.

Para mi sorpresa, el ANTLR4 tiene una documentación excelente, y hay bastantes páginas que hablan al respecto. Pero lo que falta son ejemplos reales, los ejemplos que he encontrado en Internet son ejemplos de juguete, muy simples, y hay algunas cosas excesivamente simplificadas que cuestan entender. Por eso voy a proveer un ejemplo de configuración de un Router BGP que estuve desarrollando, disponible en GitHub.

Cómo empezar

Lo obvio: leyendo la documentación oficial. El sitio www.antlr4.org dispone de amplia información sobre el tema. Pero antes de adentrarnos en un ejemplo, vamos a explorar algunos de los conceptos principales detrás del ANTLR4.

Tokens, Trees, Lexer, Parser

Lo primero es que cualquier lenguaje de programación se compone de “Tokens”, o unidades de significado. Digamos en la sentencia de asignación de valor a una variable en un lenguaje imperativo cualquiera podría ser a=4. Ahí se pueden ver 3 Tokens: la variable, a, el signo de asignación =, y el valor, 4. En un lenguaje como puede ser el Clipper Summer ’87 (se me cayó una sota por demostrar que conozco esto) sería “STORE 4 TO a”. Aquí hay 4 tokens: la palabra STORE, que indica que se trata de una operación de asignación, el 4, el valor a asignar, la palabra TO, que viene a indicar cuál va a ser la variable, y a, como antes, el nombre de tal variable.

Dentro del ANTLR4, un Lexer encuentra las tokens de las que se compone nuestro lenguaje, y se concentra específicamente en su tipo y su valor, sin preocuparse de lo que significan. Estas Tokens se alimentan al Parser, que es el que construye el llamado Syntax Tree, o árbol de sintaxis, en donde cada uno de nuestros Tokens se coloca en una posición de una estructura de árbol de acuerdo a lo que estas tokens representan dentro de nuestro lenguaje.

Pero ¿cómo representamos un lenguaje? Con un “Grammar File” o archivo de gramática. Ahí se describen las partes que componen cada sentencia válida de mi lenguaje, y cuáles son los Tokens que hay que identificar en cada una.

Ejemplo

Supongamos que yo quiero leer un archivo de configuración para un Router, bastante simple, en donde requiero una lista de placas de Red, y una lista de pares BGP con los que voy a conectarme.

Para generar mi gramática me puedo inspirar en lo que quiera, pero digamos que me baso en la gramática de una conocida línea de Routers empresariales.

Un ejemplo de configuración podría ser el que sigue:

interface {
        ip 10.60.60.1
        netmask 255.255.255.0
        description Conecta_BGP
        negotiation full_duplex
}
router {
        kind bgp
        asnumber 2000
        neighbor {
                ip 10.60.60.2
                remote_as 3000
                description Router_Internet
                type external
        }
}

Para ir pensando en cómo describiríamos esta gramática, podemos tomar enfoques “Top-down”, o “Bottom-up”. El top-down, sería que genero una lista de oraciones, después describo cada oración, y termino en los Tokens. Bottom-up es el enfoque contrario: empiezo describiendo cuáles son mis Tokens, luego cómo los integro en oraciones, y finalmente cuáles son las oraciones que componen mi lenguaje.

Para mi ejemplo yo elegí la manera “Top-Down”, o sea, a la hora de describir mi gramática, pensé en las estructuras más grandes, y luego me fui especializando.

  • En el programa hay una lista de de una o más Sentencias.
  • Cada sentencia puede ser de Interfaz o de Router.
  • La sentencia de interfaz tiene la palabra interface, le sigue una llave, luego vienen una o más opciones, y termina con otra llave.
  • Una opción de interfaz puede ser de IP, de Netmask, de descripción, de negociación.
  • La opción que especifica el IP de la interfaz tiene la palabra ip y le sigue un número IPv4.
  • El número IPv4 se compone de 4 números separados por puntos.

… y así siguiendo.

A continuación copio el archivo de gramática que sirve para interpretar la configuración enunciada más arriba.

grammar Configuration;

prog: statement+ ;
statement: (statement_interface|statement_router);
statement_interface: interface_desc OPENBRACE option_interface+ CLOSEBRACE ;
interface_desc: ‘interface’;
option_interface: (option_interface_description|option_interface_ip|option_interface_negotiation|option_interface_netmask);
option_interface_description: ‘description’ STRING;
option_interface_ip: ‘ip’ IPV4;
option_interface_netmask: ‘netmask’ IPV4;
option_interface_negotiation: ‘negotiation’ (AUTO|full_duplex|half_duplex);
statement_router: ROUTER OPENBRACE option_router+ neighbor+ CLOSEBRACE;
option_router: (option_router_kind|option_router_asnumber|option_router_log) ;
option_router_kind: ‘kind’ STRING;
option_router_asnumber: ‘asnumber’ INT;
option_router_log: ‘log-neighbor-changes’;
neighbor: NEIGHBOR neighbor_description;
neighbor_description: OPENBRACE (neighbor_ip|neighbor_type|remote_as|neighbor_description_string)+ CLOSEBRACE ;
neighbor_description_string: ‘description’ STRING;
neighbor_ip: ‘ip’ IPV4;
neighbor_type: ‘type’ (INTERNAL|EXTERNAL);
remote_as: ‘remote_as’ INT;
ROUTER: ‘router’;
NEIGHBOR: ‘neighbor’;
AUTO: ‘auto’;
full_duplex: ‘full_duplex’;
half_duplex: ‘half_duplex’;
INTERNAL: ‘internal’;
EXTERNAL: ‘external’;
IPV4: INT ‘.’ INT ‘.’ INT ‘.’ INT ;
STRING: ID_LETTER (ID_LETTER | DIGIT)*;
ID_LETTER : ‘a’..’z’|’A’..’Z’|’_’ ;
INT: DIGIT+;
DIGIT : [0-9] ;
OPENBRACE: ‘{‘;
CLOSEBRACE: ‘}’;
WS : [ \t\n\r] + -> skip;

Como podrán ver, aquí se describe exactamente lo que les quise decir antes:

Sentencia Explicación
prog: statement+; En el programa hay una lista de de una o más Sentencias.
statement: (statement_interface|statement_router); Cada sentencia puede ser de Interfaz o de Router.
statement_interface: interface_desc OPENBRACE option_interface+ CLOSEBRACE ; La sentencia de interfaz tiene la palabra interface, le sigue una llave, luego vienen una o más opciones, y termina con otra llave.
option_interface: (option_interface_description
|option_interface_ip
|option_interface_negotiation
|option_interface_netmask);
Una opción de interfaz puede ser de IP, de Netmask, de descripción, de negociación.
option_interface_ip: ‘ip’ IPV4; La opción que especifica el IP de la interfaz tiene la palabra ip y le sigue un número IPv4.
IPV4: INT ‘.’ INT ‘.’ INT ‘.’ INT ; El número IPv4 se compone de 4 números separados por puntos.

A primera vista se puede apreciar una diferencia crucial en cómo distingo los Tokens: los tokens “finales” van en mayúsculas, y los que no, que se siguen desarrollando en una explicación van en minúsculas. Las tokens Finales son las que luego formarán las hojas de nuestro árbol de Sintaxis del lenguaje.

Poniendo en marcha la maquinaria

Una vez que tenemos el archivo de sintaxis, tenemos que tener una clase o clases que vayan consumiendo el árbol de sintaxis y reaccionando ante cada entrada.

ANTLR4 genera de manera automática las clases de Lexer y Parser a aplicar. Nosotros tenemos que construir una clase que active el Parser y nos dé como resultado acciones a realizar una vez detectadas las sentencias de nuestro lenguaje que estamos buscando.

Para generar el Lexer y Parser usamos una sentencia como esta:

antlr4 Configuration.g4

Listeners, Visitors

En la lista de archivos generados, vemos además que se generaron 2 clases: Listener y Visitor. Estas representan 2 maneras distintas de recoger los valores del árbol de sintaxis y reaccionar ante sus entradas.

Para una descripción más acabada de lo que hace un Listener y un Visitor, pueden consultar la documentación, yo les voy a mostrar cómo hice en el código fuente de mi proyecto para identificar mis tokens.

En mi código usé un Listener. Este Listener tiene métodos “enter” y “exit” para cada una de las sentencias de mi lenguaje: qué quiere decir esto? Que al recorrer el árbol, se invocará el método enter al llegar a la sentencia, y el exit al dejarla.

El árbol se recorre con una notación “infija”, o sea, se recorre la hoja final, luego el nodo padre, luego otra hoja final. En el ejemplo de la instrucción de asignación que hablé más arriba, a=4, la secuencia de llamadas sería la siguiente:

  • enter_asignacion
  • enter_nombre_variable
  • exit_nombre_variable
  • enter_operador_asignacion
  • exit_operador_asignacion
  • enter_valor
  • exit_valor
  • exit_asignacion

Código Java del lector de configuración

Veamos luego cómo utilizo el Listener generado para consumir mi archivo de configuración:

	public MyConfiguration getConfiguration(String configurationFilename) throws FileNotFoundException,IOException
	{
		this.configurationFilename=configurationFilename;
		// I'll create the parser that I'll use to consume the configuration.
		File f=new File(this.configurationFilename);
		InputStream inputStream=new FileInputStream(f);
		CharStream stream=CharStreams.fromStream(inputStream);
		ConfigurationLexer lexer=new ConfigurationLexer(stream);
		CommonTokenStream tokens=new CommonTokenStream(lexer);
		ConfigurationParser parser=new ConfigurationParser(tokens);
		// I get the interfaces present with a list.
		List<BgpInterface> interfaces=new LinkedList<BgpInterface>();
		// For the BGP peers, I need a map, because I need to retrieve them using the configured IP.
		Map<String,BgpNeighbor> neighbors=new HashMap<String,BgpNeighbor>();
		parser.addParseListener(new ConfigurationBaseListener()
				{
			private String ip;
			private String netmask;
			private String neighbor_description;
			private String neighbor_ip;
			private int remote_as;
			private String router_kind;
			private String my_as;
			private BgpNeighborType neighbor_type;
			@Override
			public void exitStatement_interface(ConfigurationParser.Statement_interfaceContext ctx)
			{
				BgpInterface iface=new BgpInterface();
				iface.setIp(ip);
				iface.setNetmask(netmask);
				interfaces.add(iface);
			}
			public void exitOption_interface_ip(ConfigurationParser.Option_interface_ipContext ctx)
			{
				ip=ctx.IPV4().getText();
			}
			public void exitOption_interface_netmask(ConfigurationParser.Option_interface_netmaskContext ctx)
			{
				netmask=ctx.IPV4().getText();
			}
				}
		parser.prog();
		configuration.setInterfaces(interfaces);
		return configuration;
	}

Vamos por partes.

Instrucción Qué hace
File f=new File(this.configurationFilename); Abre el archivo de configuración indicado previamente.
InputStream inputStream=new FileInputStream(f); Obtengo el Stream de entrada para leer el archivo.
CharStream stream=CharStreams.fromStream(inputStream); Genero un Stream de caracteres para beneficio del Lexer
ConfigurationLexer lexer=new ConfigurationLexer(stream); Creo un Lexer
CommonTokenStream tokens=new CommonTokenStream(lexer); Uso el Lexer para generar un Stream de Tokens
ConfigurationParser parser=new ConfigurationParser(tokens); Invoco el Parser
List interfaces=new LinkedList(); Creo una estructura de datos para guardar los datos de mi interfaz
parser.addParseListener(new ConfigurationBaseListener() Genero un Listener que heredará de la clase BaseListener generada por ANTLR4 para consumir el árbol de sintaxis generado por el Parser
parser.prog(); Arranco el Parser, el cual a su vez va invocando los métodos del Listener que declaré
configuration.setInterfaces(interfaces); Grabo las interfaces leídas de la configuración

Ahora veamos un poco más el Listener.

Primero de todo, hereda de una clase BaseListener, que provee una implementación default en donde simplemente pasa de largo.

En la clase anónima que yo genero, que hereda de BaseListener, me detengo ante los eventos que me interesan:

  • Cuando salgo de leer la IP
  • Cuando salgo de leer la descripción
  • Cuando salgo de la definición de la interfaz

Al salir de la opción de leer la IP, recibo un Contexto, que me permite consultar el árbol de sintaxis en el punto en el que estoy de su recorrido. Los nombres del contexto tienen los nombres de los Tokens Finales que yo designé anteriormente.

Voy consumiendo el valor de cada una de las opciones de la interfaz, y cuando salgo de leer la descripción de la interfaz, o sea, en el punto de la notación infija descripta antes, que dejo el nodo Padre del árbol, guardo todos esos datos que recogí en la estructura de datos que creé para el propósito.

El resultado de todo esto, es que ahora tengo una lista de Interfaces con los que mi Router se conecta, y cada una de ellas está descripta con su IP, Netmask, descripción y opciones de negociación.

Código

El código completo se puede encontrar en GitHub, como parte del proyecto BGPSec – para construir un Router que implementa la RFC 8205 y siguientes.