Get best of the week

SQL ergänzen. Teil 1. Die Komplexität des Parsens. Geschichten zum Finalisieren der ANTLR-Datei

Ich veröffentliche den Originalartikel über Habr, dessen Übersetzung im Codingsight- Blog veröffentlicht ist .

Was wird in diesem Artikel passieren?


Ich arbeite seit mehr als fünf Jahren in der Firma, die die IDE- Linie für die Arbeit mit Datenbanken entwickelt hat. Als ich mit der Arbeit an diesem Artikel begann, konnte ich mir nicht vorstellen, an wie viele interessante Geschichten ich mich erinnern konnte, denn als ich fertig war, bekam ich mehr als 30 Seiten Text. Nach einigem Nachdenken gruppierte ich die Geschichten nach Themen und teilte den Artikel in mehrere.

Während ich veröffentliche, werde ich Links zu den folgenden Teilen hinzufügen:

Teil 1. Die Komplexität des Parsens. Geschichten zum Finalisieren von ANTLR mit einer Datei
Teil 2. Optimierung der Arbeit mit Zeichenfolgen und Öffnen von Dateien
Teil 3. Lebensdauer der Erweiterungen für Visual Studio. Arbeite mit IO. Ungewöhnliche Verwendung von SQL
Teil 4. Arbeiten mit Ausnahmen, die Auswirkungen von Daten auf den Entwicklungsprozess. Verwenden von ML.NET

Während der Arbeit sind viele interessante Dinge passiert: Wir haben mehrere Fehler in .NET gefunden, einige Funktionen viele Male optimiert und einige nur in Prozent, beim ersten Mal etwas sehr Cooles getan und etwas, das uns selbst nach einigen nicht gelungen ist Versuche. Mein Team entwickelt und unterstützt IDE-Sprachfunktionen, die wichtigste ist die Code-Vervollständigung. Daher der Name der Artikelserie. In jedem ihrer Teile werde ich verschiedene Geschichten erzählen: einige über Erfolge, einige über Misserfolge.

In diesem Teil werde ich mich auf die Probleme beim Parsen von SQL, den Kampf gegen diese Probleme und die Fehler konzentrieren, die in diesem Kampf gemacht wurden.



Für diejenigen, die nur an einem Teil davon interessiert sind und nur für eine einfache Navigation, ist der Inhalt des Artikels:

Inhalt




Wer ich bin?


Ich kam als Juni mit sehr wenig Erfahrung zu diesem Job. Ich bin, wie viele, zum Programmieren gekommen, weil ich Spielzeug machen wollte. Einige sogar recht erfolgreich gemacht. Ich habe hier sogar über die Entwicklung eines solchen geschrieben. Vor kurzem hat er sie übrigens auf einem anderen Server wiederbelebt. Es gab immer noch ein Dutzend Spiele, die in verschiedenen Phasen der Bereitschaft gemacht oder abgebrochen wurden. Zusätzlich zu den Spielen konnte ich vor dieser Arbeit mehrere freiberufliche Projekte abschließen. Die größte davon war die Social-Media-Anwendung, ein Fußballportal mit Turniertischen, Spielerdaten und der Möglichkeit, Benutzer über das Endergebnis oder die erzielten Tore per SMS zu informieren. Dies wurde vor fast 10 Jahren getan. Zu dieser Zeit ging nicht jeder mit Smartphones, und wer früher häufiger ohne Internet oder mit der dreifach verfluchten EDGE war, auf der eine Textseite geöffnet werden konnte, war nicht immer möglich. Die Idee kam mir also gut vor.

Irgendwie stellte sich heraus, dass ich neben Spielen auch andere Tunings für mich oder andere Entwickler erstellen wollte. Manchmal war er nah an dem, was ich etwas später bei der Arbeit tun musste. Eines der Projekte, die ich beim Studium der Win32-API durchgeführt habe, war beispielsweise ein Programm, das XML-Code in Rich Edit Control hervorhebt. Darüber hinaus war es möglich, hintergrundbeleuchteten Code in BMP-, HTML- oder BB-Codes hochzuladen, die damals in verschiedenen Foren in Mode waren.

Ein anderes Projekt, das sich als verdammt nah an dem herausstellte, was ich gerade bei der Arbeit gemacht habe, war ein Programm, das C / C ++ - Code analysiert und daraus ein Blockdiagramm erstellt. Das Flussdiagramm entsprach genau den Anforderungen eines Lehrers an der Universität. Es wurde ungeschickt in der Stirn gemacht, ohne Kenntnis der Theorie der syntaktischen Analyse, und arbeitete ausschließlich an meinem beschissenen Charakter. Ein paar Jahre später, als ich den Computer von altem Müll befreite , stolperte ich darüber und konnte ihn nicht entfernen. Deshalb habe ich ihn aus Gründen der Geschichte auf Github gepostet .

Diese Experimente, gepaart mit freiberuflichen Tätigkeiten, machten eine ziemlich gute Erfahrung und ermöglichten es, einen Job zu bekommen. Im Laufe der Zeit, nach ein paar Dutzend in Blut und Tränen getränkten Bewertungen, fange ich sogar an, dem Unternehmen und dem Produkt zu nützen. Umgekehrt ist es ziemlich lustig zu verstehen, dass ich nach mehreren Unfällen genau das tat, was mich anzog.

Was sind die Schwierigkeiten?


Dieser Block wird benötigt, um den Leser in den Kontext dessen einzutauchen, was wir tatsächlich tun.



Desktop-Entwicklung


Vielleicht ist dies nicht einmal Komplexität, weil es bereits ein sehr ausgereiftes Gebiet ist, in dem es nicht viel Unbekanntes gibt, die Bibliotheken stabil sind, Best-Practice bekannt ist. Diese Funktion unseres Projekts ist hier, weil ich, wie viele andere Programmierer, anfällig für Neuheiten bin und Neuheiten jetzt alle im Web verschwunden sind. Es gab Tage, an denen ich im Regen auf die Fensterbank kletterte, bedeckt mit einer Decke, mit einem Becher Kakao, und über Redis, Reagieren, Hochladen und verteilte Systeme nachdachte, die gerade irgendwo ohne mich entwickelt werden. Die andere Seite dieses Problems ist, dass es nicht einfach ist, vertrauten Entwicklern die Komplexität des Projekts bei Bier zu beschreiben. Wenn Sie an Anwendungen arbeiten, die nach grundlegend unterschiedlichen Gesetzen arbeiten, wird es noch schwieriger.


Parsen von SQL und Dialekten


Ich habe vor dieser Arbeit auch kleine Parser für verschiedene Sprachen geschrieben. Für einige Zeit unterrichtete ich .NET-Kurse. Für einige Gruppen wurde als zusätzliche Aufgabe im Rahmen des Themas "Zeichenfolge" vorgeschlagen, einen eigenen einfachen JSON-Parser zu schreiben. Nur SQL und seine Varianten sind weit entfernt von XML oder JSON, die für Parser und Benutzer gleichermaßen verständlich sind. Darüber hinaus ist SQL syntaktisch komplexer als C / C ++, da sich viele Funktionen über einen langen Zeitraum angesammelt haben. SQL ist anders strukturiert, sie haben versucht, es übrigens recht erfolgreich wie eine natürliche Sprache aussehen zu lassen. Die Sprache hat mehrere tausend (je nach Dialekt) Schlüsselwörter. Um einen Ausdruck von einem anderen zu unterscheiden, müssen Sie häufig zwei oder mehr Wörter (Token) nach vorne schauen. Dieser Ansatz wird Lookahead genannt. Es gibt eine Klassifizierung der Parser nachWie weit sie vorausschauen können: LA (1), LA (2) oder LA (*), was bedeutet, dass der Parser so weit nach vorne schauen kann, wie er kann, um den richtigen Zweig zu bestimmen. Manchmal fällt das optionale Ende einer Klausel in einer SQL-Anweisung mit dem Beginn einer anderen zusammen, was ebenfalls optional ist: Solche Situationen machen Parser viel komplizierter. T-SQL schüttet Wasser in das Feuer, in dem das Semikolon optional ist, und das mögliche, aber nicht obligatorische Ende einiger SQL-Anweisungen kann mit dem Anfang anderer in Konflikt stehen.Solche Situationen erschweren Parser erheblich. T-SQL schüttet Wasser in das Feuer, in dem das Semikolon optional ist, und das mögliche, aber nicht obligatorische Ende einiger SQL-Anweisungen kann mit dem Anfang anderer in Konflikt stehen.Solche Situationen erschweren Parser erheblich. T-SQL schüttet Wasser in das Feuer, in dem das Semikolon optional ist, und das mögliche, aber nicht obligatorische Ende einiger SQL-Anweisungen kann mit dem Anfang anderer in Konflikt stehen.

Immer noch nicht glauben? Es gibt einen Mechanismus zur Beschreibung formaler Sprachen durch Grammatiken . Grammatik ist ein Code in einer Sprache, der eine andere beschreibt. Aus einer Grammatik können Sie häufig einen Parser mit einem Tool generieren. Die bekanntesten Grammatikbeschreibungswerkzeuge und -sprachen sind YACC und ANTLR . Von YACC generierte Parser werden direkt in den MySQL- , MariaDB- und PostgreSQL- Engines verwendet. Sie könnten versuchen, sie direkt aus Open Source zu übernehmen und Code-Vervollständigung und andere Funktionen basierend auf der darauf basierenden SQL-Analyse zu entwickeln. Darüber hinaus würde eine solche Implementierung kostenlose Aktualisierungen in Bezug auf die Entwicklung erhalten, und der Parser würde sich garantiert so verhalten, dass er mit dem Datenbankmodul identisch ist. Warum verwenden wir ANTLR? Es unterstützt qualitativ C # /. NET, es gibt gute Werkzeuge, um damit zu arbeiten, seine Syntax ist viel einfacher zu lesen und zu schreiben. Die ANTLR-Syntax erwies sich als so praktisch, dass Microsoft sie kürzlich in der offiziellen C # -Dokumentation verwendet hat .

Kehren wir zu meinem Beweis der Komplexität von SQL im Vergleich zu anderen Sprachen in Bezug auf das Parsen zurück. Dazu möchte ich die Grammatikgrößen für verschiedene öffentlich verfügbare Sprachen vergleichen. In dbForge verwenden wir unsere eigenen Grammatiken. Sie sind vollständiger als die öffentlich verfügbaren, aber leider sehr verstopft mit C # -Code-Einfügungen, um verschiedene Funktionen zu unterstützen. Weitere Informationen hierzu finden Sie im Abschnitt „Parsen ohne Bäume“ im Abschnitt „Fehler“.

Nachfolgend sind die Grammatikgrößen für verschiedene Sprachen aufgeführt:

JS - 475 Zeilen Parser + 273 Lexer = 748 Zeilen
Java - 615 Zeilen Parser + 211 Lexer = 826 Zeilen
C # - 1159 Zeilen Parser + 433 Lexer = 1592 Zeilen
C ++ - 1933 Zeilen

MySQL- 2515 Zeilen Parser + 1189 Lexer = 3704 Zeilen
T-SQL - 4035 Zeilen Parser + 896 Zeilen Lexer = 4931 Zeilen
PL SQL - 6719 Zeilen Parser + 2366 Lexer = 9085 Zeilen Am Ende einiger Lexer

steht eine Aufzählung von Unicode-Zeichen in der Sprache zur Verfügung Einschätzung der Komplexität der Sprache. Ich habe die Anzahl der Zeilen genommen, bevor ich mit solchen Übertragungen begonnen habe.

Es kann Fragen zur Komplexität des Parsens einer Sprache geben, die auf der Anzahl der Zeilen in ihrer Grammatik basiert. Fragen können sich auch auf die Fülle offener Grammatiken im Vergleich zur tatsächlichen Syntax von Sprachen beziehen. Trotzdem halte ich es immer noch für nützlich, diese Zahlen anzugeben, da der Spread zu groß ist.

Dies ist nicht alles, da wir nicht nur mehrere Dateien in SQL analysieren müssen. Wir machen eine IDE, was bedeutet, dass wir an unvollständigen oder ungültigen Skripten arbeiten müssen. Selbst wenn Sie Ihre Skripte fehlerfrei schreiben, schreiben Sie sie möglicherweise inkonsistent. Es ist unwahrscheinlich, dass das Skript während des gesamten Entwicklungsprozesses gültig ist. Zum Beispiel schreibe ich zuerst "SELECT FROM", danach freue ich mich über die Liste der verfügbaren Tabellen. Wenn ich eine Tabelle auswähle, ordne ich den Wagen auf SELECT um, drücke die Leertaste und warte auf die Liste der Spalten aus dieser bestimmten Tabelle. Dies ist ein sehr einfaches Beispiel, aber es zeigt, dass der Parser, der die Code-Vervollständigung in der IDE bereitstellt, nicht abstürzen kann, außer wenn ein ungültiges Skript auftritt. Wir mussten uns viele Tricks einfallen lassen, um sicherzustellen, dass der Tooltip in vielen solchen Szenarien korrekt funktioniert.Benutzer senden jedoch immer noch unterschiedliche Szenarien für die Arbeit mit unvollendeten Skripten, was bedeutet, dass wir uns neue Tricks einfallen lassen müssen.

Prädikatenkriege


Beim Parsen des Codes gibt es manchmal Situationen, in denen das nächste Wort nicht klar macht, welche der beiden Alternativen zu wählen ist. Manchmal reicht es aus, im Voraus eine genau definierte Anzahl von Wörtern zu betrachten, und Sie können definitiv eine Alternative auswählen. Der Mechanismus zur Behebung dieser Art von Ungenauigkeit wird als ANTLR-Lookahead bezeichnet. Die Parser-Methode ist in diesem Fall als eingebettete Kette von ifs aufgebaut, von denen jede ein Wort weiter schaut. Nachfolgend finden Sie ein Beispiel für eine Grammatik, die eine solche Unsicherheit erzeugt.

rule1:
    'a' rule2 | rule3
    ;

rule2:
    'b' 'c' 'd'
    ;

rule3:
    'b' 'c' 'e'
    ;

In der Mitte von Regel 1 muss der Parser, nachdem er bereits das Token 'a' übergeben hat, 2 Token vorausschauen, um zu entscheiden, welcher Regel er folgen soll. Diese Überprüfung wird erneut innerhalb der Regel durchgeführt. Diese Grammatik kann so umgeschrieben werden, dass dieser Lookahead nicht existiert. Leider leidet die Struktur häufig unter solchen Optimierungen, und der Leistungsgewinn ist relativ hoch.

Es gibt komplexere Mechanismen, um komplexere Unsicherheiten aufzulösen. Einer davon ist der Syntaxprädikatmechanismus (synpred) in ANTLR3.

Er kommt zur Rettung in den Fällen, in denen sich beispielsweise die optionale Vervollständigung einer Klausel mit dem Beginn der optionalen anderen Klausel überschneidet. Das Prädikat ist in ANTLR3-Begriffen die generierte Methode, die gemäß einer der Alternativen eine virtuelle Passage durch den Text durchführt und bei Erfolg true zurückgibt. Diese Vervollständigung des Prädikats wird als erfolgreich bezeichnet. Der virtuelle Pass wird auch als Backtracking-Pass bezeichnet. Wenn das Prädikat erfolgreich funktioniert hat, wird ein echter Pass erstellt. Dies wird zu einem Problem, wenn ein anderes Prädikat innerhalb eines Prädikats beginnt und ein Abschnitt hunderttausend Mal durchlaufen werden kann.

Betrachten Sie ein vereinfachtes Beispiel. Es gibt 3 Unsicherheitspunkte (A, B, C).

  1. Der Parser gibt A ein, merkt sich die Position im Text und beginnt eine virtuelle Passage der 1. Ebene.
  2. B, , 2- .
  3. C, , 3- .
  4. 3- , 2 .
  5. 2 , 1 B .
  6. , A, B .

Somit werden alle Überprüfungen innerhalb von C 4 Mal, B - 3 Mal, A - 2 Mal durchgeführt. Was aber, wenn die geeignete Alternative an zweiter oder dritter Stelle in der Liste steht? Dann schlägt irgendwann eines der Prädikate fehl, die Position im Text wird zurückgesetzt und ein anderes Prädikat wird ausgeführt.

Bei wiederholter Analyse der Ursache für das Einfrieren der Anwendung stießen wir auf Fälle, in denen der synpred „Schwanz“ mehrere tausend Mal ausgeführt wurde. Synpreds sind in rekursiven Regeln besonders problematisch. Leider ist SQL von Natur aus rekursiv, was zumindest die Fähigkeit ist, eine Unterabfrage fast überall zu verwenden. Manchmal stellt sich mit Hilfe verschiedener Tricks und Tricks heraus, dass die Regel so ausfällt, dass das Prädikat verschwunden ist.

Synpred wirkt sich natürlich negativ auf die Leistung aus. Irgendwann war es notwendig, ihre Bevölkerung unter strenge Kontrolle zu bringen. Das einzige Problem ist, dass beim Schreiben von Grammatikcode das Erscheinungsbild von Synpred möglicherweise nicht offensichtlich ist. Darüber hinaus führt manchmal eine Änderung einer Regel zum Auftreten eines Prädikats in einer anderen. Dies kann nicht manuell gesteuert werden. Um die Anzahl der Prädikate zu steuern, haben wir einen einfachen Regular geschrieben, der von einer speziellen MsBuild-Task aufgerufen wurde. Wenn sich die Anzahl der Prädikate von der in einer separaten Datei angegebenen Anzahl unterschied, unterbrach Task die Assembly und meldete einen Fehler. Als der Entwickler einen solchen Fehler bemerkte, musste er den Regelcode mehrmals umschreiben, um unnötige Prädikate zu entfernen und möglicherweise andere Entwickler in das Problem einzubeziehen. Wenn ein Prädikat unvermeidlich ist,Anschließend aktualisiert der Entwickler die Anzahl der Prädikate in der entsprechenden Datei. Eine Änderung dieser Datei macht besonders auf die Überprüfung aufmerksam.

In seltenen Fällen haben wir sogar unsere eigenen Prädikate in C # geschrieben, um die von ANTLR generierten zu umgehen. Glücklicherweise gibt es auch einen solchen Mechanismus.

Coole Fahrrad - Lösungen




Grammatikvererbung


Nach der Ankündigung von Änderungen in jedem von uns unterstützten DBMS beginnt unsere Arbeit, diese zu unterstützen. Der Ausgangspunkt dafür ist fast immer die Unterstützung syntaktischer Konstruktionen in der Grammatik. Für jeden SQL-Dialekt schreiben wir unsere eigene Grammatik. Dies führt zu einer gewissen Wiederholung des Codes, aber letztendlich ist es einfacher, nach einer gemeinsamen Grammatik zu suchen. Noch vor ein paar Jahren waren sich MySQL und MariaDB sehr ähnlich, das Schreiben separater Grammatiken war unpraktisch. Da diese wenigen Konstruktionen in MariaDB, aber nicht in MySQL enthalten waren, haben wir sie in der MySQL-Grammatik unterstützt. Dies war ein unangenehmer Moment: Für den MySQL-Benutzer könnten wir Konstrukte vorschlagen, die nicht gültig sind. In den letzten Jahren sind MariaDB und MySQL in Bezug auf Syntax und mehr sehr unterschiedlich geworden. Es wurde offensichtlichdass es falsch ist, zwei verschiedene Sprachen innerhalb derselben Grammatik zu unterstützen.

Eine mögliche Lösung könnte eine vollständige Kopie der Grammatik sein, nach der jede separat unterstützt wird. Nach einer langen Diskussion haben wir eine mutige Entscheidung getroffen. Ich bin sehr froh, dass wir den Code nicht kopiert haben, jede Zelle in mir hat sich dieser Entscheidung widersetzt. Es wurde beschlossen, einen eigenen Grammatik-Präprozessor ANTLR zu schreiben, der den Mechanismus der Grammatik-Vererbung implementiert. Vor einiger Zeit bin ich auf eine ANTLR3-Grammatik im offiziellen Repository von ANTLR4-Grammatiken gestoßen. Ich denke, dieser Satz muss mehrmals gelesen werden, um die Tiefe des Wahnsinns zu erkennen.

Als wir die Idee der Vererbung diskutierten, wurde uns schnell klar, dass wir einen Mechanismus für Polymorphismus haben möchten. Die Fähigkeit in der Grammatik des Erben, nicht nur die Regel neu zu definieren, sondern auch die Basis zu nennen. Außerdem möchte ich die Position des Aufrufs der Grundregel steuern: Anfang, Mitte oder Ende. Wir haben beschlossen, dass alle Regeln neu definiert werden können, dafür müssen Sie nichts weiter angeben. Um eine Regel neu zu definieren, reicht es aus, eine gleichnamige Regel in der Nachfolgegrammatik zu deklarieren. Danach steht die Regel aus der übergeordneten Grammatik unter einem anderen Namen zur Verfügung.

ANTLR ist ein angenehmes Werkzeug für die Entwicklung durch Tuning - es gibt eine Erweiterung für VS, es gibt ANTLRWorks. Durch die Einführung des Vererbungsmechanismus möchte ich diese Gelegenheit nicht verpassen. Aber wie soll man dann die grundlegende Grammatik angeben? Sie können sich eine Art Konvention für die Benennung von Dateien einfallen lassen, aber dies ist überhaupt nicht offensichtlich. Eine andere Möglichkeit könnte darin bestehen, solche zusätzlichen Informationen in einer separaten Datei anzugeben, aber selbst jetzt, als ich diese Zeilen tippte, spürte ich den Gestank dieser Lösung. Die Ausgabe war ein Hinweis auf die grundlegende Grammatik in der Grammatik des Erben im Format eines ANTLR-Kommentars. Alle Tools ignorieren diesen Text einfach und wir können den Code, der uns interessiert, leicht herausziehen.

Die Anforderungen wurden gebildet, es ist Zeit, sie umzusetzen. Wir haben die MsBuild-Task geschrieben, die als Pre-Build-Aktion in das allgemeine Build-System integriert wurde. Die Aufgabe führte die Arbeit des ANTLR-Grammatikpräprozessors aus, wobei die resultierende Grammatik aus der Basis generiert und geerbt wurde. Die resultierende Grammatik wurde bereits von ANTLR selbst verarbeitet. Wenn in der Nachfolgegrammatik eine Regel mit demselben Namen wie im übergeordneten Element gefunden wurde, wurde die Grundregel umbenannt: Der Name der übergeordneten Grammatik wurde nach dem Unterstrich zu ihrem Namen hinzugefügt. Unter diesem Namen konnte er im Erben kontaktiert werden.

Der Präprozessormechanismus selbst nahm nicht viel Zeit in Anspruch, aber zusammen mit der Generierung des Parsers stellte sich heraus, dass er jeden Zusammenbau des Projekts um 10 bis 20 Sekunden verlangsamte. Irgendwann hörte das auf, uns zu passen. Wir haben uns überlegt, wie dies optimiert werden kann. Die Lösung bestand darin, den Hash der Summe aller Grammatiken, von denen er abhängt, in Form eines Kommentars zum Header der CS-Parser-Datei hinzuzufügen. Bevor etwas unternommen wurde, verglich der Präprozessor diese Hashes mit den Hashes der Dateien auf der Festplatte. Wenn sie sich nicht unterscheiden, wurde die Parser-Datei als relevant angesehen. In der anfänglichen Entwicklungsphase mussten wir mehr als einmal auf den Rechen ungültiger Parser und Grammatiken treten, die von der veralteten Version des Präprozessors gesammelt wurden. Infolgedessen wurde die Hash-Summe der Assembly mit dem Präprozessor im Header-Kommentar angezeigt.

Eine weitere Nachbearbeitung von ANTLR


Wenn in vielen Programmiersprachen das Wort der Schlüssel ist, kann es nicht mehr als Name des Objekts verwendet werden. In SQL je nach Dialekt 800 bis 3000 Schlüsselwörter. Die meisten von ihnen sind eng mit dem Themenbereich verwandt, außerdem wurden nicht alle sofort eingeführt, sodass ein Verbot, sie alle als Objektnamen zu verwenden, mit Empörung einhergehen würde. SQL führt das Konzept der reservierten und nicht reservierten Schlüsselwörter ein. Sie können ein Objekt nicht wie ein reserviertes Schlüsselwort (SELECT, FROM usw.) benennen, ohne es in Anführungszeichen zu setzen, da es kein reserviertes Schlüsselwort (CONVERSATION, AVAILABILITY usw.) ist. Dieses Verhalten erschwert die Entwicklung des Parsers. Zum Zeitpunkt der lexikalischen Analyse ist der Kontext unbekannt, der Parser benötigt jedoch unterschiedliche Nummern für den Bezeichner und das Schlüsselwort. Um dieses Problem zu lösen, haben wir dem ANTLR-Parser eine weitere Nachbearbeitung hinzugefügt.Die Nachbearbeitung ersetzt alle expliziten Prüfungen durch einen Bezeichner und ruft eine spezielle Methode auf. Diese Methode implementiert eine schwierigere Prüfung. Wenn ein Bezeichner eingegeben wird und ein Bezeichner weiter erwartet wird, ist alles in Ordnung. Wenn jedoch ein nicht reserviertes Schlüsselwort für die Eingabe angegeben wird, muss es zusätzlich überprüft werden. Eine zusätzliche Überprüfung besteht darin, dass die Methode im aktuellen Kontext bei der Suche nach Zweigen untersucht wird, wobei dieses nicht reservierte Schlüsselwort genau als Schlüsselwort verwendet werden kann. Wenn es keine solchen Zweige gibt, kann es als Bezeichner verwendet werden.Wenn jedoch ein nicht reserviertes Schlüsselwort eingegeben wird, muss es zusätzlich überprüft werden. Eine zusätzliche Überprüfung besteht darin, dass die Methode im aktuellen Kontext bei der Suche nach Zweigen untersucht wird, wobei dieses nicht reservierte Schlüsselwort genau als Schlüsselwort verwendet werden kann. Wenn es keine solchen Zweige gibt, kann es als Bezeichner verwendet werden.Wenn jedoch ein nicht reserviertes Schlüsselwort eingegeben wird, muss es zusätzlich überprüft werden. Eine zusätzliche Überprüfung besteht darin, dass die Methode im aktuellen Kontext bei der Suche nach Zweigen untersucht wird, wobei dieses nicht reservierte Schlüsselwort genau als Schlüsselwort verwendet werden kann. Wenn es keine solchen Zweige gibt, kann es als Bezeichner verwendet werden.

Genau genommen kann dieses Problem nur mit ANTLR gelöst werden, aber eine solche Lösung ist nicht optimal. Eine klassische Lösung für dieses Problem besteht darin, eine Regel zu erstellen, in der alle nicht reservierten Schlüsselwörter und ein Bezeichner-Token aufgelistet sind. Wo immer es zulässig ist, einen Bezeichner zu verwenden, wird das Bezeichner-Token des Bezeichners nicht mehr verwendet, dies ist jedoch eine Sonderregel. Eine solche Lösung erinnert Sie nicht nur daran, das Schlüsselwort bei der Eingabe hinzuzufügen, nicht nur dort, wo es verwendet wird, sondern auch in dieser Sonderregel viel langsamer.

Fehler



Baumloses Parsen




Das Ergebnis des Parsers ist in der Regel ein Syntaxbaum. Ein Syntaxbaum ( abstrakt oder konkret ) ist eine Datenstruktur, die den Programmtext durch das Prisma der formalen Grammatik widerspiegelt. Wenn Sie einen Code-Editor mit automatischer Vervollständigung für die Sprache implementieren möchten, die Sie kürzlich entwickelt haben, nachdem Sie das Problem untersucht haben, implementieren Sie wahrscheinlich ungefähr den folgenden Algorithmus:

  1. Analysieren Sie den Text im Editor. Holen Sie sich den Syntaxbaum.
  2. Finde den Knoten unter dem Wagen. Ordne es der Grammatik zu. Finden Sie heraus, welche Schlüsselwörter und Objekttypen zu diesem Zeitpunkt verfügbar sein werden.

In diesem Fall wird die Grammatik bequem als Graph oder Finite-State-Maschine dargestellt.

Leider existierte die IDE ANTLR zu Beginn der Entwicklung in ihrer dritten Version. Die vierte Version wurde von Grund auf neu geschrieben und unterscheidet sich grundlegend von der dritten. Durch Übergeben des Codes generiert der Parser automatisch einen Analysebaum ohne eine einzige zusätzliche Zeile. In der dritten Version gab es einen Mechanismus, mit dem man ANTLR sagen konnte, wie man einen Baum baut, aber es war nicht sehr angenehm, ihn zu benutzen. Darüber hinaus wurde in vielen Beispielen und Artikeln zu diesem Thema vorgeschlagen, den Aktionsmechanismus zum Ausführen von Code zu verwenden, sobald der Parser die Regel übergibt. Dieser Mechanismus ist unglaublich praktisch und ermöglicht es Ihnen, schnell Ergebnisse zu erzielen. Leider führte diese Lösung zu großen architektonischen Problemen bei der Entwicklung des Produkts und zu einer zunehmenden Komplexität der Unterstützung neuer Funktionen. Tatsache ist, dass in einer Datei, in einer Grammatikdatei,Es häuften sich Aktionen, die mit einer großen Anzahl unterschiedlicher Funktionen verbunden waren, die sich auf verschiedene Baugruppen verteilen ließen. In Zukunft konnten wir die Aktionshandler für verschiedene Assemblys verteilen, indem wir eine ziemlich knifflige Version des Abonnenten-Benachrichtigungsmusters implementierten. Die Aufrufe selbst, die die erforderlichen Informationen übermitteln, überladen jedoch weiterhin unsere Grammatik, erschweren die Unterstützung neuer Funktionen und legen der Architektur schwerwiegende und unangenehme Einschränkungen auf.erschweren die Unterstützung neuer Funktionen und legen der Architektur schwerwiegende und unangenehme Einschränkungen auf.erschweren die Unterstützung neuer Funktionen und legen der Architektur schwerwiegende und unangenehme Einschränkungen auf.

Aber alles ist nicht so offensichtlich, wie es scheinen mag. Tatsache ist, dass ANTLR3 viel schneller ist als ANTLR4. Nach unseren Messungen betragen die Unterschiede etwa das 6-fache. Darüber hinaus kann der Syntaxbaum für große Skripte viel RAM-Speicherplatz beanspruchen. Solange wir im 32-Bit-Adressraum von Visual- und SqlServer Management-Studios überleben müssen, kann dies von entscheidender Bedeutung sein.

Fazit


Zwischensummen können wie folgt sein:

  • ANTLR ist ein leistungsstarkes Tool zum Erstellen von Parsern
  • Der Vorteil gegenüber anderen sind Tools, eine praktische Syntax und eine große Anzahl unterstützter Sprachen
  • ANTLR4 wurde von Grund auf neu geschrieben und impliziert die Arbeit mit dem Parser, der sich von der dritten Version unterscheidet
  • Es gibt immer eine Möglichkeit, ein bisschen mehr aus ThirdParty-Bibliotheken herauszuholen, als sie geben
  • SQL-spezifische Sprache, Parser dafür zu erstellen, ist keine leichte Aufgabe
  • Das Parsen von Code für Aufgaben im Zusammenhang mit dem Erstellen einer IDE hat seine eigenen Besonderheiten: Sie müssen in Betracht ziehen, an Skripten zu arbeiten, die nicht geschlossen oder ungültig sind

Wir sehen uns im nächsten Teil!

More articles:


All Articles