Resumo Software Básico para 1ª Prova (Bruno Macchiavello)

Prévia do material em texto

Conceitos básicos 
 
Linguagem de alto nível (C, C++, Java): mais próxima da linguagem usada pelo ser­humano,                           
facilitando a codificação e manutenção. 
 
Linguagem de baixo nível: mais próxima da máquina, comandos parecidos com instruções da                         
CPU. 
Assembly: Linguagem de máquina em mnemônicos. Utilizada por montadores para gerar código                       
de máquina. 
Código de máquina: bits utilizados pela CPU para executar operações de baixo nível. Programas                           
mais leves e rápidos, mas o programador precisa de mais conhecimento técnico. 
 
Características da linguagem C: fácil por possuir estruturas de alto nível, flexível, alto nível de                             
portabilidade, usada tanto para fins acadêmicos, quanto comerciais. 
 
Características de linguagem Assembly: cada CPU implementa uma Instruction Set Architecture,                     
ou seja, uma CPU entende apenas o seu conjunto de instruções; mapeando os códigos das instruções da                                 
ISA para mnemônicos, é possível programar de forma mais confortável. 
 
Linguagens naturais: lidam com ambiguidades. 
 
Compilador: traduz código em linguagem alto­nível para código em linguagem baixo­nível, ou                       
arquivo executável (C → {Assembly|Código de máquina|Arquivo executável}). 
 
Montador: traduz código Assembly para código de máquina. 
 
Estágios da compilação: 1) pré­processamento: expansão de macros e modificação do                     
código­fonte que será compilado de acordo com as flags definidas em tempo de compilação; 2)                             
compilação/montagem: geração de código baixo­nível, como Assembly ou código de máquina; e 3) ligação:                           
combina códigos de máquina resolvendo pendências e gerando um arquivo executável. 
 
Anatomia de um programa em Assembly: 
; comentarios, apenas unilinha, sao feitos utilizando 
ponto­e­virgula 
section .data 
(dados inicializados vem aqui) 
 
section .bss 
(dados nao inicializados vem aqui) 
 
section .text 
global _start ; diz que _start eh um simbolo visivel 
externamente 
_start: 
(codigo vem aqui) 
mov eax, 1 
mov ebx, 0 
int 80h ; retorna o controle para o SO 
Observação: Símbolos podem ser endereços de código, de dados na memória, ou de constantes,                           
que frequentemente são inicializadas como zero pelo montador. 
 
Instruções são para a máquina, diretivas (macros) são para o compilador/montador. 
 
Evolução das linguagens de programação 
 
Linguagens da primeira geração: linguagens de máquina. Palavras formadas por bits que dizem a                           
uma CPU o que deve ser executado. Programas são sequências de zeros e uns, portanto era muito difícil                                   
de programar; fácil de cometer erros. 
 
Linguagens de segunda geração: linguagens simbólicas ou Assembly. Feitas para facilitar a                       
programação. Mnemômicos correspondendo a códigos de máquina, que são convertidos por um programa                         
Montador (Assembler). 
 
Linguagens da terceira geração: linguagens modernas ou estruturadas. Tipagem de dados; grande                       
capacidade procedural e estrutural; possibilidade de criar sistemas distribuídos. Divididas em: 
Linguagens de propósito geral (C, Pascal, Fortran, PL/1, Modula­2): derivadas do Algol.                       
Servem inúmeros propósitos, indo desde a área científica à área comercial. 
Linguagens especializadas: uma linguagem com sintaxe especializada para uma aplicação                   
distinta. 
Lisp: manipula símbolos e listas; 
Prolog: trata e representa conhecimento; 
Smalltalk: primeira linguagem puramente orientada a objetos; 
APL: manipula vetores. 
 
Linguagens de quarta geração (SQL, Access): comandos similares aos da linguagem natural.                       
Normalmente empregados em bancos de dados e scripts. 
 
Linguanges de quinta geração (VB, Delphi): linguagens que utilizam recursos visuais para                       
desenvolver programas. Comum utilizar IDEs para desenvolver. 
 
Processadores de linguagens: linguagens de alto nível, que são independentes de instruções de                         
máquina, são implementadas através de compilação, interpretação, ou uma combinação das duas coisas.                         
Qualquer sistema para processar um programa é chamado de processador de linguagem, como                         
compiladores, interpretadores e ferramentas auxiliares, como editores de texto dirigidos à sintaxe. 
 
Interpretação: cada ação indicada no programa é executada diretamente pelo interpretador. Um                       
interpretador é a repetição dos seguintes passos: 
­ obter o próximo comando; 
­ determinar as ações que precisam ser executadas; 
­ executar as ações. 
Um interpretador é semelhante à máquina: 
­ obter a instrução no endereço indicado pelo contador de programa; 
­ deslocar o contador de programa para a próxima instrução a ser executada; 
­ decodificar a instrução; 
­ executar a instrução; 
 
Tradução ou Compilação: programas em linguagem de alto nível são traduzidos para uma                         
sequência equivalente de instruções de máquina. 
Etapas da tradução: 
subprogramas → compilação → Assembly 
Assembly → montagem → código objeto (código de máquina) 
códigos objeto → ligação → arquivo executável 
arquivo executável → carregamento → módulo de carga na memória da máquina pronto                         
para ser executado 
É possível realizar tradução cruzada. Situação em que a arquitetura alvo para a qual o programa é                                 
compilado não é a arquitetura da máquina que executa a tradução. 
 
Tradutores: programas que convertem um programa de uma linguagem fonte para uma linguagem                         
alvo. 
Classificação dos tradutores: 
Assemblers (Montadores): convertem mnemônicos Assembly para código de máquina.                 
Macro­assemblers suportam expansão de diretivas, macros e pseudo­instruções. 
Pré­processadores, pré­compiladores ou filtros: realizam a expansão de diretivas e macros                     
em um código fonte. 
Interpretadores: produzem o “efeito de execução” para um programa previamente                   
convertido em código intermediário. 
Compiladores: traduzem programas de uma linguagem para outra de mais baixo nível                       
semântico. Pode gerar tanto Assembly, quanto código de máquina. 
 
Tradução X Interpretação: tradução pura e interpretação pura são dois extremos. Muitas                       
linguagens são implementadas como combinação das duas coisas. Programas traduzidos executam mais                       
rápido do que programas interpretados. Programas interpretados são menores e mais fáceis de                         
desenvolver e dar manutenção. 
 
Estruturas de tradutores 
 
Uma linguagem de programação é descrita por sua gramática, que descreve a sintaxe. A sintaxe                             
descreve a forma dos enunciados legais (ou legal statements). Enunciados são formados por tokens,                           
blocos fundamentais da linguagem. Tokens podem ser palavras­chave, identificadores (ou símbolos),                     
constantes (ou literais), operadores e pontuadores. 
 
Etapas da tradução: 
Análise: detecção de erros acontece nesta etapa 
Analisador léxico (ou Scanner): lê enunciados para reconhecer e classificar                   
tokens. Cospe uma lista de tokens. 
Analisador sintático (ou Parser): verifica se os enunciados estão de acordo com                       
as regras gramaticais. Cospe uma árvore sintática. 
Analisador semântico: verifica se os enunciados são válidos levandoem                   
consideração o contexto em que estão inseridos. Trata o inter­relacionamento entre partes distintas do                           
programa. Cospe a árvore sintática com anotações. 
Síntese: 
Gerador de código intermediário: cospe código intermediário. 
Otimizador de código intermediário: cospe código intermediário otimizado. 
Gerador de código de máquina: cospe código de máquina otimizado. 
 
Gramáticas: regras que determinam as possíveis formas, e não o significado, de um enunciado.                           
Utilizam símbolos terminais, que fazem parte do código­fonte, e símbolos não terminais, que geram outras                             
regras gramaticais. 
 
Exemplo de grámatica: gramática BNF (Backus­Naur Form). 
Exemplo 1: 
<data> = <dia> <mes> <ano> 
<mes> = JAN | FEV | MAR | … 
<dia> = 1..31 
<ano> = 1900..3000 
Exemplo 2: 
<comando> → <while> | <atrib> | … 
<while> → while <expr_bool> <comando> 
<atrib> → <variavel> = <expr_arit> 
<expr_bool> → <expr_arit> < <expr_arit> 
<expr_arit> → <expr_arit> + <termo> | <termo> 
<termo> → <numero> | <variavel> 
<variavel> → I | J 
<numero> → 100 
 
Árvore sintática ou de derivação: representação gráfica de derivações feitas em um enunciado                         
seguindo as regras de uma gramática. 
Exemplo de árvore sintática: while (I < 100) <comando>. 
 
 
Análise semântica: verifica se um enunciado está correto levando em consideração o contexto em                           
que ele está inserido. 
 
Verificações da análise semântica: 
Verificação de tipos: 
Exemplo de erro: 
int mod(int a, float b) { return a%b; } 
Nãoépossívelobterorestodeumadivisãopor                 
número real. 
Exemplo de coerção automática (casting automático): 
a = x – 'c'; 
O casting da constante 'c' é feito pelo               
compilador automaticamente para int, de modo que a operação de                   
subtração pode ser executada corretamente. 
Exemplo de aviso: 
int a; 
int* p; 
a = p; 
Avisodequeuminteiroécriadoapartirdeum                   
ponteiro sem coerção. Solução: a = (int) p; 
Verificação de fluxo de controle (exemplo): 
void f2(int j, int k) { 
if (j == k) 
break; 
else 
continue; 
} 
O compilador gera um erro, pois o break não está 
dentro de um loop ou switch; e o continue não está dentro de um loop. 
Verificação de unicidade na declaração de variáveis: 
void foo() { 
int a; 
float a, b; 
a = 2*b; 
} 
O compilador reclama da redeclaração da variável ‘a’. 
Exemplo de árvore de sintaxe anotada: 
 
 
Geração de código intermediário: a linguagem do código intermediário gerado pelo compilador                       
deve estar entre a linguagem de alto­nível e o Assembly alvo. Duas formas de representação                             
intermediária são comuns. 
 
Representação de código intermediário com código de três endereços: código em que uma                         
atribuição possui um operando de escrita e no máximo dois operandos de leitura. Assim o código fica mais                                   
próximo de um Assembly. Este tipo de representação requer quatro tipos básicos de instruções: 
Instruções de atribuição: 
x = y op z 
x = op y 
x = y 
Traduzindo “a = b + c * d”: 
_t1 = c * d 
a = b + _t1 
Instruções de desvio: 
goto L  ; instrucao de desvio incondicional 
if x op y goto L ; instrucao de desvio condicional 
Exemplo de while: 
while (i++ <= k) 
x[i] = 0; 
x[0] = 0; 
Traduz para: 
_L1: if i > k goto _L2 
i = i + 1 
x[i] = 0 
goto _L1 
_L2: x[0] = 0 
Invocação de rotinas: 
; os parametros sao empilhados e a chamada eh feita 
param a 
param b 
param c 
_t1 = call f, 3 
; a instrucao return retorna a rotina 
return _t2 
Acesso indexado e indireto: 
; acesso indexado eh como lidar com vetores em C 
x = y[i] 
y[i] = z 
; acesso indireto eh como ligar com ponteiros em C 
x = &y 
w = *x 
*x = z 
A representação das instruções é feita através de tabelas com quatro ou três colunas: 
 
Na representação com três colunas, a coluna de variáveis temporárias é suprimida pela                         
referenciação à outras instruções: 
 
 
Representação de código intermediário com notação posfixa: notação polonesa. Operandos vêm                     
antes do operador. É interessante por dispensar o uso de parênteses: 
 
Exemplos de instruções intermediárias em notação posfixa: 
L jump ; desvio incondicional 
x y L jcc ; desvio condicional para (x cc y), cc contido                 
em {eq, ne, lt, le, gt, ge} 
; operacoes sao realizadas eficientemente com uma maquina               
de pilha. o algoritmo de uma maquina de pilha eh sempre empilhar                       
operandos; e desempilhar dois operandosquandoencontrarumoperador                 
e empilhar o resultado da operacao. 
; “a = a*(b+c)” ou “a a b c + * =” eh codificado assim: 
push a 
push b 
push c 
add 
mult 
pop a 
 
Otimizador de código: é possível fazer otimizações dependentes e otimizações independentes de                       
máquina. 
Otimização dependente de máquina: algumas máquinas podem possuir registradores para                   
armazenar valores temporários. Escolhas de como utilizar esses registradores de modo mais eficiente                         
fazem parte da otimização. 
Otimização independente de máquina: exemplos são calcular o valor de expressões iguais apenas                         
uma vez; e retirar expressões constantes de loops. 
 
Gerador de código objeto: produz código objeto reservando memória para constantes, variáves,                       
etc. Tarefa difícil, pois depende da máquina alvo. Arquivo de código objeto possui formato dependente do                               
SO. 
 
Gerência de tabelas: um tradutor utiliza diversas tabelas durante o processo de tradução. Entre                           
elas, tabelas para palavras reservadas, delimitadores, etc. A principal é a tabela de símbolos, que                             
armazena nomes de variáveis, constantes e funções; e metadados sobre estes símbolos. A maior parte do                               
processamento se vai com acessos a tabela de símbolos. 
 
Atendimento a erros: um tradutor precisa indicar erros com precisão. Um tradutor deve detectar                           
erros e prosseguir com a análise, utilizando mecanismos de recuperação à erros para que isto seja                               
possível. 
 
 
 
Montadores 
 
Máquina hipotética: 1 registrador acumulador ACC de 16 bits; 1 registrador contador de programa                           
PC de 16 bits; memória de 2^16 palavras de 16 bits. Operações: 
 
Instruções e diretivas: 
 
 
 
Exemplo de programa: ler dois números e exibir a soma. 
INPUT N1 
INPUT N2 
LOAD N1 
ADD N2 
STORE N3 
OUTPUT N3 
STOP 
 
 
O processo de montagem deve expandir pseudo­instruções e macros, representar o programa em                         
binário de acordo com a arquitetura alvo, separar espaço para dados no arquivo de código objeto e                                 
registrar informações sobre símbolos externos utilizados no módulo (tabela de definições), e símbolos                         
exportados e seus atributos (tabela de uso). 
 
Algoritmo de duas passagens (seção de texto): 
Primeira passagem: 
contador_posicao = 0 
contador_linha = 1 
Enquanto (arquivo fonte não se encerrou) Faça 
Ler uma linha do arquivo 
Separar a linha em tokens 
Aplicar a regra gramatical para detectar erros 
Se (define rótulo) Então 
Se (símbolo já existente) Então 
Erro de redefinição de símbolo 
Senão 
Adiciona rótulo e contador de posição na tabela de símbolos 
FimSe 
FimSe 
contador_posicao += tamanho da instrução 
contador_linha++ 
FimEnquanto 
Segunda passagem: 
contador_posicao= 0 
contador_linha = 1 
Enquanto (arquivo fonte não se encerrou) Faça 
Ler uma linha do arquivo 
Separar a linha em tokens 
Se (algum operando não foi declarado) Então 
Erro de símbolo não declarado 
Senão 
Gera o código de máquina 
contador_posicao += tamanho da instrução 
FimSe 
contador_linha++ 
FimEnquanto 
 
Algoritmo de passagem única (seção de texto): 
contador_posicao = 0 
contador_linha = 1 
Enquanto (arquivo fonte não se encerrou) Faça 
Ler uma linha do arquivo 
Separar a linha em tokens 
Aplicar a regra gramatical para detectar erros 
Se (define rótulo) Então 
Se (símbolo já existente) Então 
Erro de redefinição de símbolo 
Senão 
Adiciona rótulo e contador de posição na tabela de símbolos 
Percorre lista de referências atualizando endereço 
FimSe 
FimSe 
Se (operação referencia símbolo) Então 
Se (símbolo definido) Então 
Gera o código de máquina 
Senão 
Cria o símbolo indefinido na tabela de símbolos 
FimSe 
FimSe 
contador_posicao += tamanho da instrução 
contador_linha++ 
FimEnquanto 
 
Características adicionais de montadores 
 
Reserva de espaço para variáveis: diretivas não ocupam espaço. Montadores comerciais                     
suportam expressões aritméticas no lugar de operandos, calculando expressões constantes em tempo de                         
montagem e salvando num espaço reservado. 
 
Contadores de posição: montadores podem possuir diretivas para dizer em qual endereço a partir                           
de um certo valor o código que vier à seguir deve ser alocado, como ORG valor. 
 
Diretiva comum: EQU. “símbolo EQU valor” expande “símbolo” para o valor “valor”. 
 
Assembly condicional: utilizando IF <CONDICAO> é possível montar Assembly variável, de                     
acordo com a expressão do macro. 
 
Exemplo de macro: 
TROCA: MACRO 
COPY A, TEMP 
COPY B, A 
COPY TEMP, B 
ENDMACRO 
… 
TROCA ; expande a macro nesta posicao 
 
Macros com parâmetros: é possível expandir macros utilizando parâmetros. Exemplo: 
SWAP: MACRO &A, &B, &T 
COPY &A, &T 
COPY &B, &A 
COPY &T, &B 
ENDMACRO 
… 
SWAP A, B, C ; expande a macro nesta posicao 
 
O montador implementa duas tabelas para macros: 
Macro Name Table (MNT): para um nome de macro, existem colunas com a quantidade de                             
parâmetros e a posição na MDT onde está o corpo da macro. 
Macro Definition Table (MDT): para um nome de macro, armazena o corpo desta macro. 
 
A maior parte da tradução é gasta acessando tabelas de strings. Uma técnica que torna estes                               
acessos mais eficientes é hashing. 
 
Montadores geram informações no código objeto sobre endereços serem absolutos, ou relativos à                         
um endereço base que é informado pelo programa carregador do SO. O carregador é o último responsável                                 
por resolver pendências, deixando o programa pronto para ser executado na memória do computador.