Development/KDevelop-PG-Qt Introduction (de): Difference between revisions

From KDE TechBase
No edit summary
(→‎Weblinks: projects.kde.org > quickgit)
 
(6 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{Template:I18n/Language Navigation Bar|Development/KDevelop-PG-Qt Introduction}}
 


KDevelop-PG-Qt ist der Parser-Generator aus KDevplatform. Er wird für einige KDevelop-Sprachunterstützungs-Plugins verwendet (Ruby, PHP, Java...).
KDevelop-PG-Qt ist der Parser-Generator aus KDevplatform. Er wird für einige KDevelop-Sprachunterstützungs-Plugins verwendet (Ruby, PHP, Java...).
Line 52: Line 52:


== Tokenizer mit KDevelop-PG-Qt ==
== Tokenizer mit KDevelop-PG-Qt ==
Siehe foolisp-Beispiel im Code.
KDev-PG-Qt kann einen Tokenizer generieren, dies erspart das Schreiben einer TokenStream-Klasse, die dann flex-code aufrufen muss o.ä. Siehe examples/foolisp im Repository für ein einfaches Beispiel.
'''TODO'''
'''TODO'''


Line 63: Line 63:


= Schreiben von .g-Dateien =
= Schreiben von .g-Dateien =
== Typ2-Grammatiken ==
== Kontextfreie Grammatiken ==
Die verwendeten Typ2-Grammatiken werdenso aufgebaut, das sich jeweils ein Nicht-Terminal (Symbol) aus weiteren Nicht-Terminalen und Terminalen (Tokens) zusammensetzt. Bei der Grundstruktur kann man sich an die Semantik der Sprache halten, allerdings wird man immer wieder ''kleine Helfer'' benötigen. Ein C++-Dokument besteht beispielsweise aus vielen Deklarationen. Klassen-Definitionen sind ein Beispiel. Diese bestehen wiederum aus dem Token ''CLASS'', einem Namen, dem Token ''{'', Klassen-Element-Deklarationen, dem Token ''}'' und dem Token '';''. ''Klassen-Element-Deklaration'' ist ein solcher Helfer. Kein normaler C++-Entwickler benutzt solch ein Wort, sie helfen jedoch die Struktur des Codes aufzuschlüsseln.
Die verwendeten kontextfreien Grammatiken werden so aufgebaut, das sich jeweils ein Nicht-Terminal (Symbol) aus weiteren Nicht-Terminalen und Terminalen (Tokens) zusammensetzt. Bei der Grundstruktur kann man sich an die Semantik der Sprache halten, allerdings wird man immer wieder ''kleine Helfer'' benötigen. Ein C++-Dokument besteht beispielsweise aus vielen Deklarationen. Klassen-Definitionen sind ein Beispiel. Diese bestehen wiederum aus dem Token ''CLASS'', einem Namen, dem Token ''{'', Klassen-Element-Deklarationen, dem Token ''}'' und dem Token '';''. ''Klassen-Element-Deklaration'' ist ein solcher Helfer. Kein normaler C++-Entwickler benutzt solch ein Wort, sie helfen jedoch die Struktur des Codes aufzuschlüsseln.
 
== Grundlegende Syntax ==
== Grundlegende Syntax ==
Nun kann man einmal versuchen solche Beschreibungen in der KDevelop-PG-Qt-Syntax zu fassen:
Nun kann man einmal versuchen solche Beschreibungen in der KDevelop-PG-Qt-Syntax zu fassen:
<code>
<syntaxhighlight lang="bash">
   class_declaration
   class_declaration
  | struct_declaration
  | struct_declaration
Line 76: Line 77:
  | extern_declaration
  | extern_declaration
-> declaration ;;
-> declaration ;;
</code>
</syntaxhighlight>
Das ''|''-Zeichen steht für ein ''oder''. Jede Regel endet mit zwei Semikola. Diese Unter-Deklarationen müssen nun wiederum definiert werden. Dabei werden Nicht-Terminale klein und Tokens groß geschrieben.
Das ''|''-Zeichen steht für ein ''oder''. Jede Regel endet mit zwei Semikola. Diese Unter-Deklarationen müssen nun wiederum definiert werden. Dabei werden Nicht-Terminale klein und Tokens groß geschrieben.
<code>
<syntaxhighlight lang="bash">
   CLASS IDENTIFIER SEMICOLON
   CLASS IDENTIFIER SEMICOLON
  | CLASS IDENTIFIER LBRACE class_declaration* RBRACE SEMICOLON
  | CLASS IDENTIFIER LBRACE class_declaration* RBRACE SEMICOLON
-> class_declaration ;;
-> class_declaration ;;
</code>
</syntaxhighlight>
Ein neues Zeichen ist aufgetaucht: Der Stern bedeutet wie in regulären Ausdrücken, dass etwas 0-unendlich mal auftreten darf. Das Zeichen ''0'' steht für eine leere Token-Folge. Klammerung ist beliebig möglich.
Ein neues Zeichen ist aufgetaucht: Der Stern bedeutet wie in regulären Ausdrücken, dass etwas 0-unendlich mal auftreten darf. Das Zeichen ''0'' steht für eine leere Token-Folge. Klammerung ist beliebig möglich.
== Speicherung im Parsetree ==
== Speicherung im Parsetree ==
Mit dieser einfachen Regel-Deklaration wird zwar die Token-Folge geparst, jedoch wird kein Parsetree gespeichert. Dies lässt sich leicht ändern:
Mit dieser einfachen Regel-Deklaration wird zwar die Token-Folge geparst, jedoch wird kein Parsetree gespeichert. Dies lässt sich leicht ändern:
<code>
<syntaxhighlight lang="bash">
   class_declaration=class_declaration
   class_declaration=class_declaration
  | struct_declaration=struct_declaration
  | struct_declaration=struct_declaration
Line 95: Line 96:
  | extern_declaration=extern_declaration
  | extern_declaration=extern_declaration
-> declaration ;;
-> declaration ;;
</code>
</syntaxhighlight>
In der Klasse DeclarationAst werden nun Zeiger auf Class_declarationAst, Struct_declarationAst etc. angelegt. Beim Parsen werden diese Zeiger belegt. (in diesem Fall natürlich immer nur einer, die anderen werden auf NULL gesetzt)
In der Klasse DeclarationAst werden nun Zeiger auf Class_declarationAst, Struct_declarationAst etc. angelegt. Beim Parsen werden diese Zeiger belegt. (in diesem Fall natürlich immer nur einer, die anderen werden auf NULL gesetzt)
Möchte man Wiederholungen speichern, so wird auch noch eine Listenstruktur zur Verfügung gestellt, hierfür muss dem Variablennamen eine Raute (''#'') vorangestellt werden:
Möchte man Wiederholungen speichern, so wird auch noch eine Listenstruktur zur Verfügung gestellt, hierfür muss dem Variablennamen eine Raute (''#'') vorangestellt werden:
<code>
<syntaxhighlight lang="bash">
   CLASS IDENTIFIER SEMICOLON
   CLASS IDENTIFIER SEMICOLON
  | CLASS IDENTIFIER LBRACE (#class_declaration=class_declaration)* RBRACE SEMICOLON
  | CLASS IDENTIFIER LBRACE (#class_declaration=class_declaration)* RBRACE SEMICOLON
-> class_declaration ;;
-> class_declaration ;;
</code>
</syntaxhighlight>
Variablen können mehrfach benutzt werden:
Variablen können mehrfach benutzt werden:
<code>
<syntaxhighlight lang="bash">
   #one=one (#one=one)*
   #one=one (#one=one)*
-> one_or_more ;;
-> one_or_more ;;
</code>
</syntaxhighlight>
Unabhängig davon, wo die Variable #one benutzt wird: Ein Element wird an die selbe Liste angehängt.
Unabhängig davon, wo die Variable #one benutzt wird: Ein Element wird an die selbe Liste angehängt.
== Angabe der Tokens ==
== Angabe der Tokens ==
An einer Stelle müssen alle Tokens aufgezählt werden. Aus ihnen wird ein enum in parser.h erstellt. Der zusätzlich anzugebende Name wird zur Anzeige von Fehlermeldungen u.ä. verwendet:
An einer Stelle müssen alle Tokens aufgezählt werden. Aus ihnen wird ein enum in parser.h erstellt. Der zusätzlich anzugebende Name wird zur Anzeige von Fehlermeldungen u.ä. verwendet:
<code>
<syntaxhighlight lang="bash">
%token T1 ("T1-Name"), T2 ("T2-Name"), COMMA (";"), SEMICOLON (";") ;;
%token T1 ("T1-Name"), T2 ("T2-Name"), COMMA (";"), SEMICOLON (";") ;;
</code>
</syntaxhighlight>
== Spezielle Zeichen... ==
== Spezielle Zeichen... ==
=== ...für Regeln ===
=== ...für Regeln ===
Einige weitere Zeichen erleichtern die Arbeit:
Einige weitere Zeichen erleichtern die Arbeit:
==== Positive Kleenesche Hülle ====
==== Positive Kleenesche Hülle ====
<code>
<syntaxhighlight lang="bash">
   (#one=one)+
   (#one=one)+
-> one_or_more ;;
-> one_or_more ;;
</code>
</syntaxhighlight>
...entspricht genau obigem Beispiel.<br>
...entspricht genau obigem Beispiel.<br>


Line 128: Line 129:
==== Separierte Auflistung ====
==== Separierte Auflistung ====
Ebenfalls häufig verwendet ist das '@':
Ebenfalls häufig verwendet ist das '@':
<code>
<syntaxhighlight lang="bash">
   #item=item @ COMMA
   #item=item @ COMMA
-> comma_separated_list ;;
-> comma_separated_list ;;
</code>
</syntaxhighlight>
...sorgt genau dafür, dass zwischen den Items ein Komma stehen muss.<br>
...sorgt genau dafür, dass zwischen den Items ein Komma stehen muss.<br>


==== Optionales Parsing ====
==== Optionales Parsing ====
<code>
<syntaxhighlight lang="bash">
   ?item=item
   ?item=item
-> optional_item ;;
-> optional_item ;;
</code>
</syntaxhighlight>
...entspricht genau:
...entspricht genau:
<code>
<syntaxhighlight lang="bash">
   (item=item | 0)
   (item=item | 0)
-> optional_item ;;
-> optional_item ;;
</code><br>
</syntaxhighlight><br>
Vorsicht: ''(0|x)'' ist nichts anderes als ''0''!
Vorsicht: ''(0|x)'' ist nichts anderes als ''0''!


Line 169: Line 170:
*Zusätzliche Prüfungen, die sich am schnellsten in C++ durchführen lassen
*Zusätzliche Prüfungen, die sich am schnellsten in C++ durchführen lassen


<code>
<syntaxhighlight lang="bash">
[:
[:
// Code
// Code
:]
:]
</code>
</syntaxhighlight>
...fügt der Datei parser.cpp den angegebenen Code hinzu.
...fügt der Datei parser.cpp den angegebenen Code hinzu.
Wird diese Konstrukt innerhalb einer Regel verwendet, so wird der Code an der entsprechenden Stelle des Parsens eingefügt.
Wird diese Konstrukt innerhalb einer Regel verwendet, so wird der Code an der entsprechenden Stelle des Parsens eingefügt.
<code>
<syntaxhighlight lang="bash">
?[:
?[:
// Boolescher Ausdruck
// Boolescher Ausdruck
:]
:]
</code>
</syntaxhighlight>
...sorgt dafür, dass der Boolesche Ausdruck Voraussetzung für die aktuelle Regel wird. Innerhalb dieser Code-Segmente kann man auf die aktuell bearbeitete Node über die Variable ''yynode'' des Typs 'XYZAst**', auf das aktuelle Token über die Variable ''yytoken'' und auf die aktuelle Position im Tokenstream über ''tokenStream->index()'' zugreifen.
...sorgt dafür, dass der Boolesche Ausdruck Voraussetzung für die aktuelle Regel wird. Innerhalb dieser Code-Segmente kann man auf die aktuell bearbeitete Node über die Variable ''yynode'' des Typs 'XYZAst**', auf das aktuelle Token über die Variable ''yytoken'' und auf die aktuelle Position im Tokenstream über ''tokenStream->index()'' zugreifen.
= Konflikte=
= Konflikte=
Erste Versuche, so einen Parser zu erzeugen, werden wahrscheinlich fehlschlagen. Es wird ein Konflikt angezeigt und das Parsen funktioniert nicht richtig.
Erste Versuche, so einen Parser zu erzeugen, werden wahrscheinlich fehlschlagen. Es wird ein Konflikt angezeigt und das Parsen funktioniert nicht richtig.
Ein Beispiel für einen sogenannten FIRST/FIRST-Konflikt:
Ein Beispiel für einen sogenannten FIRST/FIRST-Konflikt:
<code>
<syntaxhighlight lang="bash">
   CLASS IDENTIFIER SEMICOLON
   CLASS IDENTIFIER SEMICOLON
-> class_declaration ;;
-> class_declaration ;;
Line 195: Line 196:
  | class_definition
  | class_definition
-> class_expression ;;
-> class_expression ;;
</code>
</syntaxhighlight>
Ausgabe:
Ausgabe:
<pre>
<pre>
Line 204: Line 205:
== Backtracking ==
== Backtracking ==
Wer solche Grammatiken nur von der Theorie her kennt, den wird diese Vorgehensweise vielleicht verwundern. Denn in der BNF wäre so eine Angabe beispielsweise vollkommen in Ordnung. Der Parser könnte zum Beispiel zurück springen und die nächste Alternative ausprobieren. Dies ist jedoch nicht immer erforderlich und für eine gesteigerte Effizienz wird nach Möglichkeit darauf verzichtet. Es gibt jedoch eine Möglichkeit, die ganzen Konflikte zu umgehen, denn KDevelop-PG-Qt unterstützt besagtes Backtracking:
Wer solche Grammatiken nur von der Theorie her kennt, den wird diese Vorgehensweise vielleicht verwundern. Denn in der BNF wäre so eine Angabe beispielsweise vollkommen in Ordnung. Der Parser könnte zum Beispiel zurück springen und die nächste Alternative ausprobieren. Dies ist jedoch nicht immer erforderlich und für eine gesteigerte Effizienz wird nach Möglichkeit darauf verzichtet. Es gibt jedoch eine Möglichkeit, die ganzen Konflikte zu umgehen, denn KDevelop-PG-Qt unterstützt besagtes Backtracking:
<code>
<syntaxhighlight lang="bash">
   try/rollback(class_declaration)
   try/rollback(class_declaration)
       catch(class_definition)
       catch(class_definition)
-> class_expression ;;
-> class_expression ;;
</code>
</syntaxhighlight>
So lassen sich alle Konflikte auflösen, dieses Vorgehensweise geht allerdings auf Kosten der Effizienz. Außerdem sollte die Reihenfolge beachtet werden (zur Effizienzsteigerung und zum korrekten Aufbau des Parsetrees).
So lassen sich alle Konflikte auflösen, dieses Vorgehensweise geht allerdings auf Kosten der Effizienz. Außerdem sollte die Reihenfolge beachtet werden (zur Effizienzsteigerung und zum korrekten Aufbau des Parsetrees).
== Look ahead ==
== Look ahead ==
KDevelop-PG-Qt bietet eine Möglichkeit an, andere Stellen des Token-Streams zu berücksichtigen, ohne gleich in eine tiefe Backtracking-Struktur einzutauchen. Hierfür gibt es eine Funktion LA(qint64). LA(1) gibt das aktuelle Token zurück, LA(2) das nächste, LA(0) das vorherige usw. (die seltsame Indizierung wurde von der Bezeichnung verschiedener Parser-Typen übernommen)
KDevelop-PG-Qt bietet eine Möglichkeit an, andere Stellen des Token-Streams zu berücksichtigen, ohne gleich in eine tiefe Backtracking-Struktur einzutauchen. Hierfür gibt es eine Funktion LA(qint64). LA(1) gibt das aktuelle Token zurück, LA(2) das nächste, LA(0) das vorherige usw. (die seltsame Indizierung wurde von der Bezeichnung verschiedener Parser-Typen übernommen)
<code>
<syntaxhighlight lang="bash">
   (?[: LA(2) == Token_LBRACE :] class_definition)
   (?[: LA(2) == Token_LBRACE :] class_definition)
  | class_declaration
  | class_declaration
-> class_expression
-> class_expression
</code>
</syntaxhighlight>
Es wird weiterhin ein Konflikt angezeigt, dieser wurde so jedoch manuell gelöst. Man sollte diese manuelle Auflösung in einem Kommentar erwähnen, bevor man ihn später als Fehlerquelle ansieht.
Es wird weiterhin ein Konflikt angezeigt, dieser wurde so jedoch manuell gelöst. Man sollte diese manuelle Auflösung in einem Kommentar erwähnen, bevor man ihn später als Fehlerquelle ansieht.
== Elegante Lösungen ==
== Elegante Lösungen ==
In sehr vielen Fällen finden sich elegantere Lösungen. So auch in unserem Beispiel:
In sehr vielen Fällen finden sich elegantere Lösungen. So auch in unserem Beispiel:
<code>
<syntaxhighlight lang="bash">
   LBRACE class_content RBRACE
   LBRACE class_content RBRACE
-> class_definition ;;
-> class_definition ;;
Line 226: Line 227:
   CLASS IDENTIFIER (class_definition | 0) SEMICOLON
   CLASS IDENTIFIER (class_definition | 0) SEMICOLON
-> class_expression ;;
-> class_expression ;;
</code>
</syntaxhighlight>
Nun gibt es keine Konflikte mehr.
Nun gibt es keine Konflikte mehr.
== FIRST/FOLLOW-Konflikte ==
== FIRST/FOLLOW-Konflikte ==
Von FIRST/FOLLOW-Konflikten spricht man dann, wenn es uneindeutig ist, wo ein Symbol endet und wo das Eltern-Symbol forgesetzt wird. Ein stupides Beispiel:
Von FIRST/FOLLOW-Konflikten spricht man dann, wenn es uneindeutig ist, wo ein Symbol endet und wo das Eltern-Symbol forgesetzt wird. Ein stupides Beispiel:
<code>
<syntaxhighlight lang="bash">
   item*
   item*
-> item_list ;;
-> item_list ;;
Line 236: Line 237:
   item_list item*
   item_list item*
-> items ;;
-> items ;;
</code>
</syntaxhighlight>
Die Uneindeutigkeit ist offensichtlich. ''try/rollback'' hilft bei ernstzunehmenden Problemen (der Parser funktioniert nicht), oft lassen sich diese Konflikte allerdings auch ignorieren, jedoch sollte man sich darüber im klaren sein, dass der Parser ''greedy'' ist, also die ''item_list'' den größtmöglichen Platz einnehmen wird. Führt dies zu einer Unterteilung, die später zu Widersprüchen führt, helfen nur ''try/rollback'', Überprüfungen mit manuellem Code oder eine Umstrukturierung.
Die Uneindeutigkeit ist offensichtlich. ''try/rollback'' hilft bei ernstzunehmenden Problemen (der Parser funktioniert nicht), oft lassen sich diese Konflikte allerdings auch ignorieren, jedoch sollte man sich darüber im klaren sein, dass der Parser ''greedy'' ist, also die ''item_list'' den größtmöglichen Platz einnehmen wird. Führt dies zu einer Unterteilung, die später zu Widersprüchen führt, helfen nur ''try/rollback'', Überprüfungen mit manuellem Code oder eine Umstrukturierung.
=== Unterbrechung von Wiederholungen ===
=== Unterbrechung von Wiederholungen ===
Manchmal ist die Greedy-Verhaltensweise unerwünscht. Bei Widerholungen ist die Unterbrechung mit manuell geschriebenem Code möglich. Dieses Beispiel einer Deklaration eines Array mit fester Größe zeigt, wie eine Wiederholung beschränkt werden kann:
Manchmal ist die Greedy-Verhaltensweise unerwünscht. Bei Widerholungen ist die Unterbrechung mit manuell geschriebenem Code möglich. Dieses Beispiel einer Deklaration eines Array mit fester Größe zeigt, wie eine Wiederholung beschränkt werden kann:
<code>
<syntaxhighlight lang="bash">
   typed_identifier=typed_identifier LBRACKET UNSIGNED_INTEGER
   typed_identifier=typed_identifier LBRACKET UNSIGNED_INTEGER
   [: count = static_cast<MyTokenStream*>(token)->strForCurrentToken().toUInt(); :]
   [: count = static_cast<MyTokenStream*>(token)->strForCurrentToken().toUInt(); :]
Line 247: Line 248:
   RBRACE SEMICOLON
   RBRACE SEMICOLON
-> initialized_fixed_array [ temporary variable count: uint; ];;
-> initialized_fixed_array [ temporary variable count: uint; ];;
</code>
</syntaxhighlight>
Über den Code ''return false'' ist ein vorzeitiger Abbruch der momentanen Regelauswertung möglich. Über ''return true'' eine vorzeitige Rückkehr.
Über den Code ''return false'' ist ein vorzeitiger Abbruch der momentanen Regelauswertung möglich. Über ''return true'' eine vorzeitige Rückkehr.
== try/recover ==
== try/recover ==
<code>
<syntaxhighlight lang="bash">
   try/recover(expression)
   try/recover(expression)
-> symbol ;;
-> symbol ;;
</code>
</syntaxhighlight>
Dies entspricht in etwa:
Dies entspricht in etwa:
<code>
<syntaxhighlight lang="bash">
   [: ParserState *state = copyCurrentState(); :]
   [: ParserState *state = copyCurrentState(); :]
   try/rollback(expression)
   try/rollback(expression)
   catch( [: restoreState(state); :] )
   catch( [: restoreState(state); :] )
-> symbol ;;
-> symbol ;;
</code>
</syntaxhighlight>
Das heißt, man muss die Element-Funktionen copyCurrentState und restoreState sowie einen Typen ParserState definieren. Die Deklaration der beiden Funktionen erfolgt automatisch bei der Verwendung von ''try/recover''. Dieses Verfahren ist anscheinend sinnvoll, wenn der Parsing-Prozess unter Zuhilfenahme von zusätzlichen Zuständen durchgeführt wird. Der Java-Parser benutzt das Feature sehr ausgiebig. Ich bin jedoch in diesem Verfahren nicht firm und durchschaue nicht ganz das Ziel bei dieser Vorgehensweise. Für zusätzliche Erklärung (oder Korrekturen) wäre ich sehr dankbar.
Das heißt, man muss die Element-Funktionen copyCurrentState und restoreState sowie einen Typen ParserState definieren. Die Deklaration der beiden Funktionen erfolgt automatisch bei der Verwendung von ''try/recover''. Dieses Verfahren ist anscheinend sinnvoll, wenn der Parsing-Prozess unter Zuhilfenahme von zusätzlichen Zuständen durchgeführt wird. Der Java-Parser benutzt das Feature sehr ausgiebig. Ich bin jedoch in diesem Verfahren nicht firm und durchschaue nicht ganz das Ziel bei dieser Vorgehensweise. Für zusätzliche Erklärung (oder Korrekturen) wäre ich sehr dankbar.


= Feineinstellungen für manuellen Code =
= Feineinstellungen für manuellen Code =
<code>
<syntaxhighlight lang="bash">
%parserclass ( [private|protected|public] declaration)
%parserclass ( [private|protected|public] declaration)
[:
[:
// Code
// Code
:]
:]
</code>
</syntaxhighlight>
...fügt der Parser-Klasse in der Datei parser.h im entsprechenden Abschnitt Code hinzu.
...fügt der Parser-Klasse in der Datei parser.h im entsprechenden Abschnitt Code hinzu.
Wer Elemente hinzufügt, braucht auch Zugriff auf Konstruktor und Destruktor:
Wer Elemente hinzufügt, braucht auch Zugriff auf Konstruktor und Destruktor:
<code>
<syntaxhighlight lang="bash">
%parserclass ( [constructor|desctructor] )
%parserclass ( [constructor|desctructor] )
[:
[:
// Code
// Code
:]
:]
</code>
</syntaxhighlight>
...fügt den entsprechenden Funktionen den Code hinzu.
...fügt den entsprechenden Funktionen den Code hinzu.
Ein Code-Block am Ende der Grammatik-Datei wird in der Implementierungsdatei des Parsers eingefügt, ein Code-Block am Anfang der Datei landet dagegen in der Deklaration der AST-Knoten.
Ein Code-Block am Ende der Grammatik-Datei wird in der Implementierungsdatei des Parsers eingefügt, ein Code-Block am Anfang der Datei landet dagegen in der Deklaration der AST-Knoten.
Um in der Auswertung einer Regel eine lokale Variable zu definieren, gibt es folgede Syntax:
Um in der Auswertung einer Regel eine lokale Variable zu definieren, gibt es folgede Syntax:
<code>
<syntaxhighlight lang="bash">
   ...
   ...
-> class_member [:
-> class_member [:
   enum { A_PUBLIC, A_PROTECTED, A_PRIVATE } access;
   enum { A_PUBLIC, A_PROTECTED, A_PRIVATE } access;
:];;
:];;
</code>
</syntaxhighlight>
Hierdurch wird jedoch lediglich eine lokale Variable eingeführt, die innerhalb der Regel verwendet wird.
Hierdurch wird jedoch lediglich eine lokale Variable eingeführt, die innerhalb der Regel verwendet wird.
Möchte man dagegen im Parsetree zusätzliche Informationen speichern, so benötigt man diese Syntax:
Möchte man dagegen im Parsetree zusätzliche Informationen speichern, so benötigt man diese Syntax:
<code>
<syntaxhighlight lang="bash">
[
[
   member|temporary variable name: type
   member|temporary variable name: type
]
]
</code>
</syntaxhighlight>
Korrekt wäre folglich:
Korrekt wäre folglich:
<code>
<syntaxhighlight lang="bash">
   ...
   ...
-> class_member [
-> class_member [
       member variable access : AccessType;
       member variable access : AccessType;
];;
];;
</code>
</syntaxhighlight>
Der ''AccessType'' muss dann an anderer Stelle definiert werden. Verwendet man statt ''member'' das Wort ''temporary'', so erhält man eine äquivalente Formulierung für obigen Code.
Der ''AccessType'' muss dann an anderer Stelle definiert werden. Verwendet man statt ''member'' das Wort ''temporary'', so erhält man eine äquivalente Formulierung für obigen Code.
<code>
<syntaxhighlight lang="bash">
%ast_extra_members
%ast_extra_members
[:
[:
// Code
// Code
:]
:]
</code>
</syntaxhighlight>
...fügt jeder Knoten-Klasse Code hinzu. (ast.h)
...fügt jeder Knoten-Klasse Code hinzu. (ast.h)
<code>
<syntaxhighlight lang="bash">
%ast_base non_terminal "ClassName"
%ast_base non_terminal "ClassName"
</code>
</syntaxhighlight>
...''ClassName'' wird als Basisklasse für ''Non_terminalAst'' verwendet.
...''ClassName'' wird als Basisklasse für ''Non_terminalAst'' verwendet.
<code>
<syntaxhighlight lang="bash">
%parser_base "ClassName"
%parser_base "ClassName"
</code>
</syntaxhighlight>
...''ClassName'' wird als Basisklasse für den Parser verwendet.
...''ClassName'' wird als Basisklasse für den Parser verwendet.
<code>
<syntaxhighlight lang="bash">
%ast_header "header.h"
%ast_header "header.h"
%parser_declaration_header "header.h"
%parser_declaration_header "header.h"
%parser_bits_header "header.h"
%parser_bits_header "header.h"
</code>
</syntaxhighlight>
...sorgt für eine Einbindung der betreffenden Header-Dateien in der jeweiligen Datei (ast.h, parser.h bzw. parser.cpp).
...sorgt für eine Einbindung der betreffenden Header-Dateien in der jeweiligen Datei (ast.h, parser.h bzw. parser.cpp).


Line 329: Line 330:


= Weblinks =
= Weblinks =
*[http://quickgit.kde.org/?p=kdevelop-pg-qt.git&a=blob&f=kdev-pg/kdev-pg-parser.yy] - Die KDevelop-PG-Qt-Syntax (Bison/Yacc-Datei, also als Grammatik)
*[http://quickgit.kde.org/?p=kdevelop-pg-qt.git&a=blob&f=kdev-pg/kdev-pg-parser.yy] Die KDevelop-PG-Qt-Syntax (Bison/Yacc-Datei, also als Grammatik)
*[https://projects.kde.org/projects/extragear/kdevelop/utilities/kdevelop-pg-qt] - Pojektseite auf projects.kde.org
*[https://quickgit.kde.org/?p=kdevelop-pg-qt.git] Pojektseite auf quickgit.kde.org
*[http://stud4.tuwien.ac.at/~e0127236/thesis/jpetso-javaparser.pdf] - KDevelop-PG-Qt anhand des Java-Parsers - Das Dokument erklärt sehr gut viele Konzepte. Die KDevelop-PG-Qt Syntax ist jedoch veraltet und die erwähnten Lücken im Parser-Generator sind mittlerweile behoben.
*[http://the-user.org/category/computing/kde/kdev-pg-qt] Einige Blog-Einträge von „The User“ zu KDevelop-PG-Qt (informativ zu neuen Features)
*[http://stud4.tuwien.ac.at/~e0127236/thesis/jpetso-javaparser.pdf] - KDevelop-PG-Qt anhand des Java-Parsers Das Dokument erklärt sehr gut viele Konzepte. Die KDevelop-PG-Qt Syntax ist jedoch veraltet und die erwähnten Lücken im Parser-Generator sind mittlerweile behoben.

Latest revision as of 23:39, 17 May 2016


KDevelop-PG-Qt ist der Parser-Generator aus KDevplatform. Er wird für einige KDevelop-Sprachunterstützungs-Plugins verwendet (Ruby, PHP, Java...).

Das Programm

Anwendung

Das Programm KDevelop-PG-Qt findet sich im git. Dort finden sich auch vier kleine Beispiele. Befehle, um das ganze herunterzuladen:

git clone git://anongit.kde.org/kdevelop-pg-qt.git
oder: git clone kde:kdevelop-pg-qt.git (wenn git mit kde:-präfix eingerichtet ist)

Das Programm verlangt eine .g-Datei als Eingabe:

./kdev-pg-qt --output=prefix syntax.g

Alle Dateien werden dann mit dem angegebenen Präfix erstellt und es gibt auch den namespace für den erzeugten Code an. Übrigens stellt Kate einfaches Syntax-Highlighting für die Grammatik-Dateien zur Verfügung.

Ausgabe

Das Programm gibt Informationen über sogenannte Konflikte aus und erzeugt mehrere Dateien (jeweils mit dem gewählten Präfix).

ast.h

Hier wird eine Datenstruktur definiert, in der der Parsetree gespeichert wird. Die Knoten des Baums sind alle structs mit dem Postfix Ast, die Zeiger auf die möglichen Unterelemente enthalten. (AST heißt übrigens abstract syntax tree)

parser.h und parser.cpp

Hier werden ein enum für die Tokens definiert und das eigentliche Parsen erledigt. Für jeden Nicht-Terminal existiert eine Funktion parseNicht_terminal_name. Die Parser-Klasse verlangt einen Tokenizer. Möchte man nun eine Token-Folge parsen, erzeugt man einen Pointer auf die Wurzel (z.B. DocumentAst*) und ruft parseDocument(&root) auf. Bei Erfolg wird in root der Parsetree abgelegt.

visitor.h und visitor.cpp

Diese beiden Dateien definieren eine abstrakte Basis-Klasse zur Traversierung über den Parsetree.

defaultvisitor.h und defaultvisitor.cpp

Die hier definierte Klasse ist eine Implementierung des visitors, die automatisch die Unterknoten eines Knotens besucht. Möchte man über den gesamten Parsetree traversieren, ist diese Klasse als Basisklasse gut geeignet.

CLI-Optionen

  • --namespace=namespace - Einen Namespace unabhängig vom Datei-Präfix festlegen (dann darf das Präfix auch / enthalten)
  • --no-ast - Die ast.h-Datei wird nicht erstellt, dazu später mehr
  • --debug-visitor - Code zur Ausgabe des Parse-Trees wird erzeugt
  • --serialize-visitor - Code zur Serialisierung über ein QIODevice wird erstellt
  • --terminals - Alle Terminale werden in eine Datei kdev-pg-terminals geschrieben
  • --symbols - Alle Nicht-Terminale werden in eine Datei kdev-pg-symbols geschrieben
  • --rules - Alle Regeln werden mit Informationen zum syntaktischen Zusammenhang (hilfreich zur Konflikt-Behebun) in eine Datei namens kdev-pg-rules geschrieben
  • --token-text - Eine Funktion zur Zuordnung einer Token-Nummer zu einem Token-Namen wird erstellt
  • --help - Eine Hilfe wird angezeigt

Tokenizer

Wie bereits kurz erwähnt erfordert KDevelop-PG-Qt einen Tokenizer. Entweder man lässt ihn sich von KDevelop-PG-Qt generieren, schreibt sich diesen selbst oder man verwendet ein externes Tool wie Flex.

Der Tokenizer sollte in der Regel solche oder ähnliche Aufgaben übernehmen:

  • Umwandlung von Schlüsselwörtern und Sonderzeichen mit besonderer Bedeutung in Tokens
  • Umwandlung von Literalen und Bezeichnern in Tokens
  • Herausstreichen von allem, was die Syntax nicht beeinflusst: Kommentare, unnötige Leerzeichen (natürlich nicht in Python) u.ä.
  • Handeln der Zeichen-Kodierung

Eben alles, was mit dem Tokenizer genau so einfach oder einfacher als mit der egtl. Grammatik gemacht werden kann.

Tokenizer mit KDevelop-PG-Qt

KDev-PG-Qt kann einen Tokenizer generieren, dies erspart das Schreiben einer TokenStream-Klasse, die dann flex-code aufrufen muss o.ä. Siehe examples/foolisp im Repository für ein einfaches Beispiel. TODO

Tokenizer mit flex

Mit den Beispielen sollte es kein Problem sein, sich solch einen Tokenizer zu konstruieren. Zwischen den meisten Sprachen unterscheidet sich die Syntax von Kommentaren, Literalen etc. nicht großartig, so dass hier wenig zu tun ist. Das Hinzufügen von einfachen Tokens ist eine Triviale Angelegenheit:

"special-command"    return Parser::Token_SPECIAL_COMMAND;

Das war es im wesentlichen, wenn man vorhandene Dateien (java.ll ist exzellent) als Vorlage verwendet.

Schreiben von .g-Dateien

Kontextfreie Grammatiken

Die verwendeten kontextfreien Grammatiken werden so aufgebaut, das sich jeweils ein Nicht-Terminal (Symbol) aus weiteren Nicht-Terminalen und Terminalen (Tokens) zusammensetzt. Bei der Grundstruktur kann man sich an die Semantik der Sprache halten, allerdings wird man immer wieder kleine Helfer benötigen. Ein C++-Dokument besteht beispielsweise aus vielen Deklarationen. Klassen-Definitionen sind ein Beispiel. Diese bestehen wiederum aus dem Token CLASS, einem Namen, dem Token {, Klassen-Element-Deklarationen, dem Token } und dem Token ;. Klassen-Element-Deklaration ist ein solcher Helfer. Kein normaler C++-Entwickler benutzt solch ein Wort, sie helfen jedoch die Struktur des Codes aufzuschlüsseln.

Grundlegende Syntax

Nun kann man einmal versuchen solche Beschreibungen in der KDevelop-PG-Qt-Syntax zu fassen:

   class_declaration
 | struct_declaration
 | function_declaration
 | union_declaration
 | namespace_declaration
 | typedef_declaration
 | extern_declaration
-> declaration ;;

Das |-Zeichen steht für ein oder. Jede Regel endet mit zwei Semikola. Diese Unter-Deklarationen müssen nun wiederum definiert werden. Dabei werden Nicht-Terminale klein und Tokens groß geschrieben.

   CLASS IDENTIFIER SEMICOLON
 | CLASS IDENTIFIER LBRACE class_declaration* RBRACE SEMICOLON
-> class_declaration ;;

Ein neues Zeichen ist aufgetaucht: Der Stern bedeutet wie in regulären Ausdrücken, dass etwas 0-unendlich mal auftreten darf. Das Zeichen 0 steht für eine leere Token-Folge. Klammerung ist beliebig möglich.

Speicherung im Parsetree

Mit dieser einfachen Regel-Deklaration wird zwar die Token-Folge geparst, jedoch wird kein Parsetree gespeichert. Dies lässt sich leicht ändern:

   class_declaration=class_declaration
 | struct_declaration=struct_declaration
 | function_declaration=function_declaration
 | union_declaration=union_declaration
 | namespace_declaration=namespace_declaration
 | typedef_declaration=typedef_declaration
 | extern_declaration=extern_declaration
-> declaration ;;

In der Klasse DeclarationAst werden nun Zeiger auf Class_declarationAst, Struct_declarationAst etc. angelegt. Beim Parsen werden diese Zeiger belegt. (in diesem Fall natürlich immer nur einer, die anderen werden auf NULL gesetzt) Möchte man Wiederholungen speichern, so wird auch noch eine Listenstruktur zur Verfügung gestellt, hierfür muss dem Variablennamen eine Raute (#) vorangestellt werden:

   CLASS IDENTIFIER SEMICOLON
 | CLASS IDENTIFIER LBRACE (#class_declaration=class_declaration)* RBRACE SEMICOLON
-> class_declaration ;;

Variablen können mehrfach benutzt werden:

   #one=one (#one=one)*
-> one_or_more ;;

Unabhängig davon, wo die Variable #one benutzt wird: Ein Element wird an die selbe Liste angehängt.

Angabe der Tokens

An einer Stelle müssen alle Tokens aufgezählt werden. Aus ihnen wird ein enum in parser.h erstellt. Der zusätzlich anzugebende Name wird zur Anzeige von Fehlermeldungen u.ä. verwendet:

%token T1 ("T1-Name"), T2 ("T2-Name"), COMMA (";"), SEMICOLON (";") ;;

Spezielle Zeichen...

...für Regeln

Einige weitere Zeichen erleichtern die Arbeit:

Positive Kleenesche Hülle

   (#one=one)+
-> one_or_more ;;

...entspricht genau obigem Beispiel.

Alle Symbole, die nicht auf der linken Seite einer Regel verwendet werden, sind Start-Symbole, sie sollten zum Starten des Parsing-Vorgangs verwendet werden.

Separierte Auflistung

Ebenfalls häufig verwendet ist das '@':

   #item=item @ COMMA
-> comma_separated_list ;;

...sorgt genau dafür, dass zwischen den Items ein Komma stehen muss.

Optionales Parsing

   ?item=item
-> optional_item ;;

...entspricht genau:

   (item=item | 0)
-> optional_item ;;


Vorsicht: (0|x) ist nichts anderes als 0!

Speichern des Unterbaums in lokalen Variablen

Verwendet man an Stelle des Gleichheitszeichens den Doppelpunkt (:), so wird der jeweils in der Folge generierte Unterbaum in einer lokalen Variable in der jeweiligen parse-Funktion gespeichert. Ein Zugriff auf den Unterbaum ist dann also nur während des Parse-Vorgangs genau in dieser Regel möglich.

TODO: need example

Inlining

Anstelle eines Namens kann auch ein Punkt (.) vor das Gleichheitszeichen gesetzt werden. Dann wird die AST-Klasse alle Elemente des Unterbaums erben und das Parsen der untergeordneten Regel wird in die aufrufende Funktion integriert. Ein Beispiel:

   op=PLUS | op=MUL | op=MOD
-> operator ;;
   val1=number .=op val2=number
-> simpleArithmetics ;;

SimpleArithmeticsAst wird anschließend über die Elemente val1, val2 (enthalten die Operanden) and op (enthält das Token für den Operator) verfügen. parseSimpleArithmetics wird sich den Aufruf von parseOperator sparen und den entsprechenden Code zum Parsen eines operator einbinden. Rekursives Inlining ist natürlich nicht möglich.

...für manuellen Code

Manchmal muss im Parser manuell geschriebener Code eingebaut werden. Beispiele sind:

  • Eine eigene Fehler-Behandlung
  • Erzeugen der Tokens (wenn man es nicht von außerhalb machen möchte)
  • Setzen bestimmter Variablen in den Nodes und dem Parser-Objekt (beispielsweise ließe sich bei einem C++-Parser zwischenspeichern, ob sich der Parser gerade in einem private, protected oder public Abschnitt befindet. In den Nodes der Elemente ließe sich eine solche Information speichern.
  • Zusätzliche Prüfungen, die sich am schnellsten in C++ durchführen lassen
[:
// Code
:]

...fügt der Datei parser.cpp den angegebenen Code hinzu. Wird diese Konstrukt innerhalb einer Regel verwendet, so wird der Code an der entsprechenden Stelle des Parsens eingefügt.

?[:
// Boolescher Ausdruck
:]

...sorgt dafür, dass der Boolesche Ausdruck Voraussetzung für die aktuelle Regel wird. Innerhalb dieser Code-Segmente kann man auf die aktuell bearbeitete Node über die Variable yynode des Typs 'XYZAst**', auf das aktuelle Token über die Variable yytoken und auf die aktuelle Position im Tokenstream über tokenStream->index() zugreifen.

Konflikte

Erste Versuche, so einen Parser zu erzeugen, werden wahrscheinlich fehlschlagen. Es wird ein Konflikt angezeigt und das Parsen funktioniert nicht richtig. Ein Beispiel für einen sogenannten FIRST/FIRST-Konflikt:

   CLASS IDENTIFIER SEMICOLON
-> class_declaration ;;

   CLASS IDENTIFIER LBRACE class_content RBRACE SEMICOLON
-> class_definition ;;

   class_declaration
 | class_definition
-> class_expression ;;

Ausgabe:

** WARNING found FIRST/FIRST conflict in  "class_exp"

Manchmal kann man mit Warnungen leben, deshalb wird Code erzeugt, eine class_expression wird jedoch nicht korrekt ausgewertet werden. Enthält der Code z.B. eine class_definition, so wird der Parser zuerst in die Funktion für die class_declaration hineinspringen, da er das führende Token CLASS identifiziert hat. Das Semikolon wird jedoch nicht gefunden und es kommt zu einer Fehlermeldung.

Backtracking

Wer solche Grammatiken nur von der Theorie her kennt, den wird diese Vorgehensweise vielleicht verwundern. Denn in der BNF wäre so eine Angabe beispielsweise vollkommen in Ordnung. Der Parser könnte zum Beispiel zurück springen und die nächste Alternative ausprobieren. Dies ist jedoch nicht immer erforderlich und für eine gesteigerte Effizienz wird nach Möglichkeit darauf verzichtet. Es gibt jedoch eine Möglichkeit, die ganzen Konflikte zu umgehen, denn KDevelop-PG-Qt unterstützt besagtes Backtracking:

   try/rollback(class_declaration)
      catch(class_definition)
-> class_expression ;;

So lassen sich alle Konflikte auflösen, dieses Vorgehensweise geht allerdings auf Kosten der Effizienz. Außerdem sollte die Reihenfolge beachtet werden (zur Effizienzsteigerung und zum korrekten Aufbau des Parsetrees).

Look ahead

KDevelop-PG-Qt bietet eine Möglichkeit an, andere Stellen des Token-Streams zu berücksichtigen, ohne gleich in eine tiefe Backtracking-Struktur einzutauchen. Hierfür gibt es eine Funktion LA(qint64). LA(1) gibt das aktuelle Token zurück, LA(2) das nächste, LA(0) das vorherige usw. (die seltsame Indizierung wurde von der Bezeichnung verschiedener Parser-Typen übernommen)

   (?[: LA(2) == Token_LBRACE :] class_definition)
 | class_declaration
-> class_expression

Es wird weiterhin ein Konflikt angezeigt, dieser wurde so jedoch manuell gelöst. Man sollte diese manuelle Auflösung in einem Kommentar erwähnen, bevor man ihn später als Fehlerquelle ansieht.

Elegante Lösungen

In sehr vielen Fällen finden sich elegantere Lösungen. So auch in unserem Beispiel:

   LBRACE class_content RBRACE
-> class_definition ;;

   CLASS IDENTIFIER (class_definition | 0) SEMICOLON
-> class_expression ;;

Nun gibt es keine Konflikte mehr.

FIRST/FOLLOW-Konflikte

Von FIRST/FOLLOW-Konflikten spricht man dann, wenn es uneindeutig ist, wo ein Symbol endet und wo das Eltern-Symbol forgesetzt wird. Ein stupides Beispiel:

   item*
-> item_list ;;

   item_list item*
-> items ;;

Die Uneindeutigkeit ist offensichtlich. try/rollback hilft bei ernstzunehmenden Problemen (der Parser funktioniert nicht), oft lassen sich diese Konflikte allerdings auch ignorieren, jedoch sollte man sich darüber im klaren sein, dass der Parser greedy ist, also die item_list den größtmöglichen Platz einnehmen wird. Führt dies zu einer Unterteilung, die später zu Widersprüchen führt, helfen nur try/rollback, Überprüfungen mit manuellem Code oder eine Umstrukturierung.

Unterbrechung von Wiederholungen

Manchmal ist die Greedy-Verhaltensweise unerwünscht. Bei Widerholungen ist die Unterbrechung mit manuell geschriebenem Code möglich. Dieses Beispiel einer Deklaration eines Array mit fester Größe zeigt, wie eine Wiederholung beschränkt werden kann:

   typed_identifier=typed_identifier LBRACKET UNSIGNED_INTEGER
   [: count = static_cast<MyTokenStream*>(token)->strForCurrentToken().toUInt(); :]
   RBRACKET EQUAL LBRACE
   (#expression=expression [: if(--count == 0) break; :] @ COMMA) ?[: count == 0 :]
   RBRACE SEMICOLON
-> initialized_fixed_array [ temporary variable count: uint; ];;

Über den Code return false ist ein vorzeitiger Abbruch der momentanen Regelauswertung möglich. Über return true eine vorzeitige Rückkehr.

try/recover

   try/recover(expression)
-> symbol ;;

Dies entspricht in etwa:

   [: ParserState *state = copyCurrentState(); :]
   try/rollback(expression)
   catch( [: restoreState(state); :] )
-> symbol ;;

Das heißt, man muss die Element-Funktionen copyCurrentState und restoreState sowie einen Typen ParserState definieren. Die Deklaration der beiden Funktionen erfolgt automatisch bei der Verwendung von try/recover. Dieses Verfahren ist anscheinend sinnvoll, wenn der Parsing-Prozess unter Zuhilfenahme von zusätzlichen Zuständen durchgeführt wird. Der Java-Parser benutzt das Feature sehr ausgiebig. Ich bin jedoch in diesem Verfahren nicht firm und durchschaue nicht ganz das Ziel bei dieser Vorgehensweise. Für zusätzliche Erklärung (oder Korrekturen) wäre ich sehr dankbar.

Feineinstellungen für manuellen Code

%parserclass ( [private|protected|public] declaration)
[:
// Code
:]

...fügt der Parser-Klasse in der Datei parser.h im entsprechenden Abschnitt Code hinzu. Wer Elemente hinzufügt, braucht auch Zugriff auf Konstruktor und Destruktor:

%parserclass ( [constructor|desctructor] )
[:
// Code
:]

...fügt den entsprechenden Funktionen den Code hinzu. Ein Code-Block am Ende der Grammatik-Datei wird in der Implementierungsdatei des Parsers eingefügt, ein Code-Block am Anfang der Datei landet dagegen in der Deklaration der AST-Knoten. Um in der Auswertung einer Regel eine lokale Variable zu definieren, gibt es folgede Syntax:

   ...
-> class_member [:
   enum { A_PUBLIC, A_PROTECTED, A_PRIVATE } access;
:];;

Hierdurch wird jedoch lediglich eine lokale Variable eingeführt, die innerhalb der Regel verwendet wird. Möchte man dagegen im Parsetree zusätzliche Informationen speichern, so benötigt man diese Syntax:

[
   member|temporary variable name: type
]

Korrekt wäre folglich:

   ...
-> class_member [
      member variable access : AccessType;
];;

Der AccessType muss dann an anderer Stelle definiert werden. Verwendet man statt member das Wort temporary, so erhält man eine äquivalente Formulierung für obigen Code.

%ast_extra_members
[:
// Code
:]

...fügt jeder Knoten-Klasse Code hinzu. (ast.h)

%ast_base non_terminal "ClassName"

...ClassName wird als Basisklasse für Non_terminalAst verwendet.

%parser_base "ClassName"

...ClassName wird als Basisklasse für den Parser verwendet.

%ast_header "header.h"
%parser_declaration_header "header.h"
%parser_bits_header "header.h"

...sorgt für eine Einbindung der betreffenden Header-Dateien in der jeweiligen Datei (ast.h, parser.h bzw. parser.cpp).

Auswertung arithmetischer Ausdrücke

TODO

Weblinks

  • [1] – Die KDevelop-PG-Qt-Syntax (Bison/Yacc-Datei, also als Grammatik)
  • [2] – Pojektseite auf quickgit.kde.org
  • [3] Einige Blog-Einträge von „The User“ zu KDevelop-PG-Qt (informativ zu neuen Features)
  • [4] - KDevelop-PG-Qt anhand des Java-Parsers – Das Dokument erklärt sehr gut viele Konzepte. Die KDevelop-PG-Qt Syntax ist jedoch veraltet und die erwähnten Lücken im Parser-Generator sind mittlerweile behoben.