Turmas - 1º Semestre de 2022(vale 1,5 ponto) A arquitetura básica dos computadores exerceu um efeito crucial sobre o projeto das linguagens de programação. A maioria das linguagens de programação mais populares dos últimos 35 anos foi projetada em função da arquitetura de computador prevalecente, chamada de arquitetura von Neumann, em homenagem a um de seus criadores, John von Neumann.
Por que a arquitetura von Neumann é tão importante no projeto das linguagens de programação? É obrigatório a apresentação de algoritmos, na linguagem de programação de sua preferência, para justificar sua resposta.
Em um computador de von Neumann, os dados e os programas são armazenados na mesma memória. A unidade central de processamento (CPU), que executa realmente as instruções, é um componente separado da memória, de modo que as instruções e os dados precisam ser transferidos da memória para a CPU, e após o seu processamento, os resultados devem novamente ser transferidos da CPU para a memória.
As linguagens de programação imperativas, como Pascal e C, centralizam suas computações nas variáveis, que modelam as células de memória, nas instruções de atribuição, que modelam o trafego de dados entre a CPU e a memória, e numa forma iterativa de repetição. Esse estilo de programação é o meio mais eficiente na utilização da arquitetura de von Neumann, pois minimiza a quantidade de dados que precisa ser transferido entre a CPU e a memória, apesar de não serem consideradas a forma mais natural de se programar.
As linguagens de programação funcionais, como LISP, realizam suas computações aplicando funções a determinados parâmetros, de modo que a programação pode ser realizada sem o tipo de variáveis usadas nas linguagens de programação imperativas, sem instruções de atribuição e sem iteração, sendo considerado um formalismo mais natural para a programação de computadores. Contudo, este estilo de programação não realiza um bom gerenciamento do trafego de dados entre CPU e memória, levando muito mais tempo no processamento dos programas do que as linguagens imperativas.
Por exemplo, considere o programa em C, no estilo imperativo, para o cálculo da somatória de 1 até n.
#include <stdio.h>
#include <time.h>
unsigned long int soma (int n)
{
unsigned long int result = 0;
for (int i = 1; i <= n; i++)
{
result += i;
}
return result;
}
int main ()
{
clock_t Ticks[2];
Ticks[0] = clock();
printf ("soma(100000): %lu\n", soma(100000)) ;
Ticks[1] = clock();
double Tempo = (Ticks[1] - Ticks[0]) * 1000.0 / CLOCKS_PER_SEC;
printf("Tempo gasto: %g ms.\n", Tempo);
return 0;
}A execução do respectivo programa resultará em:
soma(100000): 5000050000
Tempo gasto: 1.262 ms.
Agora, considere o programa em C, no estilo funcional, para o cálculo da somatória de 1 até n.
#include <stdio.h>
#include <time.h>
unsigned long int soma (int n)
{
if (n > 0)
{
return n + soma(n - 1);
}
else
{
return 0;
}
}
int main ()
{
clock_t Ticks[2];
Ticks[0] = clock();
printf ("soma(100000): %lu\n", soma(100000)) ;
Ticks[1] = clock();
double Tempo = (Ticks[1] - Ticks[0]) * 1000.0 / CLOCKS_PER_SEC;
printf("Tempo gasto: %g ms.\n", Tempo);
return 0;
}A execução do respectivo programa resultará em:
soma(100000): 5000050000
Tempo gasto: 7.62 ms.
Comparando os resultados, obtemos que o programa no estilo imperativo foi, aproximadamente, 600% mais eficiente do que o mesmo programa no estilo funcional. Apesar dos inúmeros benefícios das linguagens de programação funcionais, é improvável que as linguagens de programação imperativas tornam-se obsoletas, pelo menos até que um computador não-von Neumann seja projetado, permitindo a execução eficiente de programas escritos em linguagens de programação funcionais.
(vale 1,5 ponto) Pouco depois do trabalho de Chomsky sobre classes de linguagens, o grupo da ACM-GAMM começou a projetar o ALGOL 58. Um documento decisivo descrevendo o ALGOL 58 foi apresentado por John Backus, um proeminente membro do grupo ACM-GAMM, em uma conferência internacional em 1959. Esse documento introduziu uma nova notação formal para especificar a sintaxe das linguagens de programação. A notação foi ligeiramente modificada mais tarde por Peter Naur para a descrição do ALGOL 60. Esse método revisado da descrição da sintaxe tornou-se conhecido como forma de Backus-Naur, ou simplesmente BNF.
Apresente a descrição BNF da instrução switch na linguagem de programação C.
<command> ::= switch ( <variable> ) { <options> }
<options> ::= <options> <case>
| <default>
<case> ::= <caseHead>: <statements>
<caseHead> ::= <caseHead>: case <constant>
| case <constant>
<default> ::= default: <statements>
| ε(vale 1,0 ponto) Quando se consideram linguagens especificadas através de gramáticas livres de contexto, deve-se também considerar de que forma é feita a aceitação sintática de suas sentenças para fins de compilação e/ou interpretação. Quando se trata de efetuar o reconhecimento de sentenças, o que se busca, na verdade, é localizar uma sequência de produções que, quando aplicada à raiz da gramática, forneça como resultado, através da série correspondente de derivações, a sentença fornecida para análise. Sendo possível completar a derivação, diz-se que a sentença pertence à linguagem; caso contrário, que ela não pertence à linguagem.
Por exemplo, a derivação da sentença a + a sobre a gramática livre de contexto G1 pode produzir a sequência de derivação E ⇒ T + E ⇒ F + E ⇒ F + T ⇒ a + T ⇒ a + F ⇒ a + a, no qual foram aplicadas seis produções, sendo elas (1), (4), (2), (6), (4), (6).
G1 = ({E, T, F}, {a, +, *, (, )}, P1, E)
P1 = {E → T + E (1)
E → T (2)
T → F * T (3)
T → F (4)
F → ( E ) (5)
F → A } (6)Conforme exposto, para o reconhecimento da sentença [[a];a;[a]] sobre a gramática livre de contexto G2 é necessário a aplicação de quantas produções?
G2 = ({S, L}, {;, [, ], a}, P2, S)
P2 = {S → a | [L]
L → S;L | S}a. 10 produções.
b. 11 produções.
c. 12 produções.
d. 13 produções.
e. 14 produções.
(vale 1,0 ponto) O escopo de uma variável é a faixa de comandos em que a mesma é visível, ou seja, onde a variável pode ser referenciada por aquele comando. No escopo estático (ou léxico) o escopo de uma variável é determinado através da estrutura textual do programa, enquanto que no escopo dinâmico, o escopo de uma variável é determinado através da linha de execução do programa, sendo dependente, portanto da ordem de execução das rotinas.
public class Test {
private int x, y, z;
public void sub1() { int x, y, c; }
public void sub2() { int x, b, c; }
public void sub3() { int a, b, z; }
public void sub4() { int a, y, z; }
public static void main(String[] args) { int a, b, c; }
}Supondo que o pseudoprograma apresentado utilize o escopo dinâmico, considere as assertivas a seguir:
main chama sub1; sub1 chama sub3 e sub3 chama sub2, as variáveis visíveis durante a execução da última função chamada são y de sub1, x, b e c de sub2, a de sub3 e z de Test.main chama sub3; sub3 chama sub4 e sub4 chama sub1, as variáveis visíveis durante a execução da última função chamada são x, y e c de sub1, b de sub3 e a e z de sub4.main chama sub2; sub2 chama sub1 e sub1 chama sub4, as variáveis visíveis durante a execução da última função chamada são x e c de sub1, b de sub2, a, y e z de sub4.main chama sub1; sub1 chama sub2 e sub2 chama sub3, as variáveis visíveis durante a execução da última função chamada são y de sub1, x de sub2, a, b e z de sub3 e c de main.Quais das assertivas apresentadas estão corretas?
a. apenas as assertivas I e II.
b. apenas as assertivas I e III.
c. apenas as assertivas I e IV.
d. apenas as assertivas II e III.
e. apenas as assertivas II e IV.
(vale 1,0 ponto) Uma característica de projeto de expressões menos comumente discutida é a ordem de avaliação de operandos. As variáveis, nas expressões, são avaliadas buscando seus valores na memória. As constantes, às vezes, são avaliadas da mesma maneira. Em outros casos, uma constante pode fazer parte da instrução de linguagem de máquina e não exigir uma busca na memória. Se um operando for uma expressão colocada entre parênteses, todos os operandos que ela contém devem ser avaliados antes que seu valor possa ser usado como um operando. Se nenhum dos operandos de um operador tiver efeitos colaterais, a sua ordem de avaliação é irrelevante. Um efeito colateral de uma função, chamado efeito colateral funcional, ocorre quando ele modifica um de seus parâmetros ou uma variável global (ela é declarada fora da função, mas acessível na função).
Admitindo que a função C fun seja definida como
int fun(int *i, int *j) {
*i += 5;
*j += 3;
return 4;
}
void main() {
int x = 3;
int y = 2;
int z = x + fun(&x, &y) + y;
}Avalie as seguintes assertivas:
z será 9 caso os operandos sejam avaliados da esquerda para a direita.z será 12 caso os operandos sejam avaliados da esquerda para a direita.z será 17 caso os operandos sejam avaliados da direita para a esquerda.z será 14 caso os operandos sejam avaliados da direita para a esquerda.Quais das assertivas apresentadas estão corretas?
a. apenas as assertivas I e II.
b. apenas as assertivas I e III.
c. apenas as assertivas I e IV.
d. apenas as assertivas II e III.
e. apenas as assertivas II e IV.
(vale 1,0 ponto) As regras de precedência de operadores para avaliação de expressões definem a ordem em que os operadores de diferentes níveis de precedência são avaliados. As regras de precedência de operadores referentes a expressões baseiam-se na hierarquia de prioridades do operador, conforme a visão do projetista da linguagem. Considere as seguintes regras de precedência de operadores, da linguagem de programação C, apresentadas da mais alta precedência para a mais baixa precedência.
++, -- pós-fixo
++, -- pré-fixo
+, - unário
*, /, %
+, - binário
! (not)
&& (and)
|| (or)
Por exemplo, caso a expressão a + b * c + d fosse executada, a ordem de avaliação dos operadores seria representada como ((a + (b * c)1)2 + d)3, uma vez que a associatividade dos operadores na linguagem de programação C é sempre da esquerda para a direita.
Avalie as seguintes assertivas:
Quais das assertivas apresentadas estão corretas?
a. apenas as assertivas I e II.
b. apenas as assertivas I e III.
c. apenas as assertivas I e IV.
d. apenas as assertivas II e III.
e. apenas as assertivas II e IV.
(vale 1,0 ponto) Um tipo subfaixa (subrange) é uma subsequência de um ordinal. Por exemplo, 12..14 é uma subfaixa do tipo inteiro. Os tipos subfaixa foram introduzidos pelo Pascal e também estão incluídos no Modula-2 e na Ada. Em Pascal, as declarações do tipo subfaixa típicas são
type
maiuscula = 'A'..'Z';
indice = 1..100;Desenvolva uma classe que simule o comportamento do tipo subfaixa, na linguagem de programação orientada a objetos de sua preferência (junto com a resposta, informar a linguagem de programação utilizada, e o processo para compilar e executar o programa submetido). A seguir, apresentamos alguns exemplos de uso da classe, utilizando a notação Java.
Criação do tipo
Subfaixa subfaixa = new Subfaixa(10, 20);Atribuição/recuperação de um valor
subfaixa.setValue(15);
System.out.println(subfaixa.getValue()); // 15Recuperação do elemento da posição
subfaixa.getIndex(5); // 15 (o índice começa de 0)Iteração sobre os elementos da subfaixa
for (int element: subfaixa.getValues()) {
...
}/**
* Classe responsavel pela simulacao do tipo subfaixa (subrange)
*/
public class Subfaixa
{
/**
* Inicio da faixa
*/
private final int begin;
/**
* Fim da faixa
*/
private final int end;
/**
* Valor da variavel
*/
private Integer value;
/**
* Inicializar o tipo
*
* @param begin inicio da faixa
* @param end fim da faixa
* @throws IllegalArgumentException caso os valores de begin e end sejam invalidos
*/
public Subfaixa(final int begin, final int end)
{
if (begin < end)
{
this.begin = begin;
this.end = end;
}
else
{
throw new IllegalArgumentException();
}
}
/**
* Setar o valor da variavel
*
* @param value valor da variavel
* @throws IndexOutOfBoundsException caso o valor esteja fora do intervalo especificado
*/
public void setValue(final int value)
{
if (begin <= value && value <= end)
{
this.value = value;
}
else
{
throw new IndexOutOfBoundsException();
}
}
/**
* Retornar o valor da variavel
*
* @return valor da variavel
* @throws NullPointerException caso o valor nao tenha sido inicializado
*/
public int getValue()
{
if (value != null)
{
return value;
}
else
{
throw new NullPointerException();
}
}
/**
* Retornar o elemento da posicao especificada
*
* @param index posicao no intervalo
* @return elemento da posicao especificada
* @throws IndexOutOfBoundsException caso a posicao especificada esteja fora do intervalo
*/
public int getIndex(final int index)
{
final int range = end - begin;
if (index <= range)
{
return begin + index;
}
else
{
throw new IndexOutOfBoundsException();
}
}
/**
* Retornar o vetor com os elementos do intervalo
*
* @return vetor com os elementos do intervalo
*/
public int[] getValues()
{
final int range = end - begin + 1;
final int[] values = new int[range];
for (int i = 0; i < range; i++)
{
values[i] = begin + i;
}
return values;
}
}Ybadoo - Soluções em Software Livre • Copyright 2009/2024 • 