Descrição da Disciplina
Compiladores e Linguagens Formais e Autômatos ocupa, na formação do bacharel em Ciência da Computação, uma posição que nenhuma outra disciplina do curso ocupa: é onde a teoria mais abstrata do currículo — alfabetos, gramáticas, máquinas de estados, hierarquias de linguagens — deixa de ser um objeto de contemplação matemática e passa a ser a engenharia de um programa que funciona. O estudante que chega até aqui já escreveu muitos programas; o que ele ainda não fez foi escrever o programa que lê programas. Essa inversão de papéis é o que torna a disciplina formadora, e não apenas informativa.
O curso reúne dois eixos que, em muitas grades, aparecem separados. De um lado, a teoria de linguagens formais e autômatos, que estabelece o que uma classe de máquinas consegue e o que não consegue reconhecer, e que fornece as provas de impossibilidade que impedem o engenheiro de perseguir soluções que não existem. De outro, a construção de compiladores, que toma essa teoria e a converte em análise léxica, análise sintática, análise semântica, ambiente de execução e geração de código. A fusão dos dois eixos num percurso só não é acidente de nomenclatura: um autômato finito é exatamente o que um analisador léxico executa, e um autômato de pilha é exatamente o que um analisador sintático descendente realiza. Ensinar os dois lados separados é privar o estudante da única evidência convincente de que a teoria serve para alguma coisa.
Há um risco conhecido nessa fusão, e o desenho deste curso o enfrenta de frente. Quando a construção do compilador se apoia em geradores automáticos de analisadores, os autômatos desaparecem dentro de uma ferramenta opaca e o estudante conclui o percurso sem nunca ter determinizado um autômato não determinístico com as próprias mãos. Aqui o caminho é o oposto: o artefato de referência é construído inteiramente à mão, do reconhecedor de expressões regulares ao motor de execução, de modo que cada resultado teórico apresentado tenha, poucas aulas depois, uma contrapartida em código que o estudante vê rodar. A teoria é a especificação da prática.
O percurso é integralmente prático no sentido de que tudo converge para um artefato construído. O trabalho da turma se organiza em torno de um projeto integrador desenvolvido em grupos ao longo de todo o período, e o professor conduz em paralelo a própria implementação de referência, demonstrada em aula à medida que cada tópico é apresentado. O estudante, portanto, não recebe apenas a descrição de como um compilador é feito: acompanha um sendo feito e faz o seu.
Público-alvo
O curso se destina a estudantes do sexto termo do Bacharelado em Ciência da Computação, em regime presencial. Trata-se de um público que já percorreu mais da metade da formação e que traz consigo um repertório específico, do qual a disciplina depende de forma direta.
O projeto pedagógico não fixa pré-requisito formal para este componente. A progressão dos termos, contudo, torna algumas dependências conceituais evidentes e elas devem ser tratadas como reais no planejamento. De estruturas de dados vêm as árvores, as tabelas de dispersão e as pilhas, que aqui são as estruturas em que a árvore sintática, a tabela de símbolos e o reconhecedor descendente são literalmente construídos. De lógica computacional vem a familiaridade com definições formais, com quantificadores e com a leitura de uma demonstração, sem a qual o lema do bombeamento se reduz a um ritual decorado. De linguagens de programação vem a noção de que sintaxe e semântica são coisas distintas, e de que a mesma construção pode ter significados diferentes em linguagens diferentes. De arquitetura e organização de computadores vêm registradores, memória e conjunto de instruções, que reaparecem quando o percurso chega ao ambiente de execução e à emissão de código. De algoritmos em grafos vem o vocabulário de nós, arestas e travessias, com o qual autômatos e árvores sintáticas são manipulados sem esforço adicional de abstração.
O módulo de nivelamento que abre o material existe justamente para tratar essas dependências. Ele não substitui as disciplinas anteriores, mas recompõe o que a experiência mostra ser o ponto de maior variação entre estudantes de uma mesma turma, e é precedido de uma sondagem que permite ao professor calibrar a ênfase antes que o primeiro módulo de conteúdo comece.
Espera-se, além disso, maturidade em programação suficiente para conduzir um sistema de médio porte que cresce ao longo do período, com atenção a tipos, a gerenciamento de recursos e a testes. O artefato construído aqui não cabe em um arquivo, e essa é parte da aprendizagem.
Objetivos de Aprendizagem
Ao concluir o percurso, o estudante deverá ser capaz de especificar formalmente uma linguagem, decidir a que classe da hierarquia de Chomsky ela pertence e justificar essa classificação, reconhecendo em particular quando uma linguagem está além do alcance de um autômato finito e sabendo demonstrá-lo. Deverá converter uma expressão regular em autômato finito não determinístico, determinizá-lo, minimizá-lo e argumentar sobre a equivalência entre as máquinas obtidas, compreendendo que essas transformações são a implementação de um analisador léxico.
Deverá projetar uma gramática livre de contexto adequada a uma linguagem pretendida, identificar e remover ambiguidade, recursão à esquerda e fatoração pendente, e explicar por que essas transformações são necessárias para que um analisador descendente funcione. Deverá construir esse analisador, calcular os conjuntos que orientam suas decisões e tratar erros sintáticos de modo a produzir mensagens úteis a quem escreveu o programa, e não apenas a quem escreveu o compilador. Deverá também compreender o funcionamento dos analisadores ascendentes com profundidade suficiente para avaliar, diante de um problema concreto, qual das duas famílias é a escolha adequada, ainda que a implementação conduzida no percurso siga o caminho descendente.
Deverá construir a análise semântica de uma linguagem, o que significa projetar uma tabela de símbolos com tratamento de escopo, verificar tipos e reportar de forma inteligível os erros que a sintaxe sozinha não é capaz de capturar. Deverá compreender como um programa em execução organiza sua memória e como as chamadas e os retornos são realizados, e deverá traduzir uma representação intermediária em código executável por uma máquina definida, reconhecendo as otimizações elementares que tornam esse código aceitável.
Acima de tudo, deverá ser capaz de integrar essas etapas em um sistema único e operante, e de defender as decisões técnicas que tomou ao construí-lo. Este último objetivo é o que a disciplina de fato avalia: um compilador não é a soma de seis exercícios independentes, e a competência que se pretende formar é a de sustentar um artefato inteiro, do texto de entrada ao resultado da execução.
Ementa
A ementa oficial do componente enuncia análise léxica, análise sintática, análise semântica, ambientes de execução, geração de código e projeto e implementação de um compilador. O detalhamento a seguir preserva integralmente esses tópicos e explicita a camada de linguagens formais e autômatos que, no enunciado oficial, aparece como pressuposto transversal e não como item autônomo — decisão coerente com o título do componente e com seus objetivos institucionais, que citam autômatos e gramáticas de forma explícita.
Cada subseção corresponde a um módulo de conteúdo, na ordem em que é oferecido. O último tópico da ementa oficial, o projeto e a implementação de um compilador, não recebe subseção própria por não ser um assunto entre outros: ele é o eixo que atravessa todos os módulos e se materializa no projeto integrador desenvolvido em grupos durante todo o período.
O sequenciamento adotado segue o consenso consolidado nos cursos de Ciência da Computação das universidades públicas brasileiras de maior tradição na área, entre elas as estaduais paulistas e as federais, e reflete a organização das obras de referência que compõem a bibliografia do componente. A ordem é a canônica da área: parte-se do que é regular, sobe-se ao que é livre de contexto e chega-se à tradução, de modo que cada resultado teórico esteja disponível no momento em que a construção precisa dele.
Linguagens formais e a arquitetura de um compilador
- Alfabetos, cadeias, operações sobre cadeias e a noção de linguagem como conjunto.
- Operações sobre linguagens: união, concatenação, fecho de Kleene.
- A hierarquia de Chomsky e a correspondência entre classes de gramáticas e classes de máquinas.
- Anatomia de um compilador: análise e síntese, front-end e back-end.
- As fases e o artefato que cada uma produz e consome.
- Compilação, interpretação e as formas intermediárias entre as duas.
Tratamento panorâmico e formalizante. O módulo estabelece o vocabulário e o mapa do percurso, e sua função é permitir que o estudante situe cada módulo seguinte dentro do todo.
Expressões regulares e linguagens regulares
- Sintaxe e semântica das expressões regulares; a linguagem denotada por uma expressão.
- Classes de caracteres, quantificadores e as abreviações de uso corrente.
- Propriedades de fechamento das linguagens regulares.
- Equivalência entre expressões distintas e a noção de linguagem denotada.
Tratamento operacional, com formalização. O estudante deve chegar ao fim do módulo escrevendo expressões corretas para especificações dadas e reconhecendo quando duas expressões denotam a mesma linguagem.
Autômatos finitos determinísticos
- Definição formal como quíntupla; função de transição total e estados de aceitação.
- Configuração, passo de computação e reconhecimento de cadeia.
- Projeto de autômatos para especificações dadas; a tabela de transição como estrutura de dados.
- Autômatos com estado de erro e o tratamento de entradas inválidas.
Tratamento formal e construtivo. O módulo exige que o estudante projete autômatos, e não apenas os simule, porque é a partir daqui que a tabela de transição passa a ser um objeto de programa.
Autômatos não determinísticos e a construção de Thompson
- Não determinismo, transições vazias e a noção de aceitação por existência de caminho.
- Fecho vazio e simulação de um autômato não determinístico.
- A construção de Thompson: de uma expressão regular a um autômato com transições vazias.
- Casos base e as composições para concatenação, união e fecho.
- Por que a construção é sistemática e o que isso significa para uma implementação.
Tratamento formal e construtivo. É o primeiro momento em que uma transformação teórica se apresenta como algoritmo diretamente implementável.
Determinização e minimização
- A construção de subconjuntos e a equivalência entre as duas famílias de autômatos.
- Explosão de estados: o custo do determinismo e quando ele importa na prática.
- Estados equivalentes, a relação de indistinguibilidade e o autômato mínimo.
- Algoritmos de minimização por refinamento de partições.
Tratamento formal, com demonstração de correção nos pontos em que ela é acessível ao público. O módulo fecha o ciclo que transforma uma especificação declarativa em uma máquina eficiente, e é o alicerce direto do analisador léxico.
O lema do bombeamento e os limites do reconhecimento regular
- Intuição: memória finita e a repetição forçada de estados em cadeias longas.
- Enunciado do lema e sua estrutura lógica como argumento de refutação.
- Aplicação a linguagens que não são regulares, com o caso dos delimitadores balanceados.
- O que o resultado autoriza a concluir e o que não autoriza.
Tratamento formal, com demonstração conduzida em aula. É o módulo que justifica a existência de tudo o que vem depois: sem um limite provado para o reconhecimento regular, a subida à análise sintática pareceria arbitrária.
Análise léxica
- Tokens, lexemas e padrões; o que o analisador léxico entrega ao analisador sintático.
- Especificação dos tokens de uma linguagem por expressões regulares.
- A regra do casamento mais longo e a resolução de conflitos entre padrões concorrentes.
- Tratamento de espaços, comentários e erros léxicos; posição no texto para relato de erro.
- Interação inicial com a tabela de símbolos.
Tratamento operacional e integrador. Aqui a máquina teórica dos módulos anteriores passa a ser um componente de software com interface definida.
Gramáticas livres de contexto
- Definição formal; derivações mais à esquerda e mais à direita; árvores de derivação.
- Ambiguidade: origem, consequências e técnicas de eliminação.
- Precedência e associatividade de operadores expressas na própria gramática.
- Transformações necessárias à análise descendente.
- Remoção de recursão à esquerda, direta e indireta.
- Fatoração à esquerda.
Tratamento formal e de projeto. O estudante precisa sair do módulo capaz de escrever uma gramática adequada, e não apenas de ler uma que lhe foi dada.
Autômatos de pilha
- Definição formal; a pilha como memória auxiliar de acesso restrito.
- Aceitação por estado final e por pilha vazia, e a equivalência entre os dois critérios.
- Equivalência entre autômatos de pilha e gramáticas livres de contexto.
- Determinismo e não determinismo nesta classe, e por que a distinção não é a mesma do caso finito.
Tratamento formal e conceitual. O módulo é o elo teórico entre a gramática e o analisador sintático, e sua realização concreta em código ocorre no módulo seguinte, no reconhecedor descendente.
Análise sintática descendente
- A estratégia descendente e a correspondência entre não terminais e procedimentos.
- Conjuntos de primeiros e de seguidores; construção e uso.
- A condição que caracteriza as gramáticas analisáveis com um símbolo de antecipação.
- Analisador recursivo-descendente e analisador preditivo dirigido por tabela.
- Detecção, relato e recuperação de erros sintáticos.
- Construção da árvore sintática abstrata como saída da análise.
Tratamento operacional e aprofundado. É o módulo de maior densidade de implementação do percurso e o que produz o analisador do artefato de referência.
Análise sintática ascendente
- A estratégia de deslocamento e redução; pilha de análise e handle.
- Itens, autômato de itens e a construção das tabelas de análise.
- As famílias de analisadores ascendentes e o poder de reconhecimento de cada uma.
- Conflitos e sua interpretação diagnóstica.
- Geradores de analisadores: o que automatizam e o que continua sendo decisão de projeto.
Tratamento conceitual e comparativo, com construção manual de tabelas em casos pequenos. O objetivo é que o estudante saiba escolher entre as duas estratégias com argumento técnico, mesmo tendo implementado apenas a descendente.
Análise semântica
- O que a sintaxe não captura: declaração antes do uso, compatibilidade de tipos, aridade.
- Tabela de símbolos: organização, escopo aninhado, inserção e consulta.
- Sistemas de tipos elementares; verificação, inferência local e conversão.
- Gramáticas de atributos e esquemas de tradução dirigidos pela sintaxe.
- Atributos sintetizados e herdados.
- Ordem de avaliação e sua relação com a estratégia de análise adotada.
- Qualidade das mensagens de erro semântico.
Tratamento formal e de implementação. O módulo introduz a única fase em que o compilador precisa manter conhecimento acumulado sobre o programa inteiro.
Ambientes de execução
- Organização da memória de um programa em execução: código, estática, pilha e área dinâmica.
- Registros de ativação; passagem de parâmetros, retorno e endereço de retorno.
- Escopo em tempo de execução e o acesso a nomes não locais.
- Alocação dinâmica e as estratégias de recuperação de memória, em panorama.
- Máquinas virtuais e modelos de execução baseados em pilha.
Tratamento operacional, com apoio na arquitetura já conhecida pelo estudante. O módulo é a ponte entre o que o compilador produz e o que a máquina executa.
Geração de código
- Representações intermediárias; código de três endereços e formas baseadas em pilha.
- Tradução da árvore sintática abstrata para a representação intermediária.
- Seleção de instruções e emissão do código objeto para uma máquina definida.
- Otimizações elementares e independentes de máquina.
- Propagação de constantes e dobramento de constantes.
- Eliminação de subexpressões comuns e de código morto.
- Redução de força em variáveis de indução.
- Avaliação do resultado: contagem de instruções emitidas e custo de execução.
Tratamento operacional e integrador. É o módulo que fecha o percurso, no qual o artefato passa a produzir algo executável e o estudante mede, em números, o efeito das decisões que tomou nas fases anteriores.
Bibliografia Básica
- LOUDEN, Kenneth C. Compiladores: princípios e práticas. São Paulo: Cengage Learning, 2004.
- BARBOSA, Cynthia da S. Compiladores. Porto Alegre: SAGAH, 2021.
- NETO, João José. Introdução à compilação. 1. ed. Rio de Janeiro: LTC, 1987.
Bibliografia Complementar
- AHO, Alfred V. et al. Compiladores: princípios, técnicas e ferramentas. 2. ed. São Paulo: Pearson Education do Brasil, 2008.
- SANTOS, Pedro R.; LANGLOIS, Thibault. Compiladores — da teoria à prática. Rio de Janeiro: Grupo GEN, 2018.
- SOUSA, Carlos E. B.; NASCIMENTO, Leonardo B. G.; MARTINS, Rafael L. et al. Linguagens formais e automáticas. Porto Alegre: Grupo A, 2021.
- MENEZES, Paulo B. Linguagens formais e autômatos. v. 3. 6. ed. Porto Alegre: Grupo A, 2011.
- HUMBERT, Georges L. H. et al. Linguagens formais e autômatos. 6. ed. Porto Alegre: Grupo A, 2011.
- HOPCROFT, John E.; MOTWANI, Rajeev; ULLMAN, Jeffrey D. Introdução à teoria de autômatos, linguagens e computação. Rio de Janeiro: Elsevier, 2002. Edição original: Introduction to Automata Theory, Languages, and Computation. 3. ed. Boston: Pearson/Addison-Wesley, 2006.
A bibliografia básica reproduz exatamente as obras registradas no projeto pedagógico do curso. Na complementar, a última entrada é um acréscimo deliberado do professor: trata-se da referência internacional de maior circulação para o eixo de linguagens formais e autômatos, e sua inclusão dá ao estudante o texto que ele encontrará citado fora do curso. O eixo já estava coberto pela obra brasileira que o projeto pedagógico registra; o acréscimo amplia o alcance, não supre uma ausência. Registre-se ainda que a obra de referência mais citada na área para a construção de compiladores figura na lista oficial como complementar, e não como básica.