Class ShiftReduceParser

java.lang.Object
  |
  +--ShiftReduceParser

public class ShiftReduceParser

extends java.lang.Object

Die Klasse ShiftReduceParser definiert die Parser-Komponente im Projekt. Während die Speicherung und Generierung der linguistischen Daten Objekten der Klasse 'LingDaten' obliegt, ist ein Parser ein aktives Objekt, das die linguistischen Daten nutzt, um eine Satzanalyse durchzuführen.

Der Haupteinstieg des Parsers ist die Methode 'parse'. Sie führt die eigentliche Satzanalyse durch. Sie ist so designt (und implementiert), dass sie bei jedem Aufruf genau eine Aktion durchführt und dann zum Aufrufer zurückkehrt. Das ermöglicht eine schrittweise Satzanalyse am Bildschirm mitzuverfolgen.

Damit die 'parse'-Methode schrittweise arbeiten kann, wird der aktuelle Parser-Zustand in einer internen Datenstruktur vom Typ (Klasse) Parser-Zustand gehalten.

Der Parser ermöglicht die Auflösung von Konflikten verschiedenen Typs. Konflikttypen sind:

• Konflikt mehrerer möglichen lexikalischen Kategorien eines Eingabewortes
• Shift-Shift-Konflikt
• Shift-Reduce-Konflikt
• Goto-Goto-Konflikt

Die Konflikte sind bereits in der Aktions- bzw. Sprungtabelle beschrieben, indem dort in einem Feld mehrere Aktionen eingetragen sind. Der Parser geht mit solchen Konflikten um, indem er den aktuellen Parser-Zustand auf den Stack legt. Führt das Parsen in eine Sackgasse, wird sukzessive der zuletzt gespeicherte Parser-Zustand vom Stack geholt und damit weiter gearbeitet. Dies ermöglicht auch das Auffinden mehrerer Lösungswege.

Die Klasse ShiftReduceParser ist eine der beiden Hauptklassen des Projektes (die andere ist LingDaten).

See Also:

LingDaten, ParserZustand, parse()

Field Summary

private boolean	accepted Erfolgsergebnis: wird bei accept gesetzt, kann aber durch Backtracking auch wieder zurückgesetzt werden.
private ActionGotoTabelle	actgototab Referenz auf das Tabellenmodell der Bildschirmtabelle, in der die Aktions- und Sprungtabelle dargestellt werden.
private int	aktionszaehler Bei mehreren möglichen Aktionen, die im aktuellen Zustand mit dem aktuellen Eingabesymbol möglich sind (mehrere Aktionen im Feld der Aktions- bzw.
private int	aktuellerZustand Zeigt die Nummer des aktuellen Zustands in der Aktions- bzw.
private Arbeitsbereich	arbeitsbereich Referenz auf den Arbeitsbereich, in dem die Parse-Ergebnisse und Zwischenergebnisse abgelegt werden.
private boolean	gotoAusfuehren Zwischenergebnisse und Fehler können hier protokolliert werden.
private java.lang.String[][]	kategorie Die Kategorien der Eingabewörter wird original im Parserobjekt abgelegt.
private int	kategorienzaehler Bei mehreren möglichen Kategorien eines Eingabewortes zeigt dieses Attribut die aktuelle Kategorie an.
private LingDaten	lingdat Referenz auf die linguistischen Daten, die die zur Analyse wichtige Aktions- und Sprungtabelle vorhält.
java.lang.String	parseErgebnis Zwischenergebnisse und Fehler können hier protokolliert werden.
private boolean	parserLaeuft Zeigt an, ob der Parser neu gestartet wurde oder bereits im laufenden Zustand ist.
private java.util.Stack	parsestack Stack, auf dem Parser-Zustände (Objekte vom Typ (Klasse) ParserZustand) abgelegt werden.
private int	poseingabe Zeigt auf das letzte bereits gelesene Eingabesymbol.
private int	reduceRegelnr Die Nummer der Regel der Grammatik, nach der das letzte Reduce stattgefunden hat, ist Teil des Parser-Zustands.
private java.lang.String[]	satz Referenz auf den formatierten Satz, als Teil der linguistischen Daten.

Constructor Summary

ShiftReduceParser(LingDaten lidat, Arbeitsbereich arbbereich, ActionGotoTabelle pactgototab)
Dieser Konstruktor erzeugt ein neues Parserobjekt.

Method Summary

private void	backtracke() Diese Methode ist das Gegenstück zur Methode 'zustandAufStack'.
static java.lang.String[]	bestimmeKategorie(java.lang.String symbol, LingDaten lingdat) Kategorien eines Wortes im Eingabesatz bestimmen und als Liste von Kategorien zurückgeben.
private java.lang.String	eingabeOk() erzeugt eine Protokollmeldung (Erfolgsmeldung)
private void	fuehreAcceptDurch() Wird aufgerufen, wenn der Parser als aktuelle Aktion in der Tabelle ein 'acc' findet (Aufruf in der Methode 'parse').
private void	fuehreGotoDurch(java.lang.Integer regelnummer, ArbeitsbereichZeile neueZeile) Wird aufgerufen, wenn der Parser als aktuelle Aktion in der Tabelle ein 'go' findet (Aufruf in der Methode 'fuehreReduceDurch').
private void	fuehreReduceDurch(java.lang.String aktionssymbol) Wird aufgerufen, wenn der Parser als aktuelle Aktion in der Tabelle ein 're' findet (Aufruf in der Methode 'parse').
private void	fuehreShiftDurch(java.lang.String aktionssymbol) Wird aufgerufen, wenn der Parser als aktuelle Aktion in der Tabelle ein 'sh' findet (Aufruf in der Methode 'parse').
void	parse() Aufruf des Parsers.
private void	pruefeAlternativeEingabekategorien() Hier wird geprüft, ob das aktuelle Eingabewort auch alternative Eingabekategorien besitzt, und falls ja, wird die nächste alternative Eingabekategorie auf den Stack gelegt (Methode 'zustandAufStack').
void	raeumeAuf() Diese Methode kann aufgerufen werden, wenn der Parse-Vorgang beendet oder abgebrochen werden soll.
private java.lang.String	unerwarteteEingabe(int poseingabe) erzeugt eine Protokollmeldung (Fehler unerwartete Eingabe)
private void	zustandAufStack(int pkategorienzaehler, int paktionszaehler, boolean gotoAusfuehren, int reduceRegelnr, ArbeitsbereichZeile pzeile) Wenn es in der aktuellen Parse-Situation mehrere Alternativen (= Konflikte) gibt, muss die nächste mögliche Alternative auf den Stack gebracht werden.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

lingdat

private LingDaten lingdat

Referenz auf die linguistischen Daten, die die zur Analyse wichtige Aktions- und Sprungtabelle vorhält. Der Parser benötigt nur die Tabellen; auf die Zustandsliste greift er nicht zu (diese wird somit NUR zur Generierung der Tabelle benötigt.

satz

private java.lang.String[] satz

Referenz auf den formatierten Satz, als Teil der linguistischen Daten.

kategorie

private java.lang.String[][] kategorie

Die Kategorien der Eingabewörter wird original im Parserobjekt abgelegt. Beim Parse-Start werden die Eingabewörter analysiert und die Kategorien bestimmt. Da ein Eingabewort mehrere mögliche Kategorien besitzen kann, muss auch jeder Eintrag der Kategorienliste intern eine Liste von Kategorien speichern können.

arbeitsbereich

private Arbeitsbereich arbeitsbereich

Referenz auf den Arbeitsbereich, in dem die Parse-Ergebnisse und Zwischenergebnisse abgelegt werden.

actgototab

private ActionGotoTabelle actgototab

Referenz auf das Tabellenmodell der Bildschirmtabelle, in der die Aktions- und Sprungtabelle dargestellt werden.

parseErgebnis

public java.lang.String parseErgebnis

Zwischenergebnisse und Fehler können hier protokolliert werden.

accepted

private boolean accepted

Erfolgsergebnis: wird bei accept gesetzt, kann aber durch Backtracking auch wieder zurückgesetzt werden.

parsestack

private java.util.Stack parsestack

Stack, auf dem Parser-Zustände (Objekte vom Typ (Klasse) ParserZustand) abgelegt werden. Wird für Backtracking verwendet.

parserLaeuft

private boolean parserLaeuft

Zeigt an, ob der Parser neu gestartet wurde oder bereits im laufenden Zustand ist. Wird bei der Initialisierung ausgewertet.

poseingabe

private int poseingabe

Zeigt auf das letzte bereits gelesene Eingabesymbol.

aktuellerZustand

private int aktuellerZustand

Zeigt die Nummer des aktuellen Zustands in der Aktions- bzw. Sprungtabelle an, in der sich der Parser befindet.

kategorienzaehler

private int kategorienzaehler

Bei mehreren möglichen Kategorien eines Eingabewortes zeigt dieses Attribut die aktuelle Kategorie an.

aktionszaehler

private int aktionszaehler

Bei mehreren möglichen Aktionen, die im aktuellen Zustand mit dem aktuellen Eingabesymbol möglich sind (mehrere Aktionen im Feld der Aktions- bzw. Sprungtabelle), zeigt dieses Attribut die aktuelle Aktion an.

gotoAusfuehren

private boolean gotoAusfuehren

Zwischenergebnisse und Fehler können hier protokolliert werden.

reduceRegelnr

private int reduceRegelnr

Die Nummer der Regel der Grammatik, nach der das letzte Reduce stattgefunden hat, ist Teil des Parser-Zustands. Grund ist, dass nach einem Reduce bei Mehrdeutigkeit (Goto-Goto-Konflikt) mehrere Folgezustände möglich sind. Dafür muss später auf die Regelnummer noch zugegriffen werden können.

Constructor Detail

ShiftReduceParser

public ShiftReduceParser(LingDaten lidat,
                         Arbeitsbereich arbbereich,
                         ActionGotoTabelle pactgototab)

Dieser Konstruktor erzeugt ein neues Parserobjekt.

Der Parser wird initialisiert mit einer Referenz auf die linguistischen Daten, aus denen die Aktions- und Sprungtabelle kommt. Ferner wird ein Arbeitsbereichs-Objekt übergeben, in das die Zwischenergebnisse kommen. Der letzte Parameter gibt die Referenz auf das Tabellenmodell, dass zur Anzeige der Aktions- und Sprungtabelle genutzt wird. Ferner wird hier auch der Stack initialisiert.

Parameters:

lidat - Linguistische Daten (Aktions- und Sprungtabelle, Grammatik, Lexikon)

arbbereich - Arbeitsbereich zur Anzeige der Ergebnisse und Zwischenergebnisse

pactgototab - Tabellenmodell der Aktions- und Sprungtabelle

Method Detail

raeumeAuf

public void raeumeAuf()

Diese Methode kann aufgerufen werden, wenn der Parse-Vorgang beendet oder abgebrochen werden soll. Er löscht die Referenzen auf die Objekte, so daß hiernach ein neues Parserobjekt mit neuen linguistischen Daten erzeugt werden kann.

parse

public void parse()

Aufruf des Parsers.

Der Parser führt eine Aktion (Shift, Goto, Reduce, Accept oder Backtracking) durch und kehrt dann zum Aufrufer zurück. Dadurch kann das Parsing quasi im "Debugging"-Modus mitverfolgt werden.

Ablauf:

• Wenn der Parser neu gestartet wurde (Attribut 'parserLaeuft'), dann wird er zuerst initialisiert. Dadurch werden insbesondere die lexikalischen Kategorien der Eingabewörter bestimmt. Ferner wird die Anfangszeile des Arbeitsbereiches geschrieben. Das Attribut 'eingabepos' zeigt auf den Anfang der Eingabe (-1, da 0 bedeuten würde, dass Wort Nr. 0 bereits gelesen wurde).
• Nun folgt die "normale" Verarbeitung. Da diese jedoch nur aus den "Standard-Aktionen" Shift oder Reduce bestehen würde, gibt es noch einen Sonderfall zu berücksichtigen. Dies bezieht sich darauf, dass beim letzten Parser-Aufruf ein Backtracking erfolgte, dass den Parser in einen Zustand nach einem Reduce, jedoch VOR dem Goto versetzte, und der in einen Goto/Goto-Konflikt führte. In diesem Fall soll keine normale Aktion durchgeführt werden, sondern die durch das Backtracking ermöglichte alternative Variante des Goto soll ausgeführt werden. Zur Ausführung der Goto-Aktion wird Methode 'fuehreGotoDurch' aufgerufen.
• Die Standard-Verarbeitung führt die Kategorienbestimmung durch. Da ein Wort mehrere Kategorien haben kann, wird die erste Kategorie gesucht, zu der eine Aktion in der Aktionstabelle gefunden werden kann.
• Wird keine Aktion gefunden, gibt es nur noch 2 Möglichkeiten: entweder auf dem Stack sind noch Alternativen vorhanden, oder nicht. Wenn ja, wird Backtracking ausgeführt (Methode 'backtracke'). Wenn nein, ist die Satzanalyse gescheitert. Dies wird im Attribut 'parseErgebnis' entsprechend protokolliert.
• Sind noch alternative lexikalische Kategorien des Eingabewortes möglich, müssen die für ein späteres Backtracking vorgemerkt werden. Dies leistet die Methode 'pruefeAlternativeEingabekategorien'.
• Nun wird das aktuell gültige Feld aus der Aktionstabelle gelesen (Schnittpunkt aus aktuellem Zustand und nächsten Eingabesymbol). Da das Feld bei Mehrdeutigkeit mehrere Aktionen enthalten kann, muss der Feldinhalt in die einzelnen Teile gegliedert werden (Verwendung des StringTokenizer). Das Attribut 'aktionszaehler' gibt an, die wievielte Aktion verwendet werden soll. Gibt es noch alternative Aktionen, wird der aktuelle Zustand auf den Stack zwecks späteren Backtrackings gelegt.
• Nun erst wird die bestimmte Aktion ausgeführt. Dies erfolgt durch Aufruf der Methoden 'fuehreAcceptDurch', 'fuehreShiftDurch' oder 'fuehreReduceDurch'.
• Als letzter Schritt wird der Arbeitsbereich aktualisiert.

See Also:

fuehreGotoDurch(Integer,ArbeitsbereichZeile), backtracke(), pruefeAlternativeEingabekategorien(), fuehreAcceptDurch(), fuehreShiftDurch(String), fuehreReduceDurch(String), parseErgebnis, kategorienzaehler, aktionszaehler

bestimmeKategorie

public static java.lang.String[] bestimmeKategorie(java.lang.String symbol,
                                                   LingDaten lingdat)

Kategorien eines Wortes im Eingabesatz bestimmen und als Liste von Kategorien zurückgeben. Die Liste besteht aus mehreren Elementen, wenn das Wort mehr als einer lexikalischen Kategorie zugeordnet werden kann (Beispiel: antworten Kategorie Nomen und Verb). Diese Methode wird außer von der Methode 'parse' auch (indirekt) vom Applet aufgerufen, um die Kategorien auf dem Bildschirm anzeigen zu können.

Parameters:

symbol - Eingabewort, dessen Kategorien bestimmt werden soll

lingdat - Referenz auf die linguistischen Daten

Returns:

Liste der Kategorien des Eingabewortes

See Also:

parse()

fuehreAcceptDurch

private void fuehreAcceptDurch()

Wird aufgerufen, wenn der Parser als aktuelle Aktion in der Tabelle ein 'acc' findet (Aufruf in der Methode 'parse').

Beim ersten Erreichen dieser Aktion wird das Attribut 'accepted' auf true gesetzt. Beim nächsten Aufruf (wiederrum mit Aktion 'acc') ist das Attribut damit auf true gesetzt: es wird dann ein Backtracking durchgeführt, um alternative Lösungen zu finden, und 'accepted' wird auf false zurückgesetzt.

See Also:

parse()

fuehreShiftDurch

private void fuehreShiftDurch(java.lang.String aktionssymbol)

Wird aufgerufen, wenn der Parser als aktuelle Aktion in der Tabelle ein 'sh' findet (Aufruf in der Methode 'parse').

Der Folgezustand des aktuellen Zustands wird aus dem Kopf des Zustands bestimmt (siehe Attribut 'zustand'). Die aktuelle Eingabeposition wird dann um eins weitergerückt. Es wird eine neue Zeile für den Arbeitsbereich vorbereitet und dem Arbeitsbereich hinzugefügt. Auch ein neuer Parsebaum (besteht nur aus dem geshifteten Terminalsymbol) wird erzeugt und im Arbeitsbereich angefügt. Als letztes, und ganz wichtig, wird der aktuelle Zustand auf den berechnteten Folgezustand gesetzt.

Parameters:

aktionssymbol - Aktion (Shift), die ausgeführt werden soll

See Also:

parse(), LingDaten.zustand, Arbeitsbereich, ArbeitsbereichZeile

pruefeAlternativeEingabekategorien

private void pruefeAlternativeEingabekategorien()

Hier wird geprüft, ob das aktuelle Eingabewort auch alternative Eingabekategorien besitzt, und falls ja, wird die nächste alternative Eingabekategorie auf den Stack gelegt (Methode 'zustandAufStack').

See Also:

zustandAufStack(int,int,boolean,int,ArbeitsbereichZeile)

zustandAufStack

private void zustandAufStack(int pkategorienzaehler,
                             int paktionszaehler,
                             boolean gotoAusfuehren,
                             int reduceRegelnr,
                             ArbeitsbereichZeile pzeile)

Wenn es in der aktuellen Parse-Situation mehrere Alternativen (= Konflikte) gibt, muss die nächste mögliche Alternative auf den Stack gebracht werden. Dazu dient diese Methode.

Das Gegenstück zu dieser Methode ist die Methode 'backtracke', die entsprechend den Zustand vom Stack liest und zum aktuellen Zustand macht.

Parameters:

pkategorienzaehler - Kategorienzähler, der auf den Stack geschrieben werden soll

paktionszaehler - Aktionszähler, der auf den Stack geschrieben werden soll

gotoAusfuehren - Flag, das anzeigt, ob es sich um ein Goto/Goto-Konflikt handelt, so dass beim Backtracken direkt ein Goto ausgeführt werden soll

reduceRegelnr - Wird ebenfalls bei einem Goto/Goto- Konflikt benötigt, und zwar um die Regelnummer zu bestimmen, nach der reduziert wurde

pzeile - Wird der Parameter gesetzt, wird die übergebene Arbeitsbereichzeile auf den Stack geschrieben, ansonsten wird die letzte Zeile des Arbeitsbereiches übernommen

See Also:

backtracke()

backtracke

private void backtracke()

Diese Methode ist das Gegenstück zur Methode 'zustandAufStack'. Sie liest den Parser-Zustand vom Stack und macht ihn zum aktuellen Zustand. Als Erklärung wird für den Arbeitsbereich "Backtracking" geschrieben sowie die Zeile des Arbeitsbereiches, zu dem die Alternative auf den Stack gebracht wurde.

See Also:

zustandAufStack(int,int,boolean,int,ArbeitsbereichZeile)

fuehreReduceDurch

private void fuehreReduceDurch(java.lang.String aktionssymbol)

Wird aufgerufen, wenn der Parser als aktuelle Aktion in der Tabelle ein 're' findet (Aufruf in der Methode 'parse').

Für den Arbeitsbereich wird nun eine Zeile erzeugt, die das Reduce beschreibt. Diese Zeile wird durch die Methode 'reduziere' des Arbeitsbereichs erzeugt. Sie bewirkt die Reduktion der rechts von der Produktion stehenden Symbole durch das Symbol auf der linken Seite der Produktion.

Durch die Reduktion wird kurz in einen Zwischenzustand gesprungen, und zwar den letzten Zustand, wenn man alle Symbole rechts der Produktion aus der Arbeitsbereichszeile streicht.

Um in den endgültigen Folgezustand zu kommen, wird die Methode 'fuehreGotoDurch' aufgerufen, die den Folgezustand aufgrund des Reduktionssymbols bestimmt.

Parameters:

aktionssymbol - Aktion (Reduce), die durchgeführt werden soll (enthält die Regelnummer der Reduktion)

See Also:

parse(), Arbeitsbereich.reduziere(int), fuehreGotoDurch(Integer,ArbeitsbereichZeile)

fuehreGotoDurch

private void fuehreGotoDurch(java.lang.Integer regelnummer,
                             ArbeitsbereichZeile neueZeile)

Wird aufgerufen, wenn der Parser als aktuelle Aktion in der Tabelle ein 'go' findet (Aufruf in der Methode 'fuehreReduceDurch'). Das Goto findet immer am Anschluss an eine Reduktion statt.

Zuerst wird, analog zu shift, der Folgezustand bestimmt. Dazu muss zuerst die Goto-Aktion aus der Tabelle gelesen werden. Ist das entsprechende Feld jedoch leer, ist das Parsen entweder gescheitert oder es wird ein Backtracking durchgeführt.

Danach wird die Aktion zerlegt, wenn sie aus mehreren Alternativen besteht (Verwendung von StringTokenizer). Wenn es gültige Alternativen gibt, wird die nächste Alternative auf Stack gelegt.

Nun endlich wird eine neue Zeile im Arbeitsbereich angelegt und das Goto durchgeführt.

Parameters:

regelnummer - Nummer der Regel, nach der die Reduktion durchgeführt wird

neueZeile - Arbeitsbereichzeile, die durch Reduce erzeugt wurde und hier fortgeschrieben wird

See Also:

fuehreReduceDurch(String), zustandAufStack(int,int,boolean,int,ArbeitsbereichZeile), ArbeitsbereichZeile

unerwarteteEingabe

private java.lang.String unerwarteteEingabe(int poseingabe)

erzeugt eine Protokollmeldung (Fehler unerwartete Eingabe)

Parameters:

poseingabe - Eingabeposition, an der der Fehler auftrat

eingabeOk

private java.lang.String eingabeOk()

erzeugt eine Protokollmeldung (Erfolgsmeldung)