Aufgaben

Aufgabe: Alternative Beschreibung arithmetischer Ausdrücke

Betrachten Sie die folgende (alternative) Syntaxbeschreibung in BNF für arithmetische Ausdrücke.

Ausdruck ::= Summand | Ausdruck '+' Summand
Summand  ::= Faktor  | Summand  '*' Faktor
Faktor   ::= Ziffer  | Variable | '(' Ausdruck ')'
Ziffer   ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
Variable ::= 'x' | 'y' | 'z'

Prüfen Sie, ob die folgenden Wörter aus dem Nichtterminalsymbol Ausdruck abgeleitet werden können. Geben Sie dazu entweder einen Ableitungsbaum an oder argumentieren Sie, warum dies nicht möglich ist. In den Ableitungsbäumen dürfen Sie statt der Nichtterminalsymbole deren Anfangsbuchstaben verwenden, also zum Beispiel A statt Ausdruck schreiben.

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

Bonusaufgabe: Alternative Beschreibung arithmetischer Ausdrücke um Listen-Ausdrücke erweitern

Erweitern Sie die in der vorherigen Aufgabe angegebene Syntaxbeschreibung um weitere Regeln, die Listen und Listenzugriffe beschreiben. Sie dürfen dazu die erweiterte Syntax der Backus-Naur-Form (EBNF) verwenden. Zum Beispiel sollen die folgenden Ausdrücke zusätzlich ableitbar sein.

  • [1,2+3]
  • x[2][3]
  • (x+[3,4])[1+y[5]]

Den Zugriff auf Teillisten (zum Beispiel x[0,2] zur Selektion der ersten beiden Elemente einer Liste x) brauchen Sie nicht zu beschreiben. Achten Sie aber darauf, dass die Beschreibung eindeutig bleibt und der Syntax von Python entspricht. Es also zum Beispiel nur einen Ableitungsbaum für 1+y[5] geben, der dem vollständig geklammerten Ausdruck (1+(y[5])) entspricht.

Aufgabe: Gegebene Syntaxbeschreibung untersuchen

Gegeben sei die folgende Syntaxbeschreibung in BNF:

R ::= '/' S '/'
    
S ::= E
    | E S

E ::= '(' E '|' E ')'
    | E '*'
    | D
    
D ::= '0'
    | '1'

Untersuchen Sie, ob die Zeichenfolge /0(0|1)*1/ aus dem Nichtterminalsymbol R abgeleitet werden kann. Geben Sie gegebenenfalls einen Ableitungsbaum (oder eine Ableitung) der Zeichenfolge an oder erläutern Sie, warum eine Ableitung nicht möglich ist.

Aufgabe: Syntaxbeschreibung selbst erstellen

Definieren Sie eine (E)BNF, aus der sich alle nichtleeren Zeichenfolgen ableiten lassen, die aus einer beliebigen positiven Anzahl von Buchstaben a-z gefolgt von derselben Anzahl von Ziffern 0-9 bestehen. Es sollen sich also zum Beispiel die Zeichenfolgen a4, ws12 und mat369 ableiten lassen, nicht aber die leere Zeichenfolge, bc1000, pro7, usw.