Kleines Softwarerätsel
Da ich gerade an meinen Anwendungen herumbastele und das nicht so sehr mit Blogs unterbrechen will, habe ich mir heute als Verschnaufpause für euch zum Lesen ein kleines Rätsel überlegt.
Es wendet sich an alle die schon mal programmiert haben (die können sicher auflösen) oder in Berührung mit Werkzeugen eines bestimmten Betriebssystems oder bestimmten Programmiersprachen gekommen sind, die das hier gesuchte weidlich ausnützen:
Bei welchem Algorithmus kann man unterscheiden ob er „gierig“ oder „genügsam“ ist?
Zusatzfrage; (Jetzt nur zum raten). Wo in meinen Programmen (Liste siehe hier) setze ich das ein, bzw. arbeite ich gerade),beim schreiben der Hilfe kam ich auf die Idee)
Damit können eigentlich nur Regular Expressions gemeint sein.
Bei deinen Programmen kann ich mir kaum eines vorstellen, bei dem keine RegExps zum Einsatz kommen.
Bei regulären Ausdrücken die repetition Operatoren * (Stern) und (Plus).
SmartMove
SmartEditor
SmartSearch *
und vermutlich ein paar mehr.
Richtig!
Derzeit arbeite ich am Smarteeditor, der nach einigen Jahren ein Facelift bekommt, noch etwas bedienungsfreundlicher und leistungsfähiger wird.
Mit der Problematik des gierigen Ausdrucks kam ich im vierten semester in Berührung, als wir bei Compilerbau einen Mini-Crosscompiler für Pascal in C mit Hilfe von Lex und Yacc erstellen mussten.
LEX benutzt auch reguläre Ausdrücke und die Regel für Pascalkommentare war:
\(\*.*\*\)
Ein Pascalkommentar beginnt mit (*, gefolgt von beliebigen Zeichen und wird abgeschlossen durch ein *). Die Backslashes braucht man um die Zeichen (* als Literale zu interpretieren.
der gierige Modus bedeutet, der Algorithmus versucht so viele Zeichen wie möglich zu bekommen, dass der Ausdruck passt. Hatte man in einem Programm zwei Kommentare wie hier:
dann markierte der „gierige“ Algorithmus von Yacc alles zwischen „(* ein “ und „kommentar *), also schluckte einen gute Teil des Quelltextes. Ich brauchte einige Zeit bis ich das rausfand. Der genügsame Algorithmus stoppt dagegen beim ersten vollständigen Treffer, liest also so wenige Zeichen wie möglich, das ist meist das gewünschte
Yacc kannte keinen genügsamen Mode, deswegen schrieb man zum Parsen lieber ein Stückchen C-Code, das man als Regel einfügen konnte wenn die anfangssequenz des Kommentars matcht.
Moin,
reguläre Ausdrücke sind ein interessanter Benchmark, der beweist dass in jedem nicht Trivialen Programm ein Lisp Interpreter versteckt ist.
Nicht Perl, PHP oder C hat die schnellsten Perl Compatiblem regulären Ausdrücke, sondern GNU Clisp, CMUCL/SBCL und andere schnelle Lisp Interpreter, da in Lisp der reguläre Ausdruck on the Fly nach Lisp übersetzt wird, und dann die hochoptimierte Lisp Maschine jedem anderen Regexp-Interpreter davonläuft. Clisp spielt dabei die Stärke seines schnell Bytecode Interpreter aus, während CMUCL/SBCL noch einen drauf setzen, weil das Lisp in Maschinensprache Just in Time übersetzt wird.
ciao,Michael
Interessant. – Da sieht man (bzw. ich) mal wieder, dass Informatikthemen bei mir im (E-Technik) Studium eben Nebenfächer waren, was aber eigentlich auch nicht wundern sollte. Folglich hab ich von diesem Algorithmus bisher noch nix gehört. Und Lex/Yacc hab ich auch noch nie gebraucht.