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

Origem: Wikipédia, a enciclopédia livre.
(Redirecionado de Parsing)
Ir para: navegação, pesquisa
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.

Analisador sintático[editar | editar código-fonte]

O analisador se trata de um software que realiza a função de carregar os dados de entrada e constrói com uma estrutura de dados com eles. Essa estrutura de dados pode se tratar de uma árvore de análise, árvore abstrata de sintaxe ou outras estruturas que dão ideia de hierarquia, par que resulte em uma representação estrutural da entrada que foi feita a análise. A análise pode proceder vários outros passos que são executados antes da própria análise, ou estes passos podem ser executados em um único passo, onde eles estarão combinados. Muitas vezes o processo realizado pelo analisador sintático é procedido pelo processo de análise léxica, já que esta análise gera como resultado uma tabela dos tokens dos dados de entrada analisados.  Os analisadores podem ser programados manualmente, ou podem ser gerados automaticamente por um gerador de analisador.   

                A entrada de dados que é analisada pelo analisador é normalmente um código de uma linguagem de programação, mas podem ser também textos em linguagem natural, e nesse caso não é construída uma árvore de análise, mas só são extraídas algumas partes do texto. As funções dos analisadores variam desde analisar comandos simples de um código a programas muito complexos. Uma forma importante de realizar a análise é usando expressões regulares, onde uma expressão regular define uma linguagem regular e um mecanismo de expressão regular gerando automaticamente um analisador para a linguagem. Em alguns casos as expressões regulares são usadas antes da própria análise sintática, como etapa da análise léxica cuja saída será utilizada pelo analisador sintático.

                O dos analisadores sintáticos varia de acordo com a entrada que ele recebe, ou seja, da linguagem de programação que ele irá analisar. Para linguagens de dados o analisador é utilizado para facilitar a leitura de um programa, já para linguagens de programação o analisador faz parte de um compilador, que analisa o código para criar uma forma de representação interna. As linguagens de programação possuem uma gramática determinística, ou seja, que não possui ambiguidade, com isso é implementado o analisador sintático referente a está gramática. A análise para o compilador pode ser feita em uma ou múltiplas passagens pelo código.

                Existem desvantagem em relação ao compilador de uma passagem, mas estas podem ser dribladas com a utilização de fix-ups, onde durante a passagem o fix-up realiza a função de voltar no código quando a análise de um segmento está incompleta, ao invés de continuar a passagem pelo código. Um exemplo de fix-up é o uso do comando GOTO, onde o destino desse comando é desconhecido até que seu segmento no programa seja concluído.  

                Gramáticas livres do contexto são limitadas, já que podem expressar todos os requisitos de um idioma e sua memória é limitada. Então essa gramática não consegue lembrar a presença de uma construção longa da entrada. E gramáticas mais poderosas que suprem essa limitação, não podem ser analisadas de forma eficiente. Logo é uma boa estratégia que a gramática livre do contexto aceite um conjunto de construções maiores da linguagem, aceitando construções inválidas, e posteriormente as construções indesejadas serão filtradas na análise semântica. Tudo isso para se obter um analisador mais descontraído para uma gramática livre do contexto.

Por exemplo, em Python o seguinte código é uma sintaxe válida:

y = 15  print y

O código a seguir, no entanto, é uma sintaxe válida em termos da gramática livre de contexto, produzindo uma árvore de sintaxe com a mesma estrutura que o anterior, mas é sintaticamente inválido em termos da gramática sensível ao contexto, o que requer que as variáveis ​​sejam inicializadas antes uso:

x = 20 print y

Ao invés de ser analisada na fase de análise, esta construção é capturada, verificando os valores na árvore de sintaxe, portanto, como parte da análise semântica: sintaxe sensível ao contexto é, na prática, muitas vezes mais facilmente analisada como semântica.

Visão geral do processo[editar | editar código-fonte]

O caso comum de análise de uma linguagem de programação possui dois níveis de gramática: lexicais e sintáticas.

A primeira etapa é a geração de tokens ou análise léxica, pelo qual o fluxo de caracteres de entrada é dividido em símbolos significativos definidos por uma gramática de expressões regulares.

A próxima etapa é ou a análise sintática, que é a verificação de que os tokens formam uma expressão permitida. Isso geralmente é feito com referência a uma gramática livre de contexto que define de forma recursiva componentes que podem fazer-se uma expressão e a ordem em que devem aparecer. No entanto, nem todas as regras que definem linguagens de programação podem ser expressas somente por gramáticas livres de contexto.

A fase final é a análise semântica, que elabora as implicações da expressão apenas validadas e toma a ação apropriada. Gramáticas de atributos pode ser usadas para definir estas ações.

Objetivo[editar | editar código-fonte]

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[editar | editar código-fonte]

Existem dois tipos gerais de estratégias de analisador sintático(parsing) são elas: top-down e bottom-up.

Top-Down[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

Analisador LR[editar | editar código-fonte]

Algoritmo CYK[editar | editar código-fonte]

Analisador Shift-Reduce[editar | editar código-fonte]

Analisador de Subida Recursiva[editar | editar código-fonte]

Geradores de analisadores sintáticos[editar | editar código-fonte]

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

Lookahead[editar | editar código-fonte]

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[editar | editar código-fonte]

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