Wie definieren Programmiersprachen Funktionen?

28

Wie definieren und speichern Programmiersprachen Funktionen / Methoden? Ich erstelle eine interpretierte Programmiersprache in Ruby und versuche herauszufinden, wie die Funktionsdeklaration implementiert wird.

Meine erste Idee ist, den Inhalt der Deklaration in einer Karte zu speichern. Zum Beispiel, wenn ich so etwas gemacht habe

def a() {
    callSomething();
    x += 5;
}

Dann würde ich einen Eintrag in meine Karte einfügen:

{
    'a' => 'callSomething(); x += 5;'
}

Das Problem dabei ist, dass es rekursiv wird, weil ich meine parseMethode für die Zeichenfolge aufrufen muss, die dann parseerneut aufgerufen wird, wenn sie auftritt doSomething, und schließlich nicht mehr genügend Stapelspeicherplatz zur Verfügung steht.

Wie gehen interpretierte Sprachen damit um?

Türknauf
quelle
Oh, und dies ist mein erster Beitrag auf Programmers.SE. Bitte informieren Sie mich, wenn ich etwas falsch mache oder dies nicht zum Thema gehört. :)
Türknauf
In der Vergangenheit habe ich sie alle inline in meinen Token gespeichert und Funktionsaufrufe sind nur Sprünge zu einem bestimmten Offset (ähnlich wie Beschriftungen in Assembly). Token Sie das Skript? Oder jedes Mal Zeichenfolgen analysieren?
Simon Whitehead
@SimonWhitehead Ich habe die Zeichenfolge in Token aufgeteilt und dann jedes Token separat analysiert.
Türknauf
3
Wenn Sie mit dem Design und der Implementierung von Programmiersprachen noch nicht vertraut sind, sollten Sie einen Teil der Literatur zu diesem Thema lesen. Das beliebteste ist das "Drachenbuch": en.wikipedia.org/wiki/… , aber es gibt auch andere, prägnantere Texte, die ebenfalls sehr gut sind. Zum Beispiel kann die Implementierung von Programmiersprachen von Aarne Ranta hier kostenlos bezogen werden: bit.ly/15CF6gC .
evilcandybag
1
@ddyer Danke! Ich habe nach einem Lisp-Dolmetscher in verschiedenen Sprachen gegoogelt und das hat wirklich geholfen. :)
Türknauf

Antworten:

31

Wäre es richtig anzunehmen, dass Ihre "Analyse" -Funktion den Code nicht nur analysiert, sondern gleichzeitig ausführt? Wenn Sie dies auf diese Weise tun möchten, speichern Sie den Ort der Funktion , anstatt den Inhalt einer Funktion in Ihrer Map zu speichern .

Aber es gibt einen besseren Weg. Der Aufwand im Vorfeld ist etwas höher, aber mit zunehmender Komplexität lassen sich viel bessere Ergebnisse erzielen: Verwenden Sie einen abstrakten Syntaxbaum.

Die Grundidee ist, dass Sie den Code immer nur einmal analysieren. Dann haben Sie eine Reihe von Datentypen, die Operationen und Werte darstellen, und Sie erstellen daraus einen Baum wie folgt:

def a() {
    callSomething();
    x += 5;
}

wird:

Function Definition: [
   Name: a
   ParamList: []
   Code:[
      Call Operation: [
         Routine: callSomething
         ParamList: []
      ]
      Increment Operation: [
         Operand: x
         Value: 5
      ]
   ]
]

(Dies ist nur eine Textdarstellung der Struktur eines hypothetischen AST. Der tatsächliche Baum wäre wahrscheinlich nicht in Textform.) Wie auch immer, Sie analysieren Ihren Code in einen AST und führen dann entweder Ihren Interpreter direkt über den AST aus. Oder verwenden Sie einen zweiten Durchgang ("Codegenerierung"), um den AST in eine Ausgabeform zu verwandeln.

Im Falle Ihrer Sprache würden Sie wahrscheinlich eine Zuordnung haben, die Funktionsnamen auf Funktions-ASTs abbildet, anstatt Funktionsnamen auf Funktionszeichenfolgen.

Mason Wheeler
quelle
Okay, aber das Problem ist immer noch da: Es wird eine Rekursion verwendet. Ich werde irgendwann keinen Stapelplatz mehr haben, wenn ich das tue.
Türknauf
3
@Doorknob: Was nutzt Rekursion konkret? Jede blockstrukturierte Programmiersprache (die jede moderne Sprache auf einer höheren Ebene als ASM ist) ist von Natur aus baumbasiert und daher rekursiv. Welchen speziellen Aspekt befürchten Sie, dass Stapelüberläufe auftreten?
Mason Wheeler
1
@Doorknob: Ja, das ist eine inhärente Eigenschaft jeder Sprache, auch wenn sie auf Maschinencode kompiliert wurde. (Der Aufrufstapel ist eine Manifestation dieses Verhaltens.) Ich trage tatsächlich zu einem Skriptsystem bei, das auf die von mir beschriebene Weise funktioniert. Besuchen Sie mich im Chat unter chat.stackexchange.com/rooms/10470/… und besprechen Sie mit mir einige Techniken zur effizienten Interpretation und Minimierung der Auswirkungen auf die Stapelgröße . :)
Mason Wheeler
2
@Doorknob: Hier gibt es kein Rekursionsproblem, da der Funktionsaufruf im AST die Funktion nach Namen referenziert und keinen Verweis auf die tatsächliche Funktion benötigt . Wenn Sie auf Maschinencode kompilieren, benötigen Sie schließlich die Funktionsadresse, weshalb die meisten Compiler mehrere Durchgänge ausführen. Wenn Sie einen One-Pass-Compiler haben möchten, benötigen Sie "Forward-Deklarationen" aller Funktionen, damit der Compiler zuvor Adressen zuweisen kann. Bytecode-Compiler kümmern sich nicht einmal darum, der Jitter kümmert sich um die Namenssuche.
Aaronaught
5
@ Doorknob: Es ist in der Tat rekursiv. Und ja, wenn Ihr Stapel nur 16 Einträge enthält, können Sie ihn nicht analysieren (((((((((((((((( x ))))))))))))))))). In Wirklichkeit können Stapel viel größer sein, und die grammatikalische Komplexität von echtem Code ist sehr begrenzt. Sicher, wenn dieser Code für Menschen lesbar sein muss.
MSalters
4

Sie sollten beim Sehen nicht parsen callSomething()(ich nehme an, Sie meinten es callSomethingeher als doSomething). Der Unterschied zwischen aund callSomethingbesteht darin, dass eines eine Methodendefinition ist, während das andere ein Methodenaufruf ist.

Wenn Sie eine neue Definition sehen, möchten Sie überprüfen, ob Sie diese Definition hinzufügen können.

  • Überprüfen Sie, ob die Funktion mit derselben Signatur noch nicht vorhanden ist
  • Stellen Sie sicher, dass die Methodendeklaration im richtigen Umfang ausgeführt wird (dh können Methoden in anderen Methodendeklarationen deklariert werden?)

Angenommen, diese Prüfungen bestehen, können Sie sie Ihrer Karte hinzufügen und den Inhalt dieser Methode überprüfen.

Wenn Sie einen Methodenaufruf wie finden callSomething(), sollten Sie die folgenden Überprüfungen durchführen:

  • Existiert callSomethingin Ihrer Karte?
  • Wird es richtig aufgerufen (Anzahl der Argumente stimmt mit der gefundenen Signatur überein)?
  • Sind Argumente gültig (wenn Variablennamen verwendet werden, sind sie deklariert? Kann in diesem Bereich auf sie zugegriffen werden?)?
  • Kann callSomething von Ihrem Standort aus angerufen werden (ist es privat, öffentlich, geschützt?)?

Wenn Sie der callSomething()Meinung sind , dass dies in Ordnung ist, hängt das, was Sie zu diesem Zeitpunkt tun möchten, wirklich davon ab, wie Sie es angehen möchten. Streng genommen können Sie, sobald Sie wissen, dass ein solcher Aufruf zu diesem Zeitpunkt in Ordnung ist, nur den Namen der Methode und die Argumente speichern, ohne auf weitere Details einzugehen. Wenn Sie Ihr Programm ausführen, rufen Sie die Methode mit den Argumenten auf, die Sie zur Laufzeit haben sollten.

Wenn Sie weiter gehen möchten, können Sie nicht nur die Zeichenfolge, sondern auch einen Link zur eigentlichen Methode speichern. Dies wäre effizienter, aber wenn Sie den Speicher verwalten müssen, kann dies verwirrend werden. Ich würde empfehlen, zuerst einfach an der Saite festzuhalten. Später können Sie versuchen, zu optimieren.

Beachten Sie, dass dies alles vorausgesetzt wird, dass Sie Ihr Programm lexxiert haben, was bedeutet, dass Sie alle Token in Ihrem Programm erkannt haben und wissen, was sie sind . Das heißt nicht, dass Sie wissen, ob sie zusammen noch einen Sinn ergeben. Dies ist die Analysephase. Wenn Sie die Token noch nicht kennen, sollten Sie sich zunächst darauf konzentrieren, diese Informationen zu erhalten.

Ich hoffe das hilft! Willkommen bei Programmers SE!

Neil
quelle
2

Als ich Ihren Beitrag las, bemerkte ich zwei Fragen in Ihrer Frage. Das wichtigste ist, wie man parst. Es gibt viele Arten von Parsern (z. B. Parser für rekursive Abstammung , LR-Parser , Packrat-Parser ) und Parser-Generatoren (z. B. GNU Bison , ANTLR ), mit denen Sie ein Textprogramm "rekursiv" mit einer (expliziten oder impliziten) Grammatik durchlaufen können.

Die zweite Frage betrifft das Speicherformat für Funktionen. Wenn Sie keine syntaxgesteuerte Übersetzung durchführen , erstellen Sie eine Zwischendarstellung Ihres Programms, bei der es sich um einen abstrakten Syntaxbaum oder eine benutzerdefinierte Zwischensprache handeln kann, um die weitere Verarbeitung zu ermöglichen (Kompilieren, Transformieren, Ausführen, Beschreiben) eine Datei, etc).

Thiago Silva
quelle
1

Aus allgemeiner Sicht ist die Definition einer Funktion kaum mehr als eine Beschriftung oder ein Lesezeichen im Code. Die meisten anderen Schleifen-, Bereichs- und Bedingungsoperatoren sind ähnlich. Sie stehen für einen grundlegenden "Sprung" - oder "Sprung" -Befehl in den unteren Abstraktionsebenen. Ein Funktionsaufruf besteht im Wesentlichen aus den folgenden einfachen Computerbefehlen:

  • Verketten Sie die Daten aller Parameter sowie einen Zeiger auf den nächsten Befehl der aktuellen Funktion in einer Struktur, die als "Aufrufstapelrahmen" bezeichnet wird.
  • Schieben Sie diesen Rahmen auf den Call-Stack.
  • Zum Speicheroffset der ersten Zeile des Funktionscodes springen.

Eine "return" -Anweisung oder ähnliches bewirkt dann Folgendes:

  • Laden Sie den Wert, der zurückgegeben werden soll, in ein Register.
  • Laden Sie den Zeiger auf den Anrufer in ein Register.
  • Pop den aktuellen Stack-Frame.
  • Zum Zeiger des Anrufers springen.

Funktionen sind daher einfach Abstraktionen in einer übergeordneten Sprachspezifikation, die es dem Menschen ermöglichen, Code auf eine wartbarere und intuitivere Weise zu organisieren. Beim Kompilieren in eine Assembly- oder Zwischensprache (JIL, MSIL, ILX) und definitiv beim Rendern als Maschinencode gehen fast alle derartigen Abstraktionen verloren.

KeithS
quelle