if688

IF688 - Teoria e Implementação de Linguagens Computacionais

Análise Sintática — Recursive-descent Parsing e Introdução a Bottom-Up Parsing

Objetivo

O objetivo desta aula é apresentar a técnica de recursive-descent parsing, bem como introduzir conceitos fundamentais relacionados à bottom-up parsing, como handles, prefixos viáveis, e análise shift-reduce.

Questões para Discussão

• Quais as vantagens e limitações de recursive descent parsing como técnica de construção de parsers?
• Quais as desvantagens de usar gramáticas LL(1)?
• Como funciona um parser bottom-up, intuitivamente?
• O que significa reduzir um item a partir de um handle?
• Como identificar handles, e saber quando reduzir?

Material usado em sala de aula

• Slides de recursive-descent parsing (pdf - ver parte final)
• Slides de bottom-up parsing (pdf)
• Analisador Sintático usando a técnica de recursive-descent parsing - ilustrado durante a aula
  • parse.py
  • main.py

Vídeos

• Análise Sintática - Recursive-descent parsing
• Análise Sintática - Introdução a Bottom-Up parsing
• Análise Sintática - Reduções Problemáticas e Handles
• Análise Sintática - Análise Shift-Reduce
• Análise Sintática - Prefixos Viáveis

Links Relacionados

• Context-free grammars
• Parsing
• Top-down Parsing