if688

IF688 - Teoria e Implementação de Linguagens Computacionais

Introdução à Top-Down Parsing

Objetivo

O objetivo desta aula é apresentar a classe de gramáticas LL(1) e os conceitos de first e follow, que são essenciais para montagem de tabelas de parsing. Adicionalmente, apresentar o algoritmo de parsing guiado pela tabela LL(1).

Questões para Discussão

• Por qual razão calculamos o primeiro terminal que inicia uma dada sentença (FIRST)?
• Por qual razão podemos nos interessar em saber os símbolos terminais que podem seguir logo após um não-terminal (FOLLOW)?
• Como construir uma tabela de parsing automaticamente a partir dos conjuntos FIRST e FOLLOW?
• Quais as características de gramáticas LL(1) serão refletidas nestas tabelas?
• Como realizar parsing a partir de uma tabela?
• Por que se importar com LL(1)?
• Quais as desvantagens de usar gramáticas LL(1)?

Material usado em sala de aula

• Slides (pdf)

Vídeos

• Análise Sintática - Calculando FIRST e FOLLOW
• Análise Sintática - Tabelas de Parsing LL(1)
• Análise Sintática - Algoritmo de parsing usando tabelas LL(1)

Links Relacionados

• Top-down Parsing
• LL grammar
• LL parser
• LL(1) Parser Visualization