Compiladores e Interpretadores: Estrutura e Funcionamento

Interpretador: recebe a primeira instrução, confere, converte e ordena sua execução. Repete o processo sucessivamente. Apenas uma instrução fica na memória a cada instante. Se o programa fonte for executado uma segunda vez, haverá uma nova tradução.

Compiladores: recebe a primeira instrução, confere, converte e passa para a próxima instrução sucessivamente. Após converter a última instrução (sem nenhum erro), a CPU volta à primeira instrução e executa (sucessivo). Se o programa fonte for executado uma segunda vez, não haverá uma nova tradução.
Vantagem: execução mais rápida. Desvantagem: modificação exige nova tradução.

Montadores (Assemblers): Traduzem programas escritos em linguagem de montagem em programas escritos em linguagem de máquina (0s e 1s).

Pré-processadores: Traduzem programas escritos em linguagem de alto nível em outros programas escritos também em linguagem de alto nível. Exemplo: pré-processador C (processamento de macros e inclusão de arquivos).

Análise: quebra o código-fonte em suas partes e cria uma representação intermediária do programa.

Síntese: Constrói o programa-destino a partir da representação intermediária.

Análise Léxica: lê uma sequência de caracteres e a organiza como tokens (sequências de caracteres com algum significado).

Análise Sintática: agrupa caracteres ou tokens em uma estrutura hierárquica com algum significado.

Análise Semântica: verifica se os componentes de um programa se encaixam de forma a ter um significado adequado.

Análise Sintática - Parsing:

• Também chamada de análise gramatical.
• Envolve o agrupamento dos tokens em frases gramaticais.
• Baseada na gramática da linguagem, é gerada uma árvore sintática (parse tree) do programa.

Tratamento e Recuperação de Erros:

• Erros são gerados, mas o compilador deve informar o máximo possível de erros em uma única execução: isso é feito através de recuperação de erros, que avisa sobre o erro, mas tenta continuar o processo de compilação.
• Tipos de erros: léxicos, sintáticos, semânticos, etc.

Otimização de Código: Realiza transformações no código visando melhorar sua performance em aspectos de tempo de execução, uso de memória, tamanho do código executável, etc.

Organização de um Compilador:

• As fases são separadas em:
• Interface Front-end (Vanguarda): até a geração de código intermediário. Depende da linguagem fonte e independe da máquina alvo.
• Interface Back-end (Retaguarda): inclui as fases de otimização e geração de código. Independe da linguagem fonte e depende da máquina alvo.

É comum manter a interface de vanguarda e refazer a de retaguarda para produzir um compilador da mesma linguagem em uma máquina diferente.

Linguagem = sintaxe + semântica

• Especificação da sintaxe: gramática livre de contexto, BNF (Backus-Naur Form).
• Especificação Semântica: informal (textual), operacional, denotacional, de ações.

Gramática Livre de Contexto

• Um conjunto de tokens (símbolos terminais).
• Um conjunto de símbolos não-terminais.
• Um conjunto de produções: cada produção consiste de um não-terminal, uma seta e uma sequência de tokens e/ou não-terminais.
• Um não-terminal designado como símbolo inicial (de partida).

Parsing: Processo de procurar uma árvore gramatical para uma dada string de tokens (análise gramatical ou análise sintática).

Ambiguidade: Uma parse tree gera uma string de tokens, mas uma string pode possuir várias parse trees se a gramática for ambígua.
Solução: usar sempre gramáticas não ambíguas ou gramáticas ambíguas com informações adicionais sobre como resolver ambiguidades.

Tradução Dirigida pela Sintaxe

• A definição dirigida pela sintaxe usa uma gramática livre de contexto para especificar a estrutura sintática da entrada.
• Associa a cada símbolo um conjunto de atributos e a cada produção associa regras semânticas para computar os valores dos atributos.
• Gramática e regras semânticas constituem a definição dirigida pela sintaxe.

Análise Gramatical

• Processo de se determinar se uma cadeia de tokens pode ser gerada por uma gramática.
• Método de análise gramatical para construir tradutores dirigidos pela sintaxe.
• Na prática, o parsing de linguagens pode ser feito por algoritmos lineares.
• Travessia linear da esquerda para a direita, olhando um token de cada vez.

Parsers Top-Down e Bottom-Up: Refere-se à ordem em que os nós da parse tree são criados.

• Top-down: mais fáceis de escrever à mão.
• Bottom-up: suportam uma classe maior de gramáticas e de esquemas de tradução, sendo usados pelas ferramentas de geração de parsers.

Backtracking: A escolha de uma produção pode exigir tentativa e erro, voltando para tentar novas alternativas possíveis.

• Parsing Preditivo: parsing em que não ocorre backtracking (retrocesso).

Parsing Descendente Recursivo

Método de análise sintática top-down em que um conjunto de procedimentos recursivos é usado para processar a entrada.

• Cada procedimento está associado a um símbolo não-terminal da gramática.
• O Parsing Preditivo é um caso especial de parsing descendente recursivo em que o símbolo lookahead determina sem ambiguidades o procedimento a ser chamado para cada não-terminal.

Análise Léxica

• Lê e converte a entrada para um fluxo de tokens.
• Uma sequência de caracteres de entrada compõe um único token (lexema).
• Um scanner isola o parser do lexema dos tokens.
• Quando um lexema é examinado, algum mecanismo é necessário para verificação.

Usando um Analisador Léxico:

• Funções que um analisador léxico realiza:
• Tratamento de espaços em branco (brancos, tabulações, avanço de linha).
• Tratamento de números maiores que 9 (constantes).
• Reconhecimento de identificadores e palavras-chave.