Análise sintática (computação): diferenças entre revisões
→Analisador sintático: Adicionado |
Algumas edições nos tipos de analisadores sintáticos foram efetuadas. |
||
| Linha 15: | Linha 15: | ||
=== Top-Down === |
=== Top-Down === |
||
A árvore é construída da raiz |
O analisador Top-Down realiza a derivação mais à esquerda de uma cadeia de entrada '''X''' a partir do simbolo inicial da gramática.A árvore gramatical desta cadeia de entrada é construída da raiz até 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 === |
=== Bottom-up === |
||
A árvore é construída |
Conhecida como análise de empilhar e reduzir, a análise sintática Bottom-Up realiza a redução mais a esquerda uma cadeia de entrada '''X''' ao simbolo inicial da gramática. A árvore gramatical é construída iniciando pelas folhas e indo em direção à 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 == |
== Analisador sintático == |
||
Revisão das 15h33min 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
O analisador Top-Down realiza a derivação mais à esquerda de uma cadeia de entrada X a partir do simbolo inicial da gramática.A árvore gramatical desta cadeia de entrada é construída da raiz até 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
Conhecida como análise de empilhar e reduzir, a análise sintática Bottom-Up realiza a redução mais a esquerda uma cadeia de entrada X ao simbolo inicial da gramática. A árvore gramatical é construída iniciando pelas folhas e indo em direção à 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.
Um analisador sintático é um componente de software que leva os dados de entrada (freqüência de texto) e constrói uma estrutura de dados - muitas vezes uma espécie de árvore de análise, árvore abstrata de sintaxe ou outra estrutura hierárquica - dando uma representação estrutural da entrada, verificação de sintaxe correta no processo . A análise pode ser precedido ou seguido por outros passos, ou estes podem ser combinados num único passo. O analisador é muitas vezes precedida por um analisador lexical separada, o que cria tokens de a seqüência de caracteres de entrada; Alternativamente, estes podem ser combinados em scanners. Analisadores podem ser programados manualmente ou pode ser automática ou semi-automática gerada por um gerador de analisador. O analisador sintático modelado completamente para produzir uma saída formatada. Estas podem ser aplicadas a diferentes domínios, mas aparecem frequentemente em conjunto, tal como o par scanf / printf, ou as fases de um compilador de entrada e de saída.
A entrada para um analisador de texto é muitas vezes de alguma linguagem de computador, mas pode também ser um texto em linguagem natural ou dados textuais menos estruturado, caso em que geralmente apenas certas partes do texto são extraídos, em vez de uma árvore de análise a ser construída. O analisador sintático variam de funções muito simples, como scanf, a programas complexos, tais como a interface de um compilador Delphi ou o analisador de XML de um webservice. Uma classe importante de análise simples é feito usando expressões regulares, em que uma expressão regular define uma linguagem regular e um mecanismo de expressão regular gerando automaticamente um analisador para que a linguagem, permitindo correspondência de padrão e extração de texto. Em outro contexto as expressões regulares são usadas antes da análise, como a etapa do léxico cuja saída é então utilizado pelo analisador.
O uso de analisadores varia de acordo com a entrada. No caso de linguagens de dados, um analisador é frequentemente encontrada como a facilidade de leitura do ficheiro de um programa, tal como a leitura de texto HTML ou XML; estes exemplos são linguagens de marcação. No caso de linguagens de programação, um analisador é um componente de um compilador ou intérprete, que analisa o código-fonte de uma linguagem de programação de computador para criar alguma forma de representação interna; o analisador é um passo fundamental no frontend compilador. As linguagens de programação tendem a ser especificado em termos de uma gramática livre de contexto determinista porque analisadores rápidos e eficientes podem ser escritos para eles. Para compiladores, a própria análise pode ser feito em uma passagem ou passagens múltiplas - ver compilador de uma passagem e compilador multi-pass.
As desvantagens implícitas de um compilador de uma passagem pode ser largamente superados adicionando fix-ups, em que está prevista para fix-ups durante a passagem para a frente, e os fix-ups são aplicados para trás quando o segmento actual programa tem sido reconhecido como tendo sido completada. Um exemplo em que um tal mecanismo fix-up seria útil seria uma declaração GOTO para a frente, onde o destino da GOTO é desconhecido até o segmento de programa seja concluído. Neste caso, a aplicação da correcção-se-ia ser atrasada até que o alvo da GOTO foi reconhecido. Obviamente, um GOTO para trás não exige uma correção-up.
Gramáticas livres de contexto são limitados na medida em que pode expressar todos os requisitos de um idioma. Informalmente, a razão é que a memória de um tal linguagem é limitada. A gramática não consegue lembrar a presença de uma construção mais de uma arbitrariamente longo de entrada; isto é necessário para um idioma em que, por exemplo, um nome deve ser declarado antes que pode ser referenciada. Gramáticas mais poderosas que podem expressar esta limitação, no entanto, não pode ser analisado de forma eficiente. Assim, é uma estratégia comum para criar um analisador descontraído para uma gramática livre de contexto que aceita um superconjunto das construções de linguagem desejados (isto é, ele aceita algumas construções inválidas); mais tarde, as construções indesejados podem ser filtrados na etapa de análise semântica (análise contextual).
Por exemplo, em Python o seguinte código é uma sintaxe válida:
y = 10 print y
