Test eines Parsers

[Schruppinator]

Moin zusammen,

im Moment programmiere ich einen Parser für mathematische Funktionsausdrücke. Dafür habe ich eine kontextfrei Typ 2 Grammatik erstellt. Nun bin ich den Parser natürlich mit diversen Eingaben am Testen. Das Problem nur, es dauert ^^
Kennt ihr ein Programm oder ähnliches, was mir aus meiner Grammatik Strings erstellt, die ich dann automatisiert testen kann?

Ich stell mir das so vor, dass ich die Grammatik eingebe und dann erhalte ich eine Liste von X Strings in einer Datei
2+3
3-4
etc.
Diese kann ich dann in den Parser jagen und ihn so testen...

Danke schon mal

 

[ice-breaker]

du musst doch nicht jede Variation testen sondern nur spezielle Punkte deiner Grammatik:

• funktionieren die Grundrechenarten
• funktioniert Punkt- vor Strichrechnung
• funktioniert Klammerrechnung
• funktioniert Schachtelung

und wenn jede dieser Grundeigenschaften erfüllt ist, sollte auch jede weitere korrekte mathematische Formel korrekt erkannt werden.

 

[Schruppinator]

So bin ich bis jetzt auch vorgegangen. Spezialfälle testen etc.

Was mich nur stört ist das

sollte auch

Daher hab ich die angesprochene Art des Testens überlegt, bin dann eben aber an der Erstellung der Strings gescheitert.
Mir gehts auch darum, dass ich die Grammatik kenne. Bei der Erstellung werden vielleicht Ausdrücke erstellt, an die ich noch gar nicht gedacht habe. Das kann ich ja auch schwer wem aufdrücken, mir da zich dutzend String zu erstellen

 

[ice-breaker]

Wieso das Problem nicht umdrehen?

Annahme: der Parser erzeugt Baum-Strukturen
Vorgehen: erzeuge X zufällige Bäume, verkette diese Über mathem. Operationen und lasse daraus einen String erzeugen.

 

[Schruppinator]

Dafür müsste ich aber wieder ein Programm entwickeln, wenn ich dich nun richtig verstanden habe.

Mein Gedanke war, dass es sicher ein Programm, was für eine gegebene Grammatik eine beliebe Anzahl von Grammatikergebnissen liefert, schon existieren muss. Ich bin ja nicht der Erste, der einen Parser programmiert, der nun getestet werden muss

 

[ice-breaker]

Mein Gedanke war, dass es sicher ein Programm, was für eine gegebene Grammatik eine beliebe Anzahl von Grammatikergebnissen liefert, schon existieren muss. Ich bin ja nicht der Erste, der einen Parser programmiert, der nun getestet werden muss

Prinzipiell eine wirklich geniale Idee (da musst du aber nach Tools speziell für deine Grammatik-Notation suchen ) allerdings würde es, wenn auf Basis deiner Grammatik Grammatikergebnisse erstellt würden, ja auch fehlerhafte Ergebnisse erstellen, die deine Grammatik als wahr deklarieren würde, weil sie der Grammatik entsprechen

Ich weiß nicht wie wirklich Grammatiken getestet werden, aber ich würde mal sagen das Drüberschauen durch eine 3. Person und einige positive und negative Beispiele sollten vollkommen ausreichen. Die Grammatik für mathem. Formeln ist ja im Gegensatz zu Grammatiken für Programmiersprachen oder SQL wirklich sehr gering.


Auf Basis welcher Normalform hast du denn die Grammatik gebildet? Eventuell kennt die hier ja auch einer und kann sie sich ansehen.

 

[Schruppinator]

Ich denke auch, dass am Ende meine Tests ausreichend sind. Daher möchte ich dieses Programm ja auch nicht selber entwickeln. Nur wenn es das Programm schon gäbe, würd ichs nutzen
Eine Entwicklung braucht ja wahrscheinlich auch wieder Zeit (und auch Tests) die ich nicht habe ^^

Verwendet habe ich wie gesagt eine kontextfreie Typ 2 Grammatik. Auf Normalformen habe ich sie noch nicht mal getestet, da sie auch eher nur dazu dienen soll zu zeigen, wie man was eingibt.

Generell dachte ich eben, man gibt das Startsymbol, Produktionsregeln, Terminalsymbole etc. an. Damit kann das Programm dann ja zufällig X Durchläufe machen und mir so X Wörter aus der Sprache erstellen

Ich hab schon gegoogelt, aber nichts gefunden. Ist auch schwer, da ich nicht richtig weiß wonach googeln ^^ Vielleicht kennt ja noch wer ein Programm

 

[ice-breaker]

und was ist mit meinem Einwand?
eine falsche Grammatik wird auch falsche Ergebnisse bauen, die dein Parser dann als korrekt deklarieren würde.
Aus dem Grund wird es soetwas wahrscheinlich nicht geben.
Das 2. Problem wird sein, dass solch ein Tool, sofern es existiert, auf eine Grammatik hinentwickelt worden wäre. Also um mit ANTLR, Lemon, Yacc oder Bison-Grammatiken zu arbeiten, so wie ich das herauslese, hast du dir ja eine eigene Grammatik zum beschreiben deiner Mathe-Parser-Grammatik gebaut oder?

Du kannst sie ja trotzdem mal posten, wenn du möchtest.

 

[Schruppinator]

und was ist mit meinem Einwand?
eine falsche Grammatik wird auch falsche Ergebnisse bauen, die dein Parser dann als korrekt deklarieren würde.

Ich möchte ja weniger die Grammatik, eher mehr meinen Parser testen
Generell hast du Recht.

Das 2. Problem wird sein, dass solch ein Tool, sofern es existiert, auf eine Grammatik hinentwickelt worden wäre. Also um mit ANTLR, Lemon, Yacc oder Bison-Grammatiken zu arbeiten, so wie ich das herauslese, hast du dir ja eine eigene Grammatik zum beschreiben deiner Mathe-Parser-Grammatik gebaut oder?

Ja richtig, das habe ich. Vielleicht ist das auch gar nicht möglich was ich mir vorstelle

Ich bin nicht sicher, ob ich die Grammatik so posten darf, weils Teil einer Arbeit ist
Wenn niemand mehr eine Idee sonst hat, werde ich wohl mal selber eine ganze Reihe von Funktionsausdrücken aufstellen und die dann testen

Danke dir noch mal

Edit:
Nachdem mit nichts anderes mehr einfallen ist habe ich mir nun die Arbeit gemacht und ne ganze Reihe an Testfällen selbst getippt ^^ Die hab ich dann durch nen Blackboxtest gejagt...