Über reguläre Ausdrücke hinaus: Eine Einführung in das Parsen kontextfreier Grammatiken

Ein wichtiges und nützliches Werkzeug, das bereits Teil des Arsenals der meisten Programmierer ist, ist der vertrauenswürdige reguläre Ausdruck . Aber darüber hinaus liegen kontextfreie Grammatiken. Dies ist ein einfaches Konzept mit einem ausgefallenen Namen.

Ein regulärer Ausdruck ist eine Methode zum Validieren und Finden von Mustern im Text. Die Arten von Mustern (auch Grammatiken genannt), die mit einem regulären Ausdruck beschrieben und erkannt werden können, werden als reguläre Sprachen bezeichnet . Reguläre Sprachen sind die einfachsten formalen Sprachen in der Chomsky-Hierarchie .

Reguläre Ausdrücke eignen sich hervorragend zum Auffinden oder Überprüfen vieler Arten einfacher Muster, z. B. Telefonnummern, E-Mail-Adressen und URLs. Sie sind jedoch unzureichend, wenn sie auf Muster angewendet werden, die eine rekursive Struktur haben können, wie z.

  • HTML / XML-Tags zum Öffnen / Schließen
  • Klammern {/} in Programmiersprachen öffnen / schließen
  • Klammern in arithmetischen Ausdrücken öffnen / schließen

Um diese Arten von Mustern zu analysieren, brauchen wir etwas Stärkeres. Wir können zur nächsten Stufe der formalen Grammatik übergehen, die als kontextfreie Grammatik (CFG) bezeichnet wird.

Analyse mathematischer Ausdrücke

Das Parsen der Menge aller mathematischen Ausdrücke ist jenseits der Macht eines echten regulären Ausdrucks. Der Grund ist, dass diese beliebig tief verschachtelte Klammerpaare enthalten können.

Betrachten Sie zum Beispiel den Ausdruck: (2 + (3 * (7–4)))

Beachten Sie, dass die Struktur des arithmetischen Ausdrucks effektiv ein Baum ist:

 + / \ 2 * / \ 3 - / \ 7 4

Die Baumstruktur, die als Ergebnis der Ausführung eines CFG-Parsers generiert wird, wird als Analysebaum bezeichnet .

Beschreiben kontextfreier Grammatiken

Es gibt zwei beliebte Methoden zum Ausdrücken von CFG-Grammatiken:

  1. Erweiterte Bachus-Naur-Form (EBNF) - beschreibt eine CFG in Bezug auf Produktionsregeln . Dies sind Regeln, die, wenn sie angewendet werden, alle möglichen juristischen Ausdrücke in der Sprache erzeugen können.
  2. Parsing Expression Grammar (PEG) - beschreibt eine CFG anhand von Erkennungsregeln . Dies sind Regeln, die verwendet werden können, um gültige Phrasen in der Sprache abzugleichen.

Der PEG-Formalismus hat gegenüber EBNF den Vorteil, dass die Zuordnung zu einem Parser eindeutig ist und leicht automatisiert werden kann.

Das Folgende ist ein einfaches PEG, das von seiner Wikipedia-Seite entfernt wurde und mathematische Formeln beschreibt, die die vier Grundoperationen auf nicht negative anwenden

ganze Zahlen.

Expr ← SumSum ← Product ((‘+’ / ‘-’) Product)*Product ← Value ((‘*’ / ‘/’) Value)*Value ← [0–9]+ / ‘(‘ Expr ‘)’

Im Klartext können wir dies lesen als:

  • Expr ist ein Sum
  • Sumist ein Productgefolgt von null oder mehr Untermustern, die aus einem "+" oder "-" gefolgt von einem bestehenProduct
  • Productist ein Valuegefolgt von null oder mehr Untermustern, die aus einem "*" oder "/" gefolgt von einem bestehenValue
  • Valueist entweder ein oder mehrere Mitglieder des Zeichensatzes {0, .. 9} oder es ist eine offene Klammer "(" gefolgt von einer Exprund einer schließenden Klammer ")".

Parser-Generatoren versus Parsing-Bibliotheken

Angenommen, Sie sind nicht der Typ, der das Rad gerne neu erfindet (nicht, dass daran etwas falsch ist), gibt es im Allgemeinen zwei Möglichkeiten, einen Parser zu erstellen:

1. Verwenden Sie einen Parser-Generator - ein Tool, das den Quellcode für einen Parser aus einer abstrakten Definition des Parsers generiert. Einige beliebte Beispiele in JavaScript sind Jison, PEG.js, Nearley und ANTLR.

2. Verwenden Sie eine Analysebibliothek - eine Bibliothek, die den Ausdruck der Analyseregeln als API ermöglicht. Einige Beispiele in JavaScript sind Myna, Parsimmon und Chevrotain.

Ich bevorzuge die Verwendung von Parsing-Bibliotheken, da diese leichter zu verstehen, zu debuggen, zu warten und anzupassen sind.

Schreiben von Parsern in TypeScript / JavaScript mithilfe der Myna Parsing Library

Kürzlich erforderte ein Projekt, an dem ich arbeitete (die Heron-Sprache), eine Analysebibliothek, die im Browser ausgeführt werden konnte. Ich fand die Komplexität und den Aufwand bestehender Bibliotheken zu groß. Da ich bereits Erfahrung mit dem Schreiben von Parsing-Bibliotheken in C ++ und C # hatte, habe ich beschlossen, eine Parser-Bibliothek namens Myna mit TypeScript zu schreiben .

Myna verwendet eine fließende Syntax (Methodenverkettung), um es einfach zu machen, einen Parser als eine Reihe von Regeln (Unterparser) zu definieren, die einer PEG-Grammatik ähneln.

Das folgende Beispiel stammt aus dem Myna GitHub-Repo:

Vom konkreten Syntaxbaum (CST) zum abstrakten Syntaxbaum (AST)

Wenn ein Parser die Eingabe verarbeitet, kann jede erfolgreich übereinstimmende Regel (auch als Grammatikproduktion bezeichnet) einem Knoten im Analysebaum zugeordnet werden. Diese wörtliche Zuordnung von Produktionsregeln zu Knoten in einem Baum ist ein konkreter Syntaxbaum (CST).

In einigen Fällen ist das CST von begrenztem Nutzen, da es viel syntaktisches Durcheinander enthält, z. B. Kommentare im Quellcode oder ob ein Zeichenfolgenliteral doppelte oder einfache Anführungszeichen enthält. Es kann Ergebnisse von Regeln enthalten, die erstellt wurden, um die Verwendung der Grammatik zu vereinfachen, aber nicht die beabsichtigte Baumstruktur für die Analyse darstellen.

Am einfachsten ist es, nur Knoten im Ausgabebaum für bestimmte Regeln zu erstellen und andere Regeln zu überspringen. Diese vereinfachte Version des Analysebaums wird als abstrakter Syntaxbaum (AST) bezeichnet . An einem AST können mehrere Durchgänge ausgeführt werden, um ihn in alternative AST-Darstellungen umzuwandeln und spätere Verarbeitungsschritte zu vereinfachen.

In Myna wird ein AST generiert, indem Knoten aus Regeln erstellt werden, die mit der astEigenschaft gekennzeichnet sind. Technisch gesehen gibt diese Eigenschaft eine neue Regel zurück, für die ein interner Eigenschaftssatz festgelegt ist, der den Parser anweist, einen Analyseknoten im Analysebaum zu generieren.

Verwenden des generierten abstrakten Myna-Syntaxbaums

Hier ist ein Beispiel für die Verwendung eines von Myna definierten Parsers in „Node.JS“, um einen arithmetischen Ausdruck auszuwerten:

Letzte Worte

Wenn Sie mehr über das Erstellen und Verwenden von Parsern erfahren möchten, unabhängig davon, ob die Myna-Bibliothek Ihren spezifischen Anforderungen entspricht oder nicht, empfehlen wir Ihnen, sich etwas Zeit zu nehmen, um den Quellcode der Myna-Parsing-Bibliothek durchzulesen.

Myna wurde in TypeScript geschrieben (das für die meisten Programmierer eine bekannte Syntax hat), ist in einer einzelnen Datei ohne Abhängigkeiten enthalten und enthält weniger als 1200 Zeilen einschließlich detaillierter Dokumentation.

Wenn Sie daran interessiert sind, Myna auf ein komplexeres Szenario anzuwenden, schauen Sie sich die Programmiersprache Chickadee an. Dies ist vollständig in TypeScript implementiert und hängt nur von der Myna-Parsing-Bibliothek ab. Chickadee ist eine winzige Programmiersprache, die speziell entwickelt wurde, um Menschen beim Erlernen von Techniken zur Implementierung von Programmiersprachen zu unterstützen.

Wenn Ihnen dieser Artikel gefallen hat, lassen Sie es mich bitte wissen und teilen Sie ihn Ihren Freunden und Kollegen mit.