Análise sintática (computação)

Exemplo da análise sintática de uma expressão matemática. O resultado é uma árvore da expressão

Em ciência da computação e linguística, análise sintática (também conhecida pelo termo em inglês parsing) é o processo de analisar uma sequência de entrada (lida de um arquivo de computador ou do teclado, por exemplo) para determinar sua estrutura gramatical segundo uma determinada gramática formal. Essa análise faz parte de um compilador, junto com a análise léxica e análise semântica.

A análise sintática transforma um texto na entrada em uma estrutura de dados, em geral uma árvore, o que é conveniente para processamento posterior e captura a hierarquia implícita desta entrada. Através da análise léxica é obtido um grupo de tokens, para que o analisador sintático use um conjunto de regras para construir uma árvore sintática da estrutura.

Em termos práticos, por exemplo, pode também ser usada para decompor um texto em unidades estruturais para serem organizadas dentro de um bloco.

A vasta maioria dos analisadores sintáticos implementados em compiladores aceitam alguma linguagem livre de contexto para fazer a análise. Estes analisadores podem ser de vários tipos, como o LL, LR e SLR.

Tipos de analisadores sintáticos

A tarefa do analisador sintático (um algoritmo, programa de computador ou componente de software que se preze a realizar uma análise sintática) é essencialmente a de determinar se uma entrada de dados pode ser derivada de um símbolo inicial com as regras de uma gramática formal. Isso pode ser feito de duas maneiras:

• Descendente (top-down) - um analisador pode iniciar com o símbolo inicial e tentar transformá-lo na entrada de dados. Intuitivamente, o analisador inicia dos maiores elementos e os quebra em elementos menores. Exemplo: analisador sintático LL.
• Ascendente (bottom-up) - um analisador pode iniciar com um entrada de dados e tentar reescrevê-la até o símbolo inicial. Intuitivamente, o analisador tentar localizar os elementos mais básicos, e então elementos maiores que contêm os elementos mais básicos, e assim por diante. Exemplo: analisador sintático LR.

Determinismo

Analisadores sintáticos são determinísticos se sempre souberem que ação tomar independentemente da entrada de texto. Este comportamento é desejado e esperado na compilação de uma linguagem de programação. No campo de processamento de linguagem natural, pensava-se que essa a análise sintática determinística era impossível devido à ambiguidade inerente das linguagens naturais, em que diversas sentenças possuem mais de uma possível interpretação. Entretanto, Mitch Marcus propôs em 1978 o analisador sintático Parsifal, que consegue lidar com ambiguidades ainda que mantendo o comportamento determinístico.

Ver também

• Interpretadores
• Compiladores
  • Análise léxica
  • Análise semântica