Parser LL

Os parsers LL usam um algoritmo iterativo sendo que a escolha da produção a usar encontra-se numa tabela auxiliar de decisão. A análise das entradas é efectuada da esquerda para a direita (Left to right) e constrói uma derivação mais à esquerda (Leftmost derivation). Convém igualmente referir que um parser LL é um analisador sintáctico descendente (top-down) pois tenta deduzir as produções da gramática a partir do axioma da mesma. Mais, as gramáticas que podem ser analisadas sintacticamente por estes parsers são qualificadas de gramáticas LL.

Por vezes é usado o termo LL(k), onde k é o número de tokens (em Português, "lexemas"^[1]). Estes k lexemas correspondem aos primeiros k símbolos actuais da frase de entrada ainda não consumidos e são usados para tomar decisões na análise.

O analisador sintáctico LL tem pelo menos de receber os seguintes argumentos de entrada:

• um buffer contendo a frase de entrada, sendo esta uma sequência de caracteres de uma dada linguagem ;
• uma stack servindo de apoio ao algoritmo que pode albergar termos terminais, não-terminais, assim como o símbolo $ que representa o fim da frase, indicando que não existem mais símbolos a processar ;
• uma tabela construída de acordo com a gramática onde são mapeadas as regras a usar para o reconhecimento.

De facto, o analisador realiza três tipos de passos em função do conteúdo do topo da stack:

se o topo da stack for um símbolo não-terminal

Com base no valor desse símbolo e do símbolo actual da frase de entrada, verificar na tabela de análise qual a regra da gramática que deve ser aplicada. O número da regra é escrita na saída de dados. Caso não haja regra correspondente na tabela, o algoritmo acaba com insucesso.

se o topo da stack for um símbolo terminal

Comprar esse símbolo com o símbolo actual da frase de entrada. Caso sejam iguais, ambos são emparelhados e removidos, caso contrário, o algoritmo acaba com insucesso.

se o topo da stack for o símbolo $

Se a frase de entrada não conter mais símbolos, o algoritmo de análise acaba com sucesso.

Este três passos são repetidos até o algoritmo parar.

Note-se que a decisão da escolha da regra a usar está fora do algoritmo, sendo que é tomada através do conteúdo da tabela e não por um mecanismo dentro do próprio algoritmo.

Note-se finalmente que para uma gramática G, se existe um analisador sintáctico respeitando todas as características acima enunciadas e que consiga analisar frases construídas respeitando G sem backtracking, então G é uma gramática LL(k).

Gramáticas LL

As gramáticas independentes de contexto (GIC) podem ser transformadas em gramáticas que não possuem recursividade à esquerda. No entanto a remoção da recursividade à esquerda pode nem sempre resultar numa gramática LL. De facto, estas são um subconjunto das GIC.

As gramáticas LL excluem todas as gramáticas ambíguas, assim como todas as gramáticas com recursividade à esquerda. Desta forma evita-se entrar em produções ou análises que conduzem ao ciclo infinito.

Parser Recursivo Descendente

Os analisadores recursivos descendentes usam um algoritmo recursivo. Ao contrário do parser LL, a escolha da regra gramatical a usar está embebida no algoritmo, não sendo necessário recorrer a uma tabela de decisão. De facto, os recursivos descendentes são construídos por #N funções que derivam cada símbolo, onde N é o conjunto de símbolos não-terminais e # as respectivas cardinalidades.

Cada uma dessas funções (ou sub-rotinas) recursivas implementa uma regra de produção presente na gramática. Dado que cada sub-rotina fica associada a um símbolo não-terminal da gramática, a estrutura do parser/algoritmo é parecida com a gramática em si.

Existem dois sub-tipos de analisadores sintácticos recursivos descendentes. O primeiro será mais interessante e adaptado ao uso comum, sendo que o segundo apenas consta para apurar exaustivamente este conceito.

O analisador sintáctico 'preditivo'

é um analisador sintáctico recursivo que não requer backtracking, sendo apenas possível fazer parsing de gramáticas LL(k), respeitando a sua definição anteriormente proposta. Mais, um parser `preditivo' corre num tempo linear, o que significa que a sua complexidade algorítmica é reduzida, levando este algoritmo a ser bastante eficiente.

O analisador sintáctico descendente com cópia

determina quais as produções a usar por tentativa de erro (de estilo brute force). Isto é, o algoritmo acaba ao consumir a entrada toda ou ao esgotar todas as possibilidades. Note-se que este parser não é limitado a gramáticas LL(k) mas caso a gramática seja dessa classe, haverá sempre sucesso. Note-se ainda que este tipo de parser tornou-se obsoleto devido à pouca eficiência e alto consumo de recursos que infere ao sistema.

---

[1] ↑ lexema -- nome masculino
(LINGUÍSTICA) unidade linguística que combina a forma (gráfica ou fonética) e o significado, o qual não é divisível em unidades menores; unidade lexical
(in Dicionário Porto Editora).