Reconhecimento de sentenças

O reconhecimento de sentenças, ou parsing, é o procedimento que verifica se uma dada sentença pertence à linguagem gerada por uma gramática. Este procedimento é essencial para um compilador, que deve reconhecer e validar expressões de diversos tipos -- declarações, expressões aritméticas, construções de controle de execução -- no processo de construção de um código executável equivalente à expressão reconhecida.

Considere uma gramática que define um subconjunto de expressões aritméticas aceitas por alguma linguagem de programação, apresentada na Figura 3.7.

Figura: Gramática para reconhecimento de expressões.

A primeira regra dessa gramática determina que a soma de uma expressão e um termo é também uma expressão. Pela segunda regra, um único termo é também uma expressão. Pela terceira regra, o produto de um termo e um fator é um termo válido. A quarta regra estabelece que um único fator é também um termo válido. Pela quinta regra, uma expressão entre parênteses é um fator. Finalmente, a sexta regra estabelece que um identificador é um fator.

Nessa gramática, $id$ é um símbolo terminal, ou seja, um token, assim como os símbolos $+$, $\times$, ( e ). Através de uma gramática regular seria possível determinar o que é um identificador para a linguagem; por exemplo,

$$id \rightarrow L \; L*$$

$$L \rightarrow x \vert y \vert z$$

Considere o procedimento para o reconhecimento da expressão $(x+y)z$. No procedimento de análise léxica, a expressão sob análise seria traduzida para $(id+id)id$. O procedimento de análise sintática deve então aplicar as regras da gramática para verificar se a sentença é válida ou não. Se é possível derivar a sentença a partir do símbolo sentencial (no caso, $E$), então a sentença é reconhecida. Caso contrário, a sentença é inválida e deve ser rejeitada.

Usando inicialmente um procedimento informal para esse reconhecimento, é possível estabelecer que a sentença $(id+id)id$ pode ser obtida a partir de $(F+F)F$ pela aplicação da sexta regra, ou seja,

$$(F+F)F \overset{+}{\Longrightarrow} (id+id)id$$

Pela aplicação da quarta regra, obtém-se que a expressão pode ainda ser reduzida a $(T+T)F$, ou seja,

$$(T+T)F \overset{+}\Rightarrow (F+F)F$$

Pela segunda regra,

$$(E+T) F \Rightarrow (T+T) F$$

e pela primeira regra,

$$(E) F \Rightarrow (E+T)F$$

Finalmente, pela quinta regra, obtém-se

$$F F \Rightarrow (E) F$$

Nesse momento, não há mais nenhuma regra que possa ser aplicada para obter a redução da sentença até o símbolo sentencial. Assim, o analisador indicaria que a sentença $(x+y)z$ não faz parte da linguagem descrita pela gramática especificada.

Por outro lado, para a sentença $(x+y)\times z$, o analisador reconheceria $(id+id)\times id$ como uma sentença válida:

$$E \Rightarrow T$$

$$\Rightarrow T \times F$$

$$\Rightarrow F \times F$$

$$\Rightarrow (E) \times F$$

$$\Rightarrow (E+T) \times F$$

$$\Rightarrow (T+T) \times F$$

$$\Rightarrow (T+F) \times F$$

$$\Rightarrow (F+F) \times F$$

$$\Rightarrow (F+F) \times id$$

$$\Rightarrow (F+id) \times id$$

$$\Rightarrow (id+id) \times id$$

Nesse caso, a sentença é reconhecida como válida pois foi possível derivar a sentença a partir do símbolo sentencial usando a aplicação das regras 2, 3, 4, 5, 1, 2, 4, 4, 6, 6, e 6. Essa seqüência de regras aplicadas na derivação da sentença sob análise é conhecida como a seqüência de reconhecimento da sentença.