flowchart LR
A["Leitura prévia<br/>do material do módulo"] --> B["Duas aulas teóricas<br/>exposição e discussão em duplas"]
B --> C["Primeira sessão de tutoria<br/>planejamento do incremento"]
C --> D["Segunda sessão de tutoria<br/>construção em pares"]
D --> E["Terceira sessão de tutoria<br/>testes e correção"]
E --> F["Quarta sessão de tutoria<br/>fechamento e registro no diário"]
F --> G["Entrega do incremento<br/>no repositório do grupo"]
G -.-> A
style B fill:#e8f4ea
style G fill:#f4ecdd
1 Projeto Integrador
1.1 O que é o Projeto Integrador
Ao longo deste semestre, o seu grupo vai construir um compilador. Não um exercício que simula um compilador, nem um trabalho final entregue na última semana: um programa real, construído peça por peça, que no fim lê um texto escrito em uma linguagem que vocês mesmos projetaram e produz algo executável a partir dele. A primeira peça é escrita no segundo módulo e ainda estará rodando no décimo quinto.
Essa é a razão de ser do Projeto Integrador. A teoria desta disciplina tem uma característica incômoda: ela é convincente no papel e escorregadia na cabeça. Ler a construção de subconjuntos e concordar que faz sentido é fácil; descobrir que o seu programa entra em laço porque você esqueceu de tratar as transições vazias é outra coisa completamente diferente, e é essa segunda experiência que produz entendimento durável. O projeto existe para forçar o encontro entre a definição formal e o caso concreto que não se comporta como a definição sugeria.
A regra que organiza tudo. A cada módulo, o seu grupo incorpora ao projeto exatamente aquilo que o módulo ensinou. Não há tarefa de projeto que não corresponda a um conteúdo teórico daquele módulo, e não há conteúdo teórico relevante que não apareça no projeto de alguma forma. Se em algum momento você não conseguir dizer que parte da aula daquele módulo a tarefa está exercitando, procure o professor: ou a conexão não ficou clara, ou o grupo está resolvendo o problema errado.
Vale registrar a hierarquia entre as duas coisas, porque ela costuma ser mal compreendida. O conteúdo teórico é o eixo da disciplina; o projeto existe para praticá-lo. Não é o contrário. Um grupo que produz um compilador impressionante sem conseguir explicar por que a determinização termina, ou por que a sua gramática não é ambígua, não cumpriu o objetivo da disciplina — apenas escreveu código. A pergunta que o professor fará em toda tutoria não é apenas se funciona, mas por que funciona.
O trabalho é feito em grupos de dois ou três integrantes, do primeiro ao último módulo, com a mesma composição. A permanência é intencional: parte do que se aprende aqui é sustentar decisões de arquitetura tomadas cedo, conviver com as consequências delas e negociar mudanças quando o custo de manter se torna maior que o de refazer. Essa é uma experiência que exercícios curtos e independentes não proporcionam, e é, com alguma frequência, a lembrança mais útil que a disciplina deixa.
O projeto também é o ponto em que várias práticas da disciplina se encontram. As sessões de tutoria funcionam em programação em pares, com revezamento de papéis. As entregas parciais passam por avaliação entre os próprios integrantes do grupo. O grau de orientação recebido diminui deliberadamente ao longo do semestre. E a linguagem que o grupo vai construir é escolhida pelo próprio grupo, dentro de restrições definidas, porque decidir o que construir faz parte do que se pretende ensinar.
1.2 O que o seu grupo vai construir
O professor construirá, ao longo das aulas teóricas, a sua própria implementação de referência: uma linguagem pequena para reconhecimento de padrões em texto, cujo compilador produz um motor de autômatos. Você acompanhará essa construção passo a passo e terá o resultado disponível como exemplo estudado. O projeto do seu grupo não é copiar essa implementação. É construir uma equivalente em capacidade, num domínio escolhido por vocês.
Essa escolha de domínio é a primeira decisão de projeto do semestre e será tomada no primeiro módulo, com validação do professor. A liberdade é real, mas não é ilimitada: a linguagem que o grupo projetar precisa exercitar toda a teoria da disciplina, e por isso deve satisfazer um conjunto de capacidades mínimas.
Contrato de capacidades da linguagem do grupo
A linguagem projetada pelo grupo, qualquer que seja o domínio, precisa necessariamente ter as seguintes características. Elas não descrevem como implementar nada — descrevem o que a linguagem tem de ser capaz de exprimir, para que o compilador dela exercite todo o conteúdo do semestre.
Precisa ter símbolos léxicos de mais de uma categoria, incluindo pelo menos uma categoria cuja forma seja descrita por uma notação de padrões — números, identificadores, cadeias de texto ou algo análogo. Sem isso não há o que reconhecer com autômatos finitos.
Precisa ter uma construção aninhada, em que um elemento contenha outro do mesmo tipo, com profundidade arbitrária. Expressões dentro de expressões, blocos dentro de blocos, agrupamentos com delimitadores. Sem isso a linguagem seria regular e o analisador sintático não teria função.
Precisa ter nomes que sejam declarados em um ponto e usados em outro, de modo que exista uma verificação possível de que o nome usado foi de fato declarado. Sem isso não há tabela de símbolos nem análise semântica.
Precisa ter mais de um tipo de valor, com pelo menos uma operação que só faça sentido sobre um deles. Sem isso não há verificação de tipos.
Precisa produzir um efeito observável quando executada sobre alguma entrada. Sem isso não há geração de código nem execução para demonstrar.
Precisa ser pequena. Uma linguagem com trinta construções distintas garante que o grupo não terminará o semestre. O critério de tamanho é rigoroso e será cobrado na validação do primeiro módulo: se a especificação não couber em duas páginas, está grande demais.
Domínios que costumam funcionar bem são os que descrevem regras sobre dados — filtragem e transformação de registros, descrição de layouts, roteiros de automação simples, definição de máquinas de estado, geração de relatórios a partir de consultas. Domínios que costumam dar errado são os que exigem semântica complicada demais para o prazo, como qualquer coisa que envolva funções definidas pelo usuário com recursão, sistemas de tipos com inferência ou concorrência. O professor recusará propostas fora da faixa, e recusará no primeiro módulo justamente para que a correção custe pouco.
1.3 O ambiente de trabalho
O projeto é desenvolvido em C++, compilado com o toolchain da Microsoft em ambiente Windows nativo, a partir do Visual Studio Code. A escolha da linguagem de implementação é deliberada: um compilador manipula estruturas com muitas referências cruzadas e ciclos, e fazê-lo em uma linguagem que expõe a gestão de memória obriga o grupo a tomar decisões explícitas de representação — decisões que uma linguagem com coleta automática de lixo esconderia. Esse custo é parte do exercício.
O código deve ser fortemente e explicitamente tipado, e precisa compilar sem nenhum aviso sob o modo estrito exigido pela disciplina. Avisos do compilador não são ruído a ignorar: em um projeto que cresce durante quinze módulos, o aviso de hoje é o defeito silencioso de dali a dois meses. O professor informará a configuração exata a ser usada no primeiro módulo, e ela é obrigatória desde o primeiro incremento.
Nenhum gerador automático de analisadores léxicos ou sintáticos pode ser usado no projeto. A restrição é o ponto central da disciplina: quem gera o analisador com uma ferramenta aprende a usar a ferramenta, e quem o constrói aprende a teoria que a ferramenta implementa. As ferramentas serão estudadas nos módulos correspondentes, e você sairá sabendo o que elas fazem — mas o projeto é construído à mão. Bibliotecas de uso geral da linguagem de implementação são permitidas normalmente; bibliotecas que resolvam qualquer etapa da compilação, não.
1.4 A dinâmica do trabalho
Cada módulo tem seis aulas. As duas primeiras são de exposição teórica; as quatro seguintes são de tutoria, e é nelas que o projeto avança. O professor circula entre os grupos durante a tutoria, e o formato dessa circulação muda ao longo do semestre, como será explicado adiante.
O ciclo é inteiramente contido no horário de aula, e as duas aulas teóricas são construídas para funcionar com quem chega sem ter lido nada. O material escrito do módulo fica disponível como referência permanente, e o momento mais produtivo de recorrer a ele costuma ser durante a tutoria, quando a dúvida é concreta e tem endereço: é bem mais eficiente procurar a definição de que você precisa naquele instante do que tentar absorver tudo de antemão.
A primeira sessão de tutoria de cada módulo é de planejamento. O grupo define o que exatamente vai construir naquele módulo, como saberá que funcionou, e como o trabalho será dividido. Essa sessão parece a menos produtiva e é a que mais economiza tempo: grupos que começam a escrever código sem acordo prévio sobre o que estão construindo produzem duas metades que não se encaixam. As duas sessões intermediárias são de construção e de teste. A última é de fechamento — correções finais, atualização da documentação e registro no diário de atividades.
1.4.1 Papéis dentro do grupo
O trabalho nas sessões de tutoria é feito em programação em pares, com revezamento obrigatório de papéis. Não é uma sugestão de organização: é uma exigência, e o professor observará seu cumprimento durante a tutoria.
flowchart TD
subgraph TRIO["Grupo de três integrantes"]
P["Piloto<br/>escreve o código<br/>e verbaliza o que faz"]
N["Navegador<br/>revisa em tempo real<br/>antecipa erros e próximos passos"]
R["Revisor<br/>consulta o material do módulo<br/>e cuida dos casos de teste"]
end
P -->|"revezamento a cada trecho curto"| N
N -->|"revezamento a cada trecho curto"| R
R -->|"revezamento a cada trecho curto"| P
TRIO --> D["Diário de atividades<br/>quem fez o quê, o que travou,<br/>que decisão foi tomada"]
D --> E["Entrega do módulo"]
OBS["Em grupos de dois integrantes<br/>o papel de revisor é absorvido<br/>alternadamente pelos outros dois"]
OBS -.-> TRIO
O piloto escreve e verbaliza o que está fazendo, em voz alta, mesmo que pareça desnecessário. O navegador acompanha, revisa em tempo real, aponta o que vai dar errado antes que dê, e pensa no passo seguinte enquanto o piloto executa o atual. Em grupos de três, o terceiro integrante consulta o material do módulo e cuida dos casos de teste, o que evita que a dupla se feche em uma solução sem confrontá-la com a teoria.
O revezamento acontece em intervalos curtos, e a razão é direta: o objetivo do projeto é que os dois ou três integrantes aprendam a construir um compilador, não que o grupo entregue um compilador. Um grupo em que um integrante programa e os outros assistem produzirá provavelmente um bom artefato e certamente um mau resultado de aprendizagem — e a avaliação por pares, aplicada nas entregas parcial e final, existe em boa parte para tornar essa situação visível.
1.4.2 O andaime que diminui
O grau de orientação que o grupo recebe não é constante ao longo do semestre. Ele começa alto e diminui de propósito.
flowchart LR
subgraph F1["Módulos iniciais"]
A1["Roteiro detalhado do incremento"]
A2["Critérios de aceitação fornecidos"]
A3["Tutoria frequente e próxima"]
end
subgraph F2["Módulos intermediários"]
B1["Objetivo do incremento definido<br/>caminho escolhido pelo grupo"]
B2["Critérios de aceitação<br/>propostos pelo grupo e validados"]
B3["Tutoria sob demanda"]
end
subgraph F3["Módulos finais"]
C1["Apenas o resultado esperado"]
C2["Grupo define escopo,<br/>critérios e verificação"]
C3["Tutoria como revisão crítica"]
end
F1 ==>|"o apoio diminui"| F2 ==>|"a autonomia cresce"| F3
style F1 fill:#e8f4ea
style F3 fill:#f4ecdd
Nos módulos iniciais, a tarefa do projeto vem descrita com detalhe, os critérios de aceitação são fornecidos pelo professor e a tutoria é próxima e frequente. Nos módulos intermediários, o objetivo do incremento continua definido, mas o caminho passa a ser escolhido pelo grupo, e os critérios de aceitação passam a ser propostos pelo grupo e validados pelo professor. Nos módulos finais, apenas o resultado esperado é enunciado: o grupo define o escopo, decide como verificar e responde pelas consequências, e a tutoria funciona como revisão crítica do que já foi decidido.
Essa redução progressiva é intencional e não é abandono. Se em um módulo final você sentir que a orientação sumiu, é porque sumiu mesmo — e é esse o ponto. A capacidade de tocar uma etapa de projeto sem roteiro é um dos resultados que a disciplina persegue, e ela só se desenvolve quando o roteiro deixa de existir.
1.5 A estrutura do repositório
Todo grupo mantém um repositório com a mesma estrutura de raiz, para que o professor consiga acompanhar quinze projetos diferentes sem procurar arquivos.
flowchart TD
RAIZ["Repositório do grupo"]
RAIZ --> RM["README.md<br/>identificação do grupo, domínio escolhido,<br/>como compilar e como executar,<br/>estado atual do projeto"]
RAIZ --> DOCS["docs/<br/>tudo que não é código"]
RAIZ --> SRC["src/<br/>código-fonte"]
DOCS --> D1["especificação da linguagem do grupo"]
DOCS --> D2["diário de atividades"]
DOCS --> D3["relatórios teóricos dos módulos<br/>sem tarefa de implementação"]
DOCS --> D4["diagramas gerados pela ferramenta"]
DOCS --> D5["registro de decisões de projeto"]
SRC --> S1["organização interna definida<br/>pelo próprio grupo"]
SRC --> S2["casos de teste do grupo"]
style RM fill:#f4ecdd
style S1 fill:#e8f4ea
Na raiz fica o arquivo de instruções gerais, que identifica o grupo e os integrantes, descreve o domínio escolhido, explica como compilar e como executar o projeto e registra o estado atual — o que já funciona e o que ainda não. Esse arquivo é a primeira coisa que o professor lê a cada entrega, e mantê-lo desatualizado é a forma mais barata de perder ponto por pontualidade.
A pasta de documentos guarda tudo que não é código: a especificação da linguagem do grupo, o diário de atividades, os relatórios teóricos dos módulos sem tarefa de implementação, os diagramas gerados pela própria ferramenta do grupo e o registro das decisões de projeto. Esse último merece destaque porque costuma ser negligenciado: quando o grupo escolhe entre duas alternativas, o registro de que a escolha existiu, de quais eram as opções e de por que uma foi preferida vale mais, na avaliação, do que a escolha em si.
A pasta de código-fonte tem organização interna livre. O professor não prescreverá como o grupo divide seu código — essa é uma decisão de projeto, e decisões de projeto são avaliadas, não ditadas. O que se espera é que a organização seja coerente, que o grupo consiga justificá-la, e que ela acomode o crescimento do projeto sem exigir reescrita a cada módulo. Os casos de teste do grupo também vivem ali, e sua existência é verificada em toda entrega.
1.6 As entregas módulo a módulo
O quadro geral das entregas, com os três marcos de consolidação, é o seguinte.
flowchart TD
INICIO(["Formação dos grupos<br/>e escolha do domínio"]) --> B1
subgraph B1["Bloco 1 — reconhecimento de padrões"]
M01["Módulo 1<br/>proposta e ambiente"]
M02["Módulo 2<br/>especificação léxica"]
M03["Módulo 3<br/>reconhecedor determinístico"]
M04["Módulo 4<br/>tradução da notação"]
M05["Módulo 5<br/>pipeline completo e visualização"]
M06["Módulo 6<br/>relatório de limites"]
M07["Módulo 7<br/>analisador léxico"]
end
subgraph B2["Bloco 2 — estrutura"]
M08["Módulo 8<br/>gramática da linguagem"]
M09["Módulo 9<br/>fundamentação teórica"]
M10["Módulo 10<br/>analisador sintático"]
M11["Módulo 11<br/>estudo comparativo"]
end
subgraph B3["Bloco 3 — síntese"]
M12["Módulo 12<br/>verificações de sentido"]
M13["Módulo 13<br/>formato do objeto"]
M14["Módulo 14<br/>geração de código"]
M15["Módulo 15<br/>integração final"]
end
M01 --> M02 --> M03 --> M04 --> M05 --> M06 --> M07
M07 ==> MARCO1{{"MARCO 1<br/>entrega parcial consolidada<br/>com avaliação por pares"}}
MARCO1 --> M08 --> M09 --> M10
M10 ==> MARCO2{{"MARCO 2<br/>front-end completo"}}
MARCO2 --> M11 --> M12 --> M13 --> M14 --> M15
M15 ==> MARCO3{{"MARCO 3<br/>entrega final e apresentação<br/>com avaliação por pares"}}
style MARCO1 fill:#f4ecdd
style MARCO2 fill:#f4ecdd
style MARCO3 fill:#e8f4ea
Cada módulo tem uma entrega. Além delas, três pontos concentram consolidação e avaliação mais pesada: o fim do módulo 7, com o reconhecimento de padrões completo; o fim do módulo 10, com o front-end inteiro operacional; e o fim do módulo 15, com o compilador completo e a apresentação final.
1.6.1 Módulo 1: Panorama da Compilação e Linguagens Formais
O módulo em que o grupo se forma e decide o que vai construir pelos próximos quatro meses. É a decisão mais consequente do semestre e a que se toma com menos informação disponível — situação que se repetirá na vida profissional com frequência incômoda.
O trabalho começa pela formação do grupo, de dois ou três integrantes, com composição fixa para todo o semestre. Em seguida, o grupo escolhe o domínio da sua linguagem. A escolha deve ser argumentada, não apenas anunciada: o grupo precisa mostrar que o domínio escolhido comporta as capacidades exigidas pelo contrato apresentado anteriormente, e precisa apresentar, em texto, dois ou três exemplos de como seriam programas escritos nessa linguagem — não a gramática, que ainda não existe, mas a aparência pretendida. Escrever esses exemplos antes de qualquer formalização é a prática usual em projeto de linguagens e revela cedo se a ideia se sustenta.
O grupo também configura o ambiente de trabalho, verifica que consegue compilar e executar um programa mínimo com o modo estrito exigido, e cria o repositório com a estrutura de pastas definida.
Entrega do módulo 1: repositório criado com a estrutura de pastas exigida; arquivo de instruções gerais preenchido com a identificação do grupo e do domínio escolhido; documento de proposta contendo a justificativa do domínio, a demonstração de que ele atende ao contrato de capacidades e os exemplos de programas pretendidos; e evidência de que o ambiente compila e executa com o modo estrito ativo. A proposta será validada pelo professor, e pode ser recusada — se for, o grupo tem até o módulo seguinte para ajustá-la.
1.6.2 Módulo 2: Alfabetos, Linguagens e Expressões Regulares
Com o domínio definido, o grupo precisa dizer com precisão que sequências de caracteres a sua linguagem aceita. É aqui que a intuição do módulo anterior vira especificação.
O trabalho consiste em identificar as categorias de símbolos léxicos da linguagem do grupo e descrever cada uma delas usando a notação de expressões regulares estudada no módulo. Essa descrição precisa ser completa e precisa: não basta dizer que a linguagem tem números, é preciso dizer exatamente que sequências de caracteres formam um número válido, o que acontece com sinal, com parte decimal, com zeros à esquerda. Cada decisão dessas é uma decisão de projeto de linguagem, e cada uma tem consequências que aparecerão mais adiante.
O grupo deve também produzir, para cada categoria, um conjunto de cadeias que devem ser aceitas e um conjunto de cadeias que devem ser rejeitadas — incluindo casos de fronteira escolhidos deliberadamente para serem difíceis. Esse conjunto será o critério de verificação usado nos módulos seguintes, e construí-lo antes de qualquer implementação é o que permite saber, depois, se o que foi construído está certo.
Entrega do módulo 2: documento de especificação léxica da linguagem do grupo, com todas as categorias de símbolos descritas em notação de expressões regulares, acompanhado do conjunto de cadeias de aceitação e de rejeição para cada categoria, com os casos de fronteira identificados como tal. Nenhum código é exigido neste módulo; o que se avalia é a precisão da especificação.
1.6.3 Módulo 3: Autômatos Finitos Determinísticos
Primeiro código do projeto. E, propositalmente, um código que ainda não usa nada automático: o grupo vai construir à mão o autômato de uma das categorias de símbolos que especificou, para sentir na prática o que a construção automática dos módulos seguintes fará por ele.
O trabalho tem duas partes. Na primeira, o grupo escolhe uma das categorias léxicas da sua especificação — de preferência uma não trivial, com pelo menos um ponto de decisão — e projeta manualmente o autômato finito determinístico que a reconhece, desenhando o diagrama de estados e derivando dele a tabela de transição. Esse projeto manual é entregue como documento e é onde o professor verifica se o grupo entendeu de fato o modelo.
Na segunda parte, o grupo implementa o reconhecedor: um programa que, dada a descrição do autômato e uma cadeia, decide se a cadeia é aceita. A forma de representar a descrição do autômato e de organizar o reconhecimento é decisão do grupo, e será discutida na tutoria — há escolhas melhores e piores, e descobrir a diferença faz parte do exercício. O reconhecedor é então verificado contra o conjunto de cadeias de aceitação e rejeição produzido no módulo anterior.
Entrega do módulo 3: documento com o diagrama de estados e a tabela de transição do autômato projetado à mão, com justificativa das escolhas; código do reconhecedor funcionando; e registro da execução do reconhecedor sobre o conjunto de cadeias do módulo 2, mostrando quais foram aceitas e quais rejeitadas. Casos em que o resultado diverge do esperado devem ser registrados, não escondidos — divergência documentada e compreendida vale mais que resultado limpo sem explicação.
1.6.4 Módulo 4: Não Determinismo e a Construção de Thompson
O módulo em que o projeto deixa de depender de autômatos desenhados à mão. A partir daqui, o grupo escreve a expressão regular e a máquina aparece sozinha.
O trabalho consiste em implementar a tradução automática de uma expressão regular para o autômato não determinístico correspondente, seguindo a construção estudada no módulo. Antes disso, porém, é preciso que o programa consiga ler a própria expressão regular e entender sua estrutura — o que significa que o grupo precisará construir um pequeno analisador para a notação de expressões regulares que decidiu suportar. Esse é o primeiro momento em que o projeto tem um analisador dentro de si, e vale notar a circularidade: vocês estão escrevendo um programa que lê uma notação para depois processar textos escritos em outra notação.
O grupo deve decidir, e documentar, quais operadores da notação de expressões regulares a sua ferramenta suportará. Não é preciso suportar tudo; é preciso suportar o suficiente para descrever as categorias léxicas especificadas no módulo 2, e é preciso que a decisão seja consciente.
O autômato não determinístico pode ser executado, desde que se acompanhe um conjunto de estados em vez de um único — e é assim que o grupo verifica a tradução, confrontando o autômato gerado com o que construiu à mão no módulo anterior. O que essa forma de execução não é, é eficiente: ela refaz a cada entrada um trabalho que poderia ser feito uma vez só, e esse desperdício é exatamente o que o módulo seguinte elimina.
Entrega do módulo 4: código que lê uma expressão regular e produz o autômato não determinístico correspondente; documento registrando quais operadores da notação foram suportados e por quê; e evidência de que a tradução funciona para as categorias léxicas da linguagem do grupo — cabendo ao grupo escolher e justificar a forma dessa evidência.
1.6.5 Módulo 5: Determinização e Minimização
O módulo que fecha o motor de reconhecimento de padrões. Ao final dele, o grupo terá uma ferramenta que recebe uma expressão regular e devolve um autômato determinístico mínimo, executável e visualizável — e é uma ferramenta genuinamente útil, do tipo que existe dentro de todo compilador em uso no mundo.
O trabalho tem três partes encadeadas. A primeira é implementar a conversão do autômato não determinístico em determinístico, conforme o algoritmo estudado, com o tratamento correto das transições vazias. A segunda é implementar a minimização, reduzindo o autômato determinístico ao menor equivalente. A terceira é implementar a exportação do autômato para um formato de visualização gráfica, de modo que o grupo consiga olhar o resultado em vez de apenas confiar nele.
Essa terceira parte parece acessória e não é: a partir daqui, quando algo der errado no reconhecimento, a diferença entre um grupo que consegue visualizar o autômato e um que não consegue será a diferença entre depurar em uma tarde e depurar em uma semana.
O grupo deve medir e registrar o número de estados em cada etapa — no não determinístico, no determinístico e no mínimo — para cada uma das suas categorias léxicas. Esses números são a evidência concreta do crescimento discutido em aula e serão retomados na apresentação final.
Entrega do módulo 5: ferramenta completa que converte expressão regular em autômato determinístico mínimo; exportação visual funcionando, com os diagramas gerados salvos na pasta de documentos; tabela com a contagem de estados nas três etapas para cada categoria léxica da linguagem do grupo; e verificação de que o autômato mínimo aceita e rejeita exatamente as mesmas cadeias que o reconhecedor do módulo 3, no caso da categoria que foi feita à mão.
1.6.6 Módulo 6: Limites das Linguagens Regulares
O módulo em que o grupo descobre, formalmente e na prática, o que a ferramenta que acabou de construir não consegue fazer. É um módulo de demonstração matemática e de experimento, e a combinação dos dois é o ponto.
A parte formal consiste em identificar, dentro da linguagem que o grupo está projetando, alguma construção que não seja regular — tipicamente a construção aninhada exigida pelo contrato de capacidades — e demonstrar rigorosamente que ela não pode ser reconhecida por autômato finito. A demonstração deve seguir a técnica estudada em aula, com todos os passos explícitos e a estrutura lógica correta. Demonstrações incompletas ou com a ordem dos quantificadores trocada serão devolvidas para correção, porque uma prova “quase certa” não prova nada.
A parte experimental consiste em confrontar a ferramenta do módulo 5 com essa construção: escrever a expressão regular que o grupo tentaria usar, observar o comportamento e documentar exatamente como e por que falha. A conexão entre as duas partes é o que se avalia — o experimento sozinho é anedota, a prova sozinha é abstração, e juntas são entendimento.
O grupo deve fechar o documento explicando qual consequência isso tem para o projeto: que parte da linguagem precisará de um mecanismo mais forte, e onde ele entrará.
Entrega do módulo 6: documento contendo a demonstração formal de não regularidade da construção escolhida, o registro do experimento com a ferramenta do grupo, a articulação entre os dois e a conclusão sobre o que isso implica para os próximos módulos do projeto. O código usado no experimento acompanha a entrega, ainda que seja pequeno.
1.6.7 Módulo 7: Análise Léxica
Marco de consolidação. Tudo que foi construído desde o módulo 2 se junta aqui em uma peça com nome próprio, e o grupo passa a ter a primeira fase de um compilador funcionando de verdade.
O trabalho consiste em construir o analisador léxico completo da linguagem do grupo: um componente que recebe o texto de um programa e produz a sequência de símbolos léxicos correspondente, reutilizando o motor de autômatos já pronto. As decisões práticas estudadas no módulo precisam todas aparecer — o desempate entre padrões que casam a mesma entrada, o tratamento de espaços e comentários, a detecção do fim da entrada, e a produção de mensagens de erro que informem posição e causa provável quando o texto contiver algo que nenhuma categoria reconhece.
A qualidade das mensagens de erro é critério de avaliação a partir deste módulo, e não um detalhe estético. Um analisador que diz apenas que houve erro é tecnicamente correto e praticamente inútil.
Como este módulo encerra o primeiro bloco, a entrega é consolidada: além do incremento do módulo, o grupo revisa o que foi produzido desde o início, atualiza a documentação acumulada e apresenta o conjunto como uma unidade coerente. A avaliação por pares entre os integrantes acontece nesta entrega.
Entrega do módulo 7 — consolidação parcial: analisador léxico completo da linguagem do grupo, funcionando sobre programas de exemplo reais; conjunto de casos de teste cobrindo todas as categorias léxicas e os casos de erro; documentação atualizada de tudo que foi produzido do módulo 1 ao 7, incluindo a especificação léxica revisada; diário de atividades em dia; e a avaliação por pares preenchida por cada integrante. Esta é a entrega mais pesada da primeira metade e o professor a avaliará com o mesmo rigor da entrega final.
1.6.8 Módulo 8: Gramáticas Livres de Contexto
Segundo bloco. O grupo passa a descrever não mais as palavras da sua linguagem, mas a forma como elas se combinam — e descobre que essa descrição é mais difícil de acertar do que parecia.
O trabalho consiste em escrever a gramática completa da linguagem do grupo, usando o formalismo estudado no módulo. A gramática precisa ser não ambígua, e o grupo precisa argumentar por que ela é — argumento que, para gramáticas pequenas, normalmente passa pela forma como a precedência e a associatividade dos operadores foram estratificadas. Se a linguagem do grupo tiver operadores com precedências diferentes, essa estratificação é exigida e será verificada.
O grupo deve também produzir, para pelo menos três programas de exemplo da sua linguagem, a árvore de derivação completa, desenhada à mão ou gerada por ferramenta de desenho. Esse exercício revela erros na gramática que a leitura não revela, e é frequente que grupos descubram ambiguidades justamente ao tentar desenhar a segunda árvore de um mesmo programa.
Uma advertência que a experiência recomenda: é neste módulo que muitos grupos percebem que a linguagem que projetaram no módulo 1 é maior do que conseguirão implementar. Perceber isso agora é bom. Reduzir o escopo aqui, com a gramática na mão e o professor por perto, custa uma sessão de tutoria; perceber no módulo 13 custa o semestre.
Entrega do módulo 8: gramática completa da linguagem do grupo, com todas as produções, acompanhada do argumento de não ambiguidade e da justificativa das escolhas de precedência e associatividade; árvores de derivação de pelo menos três programas de exemplo; e, se houve redução de escopo em relação à proposta original, o registro da mudança e do motivo.
1.6.9 Módulo 9: Autômatos de Pilha
Módulo sem tarefa de implementação. Este é um dos dois módulos do semestre em que o projeto não recebe código novo. O conteúdo aqui é o modelo formal correspondente às gramáticas do módulo anterior, e sua realização concreta no projeto é o analisador sintático do módulo 10. A entrega deste módulo é teórica, e as sessões de tutoria são usadas para consolidar pendências acumuladas e para preparar o módulo seguinte, que é o mais exigente do semestre.
O trabalho consiste em produzir um documento de fundamentação que conecte a gramática escrita no módulo 8 ao modelo de máquina estudado neste. Concretamente, o grupo deve explicar como a sua gramática se traduziria em um autômato de pilha, seguindo a construção vista em aula, e ilustrar essa tradução com o traçado manual do reconhecimento de um programa curto da sua própria linguagem — mostrando o conteúdo da pilha a cada passo. O traçado é feito à mão, em tabela, e é exatamente o exercício que torna o módulo seguinte compreensível em vez de mágico.
O grupo deve também discutir, com base no conteúdo do módulo, por que a análise sintática prática se restringe a subclasses determinísticas, e o que isso significa para as escolhas que terá de fazer no módulo 10.
Recomenda-se aproveitar as sessões de tutoria deste módulo para saldar dívidas: casos de erro do analisador léxico que ficaram sem tratamento, documentação atrasada, testes que nunca foram escritos. O módulo 10 é o mais denso do semestre e não é um bom lugar para carregar pendências.
Entrega do módulo 9: documento de fundamentação com a tradução da gramática do grupo para o modelo de pilha, o traçado manual do reconhecimento de um programa curto com a evolução da pilha passo a passo, e a discussão sobre determinismo e suas consequências para o projeto. Adicionalmente, o registro do que foi saldado em pendências durante a tutoria.
1.6.10 Módulo 10: Análise Sintática Descendente
O módulo mais pesado do semestre, e o segundo marco de consolidação. Ao final dele, o grupo terá o front-end completo: um programa que lê texto e produz estrutura.
O trabalho começa pela preparação da gramática. A gramática escrita no módulo 8 provavelmente não está na forma exigida pelo método de análise adotado, e o grupo precisará eliminar recursão à esquerda e aplicar fatoração onde for necessário, documentando cada transformação e verificando que a linguagem gerada não mudou. Em seguida, o grupo calcula os conjuntos que orientam as decisões do analisador e verifica se a gramática satisfaz a condição estudada. Se não satisfizer, o conflito encontrado precisa ser interpretado e resolvido — e a interpretação do conflito é, aqui, mais valiosa que a solução.
A implementação segue o método de descida recursiva estudado em aula. O grupo deve produzir também a estrutura em árvore que representa o programa analisado, distinta da árvore de derivação concreta, contendo apenas o que as fases seguintes precisarão. Decidir o que entra e o que sai dessa estrutura é uma decisão de projeto relevante e será discutida na tutoria.
Por fim, o analisador precisa recuperar-se de erros sintáticos, continuando a análise depois do primeiro problema encontrado em vez de abortar. O critério de qualidade discutido em aula vale aqui: reportar um erro real seguido de vinte erros inventados é pior do que reportar só o primeiro.
Entrega do módulo 10 — consolidação: gramática transformada, com o registro de cada transformação e a verificação de equivalência; cálculo dos conjuntos que orientam a análise, apresentado em tabela; analisador sintático funcionando sobre programas de exemplo, produzindo a estrutura em árvore; recuperação de erros sintáticos implementada, com exemplos de programas malformados e as mensagens produzidas; e o front-end completo demonstrado ponta a ponta, do texto de entrada à árvore.
1.6.11 Módulo 11: Análise Sintática Ascendente
Módulo sem tarefa de implementação. Este é o segundo e último módulo do semestre sem código novo no projeto. O método estudado aqui é o que a maioria dos compiladores de produção usa, mas o projeto segue deliberadamente o caminho do módulo anterior, e por isso este módulo é de formação conceitual. A entrega é um estudo, e a tutoria é usada para consolidação e para o início do planejamento do terceiro bloco.
O trabalho consiste em produzir um estudo comparativo fundamentado, aplicado à gramática do próprio grupo. Concretamente, o grupo deve tomar um recorte pequeno da sua gramática — três ou quatro produções, escolhidas por conterem algum ponto de decisão interessante — e construir manualmente, com lápis e papel, a tabela de análise ascendente correspondente, seguindo o método estudado. Se aparecerem conflitos, eles devem ser identificados, classificados e explicados.
Sobre essa base concreta, o grupo escreve a análise comparativa: o que o método ascendente resolveria melhor no caso da gramática deles, o que custaria mais, e qual teria sido a escolha se o projeto não tivesse a restrição pedagógica de construir tudo à mão. A comparação precisa ser específica à gramática do grupo, não genérica — afirmações que valeriam para qualquer projeto não demonstram entendimento.
As sessões de tutoria são usadas para revisar o front-end à luz do que virá e para planejar o terceiro bloco, cuja característica é que as três fases restantes dependem umas das outras de forma mais rígida do que as anteriores.
Entrega do módulo 11: estudo comparativo contendo a tabela de análise ascendente construída à mão para o recorte escolhido da gramática do grupo, a identificação e explicação de eventuais conflitos, e a análise comparativa específica entre os dois métodos aplicada ao caso do grupo. Adicionalmente, o plano do grupo para os módulos 12 a 15, com a divisão prevista do trabalho.
1.6.12 Módulo 12: Análise Semântica
Terceiro bloco. O compilador do grupo passa a verificar não apenas se o programa está bem formado, mas se ele faz sentido.
O trabalho consiste em construir a tabela de símbolos da linguagem do grupo e implementar as verificações semânticas que o contrato de capacidades exige. Concretamente, o compilador precisa detectar o uso de um nome que não foi declarado, e precisa detectar a aplicação de uma operação a um valor de tipo incompatível. Se a linguagem do grupo tiver escopos aninhados, a tabela precisa tratá-los; se não tiver, o grupo deve registrar essa característica da sua linguagem e justificá-la.
As verificações são organizadas como percursos sobre a estrutura em árvore produzida no módulo 10. Que informação cada percurso coleta, quantos percursos são necessários e em que ordem eles ocorrem são decisões de projeto do grupo, discutidas na tutoria.
Como nos módulos anteriores, a qualidade do relato de erro é avaliada. Um erro semântico bem reportado indica o nome envolvido, o ponto do programa e a natureza do problema. O compilador também deve continuar após o primeiro erro semântico, reportando os demais, em vez de parar no primeiro.
Entrega do módulo 12: tabela de símbolos implementada, com o tratamento de escopo adequado à linguagem do grupo; verificações de declaração e de compatibilidade de tipos funcionando; conjunto de programas de exemplo contendo erros semânticos deliberados, acompanhado das mensagens que o compilador produz para cada um; e documento registrando as decisões de projeto sobre a organização dos percursos.
1.6.13 Módulo 13: Representações Intermediárias e Ambientes de Execução
O módulo de projeto, no sentido mais literal: quase todo o trabalho é decidir e documentar, e o código que resulta é a consequência dessas decisões.
O trabalho tem duas frentes. A primeira é definir a representação intermediária que o compilador do grupo usará entre a análise e a geração de código, com a justificativa da escolha à luz das alternativas estudadas e das características da linguagem do grupo. A segunda é especificar o formato do programa objeto que o compilador produzirá e o modelo de execução que o interpretará — o que o objeto contém, como é organizado, e o que acontece quando é executado.
Essa especificação é um documento formal e precisa ser completa o bastante para que outra pessoa consiga, lendo apenas ela, escrever um executor compatível. Esse critério é o teste de qualidade da entrega e será aplicado literalmente: o professor lerá a especificação procurando pelo que falta.
A implementação deste módulo é a tradução da estrutura em árvore verificada para a representação intermediária escolhida. A geração do objeto final vem no módulo seguinte.
Entrega do módulo 13: documento de especificação do formato do programa objeto e do modelo de execução, completo o bastante para permitir implementação independente; documento justificando a escolha da representação intermediária; e a tradução da árvore verificada para a representação intermediária implementada e demonstrada sobre programas de exemplo.
1.6.14 Módulo 14: Geração de Código
O compilador começa a produzir saída. A partir deste módulo existe um artefato que não é mais uma estrutura interna, e sim um arquivo que representa o programa traduzido.
O trabalho consiste em implementar o gerador que percorre a representação intermediária do módulo anterior e emite o programa objeto no formato especificado. Se a linguagem do grupo tiver operadores lógicos, a avaliação com curto-circuito deve ser tratada, o que exige emissão de desvios e não apenas de operações — é o ponto do módulo em que a maioria dos grupos encontra dificuldade, e convém enfrentá-lo cedo na tutoria.
O grupo deve também implementar um executor mínimo, capaz de rodar o objeto gerado sobre uma entrada simples e produzir o efeito observável exigido pelo contrato de capacidades. Mínimo, aqui, significa suficiente para demonstrar que o objeto está correto; o executor completo, com todo o tratamento de erro e de casos de fronteira, é assunto do módulo 15.
Para os grupos cuja linguagem envolva reconhecimento de padrões, este é o módulo em que os autômatos construídos no primeiro bloco reaparecem dentro do arquivo gerado — situação que vale documentar explicitamente na entrega, porque é a evidência mais direta da unidade da disciplina.
Entrega do módulo 14: gerador de código funcionando, produzindo o objeto no formato especificado no módulo 13; executor mínimo capaz de rodar o objeto; demonstração de pelo menos três programas da linguagem do grupo compilados e executados, com a entrada e a saída registradas; e o objeto gerado para esses programas, salvo na pasta de documentos para inspeção.
1.6.15 Módulo 15: Otimização e Integração Final
Último módulo. O compilador fica pronto, o grupo mede o que construiu e apresenta o resultado.
O trabalho tem três frentes. A primeira é a otimização: o grupo identifica os blocos básicos na representação intermediária, constrói o grafo de fluxo de controle e implementa pelo menos duas das transformações locais estudadas em aula, verificando em cada caso que a semântica do programa foi preservada. A escolha de quais transformações implementar é do grupo e deve ser justificada pelo que faz sentido na linguagem que projetaram.
A segunda é a integração final: o executor completo, com todo o tratamento de erro, rodando sobre entradas reais e não apenas sobre exemplos preparados. Todas as fases funcionando em sequência, do texto de entrada ao efeito observável, com mensagens de erro adequadas em qualquer ponto em que algo possa dar errado.
A terceira é a consolidação da documentação e a preparação da apresentação. O grupo revisa todo o material produzido ao longo do semestre, atualiza o que ficou defasado, e prepara a demonstração final segundo as orientações da última seção deste documento.
Entrega do módulo 15 — entrega final: compilador completo e funcionando ponta a ponta; otimizações locais implementadas com a demonstração de preservação de semântica; documentação integral revisada e coerente; diário de atividades completo; avaliação por pares preenchida por cada integrante; e a apresentação preparada. A entrega final ocorre na semana seguinte ao término deste módulo.
1.7 Entregas, prazos e o diário de atividades
Cada módulo tem uma entrega, publicada no repositório do grupo antes do início do módulo seguinte. O fluxo é sempre o mesmo.
flowchart LR
T["Trabalho do módulo<br/>nas sessões de tutoria"] --> V{"O incremento<br/>passa nos casos<br/>de teste do grupo?"}
V -->|"não"| C["Correção<br/>ainda dentro do módulo"]
C --> V
V -->|"sim"| REG["Registro no diário<br/>decisões, dificuldades,<br/>divisão do trabalho"]
REG --> DOC["Atualização da<br/>documentação afetada"]
DOC --> PUB["Publicação no repositório<br/>antes do início do módulo seguinte"]
PUB --> FB["Retorno do professor<br/>sobre o incremento"]
FB -.->|"pendências entram no<br/>planejamento do módulo seguinte"| T
style PUB fill:#f4ecdd
O incremento do módulo é construído nas sessões de tutoria e verificado contra os casos de teste do próprio grupo. Só depois de passar é que se registra no diário, atualiza-se a documentação afetada e publica-se no repositório. Publicar código que não passa nos próprios testes do grupo é contado como entrega em atraso, não como entrega parcial.
O professor devolve retorno sobre cada entrega, e as pendências apontadas entram no planejamento do módulo seguinte, na primeira sessão de tutoria. Pendência ignorada acumula, e o efeito do acúmulo é conhecido: os módulos 10 e 14 são onde a dívida cobra juros.
O diário de atividades. É um documento contínuo, mantido na pasta de documentos, com uma entrada por módulo. Cada entrada registra o que foi feito, quem fez o quê, o que travou e como foi resolvido, e que decisões de projeto foram tomadas com quais alternativas descartadas.
Ele tem três funções. Para o grupo, é memória: no módulo 13 ninguém lembra por que uma decisão foi tomada no módulo 5, e o diário lembra. Para o professor, é a principal evidência de que o trabalho foi distribuído entre os integrantes, e é lido junto com a avaliação por pares. Para a avaliação, é o registro de que decisões foram tomadas conscientemente — um grupo que documenta ter escolhido entre duas alternativas demonstra entendimento que um grupo com o mesmo código e nenhum registro não demonstra.
Um diário escrito na véspera da entrega é reconhecível e vale pouco. Um diário escrito na última sessão de tutoria de cada módulo, quando os fatos ainda estão frescos, é a diferença entre um registro útil e um formulário preenchido.
A entrega final ocorre na semana seguinte ao término do último módulo e compreende o projeto completo, a documentação integral e a apresentação. As duas entregas de maior peso — a consolidação parcial do módulo 7 e a entrega final — são acompanhadas de avaliação por pares, em que cada integrante avalia a contribuição dos demais segundo o formulário fornecido pelo professor.
1.8 Critérios de avaliação
A composição da nota da disciplina é a seguinte.
flowchart TD
NOTA["Nota da disciplina"]
NOTA --> CONT["Avaliação contínua<br/>50%"]
NOTA --> FINAL["Projeto Integrador final<br/>50%"]
CONT --> C1["Engajamento no estudo<br/>pelo aplicativo da disciplina<br/>50% da contínua"]
CONT --> C2["Engajamento nas<br/>atividades colaborativas<br/>20% da contínua"]
CONT --> C3["Pontualidade nas entregas<br/>20% da contínua"]
CONT --> C4["Contribuição nas<br/>discussões em sala<br/>10% da contínua"]
FINAL --> F1["Implementação"]
FINAL --> F2["Documentação"]
FINAL --> F3["Apresentação"]
PARES["Avaliação por pares<br/>entre integrantes do grupo"]
PARES -.->|"na entrega parcial"| CONT
PARES -.->|"na entrega final"| FINAL
style NOTA fill:#e8f4ea
style PARES fill:#f4ecdd
Metade da nota vem da avaliação contínua, acumulada ao longo dos módulos, e metade vem da avaliação do Projeto Integrador completo na entrega final. Dentro da avaliação contínua, o maior peso está no engajamento no estudo pelo aplicativo da disciplina, seguido do engajamento nas atividades colaborativas e da pontualidade nas entregas, com uma parcela menor atribuída à contribuição nas discussões em sala. Na avaliação final, o projeto é julgado pela implementação, pela documentação e pela apresentação.
Convém explicitar o que o professor procura ao avaliar o projeto, porque a lista não é óbvia.
Correção antes de sofisticação. Um compilador que trata bem uma linguagem pequena vale mais que um que trata mal uma linguagem ambiciosa. Grupos que reduziram escopo de forma consciente e documentada não são penalizados por isso; grupos que mantiveram escopo grande e entregaram partes quebradas são.
Compreensão demonstrável. Em toda tutoria e na apresentação final, qualquer integrante pode ser perguntado sobre qualquer parte do projeto. A resposta “essa parte foi o outro que fez” é, em si, uma informação avaliada — e é o motivo do revezamento obrigatório de papéis.
Qualidade do relato de erro. A partir do módulo 7, a forma como o compilador comunica problemas é critério explícito. Mensagens que indicam posição, causa provável e, quando possível, sugestão de correção distinguem um projeto cuidadoso de um projeto apenas funcional.
Rastreabilidade das decisões. O registro de decisões e o diário são avaliados. Uma escolha de projeto documentada com suas alternativas vale mais que a mesma escolha sem registro, porque demonstra que houve escolha.
Pontualidade e ritmo. Entregas atrasadas afetam a avaliação contínua diretamente. O projeto é cumulativo, e um módulo entregue com atraso desloca todos os seguintes — a penalidade existe para proteger o grupo de si mesmo.
Distribuição real do trabalho. Verificada pelo diário, pela avaliação por pares e pela observação durante a tutoria. Um projeto excelente produzido por um integrante enquanto os outros assistem não é um projeto excelente para efeito desta disciplina.
1.9 Dicas para uma apresentação eficaz
A apresentação final é a última entrega e costuma ser subestimada. Ela não é um resumo do que foi feito: é a demonstração de que o grupo entende o que construiu, e é avaliada como tal.
Comece pela linguagem, não pelo compilador. A primeira coisa que a plateia precisa ver é um programa escrito na linguagem que vocês projetaram, com a explicação do que ele faz e por que alguém quereria escrevê-lo. Sem isso, tudo que vier depois é abstrato. Mostre o programa antes de mostrar qualquer arquitetura.
Demonstre ao vivo, e demonstre falhando. A parte mais convincente de uma apresentação de compilador não é o programa correto que compila: é o programa com erro que produz uma mensagem precisa. Preparem três demonstrações — um programa que compila e executa, um com erro léxico ou sintático, e um com erro semântico — e mostrem as mensagens. Isso comunica qualidade de engenharia melhor que qualquer diagrama.
Mostre o autômato. O grupo tem uma ferramenta que gera diagramas dos autômatos construídos. Exibir o diagrama de uma das categorias léxicas da linguagem, e mencionar quantos estados tinha antes e depois da minimização, é a forma mais rápida de tornar visível o trabalho dos primeiros módulos, que de outro modo desaparece atrás do resultado final.
Conte uma decisão difícil. Escolham, do registro de decisões, um ponto em que o grupo hesitou entre duas alternativas, e contem: quais eram as opções, o que pesou, o que se descobriu depois. Isso demonstra maturidade de projeto e é o tipo de conteúdo que distingue uma apresentação memorável de um relatório falado.
Seja honesto sobre o que não funciona. Todo projeto de compilador em um semestre tem limitações. Apresentá-las explicitamente, sabendo por que existem e o que seria necessário para resolvê-las, é sinal de domínio. Escondê-las e ser descoberto na pergunta seguinte é o pior desfecho possível.
Distribuam a fala. Todos os integrantes apresentam, e cada um deve ser capaz de responder sobre qualquer parte. Ensaiar a divisão da fala é útil; ensaiar as respostas às perguntas prováveis é mais útil ainda.
Uma última observação, que vale para a apresentação e para o semestre inteiro. O compilador que vocês vão construir será pequeno, lento e limitado quando comparado a qualquer compilador de produção. Isso é esperado e não diminui em nada o que foi feito. O que se aprende ao construir o pequeno é exatamente o que permite compreender o grande — e, se algum dia vocês precisarem entender por que um compilador de verdade reclama do que reclama, terão a vantagem rara de já ter estado do outro lado.