if688

IF688 - Teoria e Implementação de Linguagens Computacionais

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

Objetivo

O objetivo desta aula é introduzir conceitos fundamentais relacionados à bottom-up parsing, como handles, prefixos viáveis, e análise shift-reduce, bem como apresentar como criar parsers bottom-up por meio da construção de autômatos de itens LR(0), representando prefixos viáveis.

Questões para Discussão

• 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?
• Como construir uma tabela de parsing automaticamente a partir do autômato de itens LR(0)?

Material usado em sala de aula

• Slides (pdf)

Vídeos

• 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
• Análise Sintática - LR(0) parsers
• Análise Sintática - Construindo tabelas de parsing LR
• Análise Sintática - Algoritmo de parsing usando tabelas LR

Links Relacionados

• Bottom-up Parsing
• LR parser