%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
T["texto do programa"]
L["análise léxica"]
S["análise sintática"]
M["análise semântica"]
I["geração de código intermediário"]
O["otimização"]
F["geração de código final"]
R["código da máquina de destino"]
T --> L
L -->|"fluxo de símbolos"| S
S -->|"árvore da estrutura"| M
M -->|"árvore verificada<br/>+ tabela de nomes"| I
I -->|"representação intermediária"| O
O -->|"representação melhor<br/>pelo critério declarado"| F
F --> R
1 Linguagens formais e a arquitetura de um compilador — Guia
A linha total = preco * quantidade tem 26 caracteres, contados os espaços, e um programa curto os conta. Decidir se ela é um programa válido pede a linguagem a que ela pertenceria, um conjunto infinito de textos que ninguém escreveu por extenso. Obedecer a ela pede também o tipo de cada nome: quantidade guarda um inteiro, preco guarda um real, e nesta linguagem a multiplicação só aceita dois valores do mesmo tipo.
Quem acrescenta a conversão de um dos dois é o tradutor, o programa que recebe um texto numa linguagem e produz outro, em outra. Entre o texto digitado e o código que grava o valor em total há seis etapas, as fases. Cada uma entrega à seguinte uma forma nova do mesmo programa. Por baixo das seis há duas perguntas. Como se guarda em espaço finito um conjunto que não acaba, e quanta memória uma máquina precisa para decidir se um texto está nele? Com memória fixa, ela não consegue conferir parênteses.
1.1 O conjunto, a memória e as fases
Um alfabeto \Sigma é um conjunto finito e não vazio de símbolos. O conjunto \Sigma^* reúne todas as cadeias, fileiras finitas de símbolos do alfabeto, incluída a vazia, \varepsilon, sem símbolos. Uma linguagem sobre \Sigma é qualquer subconjunto de \Sigma^*. Nenhuma regra é exigida. Sendo conjuntos, linguagens herdam a união e ganham operações que só existem porque os elementos são cadeias.
NotaDefinição — Operações sobre linguagens
Sejam L_1 e L_2 linguagens sobre \Sigma. A união é L_1 \cup L_2 = \{w : w \in L_1 \text{ ou } w \in L_2\}. A concatenação é L_1 L_2 = \{xy : x \in L_1 \text{ e } y \in L_2\}. A potência é L^0 = \{\varepsilon\} e L^{n+1} = L^n L. O fecho de Kleene é L^* = \bigcup_{n \geq 0} L^n.
Na definição, w \in L_1 lê-se “w está em L_1”, xy é x colada em y, e \bigcup_{n \geq 0} une todas as potências.
As linguagens que interessam a um tradutor são infinitas e se guardam por descrição finita. A gramática gera: parte de um símbolo inicial e aplica regras de substituição, as produções, até restarem só símbolos do alfabeto. A produção A \to \beta manda trocar A por \beta. Cada troca é um passo, escrito \Rightarrow. O infinito entra pela recursão: uma produção, ou uma sequência delas, traz de volta o símbolo substituído e se reaplica sem limite. A máquina reconhece: lê a cadeia e responde sim ou não. A hierarquia de Chomsky, linguista que mirava a língua natural e não compiladores, divide as linguagens em quatro classes, aqui chamadas degraus, cada uma com a sua máquina: autômato finito, autômato de pilha, autômato linearmente limitado e máquina de Turing. O que muda de um degrau ao seguinte é a memória da máquina: quanta, e com que acesso.
O degrau de baixo, o regular, dá à máquina um número fixo de situações, os estados, e mais nada. Quem só sabe em que estado está não sabe quantas vezes já entrou nele. Suponha que uma máquina de k estados reconheça os parênteses balanceados, e dê a ela os prefixos de zero a k aberturas (. São k+1 prefixos para k estados, e dois, com i < j aberturas, terminam no mesmo estado. Complete os dois com i fechamentos: um fica balanceado, o outro não, mas a máquina responde igual e erra num dos dois, seja qual for k.
Cada fase se define pelo que recebe e pelo que devolve. As três primeiras formam a análise e terminam numa árvore verificada, com a tabela de nomes ao lado. As três últimas formam a síntese e partem dessas duas, e só a última conhece a máquina de destino.
1.2 Uma linha pelas seis fases
Suponha total e preco declarados como reais e quantidade como inteiro, e que o inteiro ao lado de um real se converta para real. A notação vale só para este exemplo. Na léxica, cada unidade (token, nos manuais) traz a categoria, o texto e, entre parênteses, a coluna, contada a partir de 1. Os quatro espaços saem. Na árvore, cada nó é um nome com os filhos entre parênteses, e nome:tipo marca o tipo anotado. Na semântica, a primeira linha é a tabela de nomes, com o tipo de cada um. Na representação intermediária, cada linha faz uma operação e grava o resultado no nome à esquerda do =, e t1, t2 são nomes temporários do tradutor.
fonte total = preco * quantidade
léxica ID total (1) IGUAL = (7) ID preco (9) VEZES * (15) ID quantidade (17)
sintática atribui( total , multiplica( preco , quantidade ) )
semântica total: real preco: real quantidade: inteiro
atribui( total:real , multiplica( preco:real , paraReal( quantidade:inteiro ) ) )
intermediária t1 = paraReal quantidade
t2 = preco * t1
total = t2
otimização t1 = paraReal quantidade
total = preco * t1
código final CARREGA quantidade
PARAREAL
CARREGA preco
MULTIPLICA
GUARDA totalA semântica põe na árvore paraReal, nó sem caractere que o origine. A otimização tira a cópia total = t2, porque t2 não tem outro uso. O critério vem declarado: menos operações, e o mesmo valor final de total para quaisquer valores.
A máquina de destino, inventada para o exemplo, guarda valores numa pilha acessível só pelo topo. CARREGA n empilha o valor de n, e PARAREAL troca o inteiro do topo pelo mesmo valor como real. MULTIPLICA troca os dois do topo pelo produto, e GUARDA n desempilha o topo e o grava em n. Com preco = 2,5 e quantidade = 4, a pilha, da base ao topo:
1.3 Onde o vazio, a memória e a tradução contrariam o palpite
A potência zero de qualquer linguagem é \{\varepsilon\}, que tem uma cadeia, e não \emptyset, que não tem nenhuma. O vazio multiplica por zero; \{\varepsilon\}, por um. Calcule L^1 = L^0 L com L = \{a, ab\}. Partindo de \{\varepsilon\}, sai \{a, ab\}. Partindo de \emptyset, a concatenação não acha cadeia do lado esquerdo, e toda potência sai vazia.
Ganhar estados não escapa do argumento: só troca a linguagem que a máquina finita reconhece. Com um estado para cada profundidade de 0 a k, ela reconhece os aninhamentos até profundidade k, que formam outra linguagem, regular. «Mas nenhum programa real aninha tanto.» A objeção responde a uma pergunta formal, sobre cadeias de toda profundidade, com estatística de uso.
Traduzir esta linha não executou nada dela. Nenhuma das seis formas multiplicou coisa alguma. O 10,0 só aparece quando o código final roda, com valores que o tradutor nunca viu. Quem multiplica é a máquina.
1.4 Três previsões para conferir
Responda antes de abrir cada bloco.
Primeiro, calcular. Com L_1 = \{a, aa\} e L_2 = \{\varepsilon, a\}, quantas cadeias têm L_1 \cup L_2, L_1 L_2 e L_2^0?
DicaResposta
Três, três e uma. A união é \{a, aa, \varepsilon\}. A concatenação emenda quatro pares em a, aa, aa e aaa. A cadeia aa sai de a \cdot a e de aa \cdot \varepsilon, e conta uma vez.
Depois, projetar. Escreva as produções de uma gramática com símbolo inicial S que gere exatamente as cadeias de n letras a seguidas de n letras b, para todo n \geq 0.
DicaResposta
Uma gramática que serve: S \to aSb e S \to \varepsilon. Cada uso da primeira põe um a antes do S e um b depois dele, e a segunda encerra: S \Rightarrow aSb \Rightarrow aaSbb \Rightarrow aabb. Depois de cada passo, há tantos a antes do S quanto b depois dele.
Por fim, um limite. Alguma máquina com um número fixo k de estados, e nenhuma outra memória, reconhece essa linguagem?
DicaResposta
Nenhuma, para nenhum k. Entre os k+1 prefixos formados só por a, de zero a k letras, dois, com i < j letras, terminam no mesmo estado. Acrescente i letras b aos dois: com i letras a a cadeia pertence, com j não, mas a máquina responde igual às duas.
1.5 Para ir além
No material, “Duas letras no cadeado, e a cadeia que ninguém vê” define alfabeto e cadeia, e “Quem abre o arquivo decide o que ele é” segue 3x até a recusa. “Quatro regras para um conjunto sem fim” deriva uma cadeia e chega a Cantor. “A memória que cada degrau exige” mostra a pilha. “Seis fases de um tradutor, e onde a tradução termina” compara compilar e interpretar, e “A especificação antes do tradutor, e o fonte que não prova nada” escreve a primeira especificação e a recusa que a sustenta.