Start: 2021-02-01 End: 2020-05-28 Weekdays: Mon, Fri Skip:
- 2020-02-15: Feriado: Carnaval
- 2020-02-04: Feriado: Semana santa
Início das aulas – Apresentação do curso
- Linguagens e tecnologias adotadas.
- Métodos de avaliação.
- Materiais suplementares.
Introdução ao Python
- Variaveis e tipos básicos.
- Comandos básicos (if/for/while/def).
- Jupyter e Google Colab.
- Check.io.
- Ambiente de programação.
Laboratório de Python: Leitor de JSON
- Especificação do formato.
- Listas, dicionários e tipos atômicos.
- Descida recursiva.
- Testes automatizados.
Programação orientada a objetos
- Encapsulando estado.
- Métodos de uma classe.
- O parâmetro "self".
- Métodos especiais.
Combinadores de parsers I
- Representação de um parser como função.
- Operações atômicas de leitura.
- Operações de segunda ordem: mapa, sequência e alternativa.
- Lendo objetos atômicos.
Combinadores de parsers II
- Outras operações de segunda ordem.
- Operações recursivas e estruturas de dados.
- Parser de JSON.
- Opcional: DSL com sobrecarga de operadores.
Análise sintática
- Linguagens naturais e formais.
- Léxico, sintaxe e semântica.
- Gramática e representação BNF.
- Árvores sintátiacs concretas e abstratas.
Gramáticas livres de contexto
- Regras de produção.
- Lark.
- Operadores estendidos.
- Leitor de JSON.
Laboratório de análise sintática: Gerador de lero lero
- Formalização de uma linguagem natural.
- Gramática gerativa e linguística.
- Produções válidas.
- Gerador de textos aleatórios.
Linguagens de programação
- História das linguagens de programação.
- Paradigmas de programação.
- Famílias de sintaxe.
- Ambiente de execução e semântica de uma linguagem.
Calculadora
- Operações matemáticas básicas.
- Precedência e associatividade de operadores.
- Árvore sintática e avaliação de expressões.
- Variáveis e ambiente de execução.
Operadores
- Ordem infixa, sufixa e prefixa.
- Convertendo expressões.
- Operadores como funções.
- Stack machines.
Linguagens regulares
- Ortografia e léxico de uma linguagem.
- Linguagens regulares.
- Expressões regulares.
- Estensões comuns para expressões regulares.
Laboratório de regex
- Detecção de padrões.
- Expressões regulares em ferramentas de código.
- Regex101 e teste de padrões.
- Palavras cruzadas.
Análise léxica
- Tokens.
- Implementando um analizador léxico.
- Analizador léxico no Lark.
Léxico de linguagens de programação
- Exemplos em Python, C, JavaScript e outras linguagens.
- Definição de tokens.
- Precedência de expressões regulares no tokenizador.
Autômatos
- Introdução a autômatos.
- Autômato determinístico finito.
- Autômato não-determinístico.
- Regras epsilon.
Construção de Thompson
- Autômatos para linguagens regulares.
- Regras básicas e regras de composição.
Simplificando um autômato I
- Eliminação de transições epsilon.
- Propagação de estados iniciais e de aceite.
- Eliminação de estados desnecessários.
Simplificando um autômato II
- Conversão de um NFA para um DFA.
- Tabela de conversão.
- Exercícios
Hierarquia de Chomsky
- Modelos de computação.
- Tipos de autômatos.
- Hierarquia de linguagens formais.
- Máquina de Turing.
Parser LL(1)
- Construções FIRST e FOLLOW.
- Gramáticas sem epsilon.
- Construção da tabela de transição.
- Conflitos na construção.
Parser LL(1)
- Gramaticas com epsilon.
- Tradução para Python.
Descida recursiva
- Tipos atômicos (numerais, strings, etc)
- Símbolos
- Operadores e delimitadores
Algoritmos de análise sintática
- Top-down vs bottom-up.
- Redução à esquerda ou à direita.
- PEGs e ambiguidade.
- Complexidade, poder de análise.
Gramática viva: Lua
- Arquivo de gramática.
- Convertendo gramática para Lark.
- Entendendo a linguagem pela gramática.
Interpretadores
- Ambiente de execução.
- Leitura e escopo de variáveis.
- Implementando funções.
Máquinas virtuais
- Bytecodes/wordcodes vs árvores sintáticas.
- Máquina virtual Python.
- Inspeção de Bytcodes (dis e byteplay).
- Máquina de pilha.
Compiladores
- Objetivos de compilação.
- Checagem e inferência de tipos.
- Controle de memória.
- Emitindo código C.
Revisão de notas