Compilador.

 Implementação de linguagens de programação.

Macroinstruções:

Conjunto de instruções da arquitetura (ISA - Instruction Set Architecture). Ou seja, são instruções de baixo nível que correspondem diretamente à linguagem do processador. Exemplificando, a Assembly possui um conjunto de comandos de macroinstruções. 

Possuem formato: opcode (operational code) + operandos -> instrução = ação + alvo(s).

MACROINSTRUÇÃO (formato típico x86):

┌─────────────────────────────────┐

│ Opcode (sempre à esquerda)│Operando (sempre à direita) 

│        ADD                              │       R1, R2    

└─────────────────────────────────┘

Aqui, as macroinstruções serão interpretadas pelo microprograma gerando as microinstruções.

Microprograma:

Armazenada na memória de controle do processador, é uma camada intermediária de baixo nível. Atua como interface entre o hardware e as instruções de alto nível. Quando as macroinstruções chegam aqui, são quebradas em várias.

Microinstruções: 

Microinstruções são campos de bits - podemos dizer que são vetores das macroinstruções apenas para explicação didática -  já na língua do hardware, já sendo lidas pelo processador. São os comandos finais para serem executados pelo hardware como fios ativados e desativados, portas lógicas, registradores.

MICROINSTRUÇÃO (formato real, interno):

┌──┬──┬──┬──┬──┬──┬──┬──┐

│b7│b6│b5│b4│b3│b2│b1│b0│

├──┼──┼──┼──┼──┼──┼──┼──┤

│1 │0 │1 │0 │0 │1 │1 │0 │

└──┴──┴──┴──┴──┴──┴──┴──

Um computador poderia ser projetado e construído com uma linguagem de alto nível, mas seria complexo, caro e inflexível. Antigamente, muitos computadores eram desenvolvidos desta forma e só podiam ser programados com uma única linguagem.

Em 1959-1964, a IBM produziu quatro linhas de computadores, eles tinham computadores para pequenas empresas, como o 1401, computadores para grandes empresas, como o 7070, computadores científicos de pequeno porte, como o 1620, e máquinas científicas de grande porte, como a série 709x. Porém surgiu o problema, eram incompatíveis com as ações que o outro poderia oferecer. A solução era criar uma família de computadores (diferentes custos/performance) que executassem o mesmo conjunto de instruções. O System/360, surgiu como solução, uma única ISA para toda a linha, um programa escrito em um modelo funcionaria em qualquer outro.

Por isso, um projeto de máquina mais prático, rentável e garantido, implementa, em hardware, uma linguagem de nível baixo, que oferece as operações primitivas mais comumente necessárias e exige que o software de sistema (por exemplo, o Sistema Operacional) crie uma interface com programas de nível alto. É claro, existe a necessidade de um enorme conjunto de programas que compõe o sistema operacional para a facilitação do uso de seus recurso. As primitivas de um SO oferecem gerenciamento do sistema, gerenciamento de arquivos, e outros recursos necessários para que um programa possa ser executado.

E onde a compilação entra nisso?

Para um desenvolvedor possa criar programas em uma linguagem de programação de alto nível, é preciso converter o código-fonte em um código que possa ser executado e entendido pelo computador. Essa conversão pode ser feita por um programa compilador, por exemplo.

Como os sistemas de implementação - conjunto de software responsável por transformar o código que um programador escreve código-fonte, em uma linguagem de alto nível como Java, C ou Python) em algo que o computador possa realmente executar, ou seja, uma forma interessante de dizer "compilador" - necessitam de muitas facilidades do SO, eles comunicam-se com o SO ao invés de diretamente com o processador (em linguagem de máquina).

Mas essa questão há de ser levantada em outra anotação.

Um programa, ou sistema, consiste em uma entrada (podendo ser um trecho de código hello world ou a iniciação de um aplicativo) um processamento (compilação) e uma saída (a execução).

Todos programas são compilados, compilar é a forma de dizer que iremos transformar o código de alto nível (que humanos consigam entender e escrever facilmente) para o baixo nível (números binários, que as máquinas entendem), o que mudará na linguagem é o modo que ela irá compilar o programa escrito;

Ao compilarmos o programa feito, por exemplo, em C:

gcc programa.c -o programa

Ele gerará um arquivo executável 🠒 programa (Linux) programa.exe (Windows) programa.app (Mac)

Cada execução o SO irá carregar esse código na memória diretamente, ele não irá utilizar o código fonte. Aqui, o arquivo executável será criado no formato do leitor especifico do SO, exemplificando, o executável no Linux é o ELF, o SO irá pegar código e transformar em ELF. Para um Windows, o arquivo deverá ser re-compilado. 

Se alterarmos o código, precisamos recompilar o arquivo. O antigo continuará lá, mas agora rodaremos o atual.

Isso é linguagem de programação compilada. Seu processo é divido em diferentes fases:

1) Análise léxica:

Ele irá ler caractere por caractere, ignorando espaços em branco e comentários. Ao ler o código-fonte, vai agrupar os caracteres em tokens de acordo com padrões. Por exemplo, 

Quando o compilar inicia, o analisador léxico irá percorrer o código buscando:

Palavras- chave:

return, class, public  🠒 palavras reservadas / especiais

if, else, while, for  🠒 comandos de controle

int, float, string, bool  🠒 tipos primitivos

Identificadores: nomes de variáveis, nome de funções, nome de classes

Literais: inteiros (42), literais de string ("Olá"), literais de ponto de flutuante (3.14), caracteres ('a'), etc.

Operadores:  + - * / = 

Delimitadores:  ; ( { )

Uma classe em C

int soma(int a, int b) {

    return a + b;

}

Token (classe)                 |    Lexema (texto)   |   Atributo (valor, se houver)

KW_INT (keyword int)                 int                                  -

ID (identifier)                                 "soma"                       soma

LPAREN (left parentheses)            (                                        -

[..]

EOF  (end of file)                           -                                        -

A implementação do analisador léxico é algo que, por mais complexo que seja, é interessante entrarmos em seu coração um pouco:

O analisador segue o padrão de Expressões Regulares e Autômatos finitos, primeiramente, as expressões regulares,

Entrada: caractere por caractere do código.

Exemplo "soma" e 9

Nas expressões regulares terá um [a-Za-Z_] [a-zA-Z0-9_]* para a soma e um [9-0]+ para o inteiro

Ou seja, o lexema int casa com a expressão regular do int, então ele será aceito e classificado como o token do inteiro.

Mas, ele não trabalha sozinho. O analisador léxico precisa reconhecer rapidamente qual token corresponde a um trecho de entrada, para isso haverá um conversão durante a execução.

Para cada expressão regular, constrói-se um NFA (autômato finito não determinístico)

Todos os NFAs são combinados em um único NFA

Esse NFA é convertido para um DFA (determinístico)

O DFA funcionará como uma tabela de transição, quando ele está lendo um caractere, consulta a tabela, muda de estado, e assim conseqüentemente, até que quando chega a um estado final, reconhece o token correspondente a expressão e o encapsula no token.

Do estado inicial, ele lê  i, vai para um estado intermediário; o n e t, vai para o estado que reconhece KW_INT

Contudo, também haverá anotação para isso. 

2) Análise sintática

Recebendo como entrada os tokens do analisador léxico, usa-se para construir estruturas hierárquicas.

Abstract Syntax Tree (AST) 

A árvore sintática é responsável por organizar de a gramática dos tokens. Quando o ela ver token KW_INT converterá para algo como "declaração_funcao" e quando ver LPAREN, saberá que é o início de um parâmetro. O sintático usa gramáticas livres de contexto (CFG – Context-Free Grammar)

terminais = tokens

não-terminais = símbolos que representam as funções da linguagem

produção = combinação dos terminais e não-terminais para criação da estrutura

Esclarecimentos: 

Essa é uma anotação autodidata para estudos sem intenções de ganhar créditos.

Links legais:

https://www.geeksforgeeks.org/dsa/expression-tree/

https://www.geeksforgeeks.org/compiler-design/parse-tree-and-syntax-tree/

https://panda.ime.usp.br/pythonds/static/pythonds_pt/06-Arvores/ParseTree.html