Was sind die Argumente gegen das Parsen der Cthulhu-Methode?

24

Mir wurde die Aufgabe übertragen, eine domänenspezifische Sprache für ein Tool zu implementieren, das für das Unternehmen sehr wichtig werden kann. Die Sprache ist einfach, aber nicht trivial, sie erlaubt bereits geschachtelte Schleifen, Verkettung von Zeichenfolgen usw. und es ist praktisch sicher, dass andere Konstrukte hinzugefügt werden, wenn das Projekt voranschreitet.

Ich weiß aus Erfahrung, dass das Schreiben eines Lexers / Parsers von Hand - es sei denn, die Grammatik ist trivial - ein zeitaufwendiger und fehleranfälliger Prozess ist. Ich hatte also zwei Möglichkeiten: einen Parser-Generator à la Yacc oder eine Combinator-Bibliothek wie Parsec. Ersteres war auch gut, aber ich habe mich aus verschiedenen Gründen für Letzteres entschieden und die Lösung in einer funktionalen Sprache implementiert.

Das Ergebnis ist für mich ziemlich spektakulär, der Code ist sehr präzise, ​​elegant und lesbar / fließend. Ich gebe zu, es mag etwas seltsam aussehen, wenn Sie nie etwas anderes als java / c # programmiert haben, aber das würde für alles gelten, was nicht in java / c # geschrieben ist.

Irgendwann wurde ich jedoch buchstäblich von einem Mitarbeiter angegriffen. Nach einem kurzen Blick auf meinen Bildschirm erklärte er, dass der Code unverständlich ist und dass ich das Parsen nicht neu erfinden sollte, sondern nur einen Stack und String.Split verwenden sollte, wie es jeder tut. Er machte viel Lärm, und ich konnte ihn nicht überzeugen, zum Teil, weil ich überrascht war und keine klare Erklärung hatte, zum Teil, weil seine Meinung unveränderlich war (kein Wortspiel beabsichtigt). Ich bot ihm sogar an, ihm die Sprache zu erklären, aber ohne Erfolg.

Ich bin mir sicher, dass die Diskussion vor dem Management wieder auftauchen wird, also bereite ich einige solide Argumente vor.

Dies sind die ersten Gründe, die mir einfallen, um eine auf String.Split basierende Lösung zu vermeiden:

  • Sie brauchen eine Menge Wenns, um Sonderfälle zu bewältigen, und die Dinge geraten schnell außer Kontrolle
  • Viele fest codierte Array-Indizes machen die Wartung schmerzhaft
  • extrem schwer zu handhabende Dinge wie ein Funktionsaufruf als Methodenargument (zB add ((add a, b), c)
  • Sehr schwierig, bei Syntaxfehlern aussagekräftige Fehlermeldungen zu liefern (sehr wahrscheinlich)
  • Ich bin alle der Einfachheit, Klarheit und Vermeidung unnötiger intelligenter und kryptischer Dinge verpflichtet, aber ich bin auch der Meinung, dass es ein Fehler ist, jeden Teil der Codebasis so zu dumm zu machen, dass selbst ein Burgerflipper dies verstehen kann. Es ist das gleiche Argument, das ich höre, wenn ich keine Schnittstellen benutze, keine Trennung von Bedenken vornehme, keinen Code kopiert oder einfügt. Schließlich ist ein Minimum an technischer Kompetenz und Lernbereitschaft erforderlich, um an einem Softwareprojekt zu arbeiten. (Ich werde dieses Argument nicht verwenden, da es wahrscheinlich anstößig klingen wird und der Beginn eines Krieges niemandem helfen wird.)

Was sind Ihre Lieblingsargumente gegen das Parsen nach Cthulhu ? *

* Natürlich, wenn Sie mich überzeugen können, dass er Recht hat, werde ich auch vollkommen glücklich sein

smarmy53
quelle
9
Klingt für mich so, als würde sich Ihr Kollege freiwillig melden, um das DSL-Projekt für Sie zu erledigen!
GroßmeisterB
23
"Ich sollte das Parsen nicht neu erfinden, sondern einfach einen Stack und String.Split verwenden, wie es jeder tut" - verdammt, dieser Typ sollte froh sein, dass Unwissenheit nicht schadet ...
Michael Borgwardt
4
Weisen Sie Ihren Kollegen an, nicht zu dieser Diskussion zurückzukehren, es sei denn, er liest das gesamte Drachenbuch und besteht einen Test. Ansonsten hat er kein Recht, über Parsing-Themen zu diskutieren.
SK-logic
4
Entschuldigung, wer hat das Parsen neu erfunden?
rwong
2
Ich denke, mein Kopf wird buchstäblich explodieren, wenn ich das nächste Mal jemanden sehe, der das Wort "buchstäblich" im übertragenen Sinne verwendet.

Antworten:

33

Der entscheidende Unterschied zwischen den beiden Ansätzen besteht darin, dass derjenige, den er als den einzig richtigen Weg ansieht, zwingend ist und der Ihre deklarativ ist.

  • Ihr Ansatz deklariert explizit Regeln, dh die Regeln der Grammatik sind (fast) direkt in Ihrem Code codiert, und die Parser-Bibliothek wandelt rohe Eingaben automatisch in analysierte Ausgaben um, wobei Zustände und andere schwer zu handhabende Dinge berücksichtigt werden. Ihr Code wird in einer einzelnen Abstraktionsebene geschrieben, die mit der Problemdomäne übereinstimmt: Parsing. Es ist vernünftig anzunehmen, dass parsec korrekt ist, was bedeutet, dass der einzige Fehler darin besteht, dass Ihre Grammatikdefinition falsch ist. Andererseits verfügen Sie über vollständig qualifizierte Regelobjekte, die problemlos isoliert getestet werden können. Es kann auch erwähnenswert sein, dass ausgereifte Parser-Bibliotheken eine wichtige Funktion enthalten: die Fehlerberichterstattung. Eine anständige Fehlerbehebung, wenn das Parsen fehlgeschlagen ist, ist nicht trivial. Als Beweis rufe ich PHP auf parse error, unexpected T_PAAMAYIM_NEKUDOTAYIM: D

  • Sein Ansatz manipuliert Zeichenfolgen, behält den Status explizit bei und hebt die rohe Eingabe manuell in die analysierte Eingabe auf. Sie müssen alles selbst schreiben, einschließlich der Fehlerberichterstattung. Und wenn etwas schief geht, bist du total verloren.

Die Ironie besteht darin, dass die Richtigkeit eines mit Ihrem Ansatz geschriebenen Parsers relativ leicht bewiesen werden kann. In seinem Fall ist es fast unmöglich.

Es gibt zwei Möglichkeiten, ein Software-Design zu erstellen: Eine Möglichkeit besteht darin, es so einfach zu gestalten, dass es offensichtlich keine Mängel gibt, und die andere darin, es so kompliziert zu gestalten, dass es keine offensichtlichen Mängel gibt. Die erste Methode ist weitaus schwieriger.

AUTO Hoare

Ihr Ansatz ist der einfachere. Es steht ihm nur entgegen, seinen Horizont ein wenig zu erweitern. Das Ergebnis seiner Herangehensweise wird immer verworren sein, egal wie weit Ihr Horizont reicht.
Um ehrlich zu sein, hört es sich für mich so an, als sei der Typ nur ein ignoranter Dummkopf, der unter dem leidet Blub-Syndrom leidet und arrogant genug ist, um anzunehmen, dass Sie sich irren und Sie anschreien , wenn er Sie nicht versteht.

Am Ende stellt sich jedoch die Frage: Wer muss es warten? Wenn du es bist, dann ist es dein Anruf, egal was jemand sagt. Wenn er es sein wird, gibt es nur zwei Möglichkeiten: Finden Sie einen Weg, die Parser-Bibliothek zu verstehen, oder schreiben Sie einen imperativen Parser für ihn. Ich schlage vor, Sie generieren es aus Ihrer Parser-Struktur: D

back2dos
quelle
Hervorragende Erklärung des Unterschieds zwischen den beiden Ansätzen.
Smarmy53
6
Sie haben anscheinend eine Verknüpfung zu TVTropes for Programmers hergestellt. Auf Wiedersehen Nachmittag ...
Izkata
10

Eine Parsing-Ausdrucksgrammatik (wie der Packrat-Parser-Ansatz) oder ein Parser-Kombinator erfinden das Parsing nicht neu. Dies sind gut etablierte Techniken in der funktionalen Programmierwelt, und in den richtigen Händen kann es besser lesbar sein als die Alternativen. Ich habe vor ein paar Jahren eine ziemlich überzeugende Demonstration von PEG in C # gesehen, die es tatsächlich zu meinem ersten Mittel für relativ einfache Grammatiken gemacht hätte.

Wenn Sie eine elegante Lösung mit Parser-Kombinatoren oder einer PEG haben, sollte dies ein relativ einfacher Verkauf sein: Sie ist ziemlich erweiterbar, normalerweise relativ einfach zu lesen, sobald Sie Ihre Angst vor funktionaler Programmierung überwunden haben, und manchmal einfacher zu lesen als ein typischer Parser-Generator Das Angebot an Werkzeugen hängt jedoch stark von der Grammatik und der Erfahrung ab, die Sie mit beiden Werkzeugen haben. Es ist auch ziemlich einfach, Tests zu schreiben. Natürlich gibt es einige Grammatik-Ambiguitäten, die im schlimmsten Fall zu einer ziemlich schlechten Parsing-Leistung führen können (oder zu einem hohen Speicherverbrauch mit Packrat), aber der Durchschnittsfall ist ziemlich anständig und einige Grammatik-Ambiguitäten werden mit PEG besser gehandhabt als mit LALR, wie Ich erinnere mich.

Die Verwendung von Split und eines Stacks funktioniert mit einigen einfacheren Grammatiken als eine PEG oder kann diese unterstützen, aber es ist sehr wahrscheinlich, dass Sie mit der Zeit die rekursive Abstammung schlecht neu erfinden oder dass Sie eine Reihe von Verhaltensweisen haben, die Sie mit Bandbändern beschreiben. Hilfe bei der Einreichung auf Kosten von extrem unstrukturiertem Code. Wenn Sie nur einfache Tokenisierungsregeln haben, ist dies wahrscheinlich nicht so schlimm, aber wenn Sie die Komplexität erhöhen, ist dies wahrscheinlich die am wenigsten wartbare Lösung. Ich würde stattdessen nach einem Parser-Generator greifen.

Persönlich würde meine erste Neigung, wenn ich ein DSL erstellen muss, darin bestehen, etwas wie Boo (.Net) oder Groovy (JVM) zu verwenden, da ich die gesamte Stärke einer vorhandenen Programmiersprache und eine unglaubliche Anpassbarkeit durch das Erstellen von Makros und einfache Anpassungen erhalte auf die Compiler-Pipeline, ohne die mühsamen Dinge implementieren zu müssen, die ich tun würde, wenn ich von Null anfangen würde (Schleifen, Variablen, Objektmodell usw.). Wenn ich in einem Geschäft Ruby- oder Lisp-Entwicklung betreiben würde, würde ich nur die dort sinnvollen Redewendungen verwenden (Metaprogrammierung usw.)

Aber ich vermute, dass es bei Ihrem eigentlichen Problem entweder um Kultur oder um Ego geht. Sind Sie sicher, dass Ihr Kollege nicht genauso ausgeflippt wäre, wenn Sie Antlr oder Flex / Bison verwendet hätten? Ich vermute, dass das "Streiten" für Ihre Lösung ein verlorener Kampf sein könnte. Möglicherweise müssen Sie mehr Zeit für einen sanfteren Ansatz aufwenden, der konsensbildende Techniken verwendet, anstatt sich an Ihre lokale Verwaltungsbehörde zu wenden. Das Programmieren von Paaren und das Zeigen, wie schnell Sie Anpassungen an der Grammatik vornehmen können, ohne die Wartbarkeit zu beeinträchtigen, und das Durchführen eines Brownbags, um die Technik, ihre Geschichte usw. zu erläutern, gehen möglicherweise über 10 Aufzählungspunkte und ein "unhöfliches Q & A" hinaus Konfrontationstreffen.

JasonTrue
quelle
9

Ich kenne mich nicht mit Parsing-Algorithmen und dergleichen aus, aber ich denke, der Beweis für den Pudding ist das Essen. Wenn alles andere fehlschlägt, können Sie ihm anbieten, den Parser auf seine Weise zu implementieren. Dann

  • Vergleichen Sie die in beide Lösungen investierte Zeit.
  • Führen Sie beide Lösungen durch einen umfassenden Abnahmetest, um festzustellen, welche Lösungen weniger Fehler aufweisen
  • Lassen Sie den resultierenden Code von einem unabhängigen Richter in Größe und Klarheit mit Ihrem Code vergleichen.

Damit das Testen wirklich fair ist, möchten Sie möglicherweise, dass beide Lösungen dieselbe API implementieren und ein gemeinsames Testbed (oder ein von Ihnen beiden bekanntes Unit-Testing-Framework) verwenden. Sie könnten beide eine beliebige Anzahl und Art von Funktionstestfällen schreiben und sicherstellen, dass seine eigene Lösung alle diese Anforderungen erfüllt. Und natürlich sollte im Idealfall keiner von Ihnen vor Ablauf der Frist Zugriff auf die Implementierung des anderen haben. Der entscheidende Test wäre dann, beide Lösungen mit der vom anderen Entwickler entwickelten Testsuite zu testen .

Péter Török
quelle
Das ist eine großartige Idee! Es wäre auch einfach, ein allgemeines Unit-Testing-Framework zu verwenden.
smarmy53
1
+1 dafür, dass der Mitarbeiter die geteilte Version erstellt hat ... Das OP war derjenige, der damit beauftragt wurde, sie zu erstellen, also ist er derjenige, der sie höchstwahrscheinlich unterstützen muss - nicht der Mitarbeiter. Es könnte ausreichen, ihn zusätzlich zu seiner anderen Arbeit vorzuschlagen, um ihn von Ihrem Rücken zu kriegen.
Izkata
7

Sie haben dies so gestellt, als hätten Sie eine technische Frage, aber wie Sie wahrscheinlich bereits wussten, gibt es hier keine technische Frage. Ihr Ansatz ist weit überlegen, etwas auf Charakterebene zu hacken.

Das eigentliche Problem ist, dass Ihr (vermutlich erfahrener) Kollege unsicher ist und sich durch Ihr Wissen bedroht fühlt. Sie werden ihn nicht mit technischen Argumenten überzeugen ; das wird ihn nur defensiver machen. Stattdessen müssen Sie einen Weg finden, um seine Ängste zu lindern. Ich kann nicht viele Vorschläge machen, aber Sie werden versuchen, seine Kenntnis des Legacy-Codes zu würdigen.

Wenn Ihr Manager mit seinen technischen Argumenten einverstanden ist und Ihre Lösung verwirft, müssen Sie sich meines Erachtens nach einer anderen Stelle umsehen. Natürlich wären Sie in einer anspruchsvolleren Organisation wertvoller und wertvoller.

Kevin Cline
quelle
Sie haben Recht, ich wusste bereits, dass meine Herangehensweise überlegen ist, aber ich konnte keine gute, überzeugende Erklärung liefern - das sind die technischen Informationen, nach denen ich suche. Einigermaßen ist die "menschliche Interaktions" -Seite des Problems ebenso wichtig wie die technische (wenn nicht mehr).
Smarmy53
4

Ich werde mich kurz fassen:

Das Parsen der Cthulhu-Methode ist schwierig. Das ist das einfachste und überzeugendste Argument dagegen.

Es kann den Trick für einfache Sprachen tun; sagen wir, reguläre Sprachen. Es wird jedoch wahrscheinlich nicht einfacher sein als ein regulärer Ausdruck.

Es kann auch den Trick für ein bisschen komplexere Sprachen tun.

Ich würde mir jedoch einen Cthulhu-Parser für jede Sprache mit Verschachtelung oder nur "signifikantem Status" wünschen - mathematische Ausdrücke oder Ihr Beispiel (verschachtelte Funktionsaufrufe).

Stellen Sie sich vor, was passieren würde, wenn jemand versuchen würde, einen Parser für eine solche (nicht-triviale, kontextfreie) Sprache zu entwickeln. Vorausgesetzt, er ist schlau genug, einen korrekten Parser zu schreiben, würde ich wetten, dass er während des Codierens zuerst die Tokenisierung und dann die Analyse nach rekursiver Herkunft "entdeckt" - in irgendeiner Form.

Danach ist es ganz einfach: "Hey, sieh mal, Sie haben etwas geschrieben, das als rekursiver Abstiegsparser bezeichnet wird. Wissen Sie, dass es wie reguläre Ausdrücke automatisch aus einer einfachen Grammatikbeschreibung generiert werden kann?


Lange Rede, kurzer Sinn:
Das Einzige, was jemanden davon abhalten kann, den zivilisierten Ansatz anzuwenden, ist, dass er ihn nicht kennt.

Kos
quelle
1

Vielleicht ist es auch wichtig, an einer guten DSL-Semantik zu arbeiten (die Syntax ist wichtig, aber auch die Semantik). Wenn Sie mit diesen Themen nicht vertraut sind, empfehle ich Ihnen, einige Bücher zu lesen, z. B. Programmiersprachen Pragmatik (von M.Scott) und Christian Queinnec. Lisp in kleinen Stücken . Cambridge University Press, 1996.

Lesen Sie auch die neuesten Artikel in den DSL-Konferenzen, z. B. DSL2011 .

Das Entwerfen und Implementieren einer domänenspezifischen Sprache ist schwierig (und der größte Teil der Schwierigkeit besteht nicht im Parsen!).

Ich verstehe nicht wirklich, was du meinst, wenn du den Cthulhu-Weg analysierst . Ich nehme an, Sie wollen nur irgendwie bizarr analysieren.

Basile Starynkevitch
quelle
Gute Verbindungen. Cthulhu, sorry, ich habe den Link vergessen. Es ist ein Verweis auf einen klassischen Codinghorror-Artikel: codinghorror.com/blog/2009/11/parsing-html-the-cthulhu-way.html . Ich habe den ursprünglichen Beitrag aktualisiert.
smarmy53