Lösungen

Aufgabe: Syntaktische Ableitung arithmetischer Ausdrücke

Der folgende Ableitungsbaum zeigt, dass das Wort (sqrt(((x**2)+1))/x) Aus dem Nichtterminalsymbol Exp der BNF für vollständig geklammerte arithmetische Ausdrücke ableitbar ist.

graph TD e0(["Exp"]) --> t0["("] & e1(["Exp"]) & o0(["Op"]) & e2(["Exp"]) & t1[")"] e1 --> f1(["Fun"]) & t2["("] & e3(["Exps"]) & t3[")"] f1 --> t4["sqrt"] e3 --> e4(["Exp"]) --> t5["("] & e5(["Exp"]) & o2(["Op"]) & e6(["Exp"]) & t6[")"] e5 --> t7["("] & e7(["Exp"]) & o3(["Op"]) & e8(["Exp"]) & t8[")"] e7 --> v0(["Var"]) --> t9["x"] o3 --> t10["**"] e8 --> v1(["Val"]) --> n0(["Num"]) --> d0(["Digit"]) --> t11["2"] o2 --> t12["+"] e6 --> v2(["Val"]) --> n1(["Num"]) --> d1(["Digit"]) --> t13["1"] o0 --> t14["/"] e2 --> v3(["Var"]) --> t15["x"]

Das Wort (sqrt((x**2)+1)/x) wird nicht durch dieselbe BNF beschrieben, da es ein Klammernpaar weniger enthält als Funktions- und Operatorsymbole.

Aufgabe: Syntaktische Beschreibung logischer Ausdrücke

Die folgende BNF beschreibt vollständig geklammerte logische Ausdrücke. Die Nichtterminalsymbole Exp und Var verweisen dabei auf die BNF für arithmetische Ausdrücke.

BExp ::= 'true' | 'false'
       | 'not(' BExp ')'
       | '(' BExp BOp BExp ')'
       | '('  Exp COp  Exp ')'
       | Var

BOp  ::= 'and' | 'or'

COp  ::= '<' | '>' | '<=' | '>=' | '==' | '!='

Diese BNF beschreibt zum Beispiel das Wort (not((false or x)) and (2 < y)) wie der folgende Ableitungsbaum zeigt.

                                             BExp
 '('     BExp                                BOp              BExp            ')'
     'not('            BExp           ')     'and'  '('  Exp  COp  Exp  ')'
            '('  BExp  BOp  BExp  ')'                    Val  '<'  Var
               'false' 'or' Var                          Num       'y'
                            'x'                          '2'

Aufgabe: Alternative Beschreibung arithmetischer Ausdrücke

Es gibt für alle Wörter Ableitungsbaume, deren Struktur derjenigen der folgenden vollständig geklammerten Ausdrücke entspricht.

  • ((2*x)+3)
  • (2+(x*3))
  • ((2+x)*3)
  • ((1+2)+3)

Diese Klammerung entspricht auch der in der Mathematik üblichen Klammerung, die Punkt-vor-Strich-Rechnung respektiert und gleichwertige Operatoren linksassoziativ wertet.

Erweiterung um Listen:

Faktor ::= ... 
         | '[' [ Ausdruck { ',' Ausdruck } ] ']'
         | Faktor '[' Ausdruck ']'

Die erste neue Regel ist für Listen-Literale, die zweite für Listen-Zugriffe. Beachtenswert ist bei letzterer die Verwendung von Faktor statt Ausdruck, die sicherstellt, dass zusammengesetzte Listen-Ausdrücke an dieser Position geklammert werden müssen.

Aufgabe: Gegebene Syntaxbeschreibung untersuchen

Ableitung des Wortes /0(0|1)*1/ aus der gegebenen BNF:

     R                                       | Regel  R -> '/' S '/'
 => '/'  S  '/'                              | Regel  S -> E S
 => '/'  E   S  '/'                          | Regel  E -> D
 => '/'  D   S  '/'                          | Regel  D -> '0'
 => '/' '0'  S  '/'                          | Regel  S -> E S
 => '/' '0'  E   S  '/'                      | Regel  E -> E '*'
 => '/' '0'  E  '*'  S  '/'                  | Regel  E -> '(' E '|' E ')'
 => '/' '0' '('  E  '|'  E  ')' '*'  S  '/'  | Regel  E -> D (2x)
 => '/' '0' '('  D  '|'  D  ')' '*'  S  '/'  | Regel  D -> '0'
 => '/' '0' '(' '0' '|'  D  ')' '*'  S  '/'  | Regel  D -> '1'
 => '/' '0' '(' '0' '|' '1' ')' '*'  S  '/'  | Regel  S -> E
 => '/' '0' '(' '0' '|' '1' ')' '*'  E  '/'  | Regel  E -> D
 => '/' '0' '(' '0' '|' '1' ')' '*'  D  '/'  | Regel  D -> '1'
 => '/' '0' '(' '0' '|' '1' ')' '*' '1' '/'

Ableitungsbaum des Wortes /0(0|1)*1/:

                      R
                      |
                 +----+----+
                 |    |    |
                 /    S    /
                      |
                 +----+----+
                 |         |
                 E         S
                 |         |
                 D    +----+----+
                 |    |         |
                 0    E         S
                      |         |
                   +--+--+      E
                   |     |      |
                   E     *      D
                   |            |
           +---+---+---+---+    1 
           |   |   |   |   |
           (   E   |   E   ) 
               |       |
               D       D
               |       |
               0       1

Aufgabe: Syntaxbeschreibung selbst erstellen

Definition einer BNF für Zeichenfolgen aus n Buchstaben gefolgt von n Ziffern (n > 0):

Z ::= A B | A Z B
A ::= 'a' | ... | 'z'
B ::= '0' | ... | '9'