Wie am besten Parsen?

[alzaimar]

Ich misch mich mal ein: Der Tokenizer zerlegt den Inputtext (eine Folge von Zeichen) in eine Folge von 'Token', damit des der Parser einfacher hat. Aus dem Wort 'begin' wird der Token BEGIN, aus dem String 'ein String mit begin' wird der Token STRING (mit einem Verweis auf den String-inhalt), aus einem FooBar wird ein IDENTIFIER (mit dem Verweis auf den Namen 'FooBar') und aus dem Zeichen '-' wird das Token MINUS. Dabei gibt es schon ein paar Fallen. Was soll der Tokenizer z.B. aus ':=' machen? Zwei Token, nämlich COLON und EQUAL, oder ein Token, 'ASSIGNMENT'. Was ist '..', DECIMALPOINT DECIMALPOINT oder DOTDOT (oder was auch immer). Hier kann man z.B. vor den Tokenizer noch einen Präprozessor knallen, der mit einem Lookaheadbuffer das nächste Zeichen prüft und ggf. Metazeichen (z.B. #255, statt :=) an den Tokenizer übermittelt, damit der eben bei jeden 'Zeichen' weiss, woran er gerade ist. Zu kompliziert? Na, ein guter Tokenizer ist ja auch nicht so mal eben geschrieben.

Ein Tokenizer und Parser sollte Jeder ernsthafte Programmierer mal implementiert haben. Meine Meinung.

Eine Möglichkeit, die Punkt-Vor-Strichrechnung zu implementieren, ist die, die Grammatik erstmal zu formulieren und diese dann in Funktionen zu packen, z.B. so:

Code:

Term ::= <Ausdruck> [<StrichOp> <Term>] /* Das in [] angegeben kann, muss aber nicht angegeben werden
StrichOp ::= '+' | '-'
Ausdruck ::= <SimpleTerm> [ <MulOp> <Ausdruck> ]
MulOp ::= '*' | '/'
SimpleTerm ::= '(' <Term> ')'  | <Number> 
Number ::= [ <Sign> ] <Digits>
<Sign> ::= [<PlusOrMinus> [<Sign>]]
PlusOrMinus ::= '+' | '-'

Das kann man z.B. so programmieren:

Delphi-Quellcode:

Function IsTerm : Boolean;
Begin
  If IsAusdruck Then Begin
    If IsStrichOp then
      If IsTerm Then 
        Result := True
      else
        Error 'Term erwartet'
  end
  else
    Error 'Ausdruck erwartet'
End;

Function IsAusdruck : Boolean;
Begin
  If IsSimpleTerm Then Begin
    If IsMulOp then
      If IsAusdruck Then 
        Result := True
      else
        Error 'Ausdruck erwartet'
  end
  else
    Error 'SimpleTerm erwartet'
End;

Function IsStrichOp : Boolean;
Begin
  If (CurrentToken = PLUS) Or (CurrentToken = MINUS) Then Begin
    AdvanceToNextToken;
    Result := True;
  End
  Else
    Result := False;
End;
...

Man sollte sich aber mit formalen Grammatiken (z.B. in Backus-Naur Form) auskennen. Das wichtige an der Grammatik ist, das man zu jeden Zeitpunkt anhand des nächsten Token entscheiden kann, wohin die Reise geht. Bei einem mathematischen Ausdruck geht das noch, aber bei einer Programmiersprache wird das schon schwieriger...

Viel Spass!