if688

IF688 - Teoria e Implementação de Linguagens Computacionais

Análise Sintática — Introdução a Análise Sintática e First/Follow

Objetivo

O objetivo desta aula é introduzir os conceitos fundamentais de análise sintática no processo de compilação. Discutimos o papel do analisador sintático, a importância das gramáticas livres de contexto (GLCs) e a diferença em relação às expressões regulares. Introduzimos o funcionamento do parsing top-down, evidenciando os problemas relacionados ao uso de backtracking e como técnicas como eliminação de recursão à esquerda e fatoração à esquerda ajudam a tornar a gramática adequada para parsers preditivos. Finalmente, apresentamos as funções FIRST e FOLLOW, essenciais para a construção de parsers preditivos sem backtracking.

Questões para Discussão

O que são gramáticas livres de contexto (GLCs) e como se comparam a expressões regulares?
Qual o papel do analisador sintático em um compilador?
Como funciona um parser top-down, de forma intuitiva?
Por que o backtracking é um problema de eficiência e como podemos evitá-lo?
O que significa uma gramática ser recursiva à esquerda ou exigir fatoração à esquerda?
Por qual razão calculamos o conjunto FIRST de uma produção?
Por qual razão é útil conhecer o conjunto FOLLOW de um não-terminal?

Tópicos Abordados em Sala

Papel do parser dentro do compilador: comunicação entre o analisador léxico e as fases posteriores.
Gramáticas livres de contexto: derivações, árvores sintáticas e linguagens geradas.
Diferença entre expressões regulares e gramáticas livres de contexto: quando usar cada formalismo.
Métodos de parsing: universais, top-down e bottom-up.
Parsing top-down: funcionamento, exemplos passo a passo.
Backtracking como fonte de ineficiência.
Técnicas de transformação de gramáticas:
- Eliminação de recursão à esquerda
- Fatoração à esquerda
Ambiguidade em gramáticas: múltiplas árvores sintáticas para a mesma string.
Funções FIRST e FOLLOW: definição, exemplos e algoritmos de cálculo.

Material usado em sala de aula

Slides (pdf)