if688

IF688 - Teoria e Implementação de Linguagens Computacionais

Introdução a Análise Sintática

Objetivo

O objetivo desta aula é apresentar os conceitos fundamentais relacionados à análise sintática, introduzir o conceito de top-down parsing, ilustrando que o principal problema de eficiência relacionado a parsers, que é a necessidade de fazer backtracking e ilustrar a técnica de recursive-descent parsing.

Questões para Discussão

• O que são gramáticas livres de contexto?
• Qual a diferença entre o que é possível de ser representado com expressões regulares vs. gramáticas livres de contexto?
• Como funciona um parser top-down, intuitivamente?
• O que devemos evitar em uma gramática para não precisar fazer backtracking?
• Quais as vantagens e limitações de recursive descent parsing como técnica de construção de parsers?

Material usado em sala de aula

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

Vídeos

• Análise Sintática - Visão Geral
• Análise Sintática - Introdução a top-down parsing
• Análise Sintática - Predictive parsing
• Análise Sintática - Recursive-descent parsing

Links Relacionados

• PLY
• JFlex
• lex
• Context-free grammars
• Parsing
• Top-down Parsing