Diferença entre análise de baixo para cima e de baixo para cima

o diferença chave entre a análise de cima para baixo e de baixo para cima é que o Careca a análise executa a análise do símbolo de observação para a sequência de entrada, enquanto a análise de baixo para baixo realiza a análise da sequência de entrada para o símbolo inicial. Além disso, outra diferença importante entre a análise de cima para baixo e de baixo para cima é que a análise de cima para baixo usa a derivação mais à esquerda e a análise de baixo para baixo usa a derivação mais à direita.

Linguagens de alto nível ajudam a escrever programas de computador. Eles são mais fáceis de entender pelo programador, mas não pelo computador. Portanto, o programa de alto nível é convertido em código de máquina. A tarefa do compilador é converter o código fonte legível humano em código legível por máquina. Um programa passa por várias etapas para converter em código de máquina. Todo esse processo é chamado de sistema de processamento de idiomas. Um deles é a compilação. O analisador de sintaxe ou o analisador está no compilador e executa a tarefa de análise.

CONTEÚDO

1. Visão geral e principais diferenças
2. O que é análise de cima para baixo
3. O que é análise de baixo para cima
4. Comparação lado a lado - análise de cima para baixo vs de baixo para cima em forma de tabela
5. Resumo

O que é análise de cima para baixo?

Toda linguagem de programação possui um conjunto de regras para representar a linguagem. O analisador de sintaxe ou a análise pega a sequência de entrada e verifica se está de acordo com as produções gramaticais. Em outras palavras, a gramática deve produzir essa sequência usando uma árvore de análise.

Na análise de cima para baixo, a análise acontece a partir do símbolo inicial e alcançará a sequência de entrada especificada. Considere as seguintes regras de produção gramatical. A sequência de entrada (w) é cad.

S -> cAd

A -> ab / a

A árvore de análise após executar a análise de cima para baixo é a seguinte.

Figura 01: Analisar a árvore 1 com análise de cima para baixo

S produz c A d e A produz a b. A corda é cabd. Não é a sequência necessária. Então, é necessário fazer backtracking, que é usar as outras alternativas.

Da mesma forma, S produz c A d. A aplicação da outra opção para A dará a. Agora ele fornece a string necessária. Portanto, o analisador aceita essa sequência de entrada. A árvore de análise após executar a análise de cima para baixo é a seguinte.

Figura 02: Analisar a árvore 2 com análise de cima para baixo

Quando a sequência de entrada (w) é abbcde

Considere as seguintes regras de produção gramatical.

S -> AABe

A -> Abc / b

B -> d

Na análise de cima para baixo,

S -> aABe (Substituindo A -> Abc)

S -> aAbcBe (Substituindo A -> b)

S -> abbcBe (Substituindo B -> d)

S -> abbcde

A substituição começa com a variável mais à esquerda primeiro e depois na próxima posição à direita e assim por diante. Portanto, segue o método de derivação mais à esquerda. Além disso, é importante decidir qual regra de produção escolher quando houver uma variável.

O que é análise de baixo para cima?

Na análise ascendente, acontece de outra maneira. A análise acontece da sequência de entrada ao símbolo inicial. Considere as seguintes regras de produção gramatical e deixe a string de entrada ser w cad

S -> cAd

A -> ab / a

A árvore de análise após a análise de baixo para cima é a seguinte.

Figura 03: Árvore de análise com análise de baixo para cima

A string fornecida é cad. O a é gerado por A. O c, A e d se combinam para obter o símbolo inicial S.

Quando a sequência de entrada (w) é abbcde

Considere as seguintes regras de produção gramatical.

S -> AABe

A -> Abc / b

B -> d

Na análise ascendente,

S -> aABe (Substituindo B -> d)

S -> aAde (Substituindo A -> Abc)

S -> aAbcde (Substituindo A -> b)

S -> abbcde

A substituição começa com a variável mais à direita primeiro e depois passa para a próxima posição esquerda e assim por diante. Portanto, segue um método de derivação à esquerda.

Qual é a diferença entre a análise de cima para baixo e de baixo para cima?

A análise de cima para baixo é uma estratégia de análise que primeiro analisa o nível mais alto da árvore de análise e trabalha na árvore de análise usando as regras de uma gramática formal. A análise de baixo para cima é uma estratégia de análise que primeiro analisa o nível mais baixo da árvore de análise e elabora a árvore de análise usando as regras de uma gramática formal. A análise ocorre do símbolo inicial até a sequência de entrada, na análise de cima para baixo. Por outro lado, a análise ocorre da sequência de entrada até o símbolo inicial, na análise ascendente.

Além disso, a principal decisão na análise de cima para baixo é selecionar qual regra de produção usar para construir a sequência, enquanto a decisão principal na análise de baixo para baixo é selecionar quando usar uma regra de produção para reduzir a sequência e obter o símbolo inicial. Além disso, a análise de cima para baixo usa a derivação mais à esquerda e a análise de baixo para baixo usa a derivação mais à direita.

Resumo - Análise Top Down vs Bottom Up

A diferença entre a análise de cima para baixo e de baixo para cima é que a análise de cima para baixo executa a análise do símbolo de encarar a seqüência de entrada, enquanto a análise de baixo para baixo executa a análise da seqüência de entrada para o símbolo inicial.

Referência:

1. “Aula 5 de Design do Compilador - Introdução aos Analisadores e à Análise LL (1).” Aula 5 de Design do Compilador - Introdução aos Analisadores e LL (1), Palestras sobre Portões de Ravindrababu Ravula, 22 de maio de 2014. Disponível aqui