PDA

Archiv verlassen und diese Seite im Standarddesign anzeigen : Formale Grammatik testen?

Gast
2010-10-11, 19:08:34
Hallo!

Haben dieses Semester eine Vorlesung in theoretischer Informatik und behandeln gerade formale Grammatik, also im wesentlichen so, wie sie auf

http://de.wikipedia.org/wiki/Formale_Grammatik

beschrieben wird.

Das ganze läuft bisher ganz gut von der Hand, aber ich frage mich, ob es ein Tool gibt, mit dem man seine formulierte Grammatik testen kann?

Danke!
Gast
2010-10-11, 19:10:37
Nachtrag:

ich glaube mich erinnern zu können, dass sowas mit Prolog unter Umständen möglich war und es sogar einen entsprechenden Operator für Grammatiken gab (zumindest in Winprolog). Leider hab ich die Software nicht mehr, ist desweiteren kommerziell.
patermatrix
2010-10-12, 11:11:09
Für simple Grammatiken, die du als Zustandsautomaten darstellen kannst, kannst du mal den Visual Automata Simulator (http://www.cs.usfca.edu/~jbovet/vas.html) ausprobieren.
Jotta
2010-10-13, 09:11:20
Das hängt vom Typ der Grammatik ab (Chomsky-Hierarchie).
Für alles bis einschliesslich Kontext-Frei ist z.B. der Earey-Parser
brauchbar, wenn auch nicht sehr schnell. Tools z.B. für Skriptsprachen
gibts überall im Netz.
Für Kontextsensitiv und höher wird's allerdings schwerer.

Viel Spass
Gast_samm
2010-10-13, 12:28:21
Nachtrag:

ich glaube mich erinnern zu können, dass sowas mit Prolog unter Umständen möglich war und es sogar einen entsprechenden Operator für Grammatiken gab (zumindest in Winprolog). Leider hab ich die Software nicht mehr, ist desweiteren kommerziell.Ja, mit Prolog kannst du bequem einen Top-Down-Parser basteln, mittels DCG (einfach nach DCG Prolog googlen). Sei dir aber bewusst, dass du damit *sehr* eingeschränkt bist, z.B. bei rekursiven Strukturen musst du echt aufpassen, und teilweises Parsing ist auch nicht möglich (logisch, da top-down).

@Jotta: Einfach mal den Earley-Algorithmus in den Raum zu werfen hilft nicht viel weiter. Ich könnte auch sagen, benutz lieber CYK^^
Jotta
2010-10-13, 18:43:56
@Gast_samm,

ich habe ja nicht den Earley-Algorithmus in den Raum geworfen,ich sprach vom Parser
selbst. Mit ein wenig Suche im Internet wird man ohne Probleme eine Reihe von Tools
finden, die den Algorithmus als Basis benutzen.

Earley ist für "allgemeinere" Sprachen (nicht LL1,LR1,LLK..) deswegen oft zu finden,
weil er sehr einfach zu implementieren ist und im gegensatz zu CYK keine Vorbearbeitung
der Grammatik verlangt. Versuch mal CYK-Tools zu finden..

Jotta