Análise sintática (computação): diferenças entre revisões

Origem: Wikipédia, a enciclopédia livre.
Conteúdo apagado Conteúdo adicionado
m Página marcada como esboço, usando FastButtons
m Ficheiro → Imagem e etc.
Linha 1: Linha 1:
[[Ficheiro:Parsing-example.png|thumb|right|250px|Exemplo da '''análise sintática''' de uma [[expressão matemática]]. O resultado é uma [[árvore (estrutura de dados)|árvore]] da expressão]]
[[Imagem:Parsing-example.png|thumb|right|250px|Exemplo da '''análise sintática''' de uma [[expressão matemática]]. O resultado é uma [[árvore (estrutura de dados)|árvore]] da expressão]]
Em [[ciência da computação]] e [[linguística]], '''análise sintática''' (também conhecida pelo termo em [[Língua inglesa|inglês]] '''''parsing''''') é o processo de analisar uma sequência de entrada (lida de um [[arquivo de computador]] ou do [[teclado (computador)|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]].
Em [[ciência da computação]] e [[linguística]], '''análise sintática''' (também conhecida pelo termo em [[Língua inglesa|inglês]] '''''parsing''''') é o processo de analisar uma sequência de entrada (lida de um [[arquivo de computador]] ou do [[teclado (computador)|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]].


Linha 14: Linha 14:


== Determinismo ==
== 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 [[compilador|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<ref>{{Referência a livro
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 [[compilador|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<ref>{{Referência a livro
| Autor = Mitchell P. Marcus
| Autor = Mitchell P. Marcus
Linha 29: Linha 28:
</ref>, que consegue lidar com ambiguidades ainda que mantendo o comportamento determinístico.
</ref>, que consegue lidar com ambiguidades ainda que mantendo o comportamento determinístico.


{{Referências}}
{{ref-section|Notas e referências}}


=={{Ver também}}==
== Ver também ==
* [[Interpretador]]es
* [[Interpretador]]es
* [[Compilador]]es
* [[Compilador]]es
** [[Análise léxica]]
** [[Análise léxica]]
** [[Análise semântica]]
** [[Análise semântica]]



{{Esboço-computação}}
{{Esboço-computação}}

Revisão das 15h26min de 5 de março de 2014

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[1], que consegue lidar com ambiguidades ainda que mantendo o comportamento determinístico.

Referências

  1. Mitchell P. Marcus (1980). Theory of Syntactic Recognition for Natural Languages. [S.l.]: MIT Press. ISBN 0262131498  Parâmetro desconhecido |Autor= ignorado (|autor=) sugerido (ajuda); Parâmetro desconhecido |Páginas= ignorado (|páginas=) sugerido (ajuda)

Ver também

Ícone de esboço Este artigo sobre computação é um esboço. Você pode ajudar a Wikipédia expandindo-o.