Urteils vom 3. November 1999 (2A. 388/1999), hat sich ergeben:
A.- Am 19. Mai 1998 weigerte sich die Polizeidirektion (heute: Direktion für Soziales und Sicherheit) des Kantons Zürich, die Aufenthaltsbewilligung des aus Algerien stammenden, mit einer Schweizerin verheirateten Abdelouahab Boultif (geb. 1967) zu erneuern, nachdem er wegen Raubs und Sachbeschädigung zu zwei Jahren Zuchthaus verurteilt worden war.
Diesen Entscheid schützten auf Beschwerde hin sowohl der Regierungsrat und das Verwaltungsgericht des Kantons Zürich als auch das Bundesgericht (Urteil vom 3. November 1999; 2A.388/1999). Mit Entscheid vom 2. August 2001 stellte der Europäische Gerichtshof für Menschenrechte fest, dass die Schweiz damit Art. 8 EMRK verletzt habe.
B.- Am 23. August 2001 gelangte Abdelouahab Boultif mit folgenden Anträgen an das Bundesgericht:
"1. Das Urteil des Bundesgerichts vom 03.11.1999 sei
aufgrund des Urteils des Europäischen Gerichtshofs
vom 02.08.01 revisionsweise ordnungsgemäss
aufzuheben.
2. Dem Ehepaar Boultif sei nunmehr das Zusammenleben
ordnungsgemäss unverzüglich zu ermöglichen,
und die Aufenthaltsbewilligung 'B' von Herrn
Boultif sei nunmehr ordnungsgemäss und unverzüglich
zu verlängern, bzw. zu erteilen.
3. Im Rahmen einer vorsorglichen Massnahme sei die
Fremdenpolizei des Kantons Zürich anzuweisen,
den Aufenthalt Herrn Boultifs im Kanton Zürich
per sofort zu tolerieren bzw. die entsprechende
Wiedereinreise in die Schweiz sei sofort zu bewilligen.
4. Dem Ehepaar Boultif sei im Rahmen einer Partei- und Prozessentschädigung der Betrag in der Höhe
von Fr. 5'346. 70 für aufgelaufene Prozesskosten,
Rechtsberatung und Rechtsvertretung zuzüglich
5 % Verzugszins seit Fälligkeit im Sinne des
Urteilsdispositivs des Urteils des Europäischen
Gerichtshofs vom 02.08.01, Ziff. 2, zuzusprechen
sowie eine angemessene Entschädigung für das
vorliegende erneute Verfahren.
5. Unter Kosten- Entschädigungsfolge zu Lasten
Bund.. "
Das Bundesamt für Ausländerfragen beantragt, das Revisionsbegehren gutzuheissen. Die Staatskanzlei des Kantons Zürich geht davon aus, dieses sei gegenstandslos, da das Migrationsamt auf Grund des Urteils des Gerichtshofs vom 2. August 2001 Abdelouahab Boultif nach der Einreise eine förmliche Aufenthaltsbewilligung in Anwendung von Art. 7 Abs. 1 des Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; SR 142. 20) erteilen werde. Das Bundesamt für Justiz beantragt auf das Revisionsgesuch insofern nicht einzutreten, als Abdelouahab Boultif darum ersucht, ihm die vom Gerichtshof auf Fr. 5'346. 70 festgelegte Entschädigung zuzusprechen.
C.- Am 11. September 2001 wies die I. öffentlichrechtliche Abteilung ein gegen den Präsidenten der II. öffentlichrechtlichen Abteilung und gegen den Gerichtsschreiber eingereichtes Ausstandsbegehren ab. Mit Verfügung vom 28. September 2001 erklärte der Abteilungspräsident das Gesuch um Anordnung vorsorglicher Massnahmen im Sinne der Erwägungen als gegenstandslos, nachdem das Bundesamt für Ausländerfragen am 29. August 2001 die gegen Abdelouahab Boultif bestehende Einreisesperre aufgehoben und die Staatskanzlei des Kantons Zürich erklärt hatte, dass sie nach Eingang des förmlichen Gesuchs um Bewilligung der Einreise von Abdelouahab Boultif die für dessen derzeitigen Aufenthaltsort zuständige schweizerische Vertretung ermächtigen werde, ihm ein Einreisevisum zu erteilen.

Das Bundesgericht zieht in Erwägung:
1.- Nach Art. 139a OG ist die Revision eines Entscheids des Bundesgerichts zulässig, wenn der Europäische Gerichtshof für Menschenrechte eine Individualbeschwerde wegen der Verletzung der Konvention vom 4. November 1950 zum Schutze der Menschenrechte und Grundfreiheiten (EMRK; SR 0.101) gutgeheissen hat und eine Wiedergutmachung nur so möglich ist (Abs. 1). Das Gesuch muss innert 90 Tagen ab Zustellung des Entscheids durch das Bundesamt für Justiz beim Bundesgericht eingereicht werden (Art. 141 Abs. 1 lit. c OG). Dazu befugt ist, wer im Verfahren, das zum konventionswidrigen Entscheid geführt hat, Parteistellung hatte und deshalb an der Wiederaufnahme ein schutzwürdiges Interesse geltend machen kann (Elisabeth Escher, Revision und Erläuterung, in: Geiser/ Münch, Prozessieren vor Bundesgericht, 2. Aufl. , Basel/ Frankfurt a.M. 1998, S. 273, Rz. 8.6).
2.- Der Gesuchsteller war am ursprünglichen Verfahren beteiligt, weshalb er legitimiert ist, die Revision des entsprechenden Entscheids zu beantragen. Zwar hat er sein Gesuch am 23. August 2001 verfrüht eingereicht, da der Entscheid des Gerichtshofs für Menschenrechte zu diesem Zeitpunkt noch nicht rechtskräftig war (vgl. Art. 44 Ziff. 2 EMRK) und er ihm vom Bundesamt für Justiz deshalb auch noch nicht fristauslösend notifiziert wurde (Art. 141 Abs. 1 lit. c OG), doch gereicht ihm dies nicht zum Nachteil (vgl.
Martin Philipp Wyss, EMRK-Verletzung und bundesrechtliche Revision nach Art. 139a OG, in: recht 1999 S. 100; Michel Hottelier, La procédure suisse de révision consécutive à un arrêt de condamnation par la Cour Européenne des Droits de l'Homme, in: Revue trimestrielle des droits de l'homme, 47/2001 S. 750). Die Schweiz hat keine Verweisung an die Grosse Kammer beantragt, womit das Urteil des Gerichtshofs nunmehr am 2. November 2001 in Rechtskraft erwachsen ist (Art. 44 Ziff. 2 lit. b EMRK).
3.- a) aa) Nach Art. 46 EMRK übernehmen die Vertragsstaaten die Pflicht, in den sie betreffenden Fällen das Urteil des Gerichtshofs zu befolgen. Wird eine Individualbeschwerde gutgeheissen, sind sie gehalten, soweit möglich für eine vollkommene Wiedergutmachung zu sorgen. Die Art der Wiederherstellung des konventionskonformen Zustands bleibt jedoch im Wesentlichen ihre Sache. Aus der Konvention selber ergibt sich keine Verpflichtung, ein Verfahren wieder aufzunehmen.
Gestattet das innerstaatliche Recht nur eine unvollkommene Wiedergutmachung, spricht der Gerichtshof der verletzten Partei im Rahmen von Art. 41 EMRK völkerrechtlichen Gepflogenheiten entsprechend eine gerechte Entschädigung zu (vgl. das Urteil des Bundesgerichts vom 2. März 2001 i.S.
Amann, E. 2a, mit zahlreichen Hinweisen auf Rechtsprechung und Doktrin; veröffentlicht in: EuGRZ 2001 S. 320).
bb) Das Bundesgericht hat hieraus abgeleitet, dass die Revision nach Art. 139a OG ausgeschlossen ist, falls nur (noch) materielle Interessen auf dem Spiel stehen und die Konventionsverletzung bloss noch mit einer Entschädigung gutgemacht werden kann (Urteil des Bundesgerichts vom 2. März 2001 i.S. Amann, E. 2b/bb, veröffentlicht in: EuGRZ 2001 S. 321; <ref-ruling> E. 3 S. 188; <ref-ruling> E. 3a S. 287; <ref-ruling> E. 3 S. 335 ff.). Die Frage der "gerechten Entschädigung" für die festgestellte Beeinträchtigung in den konventionsmässigen Rechten ist in diesem Fall direkt durch den Gerichtshof zu erledigen (vgl. Frank Schürmann, Erste Erfahrungen mit Art. 139a OG, in: Festschrift 125 Jahre Kassationsgericht des Kantons Zürich, Zürich 2000, S. 99 f.; Jörg Polakiewicz, Die Verpflichtungen der Staaten aus den Urteilen des Europäischen Gerichtshofs für Menschenrechte, Berlin et al. 1993, S. 144). Die von ihm dabei zugesprochene Abgeltung ist völkerrechtlicher Natur und kann deshalb nicht innerstaatlich im Revisionsverfahren durchgesetzt werden (vgl. Mark E. Villiger, Handbuch der Europäischen Menschenrechtskonvention [EMRK], 2. Aufl. , Zürich 1999, Rz. 237; Urteil vom 2. März 2001 i.S. Amann, E. 2b/bb, veröffentlicht in: EuGRZ 2001 S. 321).
cc) Anders verhält es sich, wenn die Entschädigung und die Feststellung des Gerichtshofs die Verletzung nicht hinreichend auszugleichen vermögen, etwa bei einem (allenfalls auch nur impliziten) Fortbestehen eines Schuldvorwurfs (<ref-ruling> E. 2c S. 485), oder wenn der konventionswidrige Zustand trotz der Feststellung einer Konventionsverletzung durch den Gerichtshof andauert (<ref-ruling> E. 4b S. 190): In diesen Fällen ist die Revision möglich, falls sie geeignet erscheint, über die finanzielle Abgeltung hinaus fortbestehende, konkrete nachteilige Auswirkungen zu beseitigen (Schürmann, a.a.O., S. 100). Allein die Tatsache, dass eine Individualbeschwerde in Strassburg gutgeheissen wurde, bewirkt nicht, dass das zugrundeliegende bundesgerichtliche Urteil revidiert werden müsste (Wyss, a.a.O., S. 100; BBl 1991 II 465, S. 529). Dies rechtfertigt sich mit Blick auf die Natur der Revision als ausserordentliches Rechtsmittel nur, soweit eine Wiedergutmachung allein auf diesem Weg und nicht mittels anderer wirksamer Vorkehren möglich erscheint (vgl. Schürmann, a.a.O., S. 102; Wyss, a.a.O., S. 99).
b) aa) Der Gerichtshof für Menschenrechte hat am 2. August 2001 entschieden, dass die vom Bundesgericht in seinem Urteil vom 3. November 1999 geschützte Verweigerung der Verlängerung der Aufenthaltsbewilligung des Gesuchstellers einen unverhältnismässigen Eingriff in dessen Recht auf Familienleben (Art. 8 EMRK) gebildet habe. Gestützt hierauf ist das Bundesamt für Ausländerfragen auf die gegen den Gesuchsteller verhängte Einreisesperre zurückgekommen und hat die Staatskanzlei des Kantons Zürich zugesichert, ihm nach Bekanntgabe seines Aufenthaltsorts das nötige Einreisevisum und hernach eine förmliche Aufenthaltsbewilligung zum Verbleib bei seiner Frau nach Massgabe von Art. 7 Abs. 1 ANAG zu erteilen. Unter diesen Umständen ist vorliegend nicht ersichtlich, welche konkreten nachteiligen Auswirkungen fortbestehen würden, die noch durch eine Revision des bundesgerichtlichen Entscheids beseitigt werden müssten. Die Beeinträchtigung, die darin liegt, dass der Gesuchsteller zu Unrecht über keine Aufenthaltsbewilligung verfügt hat und daher für eine gewisse Zeit von seiner Ehefrau getrennt leben musste, kann auch durch deren rückwirkend erfolgende Erteilung nicht mehr beseitigt werden. Eine Wiedergutmachung wäre insofern - in unvollkommener Weise - nur durch die Zusprechung von Schadenersatz oder Genugtuung möglich, was der Gesuchsteller im Rahmen von Art. 41 EMRK beim Gerichtshof hätte geltend machen müssen (vgl. oben E. 3a/bb; Schürmann, a.a.O., S. 100).
bb) Das bundesgerichtliche Urteil vom 3. November 1999 entfaltet keine Rechtskraft in dem Sinne, dass es der kantonalen Fremdenpolizei verwehren würde, dem Gesuchsteller gestützt auf den Entscheid des Gerichtshofs vom 2. August 2001 nunmehr sofort wieder eine Aufenthaltsbewilligung zu erteilen. Nach Art. 7 ANAG und Art. 8 EMRK hat der ausländische Ehegatte eines Schweizer Bürgers grundsätzlich Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung.
Aufgrund von Art. 1 EMRK sind sämtliche staatlichen Organe auf allen Ebenen gehalten, zur Sicherung und Gewährleistung der Konventionsgarantien beizutragen (Wyss, a.a.O., S. 94). Der Migrationsdienst des Kantons Zürich muss deshalb auch ohne Revision des bundesgerichtlichen Entscheids prüfen, ob dem Gesuchsteller wieder eine Aufenthaltsbewilligung zu erteilen ist. Mit dem Urteil vom 2. August 2001 hat sich die Ausgangslage gegenüber dem Entscheid der Polizeidirektion vom 19. Mai 1998 grundlegend geändert, weshalb einem erneuten Gesuch nicht dessen allfällige Rechtskraft entgegengehalten werden kann (vgl. <ref-ruling> E. 2b S. 46 f.).
Verweigerte der Migrationsdienst - soweit der Gesuchsteller nach wie vor verheiratet ist und keine neuen Umstände eingetreten sind, welche einen Eingriff in sein Recht auf Familienleben rechtfertigen - die Bewilligung, läge hierin wiederum eine Verletzung von Art. 8 EMRK, die der Gesuchsteller auf dem Rechtsweg geltend machen könnte.
cc) Die neu zu erteilende und vom Migrationsdienst auf Gesuch hin - welches für die technische Abwicklung so oder anders erforderlich ist - bereits in Aussicht gestellte Bewilligung wird ihre Wirkungen pro futuro entfalten, und insofern die vom Gerichtshof festgestellte ungerechtfertigte Beeinträchtigung des Familienlebens des Gesuchstellers wirksam beseitigen, weshalb keine Notwendigkeit für eine Revision des bundesgerichtlichen Urteils besteht, wie sie Art. 139a OG voraussetzt ("und eine Wiedergutmachung nur durch eine Revision möglich ist"). Der Gesuchsteller legt nicht dar, welche anderen konkreten Nachteile ihm drohen, die nicht mit der neuen Bewilligung beseitigt werden könnten und mittels einer Wiederaufnahme des ursprünglichen Verfahrens auszugleichen wären. Das Revisionsgesuch ist insofern somit unbegründet und deshalb abzuweisen.
c) Nicht darauf einzutreten ist, soweit der Gesuchsteller beantragt, ihm und seiner Frau die vom Gerichtshof für Menschenrechte zuerkannte Entschädigung von Fr. 5'346. 70 zuzusprechen: Entschädigungen, die der Gerichtshof für Menschenrechte in Anwendung von Art. 41 EMRK gewährt, sind völkerrechtlicher Natur und - wie dargelegt - innerstaatlich nicht im Revisionsverfahren durchsetzbar. Nach Ziffer 2a des Dispositivs des Urteils des Gerichtshofs für Menschenrechte ist die Schweiz gehalten, ihm innert drei Monaten ab Rechtskraft gemäss Art. 44 Ziff. 2 EMRK eine Entschädigung von Fr. 5'346. 70 auszurichten, die sie hernach zu 5% verzinsen muss. Der Entscheid des Gerichtshofs ist am 2. November 2001 rechtskräftig geworden, womit die Entschädigung nunmehr bis zum 2. Februar 2002 zu leisten ist. Das Bundesamt für Justiz hat zugesichert, die Zahlung - praxisgemäss - auf diesen Fälligkeitstermin hin auszurichten. Für weitere vermögensrechtliche Ansprüche verbleibt kein Raum (vgl. <ref-ruling> E. 3 S. 188).
4.- Bei diesem Verfahrensausgang würde der unterliegende Gesuchsteller kostenpflichtig (Art. 156 Abs. 1 OG).
Da das Bundesgericht vorliegend aber zum ersten Mal die Anwendbarkeit von Art. 139a OG bei der konventionswidrigen Verweigerung einer ausländerrechtlichen Bewilligung zu prüfen hatte, rechtfertigt es sich, keine Kosten zu erheben und keine Parteientschädigungen zuzusprechen (Art. 154 OG).

Demnach erkennt das Bundesgericht:
1.- Das Revisionsgesuch wird abgewiesen, soweit darauf einzutreten ist.
2.- Es werden keine Kosten erhoben und keine Entschädigungen zugesprochen.
3.- Dieses Urteil wird dem Gesuchsteller, dem Regierungsrat (Staatskanzlei) und dem Verwaltungsgericht (2. Kammer) des Kantons Zürich sowie dem Bundesamt für Ausländerfragen und dem Bundesamt für Justiz (Abteilung für internationale Angelegenheiten) schriftlich mitgeteilt.
_
Lausanne, 6. November 2001
Im Namen der II. öffentlichrechtlichen Abteilung
des SCHWEIZERISCHEN BUNDESGERICHTS
Der Präsident:
Der Gerichtsschreiber: