if688

IF688 - Teoria e Implementação de Linguagens Computacionais

Análise Sintática — LL(1) Parsing

Objetivo

O objetivo desta aula é apresentar a classe de gramáticas LL(1), discutindo suas características e limitações. Mostramos como os conjuntos FIRST e FOLLOW são usados para construir tabelas de parsing preditivo, e como verificar se uma gramática é LL(1). Também apresentamos o algoritmo de parsing dirigido por tabela (table-driven), incluindo o uso de pilha e lookahead. Por fim, discutimos por que gramáticas LL(1) são relevantes na prática, suas vantagens (simplicidade e eficiência) e desvantagens.

Questões para Discussão

Como construir uma tabela de parsing LL(1) automaticamente a partir dos conjuntos FIRST e FOLLOW?
Quais características das gramáticas LL(1) se refletem na tabela de parsing?
Como funciona o algoritmo de parsing baseado em tabela LL(1)?
Por que LL(1) é uma classe de gramáticas interessante para linguagens de programação?
Quais as limitações das gramáticas LL(1)?

Tópicos Abordados em Sala

Revisão de parsing top-down e motivação para parsers preditivos sem backtracking.
Definição de gramáticas LL(1).
Condições formais para que uma gramática seja LL(1).
Construção da tabela de parsing LL(1):
- Uso de FIRST e FOLLOW.
- Regras de preenchimento da tabela.
- Identificação de entradas inválidas (erros).
Exemplos práticos de construção de tabelas (gramáticas simples e expressões aritméticas).
Algoritmo preditivo não recursivo (table-driven).

Material usado em sala de aula

Slides (pdf)