Compilerbau

Arithmetische Ausdrücke

Ein weiteres EBNF Beispiel anhand von arithmetischen Ausdrücken: 

expression = term [ + | - term ]
term       = factor [ * | / factor ]
factor     = value | ( "(" expression ")" )

Folgende Ausdrücke sind korrekte Sätze im Sinne der obigen Grammatik, d.h. sie lassen sich formal mit Hilfe der Grammatikregeln ableiten: 

2*(3+4)
2+3*4

Anwendung der Ableitungsregeln am Beispiel des letzteren Ausdrucks: 

2+3*4 = term [ + | - term ]
      = factor [ * | / factor ] [ + | - term ]
      = value [ * | / factor ] [ + | - term ]
      = 2 [ * | / factor ] [ + | - term ]
      = 2 [ + | - term ]
      = 2 + term
      = 2 + factor [ * | / factor ]
      = 2 + value [ * | / factor ]
      = 2 + 3 [ * | / factor ]
      = 2 + 3 * factor
      = 2 + 3 * value
      = 2 + 3 * 4

Die Reihenfolge der Ableitungen spiegelt die Priorität der verwendeten arithmetischen Operatoren wieder.

Folgende Ausdrücke lassen sich nicht ableiten, sind also kein formal korrekter arithmetischer Ausdruck im Sinne der EBNF-Definition: 

2(3+4)
2+3+4
2*(3+4

Überprüfung der Ableitbarkeit am Beispiel des letzten Ausdrucks: 

2*(3+4 = term [ + | - term ]
       = factor [ * | / factor ] [ + | - term ]
       = value [ * | / factor ] [ + | - term ]
       = 2 [ * | / factor ] [ + | - term ]
       = 2 * factor [ + | - term ]
       = 2 * ( expression ) [ + | - term ]
       = 2 * ( term [ + | - term ] ) [ + | - term ]
       = 2 * ( factor [ * | / factor ] [ + | - term ] ) [ + | - term ]
       = 2 * ( value [ * | / factor ] [ + | - term ] ) [ + | - term ]
       = 2 * ( 3 [ * | / factor ] [ + | - term ] ) [ + | - term ]
       = 2 * ( 3 [ + | - term ] ) [ + | - term ]
       = 2 * ( 3 + term ) [ + | - term ]
       = 2 * ( 3 + factor [ * | / factor ] ) [ + | - term ]
       = 2 * ( 3 + value [ * | / factor ] ) [ + | - term ]
       = 2 * ( 3 + 4 [ * | / factor ] ) [ + | - term ]
       = 2 * ( 3 + 4 ) [ + | - term ]
      != 2 * ( 3 + 4

Die Ableitung des Ausdrucks ergibt, dass als nächstes Token zwingend eine schliessende Klammer erwartet wird. Da sie jedoch nicht im Originalausdruck vorhanden ist, bedeutet dies, dass sich der Ausdruck nicht ableiten lässt.

An dieser Stelle würde ein Compiler eine entsprechende Fehlermeldung ausgeben: “token ) erwartet nach zahl 4”.

Q Warum ist 2+3+4 kein formal korrekter Ausdruck im Sinne der Grammatik?

Q Wie muss man die obigen Ableitungsregeln umformulieren, so dass auch die Ausdrücke 2+3+4 usw. zum Umfang der erlaubten arithmetischen Ausdrücke dazugehören?

Q Wie muss man einen Parser aufbauen, damit er die obige Grammatik anhand der bisher aufgetretenen Schlüsselwörter erkennt?

Lösung

← EBNF Beispiel | ● | Ein Beispiel-Parser →

Options: