cap5-tradutor.asc 29.4 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

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

.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.

____________________


17
=== Algoritmos
18

19
20
(((Algoritmos)))

21
Historiadores trazem divergências sobre a origem da palavra algoritmo, sendo a 
22
23
24
25
26
27
28
29
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 
30
por Alan Turing (Máquina de Turing) e Alonzo Church, que formaram as primeiras 
31
fundações da Ciência da Computação. Sendo esta formalização descrita a 
32
33
34
35
36
37
38
39
40
41
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 
42
43
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 
44
segundo, e assim por diante.footnote:[Muitos algoritmos, conhecidos como algoritmos 
45
46
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 
47
sequências dos passos podem intercalar entre si dependendo do ambiente de 
48
execução, entretanto, dentro de uma mesma sequência sua ordem de execução 
49
não muda durante o processo.]
50

51
Seguindo a definição, todo algoritmo deve consistir em passos executáveis. 
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
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. 


==== Exemplo de um Algoritmo

76
Guilherme recebe alguns convidados que estão visitando a cidade em sua casa e precisa 
77
ensiná-los a chegar à igreja para a missa do domingo. O anfitrião muito 
78
organizado apresenta o mapa de seu bairro como visto na <<fig_mapa_cidade>> e propõe o 
79
80
81
seguinte algoritmo para que seus amigos não se percam nas ruas da cidade.

.Algoritmo
82
....
83
Tire o carro da garagem
84
Pegue a rua à esquerda
85
86
87
88
89
90
91
92
93
Siga em frente
Pegue a primeira rua à direita
Siga em frente
Pegue a primeira rua à esquerda
Siga em frente
Pegue a primeira à direita
Siga em frente
Procure a igreja no lado esquerdo
Estacione em frente à igreja
94
....
95

96
[[fig_mapa_cidade]]
97
98
.Mapa da cidade de Guilherme
image::images/tradutor/mapa_a.png[scaledwidth="60%"]
99

100

101
102
.Rota para igreja descrita no algoritmo
image::images/tradutor/mapa_b.png[scaledwidth="60%"]
103
104
105
106

Neste exemplo, os passos são descritos em sua ordem de execução de forma 
concisa e sem dubiedades em seu entendimento.

107
[NOTE]
108
109
110
Que tal fazer um algoritmo? Como seria o algoritmo para Guilherme ensinar seus 
amigos a chegarem no banco?

111
112
// XXX Não seria o caso de adicionar isso nas atividades?

113
==== Programa de Computador
114
115
116
117
118
119
120
121

Um programa de computador é essencialmente um algoritmo que diz ao computador 
os passos específicos e em que ordem eles devem ser executados, como por 
exemplo, os passos a serem tomados para calcular as notas que serão impressas 
nos boletins dos alunos de uma escola.

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 
122
valor após processamento, o que geralmente é realizado com o auxílio de um 
123
124
conjunto de instruções e estrutura de dados.

125
126
127
128
// Foto: Jessica Kourkounis / The New York Times     

[[fig_automatoA]]
.(a) Autômato suíço do século XIX escrevendo um poema
129
image::images/tradutor/automatoA.png[scaledwidth="40%"]
130

131
132
[[fig_automatoB]]
.(b) Autômato do filme “A Invenção de Hugo Cabret”
133
image::images/tradutor/automatoB.png[scaledwidth="40%"]
134
135
136


Algoritmos podem ser implementados em circuitos elétricos ou até mesmo em 
137
dispositivos mecânicos (autômatos, vide <<fig_automatoA>> e <<fig_automatoB>>). Mania dos inventores do 
138
139
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 
140
autônomas. Em 2011, o filme 'A Invenção de Hugo Cabret' (tradução 
141
142
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 
143
máquinas o fio condutor desta história. O autômato específico era capaz de 
144
145
desenhar a cena emblemática do seu filme "Viagem à Lua".

146
Entretanto, a maioria dos algoritmos são desenvolvidos para programas de 
147
148
149
computador, para isto, existe uma grande variedade de linguagens de 
programação, cada uma com características específicas que podem facilitar a 
implementação de determinados algoritmos ou atender a propósitos mais 
150
gerais, definiremos melhor uma linguagem de programação na <<sec_linguagem_programacao>>.
151

152
==== Construindo um algoritmo em sala de aula
153
154
155

Imagine que o leitor queira ensinar o conceito de algoritmo para um grupo de 
alunos. Uma forma muito interessante de abordar a construção de um primeiro 
156
algoritmo em sala é apresentar um jogo que utilize uma sequência de passos 
157
lógicos para sua resolução. Peça para os alunos pensarem em uma solução e 
158
definir comandos em português a serem seguidos pelo seu colega ao lado para 
159
160
161
162
163
164
165
166
167
resolver o problema através de sua solução proposta. Se o colega obtiver 
ê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 
168
corrente testado. O jogo acaba quando o jogador descobre o número escolhido.
169
170


171
172
173
.Proposta de algoritmo para o “imprenssadinho”
image::images/tradutor/imprenssadinho.png[]

174

175
[NOTE]
176
177
178
179
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.

180
[[sec_linguagem_programacao]]
181
=== Linguagem de Programação
182

183
184
(((Linguagem de Programação)))

185
186
187
188
189
190
191
192
193
Imagine aplicações para redes sociais como o Facebook, jogos eletrônicos e 
decodificadores de vídeo digital sendo implementados em linguagem de máquina 
(linguagem binária), seria uma tarefa impossível. Para isso, linguagens de 
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.

194
==== Primeiras gerações
195

196
Os códigos interpretados pelos primeiros computadores consistiam em 
197
instruções codificadas como dígitos numéricos. Escrever programas nesta 
198
linguagem, além de ser tedioso, é passível de muitos erros que devem 
199
200
201
202
203
204
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 
instrução

205
 Mova o conteúdo do registrador 3 para o registrador 1
206

207
expressa numericamente como:
208
209
210
211
212
213
214
215

 4056

usando uma linguagem de máquina. Já em um sistema mnemônico podemos 
representar esta instrução como:

 MOV   R5,   R6

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

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 
está sendo desenvolvido (dependência de plataforma). E a filosofia de 
desenvolvimento era toda baseada em comandos de mais baixo nível da máquina. 
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 
projeto de uma casa, o arquiteto pensa em termos de salas, varanda, portas e 
etc.

Com esta filosofia os pesquisadores de computação desenvolveram a terceira 
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 
236
anteriores. Estas linguagens são desenvolvidas para usos mais especializados. 
237
Os exemplos mais conhecidos desta primeira fase das linguagens de alto nível 
238
são o FORTRAN (FORmula TRANslation), que foi desenvolvido para aplicações 
239
científicas e de engenharia, e o COBOL (Common Business-Oriented Language) 
240
241
242
243
244
245
246
247
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 
nível necessárias para o algoritmo, um programa, conhecido como tradutor, é 
acionado para converter programas escritos na linguagem de alto nível, em 
programas com linguagem de máquina. Este software entre outros serão melhor 
248
detalhados na <<sec_tradutor_interpretador>>. 
249

250
==== Paradigma de Programação
251

252
253
(((Paradigma de Programação)))

254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
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 
visto no algoritmo das rotas.

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 
Language – NCL, adota pelo padrão brasileiro de TV Digital. 

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 
277
Media (Numeros) ser representada pela expressão:
278
279
280
281
282
283
284
+
 (Divide  (Soma Numeros)  (Conta Numeros) )
+
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 
285
algoritmo. No paradigma imperativo, rotinas de controle manipulam os dados que 
286
287
288
289
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.  

290
[[sec_tradutor_interpretador]]
291
=== Tradutor e Interpretador
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343

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 
ser “interpretado” já que não sabia ler em francês. Para resolver o 
problema seu pai contratou um tradutor de francês para português, assim, este 
novo manual pôde ser “interpretado” por Carlinhos e enfim sua bicicleta 
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 
outra linguagem são chamados de tradutores. A linguagem na qual o programa 
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.

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.

O método de tradução é empregado quando há um processador (seja ele 
implementado em hardware ou por interpretação) disponível para executar 
programas expressos na linguagem alvo mas não na linguagem fonte. Se a 
tradução tiver sido feita corretamente, a execução do programa traduzido 
vai obter exatamente os mesmos resultados que a execução do programa fonte 
obteria se houvesse um processador que o executasse diretamente. 

É importante observar a diferença entre tradução e interpretação. Na 
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 
binário executável, que será executado após o término do processo de 
tradução. 

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

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

No processo de interpretação existe apenas um único passo: a execução do 
programa original na linguagem fonte.

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

344
==== Tradutores
345

346
347
(((Tradutores)))

348
349
350
Os tradutores podem ser divididos em dois grupos, dependendo da relação 
existente entre a linguagem fonte e a linguagem alvo. Quando a linguagem fonte 
for essencialmente uma representação simbólica para uma linguagem de 
351
máquina numérica, o tradutor é chamado de montador e a linguagem fonte é 
352
353
chamada de linguagem de montagem. Quando a linguagem fonte for uma linguagem de 
alto nível, como é o caso do Pascal ou do C, e a linguagem alvo for uma 
354
linguagem de máquina numérica ou uma representação simbólica desta 
355
356
linguagem (linguagem de montagem), o tradutor é chamado de compilador.

357
Podemos observa na <<fig_processo_compilacao>> todos os passos necessários para que um 
358
359
360
361
362
algoritmo expresso em uma linguagem de programação possa ser carregado em 
memória para ser executado por um computador. Cada fase possui um conjunto de 
entradas e saídas de seu processamento. Estas fases e seus respectivos 
softwares envolvidos são descritas nas seções seguintes.

363
[[fig_processo_compilacao]]
364
.Etapas do processo de compilação.
365
image::images/tradutor/processo_compilacao.png[]
366

367
==== Processo de Compilação
368

369
370
(((Compilação)))

371
Diferente do processo de montagem de um programa em linguagem de montagem para 
372
um programa em linguagem de máquina, que é bastante simples, pois existe um 
373
374
375
376
377
378
379
380
381
382
383
384
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.

===== Passos da compilação

Considere o comando simples abaixo:

 A = B + 4;

O compilador tem que resolver um número grande de tarefas na conversão deste 
comando em um ou mais comandos em linguagem de montagem:
385

386
. Reduzir o texto do programa para símbolos básicos da linguagem, como 
387
388
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 é 
389
chamada de ((análise léxica)).
390

391
. Decodificar os símbolos para reconhecer a estrutura do programa. No comando 
392
393
394
395
396
397
398
usado acima, por exemplo, um programa chamado parser deve reconhecer o comando 
como sendo uma atribuição de valores da forma:
+
----------------
<Identificador> “=” <Expressão>
----------------
+
399
onde `<Expressão>` é decodificado na forma:
400
401
402
403
404
+
----------------
<Identificador> “+” <Constante> 
----------------
+
405
Essa tarefa é chamada de ((análise sintática)).
406

407
. Análise de nomes: associar os nomes A e B com variáveis do programa, e 
408
associá-los também a posições de memória específicas onde essas variáveis 
409
serão armazenadas durante a execução.
410

411
. Análise de tipos: determinar os tipos de todos os dados. No caso anterior, 
412
413
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)): 
414
determina o significado dos componentes do programa.
415

416
. Mapeamento de ações e geração de código: associar comandos do programa 
417
418
419
420
421
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
--------------------------
422
423
424
ld[B], %r0, %r1    // Carrege variável B em um registrador.
add %r1, 4, %r2    // Calcule o valor da expressão.
st %r2, %r0, [A]   // Faça a atribuição na variável A.
425
426
--------------------------

427
. Existem passos adicionais que o compilador deve tomar, tais como, alocar 
428
429
430
431
432
433
variáveis a registradores, usar registradores e, quando o programador desejar, 
otimizar o programa. O otimizador de código (independente de máquina) é um 
módulo opcional (presente na grande maioria dos compiladores) que objetiva 
melhorar o código intermediário de modo que o programa objeto produzido ao 
fim da compilação seja menor (ocupe menos espaço de memória) e/ou mais 
rápido (tenha tempo de execução menor). A saída do otimizador de código é 
434
um novo ((código intermediário)).
435

436

437
==== Processo de Montagem
438

439
(((Montador)))
440

441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
O processo de traduzir um programa em linguagem de montagem para programa em 
linguagem de máquina é chamado de processo de montagem. Este processo é 
muito simples, uma vez que existe um mapeamento um para um de comandos em 
linguagem de montagem para seus correspondentes em linguagem de máquina. 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.

===== 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 
que seu desenvolvimento em uma linguagem de alto nível. A depuração e 
manutenção dos programas em linguagem de montagem são mais complicados.

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

458
Existem duas razões que justificam esta opção: performance e acesso aos recursos 
459
460
461
462
463
464
465
466
467
468
469
470
471
da máquina. Um expert na linguagem de montagem pode produzir um código menor 
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. 
Por exemplo, se a máquina alvo tiver um bit para expressar o overflow de 
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.

===== Tarefas do montador

472
Embora a montagem seja um processo simples, é tedioso e passível de erros 
473
474
475
476
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 
477
durante a execução;
478
* Permitem que o programador de início realize valores de dados na memória 
479
antes da execução do programa;
480
481
* 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 
482
montagem válidos, nos seus equivalentes em linguagem de máquina;
483
* Permitem o uso de rótulos simbólicos para representar endereços e 
484
constantes;
485
* Incluem um mecanismo que permite que variáveis sejam definidas em um 
486
487
programa em linguagem de montagem e usadas em outros programas separadamente;
* Possibilitam a expansão de macros, ou seja, rotinas (semelhantes às funções 
488
489
490
491
492
493
494
495
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 
496
máquina, e selecionar quais instruções devem ser geradas para cada 
497
498
499
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 
500
uso de um contador de programa para a montagem, chamado contador de 
501
502
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 é 
503
504
inicializada com `0` (zero). No início do primeiro passo, é incrementado de 
acordo com o tamanho de cada instrução.
505
506
507
508
509
510
511
512
513
514
515
516

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.

517
==== Ligação e Carregamento
518

519
520
A maioria dos programas é composto de mais de um procedimento. Os compiladores 
e os montadores geralmente traduzem um procedimento de cada vez, colocando a 
521
522
523
524
saída da tradução em disco. Antes que o programa possa rodar, todos os seus 
procedimentos precisam ser localizados e ligados uns aos outros de maneira a 
formarem um único código.

525
===== Ligação
526

527
528
A função do ((ligador)) é coletar procedimentos traduzidos separadamente e 
ligá-los uns aos outros para que eles possam executar como uma unidade chamada 
529
530
531
532
533
534
535
536
537
538
539
540
programa binário executável.

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.

Usando a técnica do módulo objeto separado, o único procedimento a ser 
novamente traduzido seria aquele modificado. Havendo a necessidade de realizar 
apenas a etapa de ligação dos módulos separados novamente, sendo esta tarefa 
mais rápida que a tradução.

541
===== Carregamento
542

543
O ((carregador)) é um programa que coloca um módulo de carregamento na memória 
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
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.

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.

563
=== Interpretadores
564

565
566
567
(((Interpretadores)))

O software interpretador é um programa de computador que executa instruções 
568
569
570
571
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 
572
573
574
575
576
577
representação intermediária e depois executar este código.

Para isso, certos tipos de tradutores transformam uma linguagem fonte em uma 
linguagem simplificada, chamada de código intermediário, que pode ser 
diretamente “executado” por um programa chamado interpretador. Nós podemos 
imaginar o código intermediário como uma linguagem de máquina de um 
578
computador abstrato projetado para executar o código fonte. 
579
580
581
582

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 
583
maior que o tempo de execução deste mesmo programa compilado, pois o 
584
585
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 
586
apenas executa a ação dentro de um contexto fixo, anteriormente determinado 
587
588
589
pela compilação. Este tempo no processo de análise é conhecido como 
"overhead interpretativa".

590
591
=== Prática

592
Em <<pratica_compilacao>> é possível encontrar uma prática para compreender
593
os processos de compilação e ligação.
594

595
=== Recapitulando
596

597
Neste capítulo estudamos o conceito de algoritmo e vimos que o mesmo pode ser 
598
599
600
601
602
603
604
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.

605
Dentre os softwares básicos estudados vimos os Tradutores e Interpretadores, 
606
cada um com seu uso exclusivo. Os Tradutores ainda podem ser classificados em 
607
Compiladores e Montadores, ambos tendo como objetivo traduzir uma linguagem 
608
609
610
fonte para uma linguagem alvo cujo Interpretador seja implementado no 
computador corrente.

611
=== Atividades
612

613
. Quais os ganhos que as linguagens de programação de alto nível trazem 
614
para os programadores?
615
616
617
618

. Descreva 3 diferentes paradigmas de programação.

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

621
. Marque a alternativa correta. Um interpretador, a partir de um programa-fonte:
622
.. Gera um programa-objeto para posterior execução
623
624
625
626
.. 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
627
628
629
630

. Qual a função de uma linguagem de montagem (linguagem assembly)?
. Quais as diferenças entre software interpretador e software tradutor?
. O compilador e o montador são softwares tradutores. Qual a diferença entre eles?
631
632
633

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

634
635
// Sempre manter uma linha em branco no final