Aula 07: Análise Sintática: Fundamentos

Objetivos

• Introduzir a teoria de parsing.
• Compreender Gramáticas Livres de Contexto (GLC) e Árvores de Derivação.

Conteúdo

Enquanto o Scanner lida com palavras, o Parser lida com frases. O objetivo é verificar se a sequência de tokens forma uma estrutura válida segundo a gramática da linguagem.

Por que não Expressões Regulares?

ERs são ótimas para padrões lineares, mas falham em estruturas aninhadas/recursivas (como parênteses balanceados ((...))). Para isso, precisamos de Gramáticas Livres de Contexto (GLC).

Gramáticas Livres de Contexto (GLC)

Uma GLC é definida por \(G = (V, T, P, S)\): - \(V\): Variáveis (Não-terminais) - representam conceitos sintáticos (Expressão, Comando, Bloco). - \(T\): Terminais - os tokens gerados pelo scanner. - \(P\): Produções (Regras) - como as variáveis se transformam. Ex: \(Exp \to Exp + Term\). - \(S\): Símbolo Inicial.

Derivação e Árvores (Parse Trees)

Uma derivação é uma sequência de substituições de regras, começando em \(S\) e terminando numa string de terminais. - Essa derivação pode ser visualizada como uma Árvore Sintática (Parse Tree). - A raiz é \(S\), as folhas são os Tokens. - A estrutura da árvore define a precedência e associatividade das operações. - Ex: Em 3 + 4 * 5, a multiplicação deve estar “mais abaixo” na árvore para ser avaliada primeiro (se a gramática for bem desenhada).

Referências

• Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, Techniques, and Tools.
• Cooper, K., & Torczon, L. (2011). Engineering a Compiler.