Looking for parsing Keywords? Try Ask4Keywords

parsingErste Schritte mit dem Parsen


Bemerkungen

Parsing bezieht sich im allgemeinen Sprachgebrauch darauf, ein Sprachstück wie einen Satz zu analysieren und die Grammatikregeln dieser Sprache zu verwenden, um die Einzelteile zu identifizieren und die Bedeutung zu erlernen. In der Informatik bezieht sich dies auf einen spezifischen algorithmischen Prozess, bei dem die Folge von Symbolen als gültig erkannt wird und die Bestimmung der Bedeutung (oder Semantik ) eines Sprachkonstrukts ermöglicht wird, häufig in einem Computersprachcompiler oder -interpreter.

Ein einfacher Parser

Der einfachste Weg, einen Parser zu schreiben, ist die rekursive Abstiegstechnik. Dies erzeugt einen Top-Down-Parser (der formal als LL (1) beschrieben werden kann). Um das Beispiel zu beginnen, müssen wir zunächst die Grammatikregeln für unsere Sprache festlegen. In diesem Beispiel verwenden wir einfache arithmetische Ausdruckszuweisungen für Ausdrücke, die nur den Plus-Operator verwenden können:

 Assignment --> Identifier := Expression
 Expression --> Expression + Term | Term
 Term --> Identifier | (Expression)
 Identifier --> x | y | z 
 

Für jede Regel der Grammatik können wir eine Prozedur schreiben, um die ankommenden Token der Regel zu erkennen. Für die Zwecke dieses Beispiels können wir von einer Routine namens NextToken die einen lexikalischen Analysator zur Bereitstellung des Tokens aufruft, und einer Routine namens error die zur Ausgabe einer Fehlermeldung verwendet wird. Die verwendete Sprache basiert auf Pascal.

 var token:char;  (* Updated by NextToken *) 

 procedure identifier;
 begin
    if token in ['x','y','z']
    then
        NextToken
    else
        error('Identifier expected')
 end; 
 

Sie sehen, dass dieser Code die Regel zum Erkennen eines Identifier implementiert. Wir können dann die Regel für einen Term ähnlich implementieren:

 procedure expression forward; 

 procedure term;
 begin
     if token = '('
     then
         begin
         nextToken;
         expression;
         if token <> ')'
         then
             error(') expected')
         else NextToken
         end
     else
         identifier
 end; 
 

Wenn wir die Regel für Expression implementieren, haben wir ein Problem. Das erste Element der Expression ist selbst ein Expression . Dies würde dazu führen, dass wir folgendes schreiben:

procedure expression;
begin
expression;
...
end;
 

Dies ist direkt selbstrekursiv und würde daher für immer in einer Schleife ablaufen. Die von Top-Down-Algorithmen analysierte Grammatik kann aus diesem Grund nicht rekursiv sein. Ein einfacher Ausweg aus diesem Problem besteht darin, die Rekursion als Iteration auf folgende Weise neu zu erstellen:

Expression --> Term { + Term}* 
 

Wir können die Grammatikregel jetzt wie folgt codieren:

 procedure expression;
 begin
     term;
     while token = '+'
         do
         begin
             NextTerm;
             term
         end
 end; 
 

Wir können jetzt den Parser mit der verbleibenden Regel für die Zuweisung vervollständigen:

procedure assignment;
begin 
    identifier;
    if token <> '='
    then
        error('= expected')
    else
        begin
        NextToken;
        expression;
        end
 end; 
 

Beispiel für die Analyse eines englischen Satzes

Zum Beispiel im Satz:

Dieser Kuchen ist sehr nett.

Die Regeln der englischen Sprache würden Cake zu einem Substantiv machen , extrem zu einem Adverb , das das Adjektiv schön modifiziert, und durch diese Analyse konnte die Bedeutung verstanden werden.

Diese Analyse hängt jedoch davon ab, dass wir erkennen, dass die Reihenfolge der verwendeten Symbole Wörter ist. Wenn uns die verwendeten Zeichen nicht vertraut wären, könnten wir das nicht. Wenn wir auf einen Satz stoßen, der eine unbekannte Schreibweise verwendet, wie zum Beispiel Chinesisch, könnte das Parsen auf diese Weise schwierig sein. Hier ist ein chinesischer Beispielsatz:

可以 写 一点儿 中文。

Für alle, die keine chinesischen Schriftzeichen lesen, ist nicht klar, welche Symbole zu Wörtern zusammengefasst wurden. Dasselbe kann für einen Computeralgorithmus gelten, wenn entweder Englisch oder Chinesisch verarbeitet wird.

Daher muss das Parsing durch einen Prozess erfolgen, der als lexikalische Analyse oder Scannen bezeichnet wird. Dabei werden die einzelnen Zeichen zu erkannten Symbolen zusammengefasst, die wir häufig als Wörter bezeichnen. In Parsing-Algorithmen werden sie als Token bezeichnet .

Was Sie zum Parsen brauchen

Bei der Analyse muss vor dem Start die Grammatik für die Sprache angegeben werden. Für den Parser wird auch eine Quelle für Token benötigt.

Der Parser könnte handgeschriebener Code sein oder ein Parser-Generator-Tool könnte verwendet werden. Wenn ein Parser-Generator-Tool verwendet wird, muss dieses Tool heruntergeladen und installiert werden, sofern es noch nicht in Ihrer Plattform enthalten ist.

Grammatikdefinitionen

Eine Grammatik für einen Parser müsste normalerweise in einer kontextfreien Form geschrieben werden . Hierfür wird häufig eine Notation wie BNF (Backus-Naur-Form) oder EBNF (Extended-Back-Naur-Form) verwendet. Andere zur Beschreibung von Programmiersprachen häufig verwendete Notizen sind Eisenbahndiagramme .

Lexikalische Analyse

Token werden normalerweise von einem lexikalischen Analysator (oder Scanner) für den Parser bereitgestellt. Weitere Einzelheiten finden Sie in der Dokumentation zu einem lexikalischen Analysator (TBC).

Analysetechniken

Um einen Parser manuell zu codieren, müsste ein geeigneter Algorithmus ausgewählt werden, der sowohl der geparsten Sprache als auch den Implementierungsmitteln entspricht. Parsing-Algorithmen werden in die zwei Arten von Top-Down-Parsing und Bottom-Up-Parsing unterteilt . Ein (rekursiver) Top-Down-Parser ist für Anfänger leichter zu lernen, wenn er mit dem Schreiben von Parsern beginnt.

Parser Generator Tools

Die gebräuchlichste Methode zum Erstellen eines Parsers ist die Verwendung eines Parser-Generator-Tools. Es gibt viele solcher Tools, aber einige der am häufigsten verwendeten sind: