Análise Ascendente §

---

A análise sintática ascendente, também conhecida como bottom-up parsing, é um método para construir uma árvore de derivação para uma cadeia de entrada, começando pelos terminais da cadeia de entrada (folhas) e subindo em direção ao símbolo inicial da gramática (raiz).

Como funciona §

Vamos considerar uma gramática de expressões aritméticas simples:

Gramática:

Cadeia de entrada: id * id + id

O processo, de forma geral, funciona assim:

1. O analisador lê id da entrada. Ele reconhece que id pode ser derivado de F (pela regra ). Então, ele reduz id para F. A cadeia se torna F * id + id.

2. Agora, ele vê F. Ele sabe que F pode ser reduzido para T (pela regra ). A cadeia vira T * id + id.

3. O analisador continua e lê o * e o próximo id. Ele reduz esse segundo id para F, resultando em T * F + id.

4. Neste ponto, ele reconhece o padrão T * F na cadeia. Este padrão corresponde ao lado direito da produção . Ele então reduz T * F para T. A cadeia se torna T + id.

5. Ele sabe que T pode ser E (). A cadeia vira E + id.

6. Ele processa o + e o último id, que é reduzido para F, depois para T. A cadeia fica E + T.

7. Finalmente, ele reconhece E + T, que corresponde à produção . Ele reduz para E.

Como a cadeia foi completamente reduzida ao símbolo inicial E, a análise é aceita.

Note

O mecanismo mais comum para implementar esse processo é o analisador shift-reduce. Como o nome sugere, ele realiza duas ações fundamentais (shift e reduce) e utiliza uma estrutura de pilha para armazenar os símbolos da gramática (terminais e não-terminais) que já foram processados.

A base do funcionamento desse analisador é a redução.

Referências §

---

Aula 14-10-2025 de Compiladores