2024-05-09.md

IF688 - Teoria e Implementação de Linguagens Computacionais

Bottom-up Parsing e gramáticas LR(k)

Objetivo

O objetivo desta aula é apresentar os conceitos fundamentais relacionados à parsers LR(1), introduzir o conceito de itens LR(1) na construção de autômatos de prefixos viáveis.

Questões para Discussão

• Que tipos de conflito podem surgir a partir da estratégia LR(0)?
• Como construir autômatos que reconhecem prefixos viáveis, a partir de itens LR(1)?
• Como construir uma tabela de parsing automaticamente a partir do autômato de itens LR(1)?

Material usado em sala de aula

• Slides (pdf)

Vídeos

• Análise Sintática - Conflitos Shift-Reduce
• Análise Sintática - LR(1) parsing

Links Relacionados

• LR(1) Parsing
• Practical LR(k) Parser Construction
• DeRemer, Franklin L. (1969). Practical Translators for LR(k) languages (Ph.D.). MIT.