Construção de gramáticas

A construção de gramáticas pode ser considerada uma forma de programação simbólica, em que existem símbolos que são equivalentes a sequências (que façam sentido) de outros símbolos (ou mesmo dos próprios).

Os símbolos utilizados dividem-se em símbolos terminais e não terminais.

Os símbolos terminais (ou tokens) são predefinidos, ou definidos fora da gramática; e os símbolos não terminais são definidos por produções (regras) da gramática (sendo estas transformações equivalentes de uma sequência de símbolos noutra sequência).

No fim, todos os símbolos não terminais, com mais ou menos transformações, devem poder ser expressos em símbolos terminais.

Uma gramática é construída especificando as regras ou produções dos elementos gramaticais.

grammar SetLang;          // a grammar example
stat: set set;            // stat is a sequence of two 'set'
set: '{' elem* '}'        // set is zero or more 'elem' inside '{' '}'
elem: ID | NUM;
ID: [a-z]+;
NUM: [0-9]+;

Sendo a sua construção uma forma de programação, podemos beneficiar da identificação e reutilização de padrões comuns de resolução de problemas.

Surpreendentemente, o número de padrões base é relativamente baixo:

1. Sequência: sequência de elementos;

2. Optativo: aplicação optativa do elemento (zero ou uma ocorrência);

3. Repetitivo: aplicação repetida do elemento (zero ou mais, uma ou mais);

4. Alternativa: escolha entre diferentes alternativas (como por exemplo, diferentes tipos de instruções);

5. Recursão: definição direta ou indiretamente recursiva de um elemento (por exemplo, instrução condicional é uma instrução que seleciona para execução outras instruções);

É de notar que a recursão e a iteração são alternativas entre si. Admitindo a existência da sequência vazia, os padrões optativo e repetitivo são implementáveis com recursão.

No entanto, como em programação em geral, por vezes é mais adequado expressar recursão, e outras iteração.

Considere o seguinte programa em Java:

import static java.lang.System.*;

public class PrimeList {
    public static void main(String[] args){
        if(args.length != 1){
            out.println("Usage: PrimeList -ea <n>");
            exit(1);
        }
        int n=0;
        try {
            n = Integer.parseInt(args[0]);
        } catch (NumberFormatException e){
            out.println("ERROR: invalid argument \"+args[0]+"\");
            exit(1);
        }
        for(int i = 2; i <= n; i++){
            if(isPrime(i))
                out.println(i);
        }
    }
    
    public static boolean isPrime(int n){
        assert n > 1; // precondition
        boolean result = (n==2 || n%2 != 0);
        for(int i = 3; result && (i*i <= n); i += 2)
            result = (n%i != 0);
        return result.
    }
}

Mesmo na ausência de uma gramática definida explicitamente, podemos neste programa inferir todos os padrões atrás referidos:

1. Sequência: a instrução atribuição de valor é definida como sendo um identificador, seguido do carácter =, seguido de uma expressão.

2. Optativo: a instrução condicional pode ter, ou não, a selecção de código para a condição falsa.

3. Repetitivo: (1) uma classe é uma repetição de membros; (2) um algoritmo é uma repetição de comandos.

4. Alternativa: diferentes instruções podem ser utilizadas onde uma instrução é esperada.

5. Recursão: a instrução composta é definida como sendo uma sequência de instruções delimitada por chavetas; qualquer uma dessas instruções pode ser também uma instrução composta.