Analisadores sintáticos

Um analisador sintático para uma gramática $G$ é um programa que aceita como entrada uma sentença (uma lista de símbolos $\alpha$) e constrói para a sentença sua árvore gramatical (ou equivalentemente uma seqüência de derivação) ou, caso a sentença não pertença à linguagem descrita por $G$, uma indicação de erro.

Duas técnicas básicas para a contrução de analisadores sintáticos são a construção ascendente ou a construção descendente. Na contrução ascendente (bottom-up), o analisador sintático varre a sentença buscando aplicar produções que permitam substituir seqüências de símbolos da sentença pelo lado esquerdo das produções, até alcançar como único símbolo restante o símbolo sentencial.

O Algoritmo 3.3 ilustra a estratégia de reconhecimento de sentença baseado em construção ascendente da árvore sintática. Esse algoritmo recebe como entrada uma representação da gramática $G$ e a lista $\alpha$ de símbolos terminais que compõem a sentença. A saída é uma indicação se a sentença pertence (true) ou não (false) à gramática $G$. Para a descrição desse algoritmo, as seguintes funções são definidas:

$\Sigma$, que recebe uma gramática $G$ como argumento e retorna o seu símbolo sentencial; e

MATCH($G,\alpha$) retorna uma nova lista de símbolos gerada a partir da aplicação de alguma regra de G à sentença $\alpha$. Para tanto, esse procedimento analisa se para a sentença $\alpha$, composta pela seqüência de símbolos $\beta x_1 x_2 \dots x_n \mu$ (onde eventualmente $\beta$ e $\mu$ podem ser a string vazia), há na gramática alguma regra aplicável $\chi \rightarrow x_1 x_2 \dots x_n$. Se houver, o valor de retorno do procedimento é a lista $\beta \chi \mu$; caso contrário, o procedimento retorna uma lista vazia.

Esse algoritmo apresenta duas condições de término possíveis: a primeira quando a sentença pode ser reduzida ao símbolo sentencial da gramática (condição de sucesso) e a segunda quando a sentença não está reduzida ao símbolo sentencial e não há mais regras aplicáveis à sentença (condição de rejeição).

Na construção descendente (top-down), o objetivo é iniciar a análise com uma lista que contém inicialmente apenas o símbolo sentencial; a partir da análise dos símbolos presentes na sentença, busca-se aplicar regras que permitam expandir os símbolos na lista até alcançar a sentença desejada.

Na construção descendente, o objetivo é obter uma derivação mais à esquerda para uma sentença. Em termos de árvores gramaticais, a construção descendente busca a construção de uma árvore a partir da raiz usando pré-ordem para definir o próximo símbolo não-terminal que deve ser considerado para análise e expansão.

Pela forma como a técnica de construção descendente opera, ela não pode ser aplicada a gramáticas com produções recursivas à esquerda, ou seja, que contenham regras da forma

$$A \rightarrow A \beta$$

A limitação é que a análise descendente de tal tipo de produção poderia levar a uma recursão infinita na análise pela tentativa de expandir sempre a mesma regra sem consumir símbolo algum da entrada.

É possível transformar uma produção recursiva à esquerda em uma recursiva à direita que descreve as mesmas sentenças através da seguinte técnica. Sejam $\beta$ e $\delta$ duas seqüências de símbolos que não sejam iniciadas pelo símbolo não-terminal $A$ e sejam as produções para $A$:

$$A \rightarrow A \; \beta$$

$$A \rightarrow \delta$$

Através da introdução de um novo símbolo não-terminal $A'$, as mesmas sentenças descritas pelas produções acima podem ser descritas pelas produções recursivas à direita:

$$A \rightarrow \delta \; A'$$

$$A' \rightarrow \beta \; A'$$

$$A' \rightarrow \varepsilon$$

Nos dois casos, as sentenças são formadas por uma ocorrência de $\delta$ no início seguida por zero ou mais ocorrências de $\beta$.

Os primeiros compiladores usavam essencialmente dois tipos de analisadores sintáticos. Analisadores baseados em precedência de operadores utilizam a técnica de construção ascendente combinada com informação sobre a precedência e associatividade de operadores da linguagem para guiar suas ações, sendo adequados à análise de expressões aritméticas. Analisadores do tipo descendentes recursivos implementam a técnica de construção descendente através de um conjunto de rotinas mutualmente recursivas para realizar a análise, sendo normalmente utilizados para outros comandos que não expressões aritméticas.