---

Geschrieben von estrelladelanoche am 24.10.2012 um 15:03:

  Grammatik - gültige Ausdrücke der Programmiersprache LISP

Meine Frage:
Ich habe folgende Grammatik gegeben:

expr: atom
| '(' { expr } ')'
;

atom: id
| num
;

num: '0'..'9'{'0'..'9'}
id: ('a'..'z' | 'A'..'Z') {('a'..'z' | 'A'..'Z' | '0'..'9')}
Diese Grammatik beschreibt (fast) alle gültigen Ausdrücke der Programmiersprache LISP.

Die Fragestellung lautet ob folgenge expr gültige Ausdrücke sind
 ()
 () ()
 3
 (3)
 (-3)

 (1 (2 (3 4)))
 (a1 2)
 (a (1) (2))
 (list 1 2 (list 3 4))
 (lambda (x) (f x))

Meine Ideen:
Mein Problem ist das mir nicht klar ist, wie ich herrausfinden kann ob diese Ausdrücke gültig sind oder ob das nicht der Fall ist.

Kann mir jemand bitte erklären, wie ich das abgleichen kann?

Danke

---

Geschrieben von Karlito am 24.10.2012 um 19:36:

 

Hallo,

ich denke hier wird erwartet, dass du eine Folge von Produktionen angibst, welche zum gewünschten Wort führen.

Formal kenne ich nur den CYK-Algorithmus. Das ist etwas aufwändiger.

Ich hoffe ich konnte Dir weiterhelfen.

VG,

Karlito