Análise sintática (computação): diferenças entre revisões
m Foram revertidas as edições de Pedro White para a última revisão de 177.19.111.69, de 2015-05-29T00:51:05 (UTC) |
Adicionado os objetivos, sobre os dois analisadores Etiquetas: Referências removidas Editor Visual |
||
| Linha 7: | Linha 7: | ||
A vasta maioria dos analisadores sintáticos implementados em compiladores aceitam alguma [[gramática livre de contexto|linguagem livre de contexto]] para fazer a análise. Estes analisadores podem ser de vários tipos, como o [[Analisador sintático LL|LL]], [[Analisador sintático LR|LR]] e [[Analisador sintático SLR|SLR]]. |
A vasta maioria dos analisadores sintáticos implementados em compiladores aceitam alguma [[gramática livre de contexto|linguagem livre de contexto]] para fazer a análise. Estes analisadores podem ser de vários tipos, como o [[Analisador sintático LL|LL]], [[Analisador sintático LR|LR]] e [[Analisador sintático SLR|SLR]]. |
||
== Objetivo == |
|||
O objetivo do analisador sintático é verificar se uma determinada gramatica com uma sequencia ẟ de símbolos terminais(Frase) é uma frase válida da linguagem. Mas não só analisar se pertence ou não a linguagem, o analisador sintática reconhece a forma da frase exemplo: "O rato roeu a roupa do rei de roma", se colocarmos "O '''ratos''' roeu a roupa do rei de roma" para que a estrutura esteja correta, é necessário que antes do plural o artigo, esteja no plural. Então o analisador iria verificar e apontar um error. |
|||
== Tipos de analisadores sintáticos == |
== Tipos de analisadores sintáticos == |
||
Existem dois tipos gerais de estratégias de analisador sintático(parsing) são elas: '''top-down''' e '''bottom-up.''' |
|||
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]]. |
|||
=== Top-Down === |
|||
* Ascendente (''bottom-up'') - um analisador pode iniciar com uma 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]]. |
|||
A árvore é construída da raiz para as folhas. Em cada vértice seleciona uma produção com um símbolo não terminal A à esquerda e constrói os vértices filhos do símbolo não terminal A com símbolos à direita nessa produção, então seleciona o vértice e continua e terminará quando todas as folhas forem símbolos terminais. A aceitação se dá quando o ẟ termina. O "lookahead" toma decisões para observar o próximo símbolo e fazer a analise. |
|||
=== Bottom-up === |
|||
A árvore é construída das folhas para a raiz, os símbolos de α são associados até reconhecer o lado direito de uma produção e a aceitação se dá se, esgotada a sequência α e o símbolo inicial estiver na raiz da árvore. |
|||
== |
== Analisador sintático == |
||
O analisador sintático utiliza diversos conceitos da ciência da computação como por exemplo a estrutura de dados: árvore é um exemplo. Ao receber os dados do analisador léxico no caso do compilador ele verifica se a sintaxe está correta. |
|||
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 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 |
|||
| Título = Theory of Syntactic Recognition for Natural Languages |
|||
| Subtítulo = |
|||
| Edição = |
|||
| Local de publicação = [[Cambridge]] |
|||
| Editora = [[MIT Press]] |
|||
| Ano = [[1980]] |
|||
| Páginas = 335 |
|||
| Volumes = |
|||
| Volume = |
|||
| ID = ISBN 0262131498}} |
|||
</ref>, que consegue lidar com ambiguidades ainda que mantendo o comportamento determinístico. |
|||
{{Referências|Compiladores - Princípios , Técnicas e Ferramentas ( Aho, Alfred V.; Jeffrey; Sethi, Ravi; Lam, Monica S. = Compiladores - Princípios , Técnicas e Ferramentas (Cód: 8873692) |
|||
{{Referências}} |
|||
Aho, Alfred V.; Jeffrey; Sethi, Ravi; Lam, Monica S.}} |
|||
== Ver também == |
== Ver também == |
||
Revisão das 13h04min de 2 de dezembro de 2015
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.
Objetivo
O objetivo do analisador sintático é verificar se uma determinada gramatica com uma sequencia ẟ de símbolos terminais(Frase) é uma frase válida da linguagem. Mas não só analisar se pertence ou não a linguagem, o analisador sintática reconhece a forma da frase exemplo: "O rato roeu a roupa do rei de roma", se colocarmos "O ratos roeu a roupa do rei de roma" para que a estrutura esteja correta, é necessário que antes do plural o artigo, esteja no plural. Então o analisador iria verificar e apontar um error.
Tipos de analisadores sintáticos
Existem dois tipos gerais de estratégias de analisador sintático(parsing) são elas: top-down e bottom-up.
Top-Down
A árvore é construída da raiz para as folhas. Em cada vértice seleciona uma produção com um símbolo não terminal A à esquerda e constrói os vértices filhos do símbolo não terminal A com símbolos à direita nessa produção, então seleciona o vértice e continua e terminará quando todas as folhas forem símbolos terminais. A aceitação se dá quando o ẟ termina. O "lookahead" toma decisões para observar o próximo símbolo e fazer a analise.
Bottom-up
A árvore é construída das folhas para a raiz, os símbolos de α são associados até reconhecer o lado direito de uma produção e a aceitação se dá se, esgotada a sequência α e o símbolo inicial estiver na raiz da árvore.
Analisador sintático
O analisador sintático utiliza diversos conceitos da ciência da computação como por exemplo a estrutura de dados: árvore é um exemplo. Ao receber os dados do analisador léxico no caso do compilador ele verifica se a sintaxe está correta.
