O que você vai aprender
Relacionar níveis de abstração e o papel do compilador como ponte.
Separar responsabilidades de front-end e back-end e justificar a economia m+n.
Posicionar as linguagens na hierarquia de Chomsky e entender por que isso importa.
Conectar cada nível da hierarquia a uma fase do compilador.
Por que linguagens formais?
Para construir um compilador correto, precisamos de uma forma precisa de descrever "o que é um programa válido". Vaguezas em português não bastam — precisamos de matemática.
As linguagens formais e as gramáticas dão essa precisão. Elas permitem dizer, sem ambiguidade, quais sequências de símbolos pertencem à linguagem e quais não.
O que veremos nesta aula
- As camadas que separam o humano do hardware.
- A arquitetura em duas pontas e a economia que ela gera.
- O conceito formal de alfabeto, cadeia e linguagem.
- Os quatro níveis de Chomsky e seu papel no compilador.
Alfabeto, cadeia e linguagem
Cadeia. Sequência finita de símbolos do alfabeto.
Linguagem. Conjunto (possivelmente infinito) de cadeias sobre um alfabeto.
Por exemplo, com Σ = {a, b}, a cadeia "abba" é válida, e a linguagem "todas as cadeias com número par de a" é um subconjunto de todas as cadeias possíveis.
Dos transistores às linguagens
Programar é trabalhar em camadas de abstração. Cada camada esconde a complexidade da camada abaixo. O compilador é a ponte entre o nível em que o humano pensa e o nível que a máquina executa.
Uma gramática descreve uma linguagem
Uma gramática é um conjunto de regras que gera as cadeias de uma linguagem. Veja uma gramática mínima:
Aplicando as regras repetidamente, geramos "ab", depois "aabb", depois "aaabbb", e assim por diante. Essa é a linguagem a^n b^n, com n maior ou igual a 1.
Passo a passo: derivando uma cadeia
Front-end e back-end
Back-end. Parte que depende da máquina-alvo: otimização e geração de código. Consome a representação intermediária.
A economia da arquitetura em duas pontas
Separar o compilador em front-end e back-end traz uma vantagem prática enorme. Sem essa separação, suportar m linguagens em n máquinas exigiria m×n compiladores distintos.
O tradutor de plantão
Front-end × back-end
| Front-end | Back-end |
|---|---|
| Análise léxica, sintática e semântica | Otimização e geração de código |
| Produz a representação intermediária | Consome a representação intermediária |
| Depende da linguagem-fonte | Depende do processador-alvo |
| Reaproveitável entre máquinas | Reaproveitável entre linguagens |
A hierarquia de Chomsky em cascata
Os quatro tipos de Chomsky encaixam-se um dentro do outro: toda linguagem regular é livre de contexto, toda livre de contexto é sensível ao contexto, e assim por diante.
Irrestrita⊃Tipo 1
Sensível⊃Tipo 2
Livre de ctx.⊃Tipo 3
Regular
A hierarquia de Chomsky
Noam Chomsky classificou as linguagens formais em quatro tipos, do mais geral ao mais restrito. Cada tipo tem um reconhecedor de poder correspondente:
| Tipo | Linguagem | Reconhecedor | No compilador |
|---|---|---|---|
| 3 | Regular | Autômato finito | Análise léxica (tokens) |
| 2 | Livre de contexto | Autômato com pilha | Análise sintática (estrutura) |
| 1 | Sensível ao contexto | Autômato linearmente limitado | Aspectos da análise semântica |
| 0 | Irrestrita | Máquina de Turing | Computação geral |
Verifique você mesmo: qual nível?
Parênteses balanceados, como ((())), exigem no mínimo qual nível da hierarquia?
Por que cada fase usa um nível
A escolha do reconhecedor mais simples possível por fase não é estética: é eficiência.
Enganos sobre a hierarquia
Outro engano: pensar que "tipo 0" é o mais restrito. É o contrário — tipo 0 é o mais geral (irrestrito) e tipo 3 é o mais restrito (regular).
Ferramenta certa para cada nível
Reflita: e a semântica?
Se a sintaxe é livre de contexto (tipo 2), por que não basta uma GLC para todo o programa?
Termos-chave da aula
Onde isto se encaixa no curso
Esta aula fundamenta tudo o que vem depois:
- Tipo 3 (regular) → aulas 3 e 4: ER e autômatos para tokens.
- Tipo 2 (livre de contexto) → aulas 5 a 7: GLC, parsing e LL(1).
- Tipo 1 (sensível ao contexto) → aulas 8 e 9: análise semântica.
- A arquitetura front/back-end → aula 10: representação intermediária.
Resumo visual
Atividade em grupo · Classificando construções
Em duplas, classifiquem construções de uma linguagem na hierarquia de Chomsky.
Roteiro
- Para cada item, decidam o nível mínimo necessário: identificador, número, expressão aninhada com parênteses, "toda variável deve ser declarada antes do uso".
- Justifiquem por que um autômato finito não basta para parênteses balanceados.
- Relacionem cada item à fase do compilador correspondente.
- Apresentem a tabela final ao restante da turma.
Mini-quiz · Aula 2
20 questões sobre esta aula. Escolha e veja a explicação na hora.
📌 Resumo — leve isto para a prova
- O compilador faz o programa "descer" pelas camadas de abstração.
- Front-end depende da linguagem; back-end depende da máquina; uma RI comum os conecta.
- Alfabeto, cadeia e linguagem são os conceitos formais de base.
- Hierarquia de Chomsky: regular→léxico, livre de contexto→sintaxe.
- Cada fase usa o reconhecedor mais simples suficiente.