apostila
Pré-visualização50 páginas
a notac¸a˜o ou linguagem de “alto n´ıvel”, que vai exigir a introduc¸a˜o dos chamados compiladores. 4.4 Abstrac¸a˜o das instruc¸o˜es (linguagem) Apesar de todas as notac¸o˜es e convenc¸o˜es que foram feitas no programa, ate´ se chegar na versa˜o mostrada na figura 4.9, de certa maneira, o programa ainda esta´ em um formato muito parecido com o do programa original. Para que seja poss´ıvel aumentar o n´ıvel de notac¸a˜o ainda mais e´ preciso contar com a ajuda de programas tradutores, ou como eles sa˜o mais conhecidos, os compiladores. Estes programas conseguem receber como entrada um texto escrito em um for- mato adequado e gerar como sa´ıda um programa no formato da ma´quina. Isto e´ 32 CAPI´TULO 4. O MODELO DO COMPUTADOR dois ← 2 quatro ← 4 B ← ∨ quadradoB ← B × B C ← ∨ quadruploC ← quatro × C discriminante ← quadradoB - quadruploC raizDiscriminante ← √discriminante dobroMenorRaiz ← B - raizDiscriminante menorRaiz ← dobroMenorRaiz dois � ← menorRaiz dobroMaiorRaiz ← B + raizDiscriminante maiorRaiz ← dobroMaiorRaiz dois � ← maiorRaiz • Figura 4.9: Programa reescrito com nomes para varia´veis. poss´ıvel apenas se os programas forem escritos em um formato que respeite regras extremamente r´ıgidas, pois sena˜o a tarefa na˜o seria poss´ıvel. As linguagens de alto n´ıvel sa˜o definidas a partir de uma grama´tica extremamente mais r´ıgida que a do portugueˆs, por exemplo. Estas grama´ticas, conhecidas como grama´ticas livre de contexto, teˆm como uma de suas principais caracter´ısticas que elas na˜o permitem escrever programas amb´ıguos. O portugueˆs permite. Sem entrarmos muito em detalhes desta grama´tica, a t´ıtulo de exemplo mostrare- mos verso˜es em mais alto n´ıvel do programa da figura 4.9. Estas verso˜es sa˜o apresen- tadas na figura 4.10. read B read C discriminante ← B2 - 4 × C raizDiscriminante ← √discriminante menorRaiz ← B−raizDiscriminante 2 write menorRaiz maiorRaiz ← B+raizDiscriminante 2 write maiorRaiz read B read C raizDiscriminante ← √B2 − 4× C write B - raizDiscriminante 2 write C + raizDiscriminante 2 Figura 4.10: Duas outras verso˜es do programa. Estas verso˜es sa˜o compreens´ıveis para o ser humano, mas ainda na˜o esta˜o no formato ideal para servirem de entrada para o compilador, em particular por causa dos s´ımbolos de frac¸a˜o ou do expoente. Os compiladores exigem um grau maior de rigidez, infelizmente. A disciplina Construc¸a˜o de Compiladores, no sexto per´ıodo do curso, e´ exclusiva para o estudo profundo dos motivos desta dificuldade, tanto de se verificar se o programa esta´ correto do ponto de vista gramatical, quanto do ponto de vista de se traduzir o programa para linguagem de ma´quina. 4.5. CONCLUSA˜O 33 No momento, vamos nos limitar a apresentar na figura 4.11 uma versa˜o do mesmo programa escrito em Pascal. Apo´s compilac¸a˜o, o resultado e´ um programa que pode ser executado pelo computador. Em suma, o compilador Pascal e´ um programa que, entre outras coisas, consegue transformar o co´digo de alto n´ıvel mostrado na figura 4.11 e gerar um co´digo que o computador possa executar tal como mostrado na primeira figura. program bascara (input ,output) ; var b, c , raiz discriminante : real ; begin read (b) ; read (c) ; raizdiscriminante:= sqrt(b∗b − 4∗c) ; write ((b − raizdiscriminante)/2) ; write ((b + raizdiscriminante)/2) ; end. Figura 4.11: Versa˜o do programa escrito em Pascal. 4.5 Conclusa˜o Nesta parte do texto procuramos mostrar que qualquer linguagem de programac¸a˜o de alto n´ıvel (tal como Pascal, C ou JAVA) e´ meramente uma notac¸a˜o convencionada visando facilitar a vida do ser humano que programa o computador. Esta notac¸a˜o trata de como um texto se traduz em um programa executa´vel em um determinado sistema operacional (que usa um determinado conjunto reduzido de instruc¸o˜es). Um programa que traduz um texto que emprega uma certa notac¸a˜o convencionada em um programa executa´vel e´ chamado de “compilador”. Assim, a arte de se programar um computador em alto n´ıvel e´, basicamente, conhecer e dominar uma notac¸a˜o atrave´s da qual textos (ou programas fonte) sa˜o traduzidos em programas executa´veis. Programar, independentemente da linguagem utilizada, significa concatenar as instruc¸o˜es dispon´ıveis dentro de um reperto´rio a fim de transformar dados de entrada em dados de sa´ıda para resolver um problema. Nas linguagens de alto n´ıvel, as instruc¸o˜es complexas sa˜o traduzidas em uma sequeˆncia de operac¸o˜es elementares do reperto´rio ba´sico da ma´quina. Por isto os pro- gramas fonte, quando compilados, geram executa´veis que sa˜o dependentes do sistema operacional e do hardware da ma´quina onde o programa executa. A partir destas ideias, partindo do princ´ıpio que se tem um algoritmo que resolve um problema, o que e´ preciso saber para se programar um computador? • Ter a` disposic¸a˜o um editor de textos, para codificar o algoritmo na forma de programa fonte; 34 CAPI´TULO 4. O MODELO DO COMPUTADOR • Ter a` disposic¸a˜o um compilador para a linguagem escolhida (no nosso caso, o Free Pascal), para transformar automaticamente um programa fonte em um programa executa´vel. No restante deste curso, vamos nos preocupar com a arte de se construir algoritmos, tendo em mente que o estudante devera´ ser capaz de saber transformar este algoritmo em forma de programa fonte de maneira que este possa ser compilado e finalmente executado em um computador. 4.6. EXERCI´CIOS 35 4.6 Exerc´ıcios 1. Para perceber como o ambiente do computador e´ limitado em func¸a˜o do redu- zido nu´mero de instruc¸o˜es dispon´ıveis em baixo n´ıvel, voceˆ pode tentar jogar este jogo (http://armorgames.com/play/2205/light-bot). Nele, existe um boneco que tem que cumprir um percurso com o objetivo de apagar todas as ce´lulas azuis do terreno quadriculado usando apenas poucos comandos e com pouca “memo´ria” dispon´ıvel. Voceˆ pode fazer o uso de duas func¸o˜es que auxi- liam nas tarefas repetitivas. Divirta-se! 2. Modifique a “fotografia da memo´ria” apresentada para que o computador resolva a equac¸a˜o ax2 + bx + c = 0 pelo me´todo de Ba´scara. A diferenc¸a do que foi apresentado e´ o coeficiente a do termo x2 e o sinal de b. 3. Leia os seguintes textos da wikipedia: (a) http://pt.wikipedia.org/wiki/Arquitetura_de_von_Neumann, sobre a arquitetura de von Neumann; (b) http://pt.wikipedia.org/wiki/Von_Neumann, sobre a vida de von Neu- mann, em especial a parte sobre computac¸a˜o. 36 CAPI´TULO 4. O MODELO DO COMPUTADOR Cap´ıtulo 5 Conceitos elementares Agora que sabemos os princ´ıpios de algoritmos e as limitac¸o˜es da ma´quina, e´ preciso introduzir conceitos elementares de algoritmos, sem os quais na˜o e´ poss´ıvel seguir adiante. Apresentaremos problemas simples o bastante para nos concentrarmos nas novi- dades, isto e´, nos aspectos relevantes das estruturas de controle de fluxo e demais conceitos presentes nas linguagens de programac¸a˜o. Nos pro´ximos cap´ıtulos estas es- truturas elementares sera˜o utilizadas na construc¸a˜o de soluc¸o˜es para problemas cada vez mais sofisticados. 5.1 Algoritmos e linguagens de programac¸a˜o Conforme vimos, os algoritmos devem ser escritos em um n´ıvel de detalhamento su- ficiente para que o compilador consiga fazer a traduc¸a˜o do co´digo para linguagem de ma´quina. O compilador precisa receber um texto formatado em uma linguagem simples, na˜o amb´ıgua, precisa. Para isto as linguagens de programac¸a˜o seguem uma grama´tica r´ıgida, se comparada com a da l´ıngua portuguesa. Tambe´m segue um vocabula´rio limitado, constitu´ıdo de alguns poucos elementos. O que vamos apresentar aqui e´ uma linguagem de mais alto n´ıvel do que aquela apresentada no cap´ıtulo 4. Trata-se de uma maneira de escrever que e´ um ponto inter- media´rio entre a capacidade de redac¸a˜o