{"id":2177,"date":"2009-01-12T16:27:06","date_gmt":"2009-01-12T15:27:06","guid":{"rendered":"https:\/\/www.herr-rau.de\/wordpress\/?p=2177"},"modified":"2023-05-10T09:34:16","modified_gmt":"2023-05-10T07:34:16","slug":"formale-sprachen-teil-2-regulaere-sprachen","status":"publish","type":"post","link":"https:\/\/www.herr-rau.de\/wordpress\/2009\/01\/formale-sprachen-teil-2-regulaere-sprachen.htm","title":{"rendered":"Formale Sprachen, Teil 2: Regul\u00e4re Sprachen"},"content":{"rendered":"
(16 Kommentare.<\/a>)<\/small> <\/div>\n

Das ist die Fortsetzung dieses Eintrags<\/a>.<\/em><\/p>\n\n\n\n

Heute will ich einen Einblick geben dar\u00fcber, was eine Sprache vom Typ Chomsky 3 ausmacht. Diese Sprachen hei\u00dfen regul\u00e4re Sprachen<\/strong>, sie k\u00f6nnen durch eine regul\u00e4re Grammatik (oder durch einen regul\u00e4ren Ausdruck) beschrieben werden. Mit einem endlichen Automaten kann man \u00fcberpr\u00fcfen, ob ein Wort zu einer Sprache geh\u00f6rt oder nicht.<\/p>\n\n\n\n

Vorweg: Ich bin mir sicher, dass sich der eine oder andere Fehler eingeschlichen hat, und bin um Berichtigung dankbar. Vor allem regul\u00e4re Ausdr\u00fccken kenne ich nur aus der theoretischen Informatik, und mit der praktischen Anwendung in Perl-Syntax kenne ich mich nur wenig aus; \u00fcber backreferences schreibe ich gar nichts. Ist ja auch kein RegEx-Tutorial.<\/small><\/p>\n\n\n\n

1. Regul\u00e4re Ausdr\u00fccke<\/h3>\n\n\n\n

Am bekanntesten ist wohl der regul\u00e4re Ausdruck (regular expression, RegEx), auch wenn der Begriff vielleicht nicht jedem etwas sagt. Deshalb drei Beispiele.<\/p>\n\n\n\n

1. Wenn ich in Spam Karma<\/strong>, einem verbreiteten Anti-Spam-Plugin f\u00fcr Wordpress, eine Spam-Quelle auf die Blacklist setzen m\u00f6chte, dann geschieht das \u00fcber einen regul\u00e4ren Ausdruck. M\u00f6chte ich zum Beispiel alle Kommentare als Spam markieren lassen, die das Wort „Sex“ enthalten, dann gebe ich in Spam Karma im entsprechenden Feld ein: \/Sex\/. (Die Schr\u00e4gstriche m\u00fcssen sein, weil so in Perl-Syntax ein regul\u00e4rer Ausdruck markiert wird.)
Nun kann es aber sein, dass findige Leute die Blockierung umgehen, indem sie stattdessen das Wort „Seeex“ benutzen. Ich k\u00f6nnte nat\u00fcrlich nacheinander \/Sex\/, \/Seex\/, \/Seeex\/ und so weiter sperren, aber das w\u00e4re viel Arbeit. Stattdessen kann ich \/Se+x\/ schreiben. Das Pluszeichen gibt an, dass das Zeichen davor beliebig oft, aber mindestens einmal, erscheinen kann. \/Se+x\/ beschreibt also die Sprache, die aus den W\u00f6rter {Sex, Seex, Seeex, Seeeex, Seeeeex …} besteht.<\/p>\n\n\n\n

2. Ein weiteres Beispiel betrifft Hotlinking<\/strong>. So hei\u00dft das,wenn zum Beispiel jemand ohne meine Erlaubnis eines der Bilder auf meiner Webseite bei sich in seiner Seite einbaut – und zwar nicht etwa eine bei sich gespeicherte Kopie des Bildes, sondern direkt meine verlinkt. (Gerne geschieht das bei Foren-Bildchen.) Das macht man aus verschiedenen Gr\u00fcnden nicht. Je nach Lust und Laune sperre ich diese M\u00f6glichkeit manchmal, oder sorge daf\u00fcr, dass statt des eigentlich anvisierten Bildes und trotz dessen korrekter Adresse ein ganz anderes Bild bei der fremden Seite angezeigt wird. M\u00f6glich macht das eine Datei, die .htaccess hei\u00dft, die uns hier nicht weiter interessieren soll. In dieser Datei steht dann zum Beispiel, dass Browseranfragen von folgender Adresse ignoriert oder umgeleitet werden sollen:<\/p>\n\n\n\n

\n

(www\\.)?frecherhotlinker\\.(de|com)<\/strong><\/p>\n<\/blockquote>\n\n\n\n

Das Fragezeichen hei\u00dft, dass das Element davor – also das in den Klammern – ein oder keinmal auftauchen kann, der gerade Strich am Schluss hei\u00dft, dass entweder das Element links oder das rechts davon erscheinen kann. Der regul\u00e4re Ausdruck schlie\u00dft also folgende Adressen ein: {www.frecherhotlinker.de, www.frecherhotlinker.com, frecherhotlinker.de, frecherhotlinker.com}. — Der Schr\u00e4gstrich vor dem Punkt hei\u00dft nur, dass der Punkt tats\u00e4chlich als Punkt betrachtet werden soll. Sonst ist der Punkt n\u00e4mlich die Abk\u00fcrzung f\u00fcr „beliebiges Zeichen“, das man sonst umst\u00e4ndlicher als (a|b|c|d|1|2|3|…) schreiben m\u00fcsste.<\/p>\n\n\n\n

3. Die Suchfunktion<\/strong> unter Open Office und anderen Textverarbeitungsprogrammen benutzt auch regul\u00e4re Ausdr\u00fccke. Ich kann suchen\/ersetzen nach „grey“ oder „gray“, indem ich den regul\u00e4ren Ausdruck „grey|gray“ verwende. Ich kann suchen nach „favour“ oder „favor“, indem ich entweder „favour|favor“ verwende, oder „fav(o|ou)r“, oder „favou?r“. Das Fragezeichen hei\u00dft auch hier: erscheint 0 oder 1 mal.
(Open Office: Bei der Suchfunktion unter „Mehr Optionen“ das K\u00e4stchen „regul\u00e4rer Ausdruck“ ankreuzen. Keine Schr\u00e4gstriche am Anfang und Ende machen.)<\/p>\n\n\n\n

Etwas komplizierter: Ich will in einem Text alle geklammerten Ausdr\u00fccke l\u00f6schen. Dazu kann ich unter Open Office nach folgendem Ausdruck suchen: \\(.*\\) – dabei steht . f\u00fcr beliebiges Zeichen, * f\u00fcr eine beliebige Wiederholung solcher Zeichen, und (.*) hei\u00dft dann, dass links und rechts davon eine Klammer stehen soll. Die Schr\u00e4gstriche m\u00fcsssen dummerweise sein, weil die Klammern in RegEx-Syntax ja selber schon eine Sonderfunktion haben; die Schr\u00e4gstriche teilen dem Programm mit, dass hier wirklich nur einfache echte Klammern gemeint sind. Aber aufgepasst: dieser Ausdruck umfasst innerhalb eines Absatzes auch Kombinationen wie: (aaa) bbb (aaa)<\/em>, wo man eigentlich die b’s<\/em> in der Mitte nicht mit gemeint hat. Mehr zu Klammern beim n\u00e4chsten Mal.<\/small><\/p>\n\n\n\n

Auch sonst tauchen regul\u00e4re Ausdr\u00fccke an allen m\u00f6glichen Ecken und Enden des Computers auf. Generell gilt: Mit einem RegEx kann man verschiedene Arten von W\u00f6rtern herausfiltern oder suchen.
Von einer anderen Perspektive aus betrachtet, hei\u00dft das: Alle W\u00f6rter, die zu dem RegEx passen, geh\u00f6ren zu einer Sprache. Ich will ein paar Beispiele geben. Weil es \u00fcbersichtlicher und einfacher ist, beschr\u00e4nke ich mich auf das Alphabet {a, b, c}<\/strong>. Ich will mich auch auf einige wenige RegEx-K\u00fcrzel beschr\u00e4nken: |<\/strong> hei\u00dft „oder“, *<\/strong> hei\u00dft: beliebig oft (auch keinmal).<\/p>\n\n\n\n