Was macht es einfacher, einige Dinge zu analysieren als andere?

8

Ich habe gerade die Wikipedia-Seite für WebAssembly gelesen und dort steht: „ WebAssembly ist… so konzipiert, dass es schneller zu analysieren ist als JavaScript “, was mich zum Nachdenken brachte, was eine bestimmte Sprache oder ein bestimmtes Datenformat schneller zu analysieren macht als andere und welche Analysealgorithmen es gibt benutzt?

Moses
quelle

Antworten:

18

Dieses Thema ist sehr komplex. Sie können nach Parser-Algorithmen googeln und erhalten reichlich detailliertes Material.

Im Algemeinen:

  • Je weniger Mehrdeutigkeiten gelöst werden müssen, desto schneller ist der Analyseprozess.
  • Je mehr Token berücksichtigt werden müssen, bevor eine Entscheidung getroffen werden kann, desto komplexer wird sie.

Beispiel:
Wenn ein JS-Parser das functionSchlüsselwort in diesem Code sieht : function xyz(a, b) {}ist das Funktionsschlüsselwort nicht eindeutig. Es muss zuerst das nächste Token verarbeiten xyzund feststellen, dass es sich um eine Kennung handelt, bevor es entscheiden kann, dass es sich um eine Funktionsdeklaration handelt.

Wenn das nächste Token jedoch ein wäre (, handelt es sich um ein Funktionsliteral : function(a, b) {}. Das erfordert, dass sich der Parser sehr unterschiedlich verhält, also mehr Code im Parser, was die Ausführung verlangsamt.

Wenn es für diese beiden Zwecke unterschiedliche Schlüsselwörter gäbe, gäbe es keine Mehrdeutigkeit:

function_decl xyz(a, b, c) {} und function_lit(a, b, c) {}

Allerdings würde niemand in einer solchen Sprache schreiben wollen. WebAssembly sollte jedoch nicht von Hand geschrieben werden. Dadurch kann die Sprache eher auf Maschinen als auf Menschen zugeschnitten werden.

Marstato
quelle
1
Würde dies bedeuten, dass Lisp sehr leicht analysiert werden kann?
Moses
9
@Moses: Ja, das Schreiben eines naiven Lisp-Parsers ist trivial, da die Syntax homoikonisch mit der Struktur eines abstrakten Syntaxbaums ist und fast keine Mehrdeutigkeiten bestehen.
Phoshi
4
Ein weiteres gutes Beispiel ist Bytecode, der oft mit einer Schleifenwechselanweisung analysiert werden kann, und das war's.
Whatsisname
@whatsisname In der Tat gilt das gleiche für die reguläre Versammlung und Web-Versammlung
Marstato