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

Origem: Wikipédia, a enciclopédia livre.
Conteúdo apagado Conteúdo adicionado
Tipos de analisadores sintaticos
m Desfeita(s) uma ou mais edições de 200.20.228.15, com Reversão e avisos.
Linha 19: Linha 19:
=== Bottom-up ===
=== 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.
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 de ascendência recursiva''' ====
o analisador de ascendência recursiva é uma espécie de analisador top-down construído a partir de um conjunto de procedimentos mutuamente recursivo (ou um equivalente não-recursivo) onde cada tal procedimento geralmente implementa uma das produções da gramática. Assim, a estrutura resultante do
programa que espelha a gramática reconhece.

===== Analisador preditivo =====
Um '''''analisador preditivo''''' é um analisador de ascendência recursiva que não necessita de retrocesso. Análise preditiva é possível somente para a classe de LL (k) gramáticas, que são as gramáticas livres de contexto para o qual existe algum inteiro positivo ''k'' que permite um analisador descendente recursivo para decidir qual a produção de usar examinando apenas os próximos ''k'' símbolos de entrada. Os LL ''(k)'' gramáticas excluem todas as gramáticas ambíguas, bem como todas as gramáticas que contêm recursão à esquerda. Qualquer gramática livre de contexto pode ser transformada em uma gramática equivalente que não tem recursão à esquerda, mas a remoção da recursão à esquerda nem sempre produzir um LL ''(k)'' gramática. Um analisador preditivo é executado em tempo linear.

===== '''Analisador de precedência simples''' =====
Um '''analisador de precedência simples''' é um tipo de analisador de baixo para cima para gramáticas livres de contexto que podem ser usados ​​apenas por gramáticas de precedência simples. A implementação do analisador é bastante semelhante ao genérico analisador bottom-up. Uma pilha é usada para armazenar um prefixo viável de uma forma sentenciai a partir de uma derivação mais à direita são usados ​​para identificar o pivô, e saber quando a tecla Shift ou quando a Reduzir.


==== Analisador de precedência do operador ====
==== Analisador de precedência do operador ====

Revisão das 16h49min de 2 de dezembro de 2015

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.

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ático 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 de precedência do operador

Este tipo de analisador Bottom-Up interpreta uma gramática operadora de procedência. É capaz de analisar todos LR(1) gramáticas onde dois consecutivos não terminais nunca aparecem no lado direito de qualquer regra.

Analisador de precedência simples

Analisador LR

Algoritmo CYK

Analisador Shift-Reduce

Analisador de Subida Recursiva

Geradores de analisadores sintáticos

Hoje em dia existem vários programas que facilitam a criação de analisadores sintáticos. Eles são denominados de geradores de analisadores sintáticos, pois eles recebem como entrada uma gramática especifica e retorna como saída um analisador sintático para essa gramática.

A seguir, temos alguns exemplos de geradores de analisador sintático.

  • Yacc
  • Bison
  • SableCC
  • COCO/R
  • AntLR

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

Lookahead

Lookahead nada mais é do que analisar um token e ao mesmo tempo olhar um token a frente para poder decidir qual regra deve ser utilizada. Por exemplo, ao analisar o delimitador ‘/’, é necessário olhar a frente para poder saber se ele será um comentário de linha ou de bloco. Com ele, é possível ajudar o analisador a tomar a decisão correta em caso de conflitos e eliminar os estados duplicados aliviando a carga de uma pilha extra.

Referências

Ver também

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