btyacc – Online in der Cloud

PROGRAMM:

NAME/FUNKTION

btyacc – ein Lalr(1) Parser-Generator mit Unterstützung für Backtracking

ZUSAMMENFASSUNG

btyacc [-B Präfix] [-d] [-DNAME/FUNKTION ...] [-E] [-l] [-r] [-S x.ske] [-Fernseher]
Dateiname.y

Beschreibung

btyacc ist eine modifizierte Version von byacc (Berkeley YACC), das wiederum gemeinfrei ist
Version des ursprünglichen AT&T YACC-Parsergenerators.

btyacc liest die Grammatikspezifikation in der Datei Dateiname.y und erzeugt eine LR(1)
Parser dafür. Der Parser besteht aus einer Reihe von Lalr(1) Parsing-Tabellen und eine Treiberroutine
geschrieben in der Programmiersprache C. btyacc schreibt normalerweise die Parse-Tabellen und die
Treiberroutine in die Datei Präfix.tab.c, Wobei Präfix Der Standardwert ist „y“.

Für eine detaillierte Beschreibung des Formats einer Grammatikspezifikation und eine ausgezeichnete
Ein Tutorial zur Verwendung von YACC-ähnlichen Tools finden Sie im Infohandbuch für GNU Bison. btyacc-
Spezifische Erweiterungen werden unten erläutert.

Hinweis: Das vom Upstream-Autor von btyacc bereitgestellte Parser-Skelett lässt sich nur als C++ kompilieren. Verwenden
das Skelett /usr/doc/btyacc/examples/btyacc-c.ske um einen Parser zu generieren, der beides kompiliert
als C und C++. (Leider prüft dieses alternative Grundgerüst derzeit nicht malloc()
Rückgabewerte.)

Optionen

-b Präfix Ändern Sie das Präfix, das den Ausgabedateinamen vorangestellt wird, in die durch gekennzeichnete Zeichenfolge
Präfix. Das Standardpräfix ist das Zeichen „y“.

-d Erstellt eine Header-Datei mit dem Namen Präfix.tab.h zusammen mit Präfix.tab.c,
enthält die Symboldefinitionen und eine Deklaration für JYSTYP und Yylval.

-DNAME/FUNKTION Definieren Sie die Präprozessorvariable btyacc NAME/FUNKTION, zum Gebrauch mit %ifdef NAME/FUNKTION
Anweisungen in der Grammatikdatei.

-E Gibt die vorverarbeitete Grammatik auf der Standardausgabe aus.

-l Nicht einfügen #Leitung Direktiven in den generierten Parsercode.

-r Schreibt den Parser-Code und die zugehörigen Tabellen in verschiedene Dateien. Während die
Tabellen finden Sie in Präfix.tab.c Wie zuvor wird nun der Code geschrieben
zu Präfix.code.c.

-S x.ske Wählen Sie ein anderes Parser-Skelett aus. Das Standardgerüst ist fest mit dem verbunden
Programm, aber eine Kopie befindet sich in der Datei btyaccpa.ske.

-t Bewirkt, dass Debugging-Code in den generierten Parser kompiliert wird.

-v Schreiben Sie eine für Menschen lesbare Beschreibung des generierten Parsers in y.Ausgabe. Es
Enthält Parser-Zustände, Aktionen für ein Look-Ahead-Token und Informationen zu allen
Konflikte.

BTYACC Erweiterungen

Backtracking Support
Immer wenn ein von btyacc generierter Parser auf einen Shift-Reduce- oder Reduce-Reduce-Fehler im stößt
In der Parse-Tabelle merkt es sich den aktuellen Parse-Punkt (Stapel- und Eingabestream-Status) und fährt fort
in den Test-Parse-Modus. Anschließend wird die Analyse fortgesetzt, wobei die meisten Regelaktionen ignoriert werden. Wenn es läuft
in einen Fehler umwandeln (entweder durch die Parse-Tabelle oder durch einen Aktionsaufruf). YYERROR), es
Kehrt zum letzten Konfliktpunkt zurück und versucht eine andere Alternative. Wenn es
findet einen erfolgreichen Pfad (erreicht das Ende der Eingabe oder einen Aktionsaufruf). YYVALID), es
kehrt zu dem Punkt zurück, an dem der Test-Parse-Modus zum ersten Mal aufgerufen wurde, und fährt mit einer vollständigen Analyse fort
Analysieren (Ausführen aller Aktionen) und Verfolgen des Pfads des erfolgreichen Versuchs.

Aktionen in btyacc gibt es in zwei Varianten: {} Aktionen, die nur ausgeführt werden, wenn sie nicht vorhanden sind
Testmodus und [] Aktionen, die unabhängig vom Modus ausgeführt werden.

Beispiel: In YACC-Grammatiken für C gibt es einen Standard-Hack, der als „Lexer-Feedback-Hack“ bekannt ist
Wird verwendet, um Typedef-Namen zu finden. Der Lexer verwendet semantische Informationen, um zu entscheiden, ob welche vorhanden sind
Der Bezeichner ist ein Typdefinitionsname oder nicht und gibt ein spezielles Token zurück. Mit btyacc, nein
Sie müssen dies nicht länger tun. Der Lexer sollte einfach immer einen Bezeichner zurückgeben. Der BTYACC
Die Grammatik benötigt dann eine Regel der Form:

Modellname: ID [ if (!IsTypeName(LookupId($1))) YYERROR; ]

Beachten Sie jedoch, dass das Hinzufügen von Backtracking-Regeln den Parser verlangsamt. In der Praxis Sie
Ich sollte versuchen, die Anzahl der Konflikte in der Grammatik auf das absolute Minimum zu beschränken
notwendig. Erwägen Sie die Verwendung des „Lexer-Feedback-Hack“, wenn es sich um eine saubere Lösung handelt, und
Reservieren Sie das Zurückverfolgen für einige Sonderfälle.

btyacc führt seine Versuche nach der Regel durch: „Versuchen Sie zuerst, zu verschieben, dann versuchen Sie, die Reihenfolge zu reduzieren.“
dass die widersprüchlichen Regeln in der Eingabedatei erscheinen". Dies bedeutet, dass Sie sie implementieren können
Semantische Disambiguierungsregeln wie zum Beispiel: (1) Wenn es wie eine Deklaration aussieht, ist es das,
andernfalls (2) Wenn es wie ein Ausdruck aussieht, ist es das, andernfalls (3) handelt es sich um einen Syntaxfehler
[Ellis & Stroustrup, Annotated C++ Reference Manual, S. 93]. Um dies zu erreichen, setzen Sie alle
Regeln für Deklarationen vor den Regeln für Ausdrücke in der Grammatikdatei.

Das Zurückverfolgen wird nur ausgelöst, wenn die Analyse auf eine Verschiebung/Reduzierung oder Reduzierung/Reduzierung trifft
Konflikt in der Tabelle. Wenn Sie keine Konflikte in Ihrer Grammatik haben, fallen keine zusätzlichen Kosten an.
außer einem zusätzlichen Code, der niemals aufgerufen wird.

Derzeit wird der generierte Parser ausgeführt nicht Beschneidung alternativer Parsing-Pfade. Vermeiden
eine exponentielle Explosion möglicher Pfade (und Analysezeit), die Sie manuell ermitteln müssen
der Parser, wenn er gespeicherte Pfade mit dem verwerfen kann YYVALID Stellungnahme. In
Durch Übung gelingt dies recht einfach. Ein C++-Parser kann beispielsweise einfach
enthalten [YYVALID;] nach jeder vollständigen Deklarations- und Anweisungsregel, was zu der führt
Der Backtracking-Status wird bereinigt, nachdem ein „;“ angezeigt wurde. oder `}' – es wird nie ein geben
Situation, in der es sinnvoll ist, über eines dieser beiden Dinge hinwegzugehen.

Verbesserte Zeichen Position Umgang
Compiler müssen häufig ASTs (abstrakte Syntaxbäume) erstellen, sodass jeder Knoten in einem Baum
kann sich auf die analysierte Programmquelle beziehen, aus der es stammt. Der YYPOSN Mechanismus unterstützt
von btyacc hilft Ihnen bei der Automatisierung der Textpositionsberechnung und der Zuweisung
berechnete Textpositionen zu den AST-Knoten.

In Standard-YACCs hat jeder Token und jedes Nicht-Terminal einen JYSTYP semantischer Wert
angehängt an. Mit btyacc hat jeder Token und jedes Nicht-Terminal auch einen YYPOSN Text
Position daran befestigt. YYPOSN ist ein benutzerdefinierter Typ.

btyacc verwaltet einen Stapel von Textpositionswerten auf die gleiche Weise wie einen Stapel
semantischer Werte. Um die Textpositionierungsfunktion nutzen zu können, müssen Sie Folgendes tun #define
wie folgt vor:

YYPOSN Präprozessorsymbol für den C/C++-Typ der an jedes angehängten Textposition
Token und Nicht-Terminal.

yyposn Globale Variable vom Typ YYPOSN. Der Lexer muss die Textposition des zuweisen
hat das Token an yyposn zurückgegeben, genau wie es den semantischen Wert des zuweist
Token an Yylval zurückgegeben.

YYREDUCEPOSNFUNC
Präprozessorsymbol für eine Funktion, die unmittelbar nach der regulären Funktion aufgerufen wird
Es wurde eine Reduzierung der Grammatikregeln durchgeführt, um die darauf befindlichen Textpositionen zu reduzieren
den Stack.

Typischerweise extrahiert diese Funktion Textpositionen aus der Regel auf der rechten Seite
Komponenten und weist sie entweder der zurückgegebenen $$-Struktur/dem zurückgegebenen $$-Baum zu oder, falls nein
Der Wert $$ wird zurückgegeben und an der Ret-Textposition platziert, an der er sein wird
später durch andere Regeln aufgegriffen. Sein Prototyp ist:

ungültig Posn reduzieren(
YYPOSN& ret,
YYPOSN* term_posns,
YYSTYPE* term_vals,
int term_nr,
int stk_pos,
int yychar,
YYPOSN& yyposn,
Benutzertyp extra);

ret Verweis auf die von der Regel zurückgegebene Textposition. Sie müssen überschreiben
Dies mit der berechneten Textposition, die die Regel ergibt, analog zu
der semantische Wert $$.

term_posns
Array der Regelkomponenten auf der rechten Seite YYPOSN Textpositionen,
analog zu $1, $2, ..., $N für die semantischen Werte.

term_vals Array der Regelkomponenten auf der rechten Seite JYSTYP Werte. Diese sind
die $1, ..., $N selbst.

term_no Anzahl der Komponenten auf der rechten Seite der reduzierten Regel, d. h. die
Größe der Arrays term_posns und term_vals. Auch gleich N in $1, ...,
$N.

stk_pos JYSTYP/YYPOSN Stapelposition vor der Reduktion.

yychar Lookahead-Token, der unmittelbar auf die reduzierte rechte Seite folgt
Komponenten.

yyposn YYPOSN des Tokens, der unmittelbar auf die reduzierte rechte Seite folgt
Komponenten.

extra Benutzerdefiniertes zusätzliches Argument, das an ReducePosn übergeben wird.

YYREDUCEPOSNFUNCARG
Zusätzliches Argument, das an die ReducePosn-Funktion übergeben wird. Dieses Argument kann beliebig sein
Variable definiert in btyaccpa.ske.

Token Aufhebung im Fehler Erholung
Bei den meisten YACC-ähnlichen Parsergeneratoren die Aktion des generierten Parsers bei der Begegnung
Ein Analysefehler besteht darin, semantische Werte und Eingabetokens wegzuwerfen, bis eine Regel enthalten ist
das spezielle Nicht-Terminal Fehler aufeinander abgestimmt werden können. Das Verwerfen von Token erfolgt einfach per
Überschreiben von Variablen und Array-Einträgen des Typs JYSTYP mit neuen Werten.

Leider führt dieser Ansatz zu einem Speicherverlust, wenn JYSTYP ist ein Zeigertyp. btyacc
ermöglicht Ihnen die Bereitstellung von Funktionen zum Bereinigen der Semantik- und Textpositionswerte
#defineFügen Sie die folgenden Symbole in die Präambel Ihrer Grammatikdatei ein:

YYDELETEVAL
Präprozessorsymbol für eine aufzurufende Funktion vor dem semantischen Wert eines Tokens
oder Nicht-Terminal wird verworfen.

YYDELETEPOSN
Präprozessorsymbol für eine aufzurufende Funktion vor der Textposition eines Tokens
oder Nicht-Terminal wird verworfen.

Beide Funktionen werden mit zwei Argumenten aufgerufen. Das erste Argument des Typs JYSTYP or YYPOSN
ist der Wert, der verworfen wird. Das zweite Argument ist vom Typ int und ist einer von
drei Werte:

0 Eingabetoken wird verworfen

1 Ablagezustand auf dem Stapel

2 Stapel aufräumen beim Abbruch

Detailliert Syntax Fehler Berichterstattung
Wenn Sie #define die Präprozessorvariable YYERROR_DETAILED in Ihrer Grammatikdatei müssen Sie
Definieren Sie außerdem die folgende Fehlerverarbeitungsfunktion:

ungültig yyerror_detailed(
char * Text,
int ähm,
YYSTYPE&
errt_value,
YYPOSN& errt_posn);

Textfehlermeldung

Fehlercode des Tokens, der den Fehler verursacht hat

errt_value
Wert des Tokens, der den Fehler verursacht hat

errt_posn Textposition des Tokens, das den Fehler verursacht hat

Präprozessor Richtlinien
btyacc unterstützt die Definition von Symbolen und deren Bearbeitung mit bedingten Anweisungen
Grammatikdateien, nicht unähnlich dem C-Präprozessor.

%definieren NAME/FUNKTION
Definieren Sie das Präprozessorsymbol NAME/FUNKTION. Entspricht dem Befehlszeilenschalter
-DNAME/FUNKTION.

%ifdef NAME/FUNKTION
Wenn Präprozessorvariable NAME/FUNKTION definiert ist, verarbeiten Sie den Text daraus %ifdef zu
Die Schließung %endif, andernfalls überspringen Sie es.

%endif Schlussanweisung für %ifdef. %ifdefs können nicht verschachtelt werden.

%enthalten DATEINAME
Verarbeiten Sie den Inhalt der genannten Datei DATEINAME. Nur eine Verschachtelungsebene von %enthalten
ist erlaubt.

%ident STRING
Fügen Sie ein ` ein#ident STRING' Direktive in die Ausgabedatei. STRING muss ein sein
Zeichenfolgenkonstante, eingeschlossen in „“.

Ererbt Attribute
Geerbte Attribute sind nicht dokumentiert. (Siehe die README und der btyacc-Quellcode für a
Wenige Informationen.) Wenn Sie herausfinden, wie sie funktionieren, kontaktieren Sie mich unter[E-Mail geschützt] >!

Fehler

Die Komplexität des Parsings im schlimmsten Fall ist für jede Grammatik, die dies zulässt, exponentiell
Backtracking stattfinden soll. Mit anderen Worten, ein von btyacc generierter Parser stellt einen dar
Denial-of-Service-Bug, wenn er in Anwendungen verwendet wird, die ein Angreifer bereitstellen kann
speziell gestaltete Daten als Eingabe für den Parser. (Für alle „normalen“ Eingabedaten gilt die
potenziell exponentielle Komplexität ist normalerweise kein Problem.)

Bisons %erwarten Direktive wird nicht unterstützt.

Es gibt kein %anders und %ifndef. %ifdefs und %enthaltens können nicht verschachtelt werden.

Autoren

Robert Corbett[E-Mail geschützt] > /[E-Mail geschützt] > war einer der
Originalautoren von Berkeley byacc. Chris Dodd[E-Mail geschützt] >hatte das geniale
Idee, Backtracking-Funktionen hinzuzufügen, und ist für das anfängliche Backtracking verantwortlich
Änderungen. Vadim Maslov[E-Mail geschützt] > den Code weiter verbessert.

Diese Dokumentation wurde von Richard Atterer verfasst[E-Mail geschützt] > für das Debian
GNU/Linux-Distribution, ist jedoch gemeinfrei und darf daher frei verwendet werden
für jeden Zweck.

Mappen

/usr/doc/btyacc/examples/btyaccpa.ske

/usr/doc/btyacc/examples/btyacc-c.ske

/usr/doc/btyacc/README

See ebenfalls

Bison(1) (oder „Info-Bison“), nach Acc(1), jacc(1), Antlr(1)

btyacc(1)

Nutzen Sie btyacc online über die Dienste von onworks.net