Wie am besten Parsen?

[Christian Seehase]

Moin Malo,

Zitat von malo:

Ich weiß aber grade nicht, ob ich wirklich nur ordinale Typen dafür abfragen muss,

lass es mich mal so sagen:
Es würde mich wundern, wenn nicht

[malo]

Zitat von Mephistopheles:

Zitat von malo:

Dann muss man aber ein hässliches Break ans Ende der Schleife setzen...

Nicht bei einer C-for-Schleife

for(;Abbruchbedingung {} ...

Mag sein, gehört jedoch nicht hierher

[c.wuensch]

Hi Malo,

vor kurzem haben wir im Informatikunterricht Parser behandelt, und sogar einen Parser für ein (sehr stark vereinfachtes) Pascal geschrieben.

Besonders wichtig ist, zuerst eine klare Struktur zu haben (kann man schön in Syntaxdiagrammen darstellen).

Wenn du willst, kann ich dir den vereinfachten Parser ja mal schicken, vielleicht hilft dir das was!

Cu, Chris

[EDIT] habs mal angefügt [/EDIT]

[Ultimator]

Da es hier in dem Thread ja um u.a. Tokenizer geht, muss ich gleich mal was fragen

Bisher hab ich meinen Tokenizer soweit, dass er mir alles schön zerlegt: Klammern, Zahlen und natürlich auch Rechenzeichen.
Das Problem ist nur: Das Minus ist ja sowohl Rechenzeichen als auch ein Vorzeichen. Wie mach ich meinem Tokenizer klar, ob ein Minus als Vorzeichen oder als Rechenzeichen zu sehen ist?

[malo]

Zitat von Ultimator:

Bisher hab ich meinen Tokenizer soweit, dass er mir alles schön zerlegt: Klammern, Zahlen und natürlich auch Rechenzeichen.
Das Problem ist nur: Das Minus ist ja sowohl Rechenzeichen als auch ein Vorzeichen. Wie mach ich meinem Tokenizer klar, ob ein Minus als Vorzeichen oder als Rechenzeichen zu sehen ist?

Also, mathematisch gesehen gibt es ja eigentlich keinen wirklichen Unterschied zwischen Rechenzeichen und Vorzeichen (bei Addition und Subtraktion). Im Endeffekt wird halt eh alles addiert.

Code:

5-3=2

ist das selbe wie

Code:

5 + (-3) = 2

. Daher würde ich einfach ein Minus immer als Vorzeichen interpretieren. Dann soll der Parser nachher erkennen, dass, wenn zwei Zahlen nacheinander ohne Rechenzeichen (dafür aber einmal mit Vorzeichen) kommen, addiert werden sollen.

Nur meine Idee

[Dax]

Gar nicht. Das ist Sache des Parser, der Tokenizer zerlegt nur

[Ultimator]

Zitat von malo:

Also, mathematisch gesehen gibt es ja eigentlich keinen wirklichen Unterschied zwischen Rechenzeichen und Vorzeichen (bei Addition und Subtraktion).

Da liegt das Problem

@Dax: Okay
Der Tokenizer soll das '-' also immer als ein Token ansehen?

[Dax]

Es sei denn, du willst auch strings parsen, dann sollte der Tokenizer das - in einem string nicht erkennen. Aber generell für Matheparser: ja.

[Ultimator]

Nein, Strings will ich nicht, ich will nur nen Matheparser
Wie isses bei der Multiplikation, Division und (noch schlimmer ) den Potenzen?
Wie lass ich das den Parser richtig auswerten, wo jetzt ein Minuszeichen dazugehört?

[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!