mork: parsing made easy

Para pequenos processamentos, tanto em tempo de execução como em quantidade de código necessário para os realizar, estas técnicas são feitas de forma tradicional: processando byte a byte e tomando acções com base num dado estado, por exemplo.

Para tarefas mais complexas existem técnicas eficientes que são quase impossíveis de manter manualmente: geram uma grande quantidade de estados e dados internos que processa eficientemente os dados em causa. Aqui entram as ferramentas de geração de código, vulgarmente denominadas de compiler-compiler tools.

lex & yacc

O lex é um scanner de texto. Reconhece sequências regulares de texto e associa-lhes acções.
O yacc é um parser. Define uma gramática através de produções e símbolos terminais. O seu input é validado por essa gramática e a cada sequência de símbolos que defina uma dada produção é associada também uma acção.
O resultado (output) destas ferramentas é código em C tal como as acções definidas.

Estas ferramentas são clássicas no mundo de parsing: vêm do mundo Unix, existem há cerca de 30 anos e foram usadas para construir toda a infraestrutura de compilação em Unix aquando da sua criação. Desde então têm sido fortemente usadas para vários tipos de tarefas, em centenas dos mais variados projectos de software e são a grande referência em compilação. Quando aparece uma nova linguagem existe logo um esforço em portar equivalentes de lex e yacc para essa nova linguagem. No caso do java, temos o cup e o jlex, respectivamente.

Os dois interligam-se do seguinte modo: o lex lê o input (código fonte de C, por exemplo) e normalmente associa-lhes tokens (números). O yacc recebe esses tokens e aplica-lhes as regras gramaticais.
Exemplo:

"int value;" -> lex, produz: TYPE ID SEMICOLON
TYPE ID SEMICOLON -> yacc, insere ID na symboltable

Como disse atrás, esta é a abordagem clássica. Tem vantagens e desvantagens. Pessoalmente nunca gostei muito da abordagem, especialmente da do yacc. Entretanto foram sendo escritas mais ferramentas, alternativas, com outras estratégias e técnicas...

Entre o mork...

[nome da secção]
chave = valor
chave2 = valor2

[outra seccao]
key = val

Uma implementação em java que fiz no passado tem cerca de 250 linhas de código. Em mork temos que criar as três entidades referidas atrás, o que se faz em 4 ficheiros com 67 linhas.

Gramática ("seccao.grm")

[PARSER]

file ::= section*; 
section ::= header assign* ; 
header ::= "[" name "]" ; 
assign ::= name "=" name ; 

[SCANNER]
        white = S;

S ::= ( ' ' | '\t' | '\n' | '\f' | '\r' )+ ;
name ::= ('a' .. 'z' | 'A' .. 'Z' | '0' .. '9' )+ ; 

Como se vê, trata-se de uma gramática ao estilo EBNF. Aqui dizemos que:

1. um ficheiro são zero ou mais secções
2. uma secção é um cabeçalho e zero ou mais atribuições
3. uma atribuição é a sequência "nome = nome" em que nome tem que ser definido no scanner
4. no scanner através de uma sintaxe semelhante (mas não igual!) às expressões regulares, definimos que tipo caracteres constitui um nome

mapper seccao.Mapper;

grm = "seccao.grm";

import seccao: Main, Assign; 
import java.lang: String;
    
file => Main.file; 
section => Main.section; 
header => String; 
assign => Assign; 
name => [text]; 

Este ficheiro faz a ponte entre a gramática e o java. Isto permite-nos, logo à partida, usar a mesma gramática associada a acções diferentes, ou seja, com o mesmo ficheiro, podemos ter vários programas diferentes a operar no mesmo tipo de input. Exemplo: um compilador de C, um programa tipo "indent" e um outro para extrair os protótipos das funções. Aqui tinhamos a mesma gramática de C e três mapeamentos diferentes.

Quanto ao ficheiro:

mapper seccao.Mapper;

A classe java que vai ser produzida pela ferramenta mork. A actual implementação de mork é em si um compilador também. A partir da gramática e do mapeamento produz directamente o java bytecode, i.e. neste caso a classe Mapper.class no package "seccao"

grm = "seccao.grm";

A gramática a carregar, isto permite carregar a mesma gramática associada a código diferente, como já referido

import seccao: Main, Assign; 

As classes java que vão ser referenciadas neste ficheiro. A sintaxe é diferente dos imports de java, mas a ideia é a mesma. Neste caso faz-se: "import package: class1, class2, ...; " e todas as classes precisam de ser explicitadas

file => Main.file; 

Onde o mapeamento é feito. A sintaxe é "simbolo-da-gramatica => java-method | java-class | java-attribute". Os símbolos a mapear vêm da gramática, tanto da parte do parser como da parte do scanner. Nem todos os símbolos têm que ser mapeados, se não foram mapeados, são simplesmente ignorados na parte java, mas continuam a ser validados na gramática.
Cada símbolo pode ser mapeado:

1. num método. Exemplo: file => Main.file; neste caso vai ser invocado o método Main.file() com os argumentos deste símbolo, sempre que este seja encontrado
2. numa classe (objecto). Exemplo: assign => Assign; aqui vai ser invocado em java new Assign() com os argumentos do símbolo
3. num atributo. Semelhante a (1), mas é atribuído a esse atributo o valor do símbolo
4. em operadores internos. O mais interessante (e necessário) é o [text]. O [text] é do tipo java.lang.String e representa todo o texto do input que foi consumido por este símbolo.

Esta é a parte mais difícil (mas não muito ;-) ), saber quais os argumentos que cada construção java recebe. Mas a ideia até é simples. Cada símbolo é composto por outros símbolos ou por expressões tipo regulares. O argumento de um símbolo é os símbolos que o compõe. O tipo de cada símbolo é aquilo que ele retorna... Isto é mais fácil do que parece 8-) . Exemplo: x ::= y z; neste caso x vai receber dois argumentos, o tipo retornado por y e o tipo retornado por z. Se tiver mais tarde y ::= [text] e z ::= MyObject; então teria que ter um constructor ou método para x do com os argumentos (String y, MyObject z). Eventualmente tem que haver sempre um símbolo a mapear em [text]. Mas ver o código java para mais esclarecimentos.

Java code
Assign.java:

package seccao;

public class Assign {
        String key, value;
        public Assign(String a, String b) {
                key = a;
                value = b;
        }
        public String toString() {
                return key+"="+value;
        }
}

Main.java:

package seccao;

import de.mlhartme.mork.mapping.Mapper;

public class Main {
    public static void main(String[] args) {
                Mapper m = new Mapper("seccao.Mapper"); 
                Object[] t = m.run(args[0]); 
        }

        public static String file(String []sec) {
                int n=0; 
                if (sec != null) n =sec.length;
                D("this file have "+n+" sections:"); 
                for (int i=0; i<n; i++)
                        D(" "+sec[i]); 
                return "file"; 
        }

        public static String section(String header, Assign [] assign) {
                D("got section: "+header); 
                if (assign != null) 
                        for (int i=0, n=assign.length; i<n; i++)
                                D("  "+assign[i]); 
                return header; 
        }

        public static void D(String z) {
                System.out.println(z); 
        }
}

Vejamos como é que este código interage com a gramática.

• um file são zero ou mais section, por isso recebe um array do tipo que section retorna.
• section é um header seguido de zero ou mais assign
• um assign recebe dois name, mas os name são [text], i.e. java.lang.String, entao Assign tem que receber duas Stringcomo argumento
• header recebe um name que é String, então preciso de ter um objecto que aceite String como argumento do constructor. A própria java.lang.String aceita uma String como argumento, por isso pode ser usada (isto está ao nível do mapeamento)
• agora que já sabemos os tipos de header e assign, conseguimos escrever o cabeçalho de section: (String header, Assign []assign)
• o que section retorna é que file recebe em array
  

$ javac -d -classpath .:mork.jar *.java
$ mork -d seccao Mapper.map
$ java -classpath .:mork.jar seccao.Main ficheiro

Posso fornecer mais exemplos ou esclarecimentos a pedido (ver mail no fim).

Conclusões