❧ Parsing Descendente Recursivo ❧

O algoritmo descendente recursivo10.3

O parser descendente recursivo é a forma mais direta de transformar a ideia top-down em um programa. A ideia central é mapear diretamente a gramática para funções. O princípio do algoritmo é:

A rotina match é responsável por avançar a leitura e lidar com falhas. Ela compara o símbolo que a gramática exige naquele momento com o símbolo atual da entrada.

void match(char esperado) {
    if (entrada[ponteiro] == esperado) {
        ponteiro++;
    } else {
        erro_sintatico();
    }
}

Se o token bater, o ponteiro avança. Se vier um token inesperado (ou a entrada acabar antes da hora), o match levanta um erro sintático. Na aula anterior, vimos que a recursão à esquerda é inimiga de parsers descendentes. Agora podemos ver o motivo exato disso em código. Se tivéssemos a produção $E \to E + T$, a implementação direta seria:

void E() {
    E();           // Chamada recursiva infinita sem consumir entrada!
    match('+');
    T();
}

Ao executar E(), a função chama E() novamente na primeira linha. Isso causa um stack overflow antes que qualquer caractere seja lido ou testado. É por isso que eliminamos a recursão à esquerda antes de implementar esse algoritmo.

Exemplo de execução: Entrada Válida10.3.1

Vamos acompanhar passo a passo a leitura de uma entrada válida.

Considere a gramática já sem recursão à esquerda:

$$ G = (N, T, P, S) $$

com os elementos abaixo:

$$ \begin{split} N &= \{E, E', T\} \\ T &= \{i, +\} \\ S &= E \end{split} \hspace{1cm} \begin{split} P = E &\to T\ E' \\ E' &\to +\ T\ E' \mid \epsilon \\ T &\to i \end{split} $$

e a cadeia: $i + i$. Como as funções reconhecem essa entrada passo a passo? As funções correspondentes na linguagem C seriam:

void E() {
    T();
    E_linha();
}

void E_linha() {
    if (entrada[ponteiro] == '+') {
        match('+');
        T();
        E_linha();
    }
}

void T() {
    match('i');
}

Podemos representar a execução como uma pilha de chamadas que espelha exatamente a derivação top-down:

$$ \begin{split} E &\Rightarrow T\ E' \\ &\Rightarrow i\ E' \\ &\Rightarrow i + T\ E' \\ &\Rightarrow i + i\ E' \\ &\Rightarrow i + i \end{split} $$

main
└── E()
    ├── T()
    │   └── match('i')
    └── E_linha()
        ├── match('+')
        ├── T()
        │   └── match('i')
        └── E_linha() -> retorna (vazio)

Observe como a função E_linha() no último nível percebe que não há mais o símbolo + na entrada. Como ela possui a regra $\epsilon$, ela apenas retorna, concluindo o reconhecimento com sucesso.

Exemplo de execução: Entrada Inválida10.3.2

O que acontece quando o programador escreve código inválido? Utilizando a mesma gramática anterior, imagine a entrada incompleta: $i +$. Onde exatamente o parser percebe a falha?

O processo ocorre normalmente até faltar o segundo i.

main
└── E()
    ├── T()
    │   └── match('i')     // Avança o ponteiro, sobra "+"
    └── E_linha()           
        ├── match('+')     // Avança o ponteiro, entrada acaba
        ├── T()
        │   └── match('i') // ERRO SINTÁTICO!

A chamada de E_linha() reconhece o +, mas obrigatoriamente tem que chamar T() em seguida. A função T() invoca match('i'). Como a entrada já terminou e não há mais o token i, o match dispara a falha sintática. É assim que o parser garante que a cadeia obedeça a uma estrutura completa.

Próximos Passos10.4

Agora que a base conceitual está clara, o próximo passo é aplicar esse algoritmo à nossa linguagem. No capítulo seguinte, Parser Descendente Recursivo para Expressões do Slang, vamos pegar essa mesma lógica e transformá-la em código dentro do compilador.