CALL

É um acrônimo para as etapas para transformar um código fonte em um executável.

Compiler: converte código-fonte para assembly.
Assembler: converte assembly para machine code (binário puro/ arquivo objeto .o, mas não onde estão funções de libs externas como printf).
Linker:
Compiler:

Executável

É o machine code (raw bits) nativo, pronto para ser processado pela CPU.

Formatos

Há vários tipos de formatos, que variam dependendo do OS.

ELF

Executable and Linkable Format é o padrão do Linux. É o que o gcc gera por padrão.

PE

Portable Executable, o famoso .exe do Windows.

Etapas da Compilação

1. Análise Léxica - Scanning

O compilador lê o código caractere por caractere e os agrupa em unidades significativas chamadas tokens. Funciona como um AFD.

2. Análise Sintática - Parsing

Os tokens gerados na etapa anterior são organizados em uma estrutura hierárquica, geralmente uma Árvore de Sintaxe Abstrata (AST). O objetivo aqui é verificar se a estrutura do código segue as regras gramaticais da linguagem. Se você esquecer um ponto e vírgula ou fechar um parêntese erroneamente, o erro será detectado aqui.

Parsing Top-down

Recursive descent

LL / LL(k)

PEG

Pratt parser

Parsing Bottom-up

um analisador sintático ascendente constrói a AST de baixo para cima, uma DMD em reverso. Ou seja, ao contrário do top-down, não produz, reduz (que é meio que desfazer a producão).

A principal vantagem dele frente ao top-down é que ele consegue lidar com uma classe maior de gramáticas. Isso significa descrever a linguagem com a gramática de forma mais natural, menos “gambiarras”, menos casos especiais no compilador. Parsers top-down clássicos (LL) entram em recursão infinita, precisando fazer vários tratamentos como refatorar deixando menos natural.

Shift-Reduce Parsing

É a estratégia mais comum para realizar a análise sintática ascendente. Baseado em 4 ações:

Shift: empilhar. o próximo token de entrada é colocado na pilha.
Reduce: o analisador sabe que o símbolo mais a direita de um handle está no topo da pilha. Então, ele deve localizar o símbolo mais a esquerda do handle dentro da pilha e decidir qual não-terminal irá substituir o handle.
Accept: término com sucesso.
Error: erro sintática e invoca uma rotina para recuperação de erro.

LR(0)

O LR(k=0) (não tem lookahead/ tokens de consulta). Ou seja, na hora de montar a tabela sintática a partir da coleção canônica de itens. Se um $I$ possúi um item $A \rightarrow \beta \bullet$ o parser tenta reduzir para qualquer símbolo que encontrar na tabela. Ou seja, na parte de ACTION da tabela sintática LR, LR(0) reduz em qualquer símbolo (preenche todas as células das colunas dos terminais com o respectivo $r_k$ ).

SLR

consegue resolver vários conflitos sr/rr que #LR(0) não consegue. Se um estado contém o item $A \rightarrow \beta \bullet$ , o analisador só executa a redução se o próximo símbolo da entrada estiver no conjunto FOLLOW(A).

CLR

Canonical LR, ou LR(1) canônico. Diferente da #SLR, aqui não é nescessário o uso de FOLLOW. O número de estados dele é gigante, mas consegue reconhecer muita coisa tambem.

LALR

Lookahead LR é um meio termo de trade-off de quantidade de estados e poder de reconhecimento entre o #SLR e o LR(1). Possuí o mesmo número de estados que o #SLR/#LR(0) mas, quase como o CLR, possuí um forte poder de reconhecimento. Por isso, virou padrão na indústria. (Ainda mais antigamente que memória era um recuso muito caro).

Compiler