cap5-tradutor.asc 34.2 KB
Newer Older
1
2
3

== Algoritmos, Linguagem de Programação, Tradutor e Interpretador

4
5
:cap: cap5

6
7
// FIXME Os códigos em assembly não estão uniformes durante o livro.

8
9
10
11
12
13
14
15
16
17
18
19
20
.Objetivos do capítulo
____________________
Ao final deste capítulo você deverá ser capaz de:

* Apresentar o conceito de algoritmos;
* Apresentar como os algoritmos são formalizados nos computadores através de 
linguagens de programação;
* Descrever os softwares básicos que permitem ao computador entender os 
algoritmos descritos nas linguagens de programação.

____________________


21
=== Algoritmos
22

23
24
(((Algoritmos)))

25
Historiadores trazem divergências sobre a origem da palavra algoritmo, sendo a 
26
27
28
29
30
31
32
33
mais difundida, devido ao seu sobrenome, a de Mohamed ben Musa Al-Khwarizmi, um matemático persa do 
século IX, cujas obras foram traduzidas no ocidente no 
século XII, tendo uma delas recebido o nome 'Algorithmi de numero indorum' (indiano), 
acerca dos algoritmos que trabalham sobre o sistema de numeração decimal. 

Independente de sua real etimologia, a ideia principal contida na palavra 
refere-se à descrição sistemática da maneira de se realizar alguma tarefa. Para 
a Ciência da computação, o conceito de algoritmo foi formalizado em 1936 
34
por Alan Turing (Máquina de Turing) e Alonzo Church, que formaram as primeiras 
35
fundações da Ciência da Computação. Sendo esta formalização descrita a 
36
37
38
39
40
41
42
43
44
45
seguir:

[quote]
__________
Um algoritmo é um conjunto não ambíguo e ordenado de passos executáveis que 
definem um processo finito. 
__________

Em sua definição o algoritmo requer um conjunto de passos ordenados, isto 
significa que estes passos devem ser bem definidos e estruturados para uma 
46
47
ordem de execução. Isto não quer dizer que estes passos devem ser executados 
sempre em uma única sequência consistindo de um primeiro passo seguido por um 
48
segundo, e assim por diante.footnote:[Muitos algoritmos, conhecidos como algoritmos 
49
50
paralelos, contém mais do que uma sequência de passos, cada um sendo projetado 
para executar um processo distinto em máquinas multiprocessadas. Logo, as 
51
sequências dos passos podem intercalar entre si dependendo do ambiente de 
52
execução, entretanto, dentro de uma mesma sequência sua ordem de execução 
53
não muda durante o processo.]
54

55
Seguindo a definição, todo algoritmo deve consistir em passos executáveis. 
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
Considere a seguinte instrução

__________
Faça uma lista de todos os números inteiros ímpares
__________

Sendo um algoritmo para sua solução impossível de ser realizado, pois existe 
uma infinidade de números inteiros ímpares. Logo, um algoritmo deve ser 
eficaz, ou seja, que possa ser resolvido. Podemos criar um algoritmo para 
solucionar a instrução acima modificando sua descrição

__________
Faça uma lista de todos os números inteiros ímpares no intervalo [1; 100]
__________


Por fim, os passos em um algoritmo não podem ser ambíguos, isto significa que 
durante a execução de um algoritmo, o estado atual do processamento deve ser 
suficiente para determinar única e completamente as ações requeridas por 
cada passo. 

77
[[sec_algoritmo_rotas]]
78
79
==== Exemplo de um Algoritmo

80
Guilherme recebe alguns convidados que estão visitando a cidade em sua casa e precisa 
81
82
83
84
ensiná-los a chegar à igreja para a missa do domingo. 

[[fig_mapa_cidade]]
.Mapa da cidade de Guilherme
85
image::images/{cap}/mapa_a.eps[scaledwidth="60%"]
86
87
88


O anfitrião muito organizado apresenta o mapa de seu bairro como visto na <<fig_mapa_cidade>> e propõe o 
89
90
seguinte algoritmo para que seus amigos não se percam nas ruas da cidade.

91
.Algoritmo proposto
92
....
93
Tire o carro da garagem de ré
94
Pegue a rua no setido da sua direita
95
Siga em frente
96
Dobre na primeira rua à direita
97
Siga em frente
98
Dobre na primeira rua à esquerda
99
Siga em frente
100
Dobre na primeira rua à direita
101
Siga em frente
102
Procure a igreja ao seu lado esquerdo
103
Estacione em frente à igreja
104
....
105

106

107
.Rota para igreja descrita no algoritmo
108
image::images/{cap}/mapa_b.eps[scaledwidth="60%"]
109
110

Neste exemplo, os passos são descritos em sua ordem de execução de forma 
111
concisa e sem dubiedadesfootnote:[Sem ambiguidade.] em seu entendimento.
112

113
[NOTE]
114
115
.Pratique
====
116
117
118
Que tal fazer um algoritmo? Como seria o algoritmo para Guilherme ensinar seus 
amigos a chegarem no banco?

119
120
// XXX Não seria o caso de adicionar isso nas atividades?

121
122
123
124
====



125
==== Programa de Computador
126
127

Um programa de computador é essencialmente um algoritmo que diz ao computador 
128
os passos específicos e em que ordem eles devem ser executados.
129
130
131

Quando os procedimentos de um algoritmo envolvem o processamento de dados, a 
informação é lida de uma fonte de entrada, processada e retornada sob novo 
132
valor após processamento -- o que geralmente é realizado com o auxílio de um 
133
134
conjunto de instruções e estrutura de dados.

135
136
137
138
// Foto: Jessica Kourkounis / The New York Times     

[[fig_automatoA]]
.(a) Autômato suíço do século XIX escrevendo um poema
139
image::images/{cap}/automatoA.eps[scaledwidth="40%"]
140

141
142
[[fig_automatoB]]
.(b) Autômato do filme “A Invenção de Hugo Cabret”
143
image::images/{cap}/automatoB.eps[scaledwidth="40%"]
144
145
146


Algoritmos podem ser implementados em circuitos elétricos ou até mesmo em 
147
dispositivos mecânicos (autômatos, vide <<fig_automatoA>> e <<fig_automatoB>>). Mania dos inventores do 
148
149
século XIX, os autômatos eram máquinas totalmente mecânicas, construídas 
com a capacidade de serem programadas para realizar um conjunto de atividades 
150
autônomas. Em 2011, o filme 'A Invenção de Hugo Cabret' (tradução 
151
152
brasileira) do cineasta Martin Scorsese traz a história do ilusionista Georges 
Méliès precursor do cinema e um colecionador de autômatos, sendo uma de suas 
153
máquinas o fio condutor desta história. O autômato específico era capaz de 
154
155
desenhar a cena emblemática do seu filme "Viagem à Lua".

156
Entretanto, a maioria dos algoritmos são desenvolvidos para programas de 
157
158
computador, para isto, existe uma grande variedade de linguagens de 
programação, cada uma com características específicas que podem facilitar a 
159
160
161
162
implementação de determinados algoritmos, definiremos melhor uma linguagem de programação na <<sec_linguagem_programacao>>.

// Não ficou claro 'ou atender a propósitos mais gerais'
// removi por enquanto.
163

164
==== Construindo um algoritmo em sala de aula
165

166
Imagine que você queira ensinar o conceito de algoritmo para um grupo de 
167
alunos. Uma forma muito interessante de abordar a construção de um primeiro 
168
algoritmo em sala é apresentar um jogo que utilize uma sequência de passos 
169
170
171
172
lógicos para sua resolução. 

Peça para os alunos pensarem em uma solução e 
definir comandos em português a serem seguidos pelo seu colega ao lado. Se o colega obtiver 
173
174
175
176
177
178
179
180
êxito na resolução do jogo, seu algoritmo terá sido validado.

Propomos a abordagem do conhecido jogo “imprensadinho”, onde o jogador tem 
o objetivo de adivinhar um número escolhido aleatoriamente pelo seu 
adversário dentro de um intervalo de valores pré-estabelecido. O jogador 
pergunta por qualquer número dentro deste intervalo e o adversário tem que 
responder se o número escolhido foi descoberto ou não. O jogador ainda pode 
perguntar se o número a ser encontrado é maior ou menor que o número 
181
corrente testado. O jogo acaba quando o jogador descobre o número escolhido.
182

183
// TODO Adicionar ou linkar as regras do jogo de forma mais explícita.
184

185
.Proposta de algoritmo para o jogo `imprensadinho'
186
image::images/{cap}/imprenssadinho.eps[]
187

188

189
[TIP]
190
191
192
193
Antes de propor esta atividade a seus alunos, que tal tentar elaborar um 
algoritmo que formalize sua solução. Descreva testes a serem efetuados e 
instruções para descrever as decisões a serem tomadas.

194
195


196
[[sec_linguagem_programacao]]
197
=== Linguagem de Programação
198

199
200
(((Linguagem de Programação)))

201
Imagine aplicações para redes sociais, jogos eletrônicos e 
202
decodificadores de vídeo digital sendo implementados em linguagem de máquina 
203
(utilizando hexadecimal como na <<fig_exemplo_instrucao>>), seria uma tarefa impossível. Para isso, linguagens de 
204
205
206
207
208
209
programação foram desenvolvidas para permitir que algoritmos sejam 
aceitáveis para os humanos e facilmente convertidos em instruções de 
linguagem de máquina. Podemos definir uma linguagem de programação como um 
conjunto de palavras (vocabulário) e de regras (sintaxe) que permite a 
formulação de instruções a um computador.

210
==== Linguagem de máquina
211

212
Os códigos interpretados pelos primeiros computadores consistiam em 
213
instruções codificadas como dígitos numéricos. Escrever programas nesta 
214
linguagem, além de ser tedioso, é passível de muitos erros que devem 
215
216
217
218
ser localizados e corrigidos para finalizar o trabalho.

Na década de 40, pesquisadores desenvolveram um sistema de notação onde 
instruções numéricas podem ser representadas por mnemônicos. Por exemplo, a 
219
instrução a seguir poderia ser expressa numericamente usando uma linguagem de máquina como: `4056`
220

221
222
223
224
.Instrução
____
`Mova o conteúdo do registrador 5 para o registrador 6`
____
225

226
==== Linguagem assembly
227

228
Com o uso do sistema mnemônico, programas chamados *((montadores))* ('assemblers' em 
229
inglês) foram desenvolvidos para converter expressões mnemônicas em 
230
linguagem de máquina. Por isso, muitas vezes as linguagens mnemônicas são 
231
232
233
234
235
conhecidas como *linguagem ((assembly))*.

Em um sistema ((mnemônico)) podemos representar a instrução da seção anterior da seguinte forma:

 MOV   R5,   R6
236
237
238
239
240

Apesar da melhoria acarretada com a adoção do sistema mnemônico, sua 
programação ainda traz muitos dissabores aos desenvolvedores. A linguagem é 
uma troca direta de comandos básicos da linguagem de máquina, tornando a sua 
programação totalmente amarrada a arquitetura da máquina em que o código 
241
está sendo desenvolvido (dependência de plataforma).footnote:[  
242
243
244
Fazendo uma analogia com a construção de uma casa, seria necessário pensar 
em sua construção a partir de tijolos, canos, cimento, pedra e etc. Embora 
toda construção precise trabalhar com estes elementos básicos, durante o 
245
projeto de uma casa, o arquiteto pensa em termos de salas, varanda, portas e etc.]
246

247
248
NOTE: Por esta razão as linguagens de máquina e assembly são consideradas
linguagens da baixo nível (dependente da arquitetura).
249

250
251
252
253

==== Linguagens de alto nível

Os pesquisadores de computação desenvolveram a terceira 
254
255
geração de linguagens de programação, sendo suas primitivas básicas de 
alto nível e independentes de máquina, um diferencial das linguagens 
256
anteriores. Estas linguagens são desenvolvidas para usos mais especializados. 
257
Os exemplos mais conhecidos desta primeira fase das linguagens de alto nível 
258
são o FORTRAN (FORmula TRANslation), que foi desenvolvido para aplicações 
259
científicas e de engenharia, e o COBOL (Common Business-Oriented Language) 
260
261
262
263
264
desenvolvido para aplicações comerciais.

O objetivo das linguagens de alto nível era descrever operações sem se 
preocupar quais instruções de máquina seriam necessárias para implementar 
estas operações. Uma vez identificado este conjunto de primitivas de alto 
265
nível necessárias para o algoritmo, um programa, conhecido como *((tradutor))*, é 
266
acionado para converter programas escritos na linguagem de alto nível, em 
267
programas com linguagem de máquina.footnote:[Este software será estudado mais adiante na <<sec_tradutor_interpretador>>.] 
268

269
=== Paradigmas de Programação
270

271
(((Paradigmas de Programação)))
272

273
274
275
276
277
278
279
280
281
282
Um paradigma de programação fornece e determina a visão que o programador 
possui sobre a estruturação e execução do programa. Os paradigmas 
representam abordagens fundamentalmente diferentes para a construção de 
soluções para os problemas, portanto afetam todo o processo de 
desenvolvimento de software. A seguir serão descritos os paradigmas de 
programação clássicos:

Paradigma imperativo:: Descreve a computação como ações, enunciados ou 
comandos que mudam o estado (variáveis) de um programa. Muito parecido com o 
comportamento imperativo das linguagens naturais que expressam ordens como 
283
visto no algoritmo das rotas (<<sec_algoritmo_rotas>>).
284
285
286
287
288

Paradigma declarativo:: Descreve propriedades da solução desejada, não 
especificando como o algoritmo em si deve agir. Muito popular em linguagens de 
marcação, sendo utilizado na programação das páginas web (linguagem HTML) 
e descrição de documentos multimídia como a linguagem Nested Context 
289
290
291
292
293
Language – NCLfootnote:[Para conhecer NCL acesse http://www.gingancl.org.br/en/livrosecapitulosdelivros], adota pelo padrão brasileiro de TV Digital.
+
--
.Exemplo de código HTML
----
294
295
296
297
298
299
<h1>Frutas da estação</h1>
<ul>
  <li>Abacate</li>
  <li>Laranja</li>
  <li>Manga</li>
</ul>
300
301
----
--
302
303
304
305
306
307

Paradigma funcional:: Trata a computação como uma avaliação de funções 
matemáticas. Ela enfatiza a aplicação de funções, em contraste da 
programação imperativa, que enfatiza mudanças no estado do programa. Neste 
paradigma ao se pensar em uma função simples de calculo de médias de notas, 
usamos o auxílio de funções mais primitivas, podendo a função 
308
Media (Numeros) ser representada pela expressão:
309
+
310
----
311
 (Divide  (Soma Numeros)  (Conta Numeros) )
312
----
313
314
315
316
317
+
logo a função Divide opera com os resultados das funções Soma e Conta.  

Paradigma orientado a objeto::  Neste paradigma, diferente do paradigma 
imperativo, os dados passam a ter um papel principal na concepção do 
318
algoritmo. No paradigma imperativo, rotinas de controle manipulam os dados que 
319
320
321
são elementos passivos. Já na orientação a objetos, os dados são 
considerados objetos auto gerenciáveis formados pelos próprios dados e pelas 
rotinas responsáveis pela manipulação destes dados.  
322
323
324
325
326
+
--
.Exemplo de código orientado a objeto
[source, java]
----
327
328
carro.ligar();
carro.setVelocidade(100);
329
330
331
332
----
--


333

334
[[sec_tradutor_interpretador]]
335
=== Tradutor e Interpretador
336

337
338
339
340
// TODO melhorar este exemplo da bicicleta,
// geralmente as pessoas sabem andar de bicicleta


341
342
343
344
345
346
Ao receber uma bicicleta no natal Carlinhos precisa ler o manual de 
instruções e seguir passo a passo as tarefas descritas no documento para 
poder se divertir com seu presente. Podemos dizer que Carlinhos é um 
interpretador dos comandos fornecidos pelo manual de instruções. Entretanto 
seu pai encontrou uma promoção na internet e comprou um produto fabricado na 
França e o menino ao se deparar com o manual percebeu que o mesmo não poderia 
347
ser ``interpretado'', já que não sabia ler em francês. Para resolver o 
348
problema seu pai contratou um tradutor de francês para português, assim, este 
349
novo manual pôde ser ``interpretado'' por Carlinhos e enfim sua bicicleta 
350
351
352
353
354
355
seria montada. 

No computador, o problema de Carlinhos se repete diariamente, havendo a 
necessidade de softwares básicos para traduzir e interpretar os diversos 
programas dos usuários escritos em diversas linguagens existentes. Os 
softwares que convertem um programa de usuário escrito em uma linguagem para 
356
outra linguagem são chamados de *((tradutores))*. A linguagem na qual o programa 
357
358
359
360
original está expresso é chamada de linguagem fonte e a linguagem para a qual 
ela será convertida é conhecida como linguagem alvo. Tanto a linguagem fonte 
quanto a linguagem alvo definem níveis de abstração específicos.

361
362
// TODO Imagem?

363

364
O método de tradução é empregado quando há um *processador* (seja ele 
365
implementado em hardware ou por interpretação) disponível para executar 
366
367
368
programas expressos na linguagem alvo mas não na linguagem fonte. footnote:[Se existir um processador que possa executar diretamente programas escritos na 
linguagem fonte, não há necessidade de se traduzir o programa fonte para uma linguagem alvo.]
Se a tradução tiver sido feita corretamente, a execução do programa traduzido 
369
370
371
vai obter exatamente os mesmos resultados que a execução do programa fonte 
obteria se houvesse um processador que o executasse diretamente. 

372
[IMPORTANT]
373
É importante observar a diferença entre *tradução* e *interpretação*. Na 
374
375
376
tradução, o programa original, expresso na linguagem fonte, não é executado 
diretamente. Em vez da execução direta, esse programa precisa ser convertido 
para um programa equivalente, conhecido como programa objeto ou programa 
377
binário executável, que será executado após o término do processo de tradução. 
378
379
380

Logo, a tradução envolve dois passos distintos:

381
382
. Geração de um programa equivalente na linguagem alvo;
. Execução do programa obtido.
383

384
[NOTE]
385
386
387
No processo de interpretação existe apenas um único passo: a execução do 
programa original na linguagem fonte.

388
Nesta seção iremos analisar a função dos softwares básicosfootnote:[Programas necessários para que 
389
os softwares dos usuários implementados em alguma linguagem de programação 
390
391
específica possam ser executados em um computador.]: compilador, 
montador, ligador, carregador e interpretador.
392

393
=== Tradutores
394

395
396
397
398
399
400
Os *((tradutores))* podem ser divididos em dois grupos, dependendo da relação 
existente entre a linguagem fonte e a linguagem alvo. 

((Montador))::
Quando a linguagem fonte for essencialmente uma representação simbólica para uma linguagem de 
máquina numérica, o tradutor é chamado de montador e a linguagem fonte é chamada de linguagem de montagem. 
401

402
403
((Compilador)):: 
Quando a linguagem fonte for uma linguagem de 
404
alto nível, como é o caso do Pascal ou do C, e a linguagem alvo for uma 
405
linguagem de máquina numérica ou uma representação simbólica desta 
406
407
linguagem (linguagem de montagem), o tradutor é chamado de compilador.

408
Podemos observar na <<fig_processo_traducao_ligacao>> o processo de *((tradução))* e *((ligação))* de códigos
409
410
fonte, escrito em linguagens de programação, em um código binário executável. Nesta seção vamos
abordar apenas o processo de tradução (montagem ou compilação), o processo de ligação será visto depois.
411

412

413
////
414
[[fig_processo_compilacao]]
415
.Etapas do processo de compilação.
416
image::images/{cap}/processo_compilacao.eps[]
417
418
////

419
[[fig_processo_traducao_ligacao]]
420
["graphviz", "esquema-de-traducao.jpg"]
421
.Processos de tradução e ligação
422
423
424
425
426
427
428
429
430
431
432
----
digraph automata_0 {
  rankdir=LR;
  size ="8.5, 11";
  node [shape = box];
  
  subgraph clusterCodigos {
   label = "Código fonte";
   node [style=filled,color=white];
   style=filled;
   color=lightgrey;
433
   code_assembly [label="Linguagem de Baixo Nível\n(Linguagem de montagem)"];
434
435
436
437
438
439
440
441
442
443
444
445
   code_c [label="Linguagem de Alto Nível\n(Ex: C, Pascal, ...)"];
  }

  subgraph clusterTradutor {
   label = "Tradutor";
   node [style=filled,color=white,shape="doubleoctagon"];
   style=filled;
   color=lightgrey;
   montador [label="Montador"];
   compilador [label="Compilador"];
  }

446
447
  code_gerado [label="Código traduzido\n(Linguagem de montagem)"];

448
  subgraph clusterCodigoObjeto {
449
   label = "Código Objeto\n(binário)";
450
451
452
453
454
455
456
457
   node [style=filled,color=white];
   style=filled;
   color=lightgrey;
   objeto1 [label="Código Objeto 1"];
   objeto2 [label="Código Objeto 2"];
  }

  ligador [label="Ligador",shape="doubleoctagon"];
458
  programa [label="Código Binário\nExecutável", shape="component", fillcolor="grey", style="filled"];
459

460
461
  code_assembly -> montador -> objeto1 [color="forestgreen", style="bold"];
  code_c -> compilador -> code_gerado -> montador -> objeto2 [color="blue", style="bold"];
462

463
464
465
  objeto1->ligador [color="red", style="bold"];
  objeto2->ligador [color="red", style="bold"]; 
  ligador-> programa [color="red", style="bold"];
466
467
468
469
470
471
472
473

  {rank=source; code_c code_assembly }
  {rank=same; montador compilador}
  {rank=same; objeto1 objeto2}
  {rank=sink; programa}

}
----
474

475

476
477
478
479
480
481
482
483
484
485
486
487
==== Processo de Montagem

(((Montador)))

O processo de traduzir um programa em linguagem de montagem para programa em 
linguagem de máquina é chamado de *((processo de montagem))*. Este é um processo
simples, uma vez que existe um mapeamento de um para um dos comandos em 
linguagem de montagem para seus correspondentes em linguagem de máquina.

No processo de montagem, a instrução abaixo poderia ser traduzida no código
binário presente na <<fig_exemplo_instrucao>>.

488
.Instrução em linguagem de montagem
489
490
491
....
STORE [0xF3], regC 
....
492
493
494
495
496
497
498

////
Isto 
é o contrário da compilação, onde um comando em linguagem de alto nível 
pode ser traduzido em vários comandos em linguagem de máquina.
////

499
==== Processo de Compilação
500

501
502
(((Compilação)))

503
Diferente do processo de montagem de um programa em linguagem de montagem para 
504
um programa em linguagem de máquina, que é bastante simples, pois existe um 
505
506
507
508
mapeamento direto de um para um entre os comandos em linguagem de montagem e os 
equivalentes em código binário, o processo de compilação de linguagens é 
muito mais complexo.

509
===== Tarefas da compilação
510

511
Para compreender as tarefas do processo de compilação considere o comando de uma linguagem de alto nível a seguir:
512

513
 a = b + 4;
514

515
516
517
518
519
Diferente do processo de montagem, os comandos de alto nível não possuem um correspondente
único em linguagem de máquina, portanto o comando mencionado precisará ser traduzidos em várias
instruções de baixo nível.

O processo de compilação envolverá as seguintes etapas:
520

521
. Reduzir o texto do programa para símbolos básicos da linguagem, como 
522
523
identificadores tais como `a` e `b`, demarcações como o valor constante 4 e 
delimitadores do programa tais como `=` e `+`. Esta parte da compilação é 
524
chamada de *((análise léxica))*.
525

526
. Decodificar os símbolos para reconhecer a estrutura do programa. No comando 
527
528
usado acima, por exemplo, um programa chamado *((parser))* deve reconhecer o comando 
como sendo uma 'atribuição' de valores da forma:
529
530
+
----------------
531
<Identificador> "=" <Expressão>
532
533
----------------
+
534
onde `<Expressão>` é decodificado na forma:
535
536
+
----------------
537
<Identificador> "+" <Constante> 
538
539
----------------
+
540
Essa tarefa é chamada de *((análise sintática))*.
541

542
543
. Análise de nomes: associar os nomes `a` e `b` com variáveis do programa, e 
associá-los também a *posições de memória* específicas onde essas variáveis 
544
serão armazenadas durante a execução.
545

546
. Análise de tipos: determinar os tipos de todos os dados. No caso anterior, 
547
548
as variáveis `a` e `b` e a constante `4` seriam reconhecidas como sendo do tipo `int` 
em algumas linguagens. As análises de nome e tipo são também conhecidas como *((análise semântica))*: 
549
determina o significado dos componentes do programa.
550

551
. Mapeamento de ações e geração de código: associar comandos do programa 
552
553
554
555
556
com uma sequência em linguagem de montagem apropriada. No caso anterior, a 
sequência em linguagem de montagem poderia ser:
+
.Comando de atribuição
--------------------------
557
ld[b], %r0, %r1    // Carregue variável b em um registrador.
558
add %r1, 4, %r2    // Calcule o valor da expressão.
559
st %r2, %r0, [a]   // Faça a atribuição na variável a.
560
561
--------------------------

562
563
564
565
566
567
568
569
570

. Existem etapas adicionais que o compilador deve tomar, tais como, alocar 
variáveis a registradores, usar registradores e otimizar o código gerado.

[NOTE]
.Otimizador de código
====
O otimizador de código é um módulo opcional nos compiladores e pode ser
acionado pelo desenvolvedor na etapa de compilação. A otimização irá
571
gerar códigos mais eficientes.
572
====
573

574

575

576
[[sec_ligacao]]
577
=== Ligação
578

579
580
A maioria dos programas é composto de mais de um procedimento. Os compiladores 
e os montadores geralmente traduzem um procedimento de cada vez, colocando a 
581
saída da tradução em disco. Antes que o programa possa ser executado, todos os seus 
582
583
584
procedimentos precisam ser localizados e ligados uns aos outros de maneira a 
formarem um único código.

585
A função do ((ligador)) (<<fig_processo_traducao_ligacao>>) é coletar procedimentos traduzidos separadamente e 
586
ligá-los uns aos outros para que eles possam executar como uma unidade chamada 
587
código binário executável (o programa).
588
589
590
591
592
593

Se o compilador ou o montador lesse um conjunto de procedimentos fonte e 
produzisse diretamente um programa em linguagem de máquina pronto para ser 
executado, bastaria que um único comando fonte fosse alterado para que todos 
os procedimentos fonte tivessem que ser novamente traduzidos.

594
Usando a técnica do código objeto separado, o único procedimento a ser 
595
novamente traduzido seria aquele modificado. Havendo a necessidade de realizar 
596
apenas a etapa de ligação dos códigos separados novamente, sendo esta tarefa 
597
598
mais rápida que a tradução.

599
=== Carregamento
600

601
O ((carregador)) é um programa que coloca um módulo de carregamento na memória 
602
603
604
605
606
607
608
principal. Conceitualmente, a tarefa do carregador não é difícil. Ele deve 
carregar os vários segmentos de memória com seus valores corretos e 
inicializar certos registradores, tais como o apontador para pilha do sistema, 
responsável pelo escopo das rotinas que estarão em execução e o contador de 
instruções contido no processador, com seus valores iniciais, indicando assim 
onde o programa deve ser iniciado.

609
["graphviz", "esquema-de-carregamento.jpg", scaledwidth="60%"]
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
.Esquema de carregamento
----
digraph automata_0 {
  rankdir=LR;
  size ="8.5, 11";
  node [shape = box];
  
  programa [label="Código Binário\nExecutável", shape="component", fillcolor="grey", style="filled"];
  carregador [label="Carregador",shape="hexagon"];
  memoria  [label="Memória Princial", shape="box3d"];

  programa -> carregador -> memoria;

  {rank=source; programa}
  {rank=sink; memoria}

}
----

629
630
631
632
633
634
635
636
637
638
639
640
Em Sistemas Operacionais modernos, vários programas estão residentes na 
memória a todo instante, e não há como o montador ou o ligador saber em 
quais endereços os módulos de um programa irão residir. O carregador deve 
relocar estes módulos durante o carregamento adicionando um deslocamento a 
todos os endereços, permitindo desta forma acessar cada módulo 
individualmente na memória.

Esse tipo de carregamento é chamado de carregamento com relocação. O 
carregador simplesmente modifica endereços relocáveis dentro de um único 
módulo de carregamento para que vários programas passem a residir na memória 
simultaneamente.

641
=== Interpretadores
642

643
644
645
(((Interpretadores)))

O software interpretador é um programa de computador que executa instruções 
646
647
648
649
escritas em uma linguagem de programação. Por exemplo, as linguagens Basic, 
Prolog, Python e Java, são frequentemente interpretados. Um interpretador 
geralmente usa uma das seguintes estratégias para a execução do programa: executar
 o código fonte diretamente ou traduzir o código fonte em alguma eficiente 
650
representação intermediária e depois executar este código (<<fig_esquema_interpretacao>>).
651

652
[[fig_esquema_interpretacao]]
653
["graphviz", "esquema-interpretador.jpg"]
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
.Esquema de interpretação
----
digraph automata_0 {
  rankdir=LR;
  size ="8.5, 11";
  node [shape = box];
  
  subgraph clusterCodigos {
   label = "Código fonte";
   node [style=filled,color=white];
   style=filled;
   color=lightgrey;
   code_f [label="Código fonte \n(Ex: Basic, Prolog, Python)"];
   code_i [label="Código fonte \n(Ex: Java)"];
  }

  subgraph clusterTradutor {
   label = "Tradutor";
   node [style=filled,color=white,shape="doubleoctagon"];
   style=filled;
   color=lightgrey;
   compilador [label="Compilador"];
  }

  subgraph clusterInterpretador {
   label = "Interpretador";
   node [style=filled,color=white,shape="doubleoctagon"];
   style=filled;
   color=lightgrey;
   interpretador_f [label="Interpretador"];
   interpretador_i [label="Interpretador"];
  }


  code_gerado [label="Código intermediário"];

690
691
  code_f -> interpretador_f [style="bold"];
  code_i -> compilador -> code_gerado -> interpretador_i [style="bold"];
692
693


694
695
696
697
698
699
  {rank=source; code_f code_i }
  {rank=sink; interpretador_f interpretador_i}

}
----

700

701
Para isso, certos tipos de tradutores transformam uma linguagem fonte em uma 
702
linguagem simplificada, chamada de *((código intermediário))*, que pode ser 
703
diretamente ``executado'' por um programa chamado interpretador. Nós podemos 
704
imaginar o código intermediário como uma linguagem de máquina de um 
705
computador abstrato projetado para executar o código fonte. 
706

707
708
[NOTE]
====
709
710
711
Interpretadores são, em geral, menores que compiladores e facilitam a 
implementação de construções complexas em linguagens de programação. 
Entretanto, o tempo de execução de um programa interpretado é geralmente 
712
maior que o tempo de execução deste mesmo programa compilado, pois o 
713
714
interpretador deve analisar cada declaração no programa a cada vez que é 
executado e depois executar a ação desejada, enquanto que o código compilado 
715
apenas executa a ação dentro de um contexto fixo, anteriormente determinado 
716
pela compilação. Este tempo no processo de análise é conhecido como 
717
718
*((overhead interpretativa))*.
====
719

720
721
=== Conteúdos complementares

722
723
Nesta seção reunimos informações complementares aos conteúdos apresentados no capítulo.

724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
==== Características dos softwares montadores

Embora a montagem seja um processo simples, é tedioso e passível de erros 
quando feito manualmente. Montadores comerciais têm ao menos as seguintes 
características:

* Permitem ao programador especificar posição de valores de dados e programas 
durante a execução;
* Permitem que o programador de início realize valores de dados na memória 
antes da execução do programa;
* Implementam mnemônicos em linguagem de montagem para todas as instruções 
da máquina e modos de endereçamento, e traduzem comandos em linguagem de 
montagem válidos, nos seus equivalentes em linguagem de máquina;
* Permitem o uso de rótulos simbólicos para representar endereços e 
constantes;
* Incluem um mecanismo que permite que variáveis sejam definidas em um 
programa em linguagem de montagem e usadas em outros programas separadamente;
* Possibilitam a expansão de macros, ou seja, rotinas (semelhantes às funções 
em linguagem de alto nível) que podem ser definidas uma vez e então 
instanciadas quantas vezes necessário.

==== Montadores de dois passos

A maioria dos montadores leem textos do programa em linguagem de montagem duas 
vezes, e são chamados de ``montadores de dois passos''. O primeiro passo 
serve para determinar o endereço de todos os itens de dados e instruções de 
máquina, e selecionar quais instruções devem ser geradas para cada 
instrução em linguagem de montagem (mais ainda não gerá-las).

Os endereços dos itens de dados e instruções são determinados por meio do 
uso de um contador de programa para a montagem, chamado contador de 
localização. O contador de localização gerencia o endereço da instrução 
executada e dos itens de dados durante a montagem, que geralmente é 
inicializada com `0` (zero). No início do primeiro passo, é incrementado de 
acordo com o tamanho de cada instrução.

Durante este passo, o montador também efetua quaisquer operações 
aritméticas em tempo de montagem, e insere as definições de todos os 
rótulos de funções e variáveis e as constantes, em uma tabela chamada 
Tabela de Símbolos.

A razão principal para exigir uma segunda passagem é permitir que símbolos 
sejam usados no programa antes de serem definidos. Após a primeira passagem, o 
montador terá identificado todos os símbolos e os colocado na Tabela de 
Símbolos, já durante a segunda passagem, gerará código de máquina, 
inserindo os identificadores dos símbolos que agora são conhecidos.


==== Por que usar uma Linguagem de Montagem?

Programar em uma linguagem de montagem não é fácil. Além da dificuldade, o 
desenvolvimento de um programa na linguagem de montagem consome mais tempo do 
776
que seu desenvolvimento em uma linguagem de alto nível. A _depuração_ e 
777
778
manutenção dos programas em linguagem de montagem são mais complicados.

779
780
781
782
NOTE: *((Depuração))* (em inglês: debugging, debug) é o processo de encontrar e reduzir defeitos num 
aplicativo de software ou mesmo em hardware. Erros de software incluem aqueles que previnem o 
programa de ser executado e aqueles que produzem um resultado inesperado. Para saber mais consulte:
http://pt.wikipedia.org/wiki/Depuração.
783
784
785
786
787

Nessas condições, por que alguém escolheria programar em uma linguagem de 
montagem? 

Existem duas razões que justificam esta opção: performance e acesso aos recursos 
788
da máquina. Um 'expert' na linguagem de montagem pode produzir um código menor 
789
790
791
792
e muito mais eficiente do que o gerado por um programador usando linguagem de 
alto nível.

Em segundo lugar, certos procedimentos precisam ter acesso total ao hardware. 
793
Por exemplo, se a máquina alvo tiver um bit para expressar o 'overflow' de 
794
795
796
797
798
799
operações aritméticas, um programa em linguagem de montagem pode testar 
diretamente este bit, coisa que um programa em Java não pode fazer. Além 
disso, um programa em linguagem de montagem pode executar qualquer uma das 
instruções do conjunto de instruções da máquina alvo.


800
801
=== Prática

802
No <<pratica_compilacao>> é possível encontrar uma prática para compreender
803
os processos de compilação e ligação.
804

805
=== Recapitulando
806

807
Neste capítulo estudamos o conceito de algoritmo e vimos que o mesmo pode ser 
808
809
810
811
812
813
814
implementado por diversos mecanismos mecânicos e elétricos. Um algoritmo é 
descrito em um computador através de uma linguagem de programação. São 
diversos os níveis de abstração em cada linguagem, cada uma com um objetivo 
distinto. Para que todas estas linguagens possam coexistir no computador foram 
criados software básicos com o objetivo de realizar a execução do algoritmo 
descrito através destas linguagens de programação.

815
Dentre os softwares básicos estudados vimos os Tradutores e Interpretadores, 
816
cada um com seu uso exclusivo. Os Tradutores ainda podem ser classificados em 
817
Compiladores e Montadores, ambos tendo como objetivo traduzir uma linguagem 
818
819
820
fonte para uma linguagem alvo cujo Interpretador seja implementado no 
computador corrente.

821
822
// TODO ponte para o próximo capítulo.

823
=== Atividades
824

825
. Quais os ganhos que as linguagens de programação de alto nível trazem 
826
para os programadores?
827
828
829
830

. Descreva 3 diferentes paradigmas de programação.

. Sistemas Operacionais são tipos de software básico? Quais os tipos de 
831
softwares básicos existentes?
832

833
. Marque a alternativa correta. Um interpretador, a partir de um programa-fonte:
834
.. Gera um programa-objeto para posterior execução
835
836
837
838
.. Efetua a tradução para uma linguagem de mais alto nível
.. Interpreta erros de lógica
.. Executa instrução a instrução, sem gerar um programa-objeto
.. Não detecta erros de sintaxe
839
840

. Qual a função de uma linguagem de montagem (linguagem assembly)?
841
842
. Quais as diferenças entre *interpretador* e  *tradutor*?
. Quais as diferenças entre  *compilador* e  *montador*?
843
844


845

846
847
// Sempre manter uma linha em branco no final