BB-Code validierer

CDW

CDW

0
Mitarbeiter
Angeregt durch die Diskussion, dass theoretisches Wissen für einen Programmierer meistens nicht so wichtig ist :) eine kleine Aufgabe von mir:

Habo unterstüzt (wie so viele andere Boards) BB-Code. In dieser Aufgabe sei es auf und beschränkt.
Wir wollen prüfen, ob der Benutzer in seinem Post alle Tags korrekt geschlossen hat, bevor wir die Eingabe weiterschicken.

Vor dieser Prüfung läuft die Eingabe schon durch einen Skript, welches alle unerlaubten Zeichen usw rausschmeißt. Wir können uns also gänzlich auf das Problem konzentrieren und brauchen nicht nach verbotenen Zeichen usw zu filtern.
Natürlich fallen einem bei "Filteraufgaben" sofort RegExp ein ;). Schreibe also einen Schnipsel in Deiner Lieblingssprache, welches möglichst mittels einem regulären Ausdruck prüft, ob die Eingabe korrekt ist. BB-Code kann mehrfach verschachtelt werden!


Ich bitte mal alle, die die Lösung aus den Büchern kennen *wink mit dem Zaunpfahl an Studenten* sich herauszuhalten ;)

PS: Schwierigkeit3 gilt nur, wenn man RegExp nutzen möchte.
 
Hallo,
wie sieht es mit der Reihnfolge aus, wäre ein Code wie:
Text korrekt?

Wenn ja: Recht leicht zu lösen
Wenn nein: Würde es schon extrem schwer finden, vor allem wenn man nur RegEx nutzen soll.
 
Wir können das sogar gerne auf nur einschränken. Aber nicht vergessen: möglichst in nur einem RegEx ;)

PS: bitte nicht zuviel Zeit investieren. Das Ganze soll ein anschauliches Beispiel sein, warum Theorie doch ab und zu in der Praxis ne Menge Arbeit erspart ;)
 
Mal als Pseudocode, hab keine lust eine bestimmte Sprache zu bemühen :D

Code: 
OffeneTags = 0

Schleife: Für alle %aktuellesZeichen der Benutzereingabe

   Wenn ( aktuellesZeichen = "[" )
      Wenn ( aktuellesZeichen + 1 = "b" )
         Wenn ( aktuellesZeichen + 2 = "]" )
            OffeneTags++
      Sonst Wenn ( aktuellesZeichen + 1 = "/" )
         Wenn ( aktuellesZeichen + 2 = "b" )
            Wenn ( aktuellesZeichen + 3 = "]" )
               OffeneTags--

   Wenn ( OffeneTags < 0 )
      Error("Kein öffnendes Tag gefunden")

Schleifenende

Wenn ( OffeneTags > 0)
   Error("Es wurde mindestens ein Tag nicht geschlossen")

Und nun bin ich am Grübeln, wie man soetwas mit regulären Ausdrücken hinbekommen soll. Es ist natürlich leicht zu überprüfen, ob es zuviele offene oder zuviele schließende Tags gibt, aber wie bekommt man heraus, ob irgendwo ein schließendes Tag ist, obwohl es vorher kein Öffnendes gab?...
 
Hi,

hier mal meine Lösung in C#
Code: 
using System;

namespace regex
{
	class Program
	{
		public static void Main(string[] args)
		{			
			string bbcode = "[b]a[/b]ds[b]ssv[/b][b]a[b]sd[/b]";
			string pattern = @"(\[b\][ -Z\\-~]*(?<!\[b\])\[/b\])|(\[.?b\]?)";		
			System.Text.RegularExpressions.MatchCollection matches = System.Text.RegularExpressions.Regex.Matches(bbcode, pattern);
			
			// Alle Matches durchlaufen
			foreach(System.Text.RegularExpressions.Match match in matches) {
				// Wenn Gruppe 2 (Gruppe 1 ist immer der gesammte text) nicht zutrifft, muss es ein einzelnes BB Tag gewesen sein.
				if(!match.Groups[1].Success) {
					Console.WriteLine("BB-Code not valide");
					break;
				}
			}			
			
			Console.WriteLine("Press any key to continue . . . ");
			Console.ReadKey(true);
		}
	}
}
Hat aber ein Manko, Tags ohen inhalt werden als Fehler interpretiert.

Edit: Hab übersehen das BB-Code mehrfach verschachtelt sein kann (also <B>text<b>text</b>text</b> ?) , damit is meine Lösung für die Katz.

Edit2:
Man könnte natürlich die einzelnen <b>|</b> Tag matches counten aber ich denke das verfehlt den Sinn der Übung .?.
Code: 
using System;

namespace regex
{
	class Program
	{
		public static void Main(string[] args)
		{			
			string bbcode = "[b][/b]ds[b]ssv[/b][/b][b]asd[/b]";
			string pattern = @"(\[b\])|(\[/b\])";		
			System.Text.RegularExpressions.MatchCollection matches = System.Text.RegularExpressions.Regex.Matches(bbcode, pattern);
			
			// Alle Matches durchlaufen
			int openTags = 0;
			int closeTags = 0;
			foreach(System.Text.RegularExpressions.Match match in matches) {
				// Gruppe 2 = offenes Tag ; Gruppe 3 = geschlossenes Tag
				if(match.Groups[1].Success) {
					openTags++;
				}
				else {
					closeTags++;
				}
			}			
			if(openTags != closeTags)
				Console.WriteLine("BB-Code not Valide");
			
			Console.WriteLine("Press any key to continue . . . ");
			Console.ReadKey(true);
		}
	}
}
MfG
 
Die Auflösung ist (so doof es sich auch anhört), man kommt hier mit RegEx nicht weiter. Sprich: es ist nicht möglich, denn es exitiert kein regulärer Ausdruck, der diesen Sachverhalt allgemeingültig beschreiben kann. Man kann mittels RegExp nun mal nicht zählen oder sich etwas merken - ein RegEx kennt nur ein einzelnes Zeichen.

Anschaulich erklärt:
http://de.wikipedia.org/wiki/Reguläre_Sprache

Eine reguläre Sprache kann durch einen regulären Ausdruck beschrieben werden, durch eine reguläre Grammatik oder durch einen DFA/NFA (non/deterministic finite automaton).
Sprich: sobald man eine der 3 Darstellungen gefunden hat, weiß man, dass ein Sachverhalt regulär ist.

Beispiel: wir wollen einen Text suchen, in dem zwei mal ein a gefolgt von mindestens einem und beliebig vielen bs vorkommt. Gibt es dazu einen regulären Ausdruck? Wenn man das Problem mit einem NFA lösen kann, weiß man, dass es auch als regulärer Ausdruck darstellbar ist (und zwar kann man diesen aus der NFA Darstellung ablesen):
Code: 
                                      ,------.
  ,-----.                         ,--+.       :
 /       \    a     ,-.    a     /     \      |b
( Start   .........>   ) .....> ( Ende  )     |
 \       /          `-'          \     /      ;
  `-----'                         `---\      /
                                       `----'

Die aktuelle Aufgabe kann man nun so zusammenfassen: bezeichne den Code [ b ] mit a , den Code [ /b ] mit b und die ganze Resteingabe mit c. Wir haben:
a^n c* b^n mit n>=0 (das ^ Zeichen bedeutet hier: soviele Wiederholungen).

Sprich: wir müssen genausoviele bs wie as erkennen. Und dazu müssten wir uns irgendwie merken, wieviele davon wir gelesen haben.
Am anschaulichsten ist es, wenn man versucht den DFA/NFA dazu zu zeichnen: ein endlicher Automat kann sich weder merken was er bereits gelesen hat noch wieviel davon. Natürlich kann man bis zu einer gewissen Größe auch sowas erkennen:
Code: 
  ,-----.                         ,--+.
 /       \   a    ,-.<-.         /     \
( Start   -.....>.   )  :c    b ( Ende  )
 \       /        `+'   ; ``````>\     /
  `--+--'           `--'          `-+-
     |a                             ^
     |                              |b
     v            ,-.<-.            |
    ,+.      c   (   )  :c     c   ,+.
   (   ) -------->`+'   ; .......>(   )
    `+'             `--'           `+'
     |                              ^
     |a                             |b
     v                              |
    ,+.     c     ,-.<-.     c     ,+.
   (   )-------->(   )  :c ......>(   )
    `+'           `+'   ;          `+'
     |              `--'            ^
     |a                             |b
     v             ,-.<-.           |
    ,+.     c     (   )  :c    c   ,+.
   (   )'''''''''>'`+'   ;------->(   )
    `-'              `--'          `-'
und so weiter, für jede gewünschte Verschachtelungstiefe eben noch eine Ebene hinzufügen  (wobei hier der Fall für c=1 fehlt, aber dann müsste ich neu zeichnen ;) )
RegExp dafür wäre:
ac*b|acc*cb|aacc*cbb|aaacc*cbbb
Damit erkennt man bis zu 3 fach verschachtelte Tags
D.h wenn man nur bestimmte Verschachtelungstiefe erkennen möchte, kann man durchaus eine Regex nutzen. Nur dass es alles andere als effizient sein wird - und bei dem Versuch, einen allgemeingültigen Ausdruck zu finden, verschendet man nur seine Zeit ;).

Genauso "einsichtig" ist es, wenn man versucht das Ganze mittels regulärer Grammatik zu beschreiben, allerdings wäre das hier etwas zuviel des Guten ;)

Formell lässt sich mittels dem Pumping-Lemma auch beweisen, dass dieses Problem nicht regulär beschrieben werden kann (naja, formell ist es auch die einzig tragbare Lösung - sonst kann man ja auch sagen: "nee, nur weil DU keinen reg. Ausdruck finden kannst, heißt es noch lange nicht, dass es keinen gibt!". Ist sogar die "Musteraufgabenstellung" im Beispielbeweis der Wikipedia ;)

Zum Problem selbst: das sollte in die Klasse kontextfreier Sprachen fallen und lässt sich z.B mittels einem Kellerautomaten lösen. Und zwar gleich mit Beachtung der Reihenfolge [ i ][ b ]Text[ /b ][ /i ] :
ein Algorithmus wäre z.B
Code: 
1.solange zeichen da sind -> lese_zeichen:
  wenn zeichen=[ b ] push stack ' [ /b ]'
   wenn zeichen=[ i ] push stack  '[ /i ]'
   wenn zeichen=[ /b ]  muss auch  pop stack='[ /b ]' sein, sonst fehler
   wenn zeichen=[ /i ] muss auch pop stack='[ /i ]' sein, sonst fehler
   wenn zeichen was anderes gehe zu 1.

keine_zeichen_da: ist stack nicht leer->fehler
(nicht allzu kritisch sein, ist schon länger her, dass ich Kellerautomaten machen durfte)

Wozu die ganze Quälerei nun soll: wie gesagt, der Auslöser war eine Diskussion heute auf dem Board - allerdings gab es auch vorher schon Posts, die in dieselbe Richtung gingen.

Man beachte übrigens die Formulierung "möglichst mittels einem regulären Ausdruck prüft" und "Schwierigkeit3 gilt nur, wenn man RegExp nutzen möchte". Es wurde also niemand wirklich gezwungen, RegExp zu verwenden :)

Es gibt noch einiges mehr an Beispielen (sobald man über triviale Aufgaben hinausgeht), die zwar mit gewohnten Mitteln relativ leicht lösbar ausschauen, es aber definitiv nicht sind. Es lohnt sich daher auch vorher nachzuforschen, ob die Aufgabe auch wirklich so lösbar ist.
Sonst gilt "2 hours of trial and error can save 10 minuts of manual reading" ;). Zudem sollte es auch eine Anregung/Argument sein, nicht nur "lernen durch Ausprobieren" zu betreiben.
 
Hallo,
also mit nur 1 RegEx geht es nicht, was auch nicht notwendig ist.

Dennoch gibts eine recht simple Lösung, wenn man nur mit RegEx arbeitet.

Wenn nur [ b] erlaubt ist, geht folgender PHP Code:
PHP: 
<?php
$text = "Dies [b]ist[/b] ein [b] kleiner [b]Text[/b][/b] mit richtiger Syntax";

while(preg_match("/\[b\](.*?)\[\/b\]/si", $text) > 0)
	$text = preg_replace("/\[b\](.*?)\[\/b\]/si", "$1", $text);


$syntax_check = preg_match("/\[(\/|)b\]/si", $text);


echo $text."<br>";
echo "Richtige Syntax: ".(($syntax_check > 0) ? "Nein" : "Ja");
?>


Wenn man [ b][ i]Text[ /b][ /i] als richtig ansieht, geht folgender Code:
PHP: 
<?php
$text = "Dies [b]ist[/b] ein [b] kleiner [i]Text[/b][/i] mit richtiger Syntax";

while(preg_match("/\[b\](.*?)\[\/b\]/si", $text) > 0)
	$text = preg_replace("/\[b\](.*?)\[\/b\]/si", "$1", $text);

while(preg_match("/\[i\](.*?)\[\/i\]/si", $text) > 0)
	$text = preg_replace("/\[i\](.*?)\[\/i\]/si", "$1", $text);



$syntax_check = preg_match("/\[(\/|)(b|i)\]/si", $text);


echo $text."<br>";
echo "Richtige Syntax: ".(($syntax_check > 0) ? "Nein" : "Ja");
?>
 
also mit nur 1 RegEx geht es nicht
Zum Vergrößern anklicken....
Hm, will ich nicht wahrhaben :/

In perl können regexes ja auch rekursiv verschachtelt werden, damit kann man zum Beispiel gut mit Klammerungen arbeiten:
The following pattern matches a parenthesized group:

Code: 
  $re = qr{
	     	     \(
	     	     (?:
				(?> [^()]+ )	# Non-parens without backtracking
	      	      |
				(??{ $re })	# Group with matching parens
	     	     )*
	     	     \)
	  	  }x;
Zum Vergrößern anklicken....
von hier.

Das (?>...) Konstrukt ist afaik nur ein performance-Booster. Das (??{ $re }) Dingens sorgt dafür, dass der Inhalt in den Curly-Braces erst zur Laufzeit evaluiert wird und vor allem nicht bereits bei der Zuweisung. (Da hat es ($re) nämlich noch gar keinen Wert, da die right-hand-side zuerst evaluiert wird..)
Und (?: ... ) bedeutet nur "speichere den Inhalt dieser Klammer nicht in einer Extra-Variablen" ($n).

Klar, mit bb-Code wird das ganze etwas komplizierter, weil man nicht einfach eine negierte char-class nehmen kann wie [^()], weil bb-code Tags halt keine einzigen Zeichen, sondern mehrere sind. Aber mit lookahead sollte das auch möglich sein. Freiwillige vor! (Oder sagt mir, wo mein Denkfehler liegt.)


edit:
Hier mal für ein html-Tag, weil das syntaktisch weniger mit regulären Ausdrücken in Konflikt steht wie bb-Code-Tags und damit der Ausdruck etwas übersichtlicher ist:
Code: 
#!/usr/bin/env perl
use warnings;

$noHTMLTagChars = qr{(?: [^<] | < (?!/?html>) )*}xms;

$validHTMLTag = qr/^(??{ $noHTMLTagChars })
                        <html>
                        (?:
                            (??{ $noHTMLTagChars })
                            |
                            (??{ $validHTMLTag })
                        )
                        <\/html>
                    (??{ $noHTMLTagChars })$
                  /xms;

print "_" x 100, "\n";

while (<DATA>) {
    chomp;
    print "-" x 40, "\n";
    if (/$validHTMLTag/) {
        print "$_\nTags well balanced!\n";
    }
    else {
        print "!!! $_ !!!\nERROR in Tag count!\n";
    }
    print "-" x 40, "\n";
}

print "_" x 100, "\n";

__DATA__
Diese Zeile <html> hat ein balanciertes </html> HTML-Tag Verhältnis.
This <html> line </html> has too many closing </html> Tags!
This <html> line <html> does </html> not!
Und natürlich hätte man den Ausdruck für "$noHTMLTagChars" auch direkt in den Validierungs-Ausdruck schreiben können (dann wärs ganz kleinlich gesehen wirklich nur einer), aber dann wird das ganze verdammt unübersichtlich..

edit: hmpf, für "<html> foo <html> bar </html> blub </html>" funktioniert es schon wieder nicht. Wer will debuggen? (Ich bleibe aber dabei, dass es mit Rekursion theoretisch möglich sein müsste!)
 
Das (??{ $re }) Dingens sorgt dafür, dass der Inhalt in den Curly-Braces erst zur Laufzeit evaluiert wird
Zum Vergrößern anklicken....
Meinst Du wirklich, ein Konstrukt bei dem beim Matchen eine Unterprozedur aufgerufen wird, wäre immer noch eine RegEx ? ;) Oder doch etwas, in eine RegEx eingebettet ;) ? Denn letzendlich dient hier der Stack als "Counter"/"Speicher" und nach jedem Match wird das alte Ergebnis in diesem Speicher festgehalten.

Edit:
edit: hmpf, für "<html> foo <html> bar </html> blub </html>" funktioniert es schon wieder nicht. Wer will debuggen? (Ich bleibe aber dabei, dass es mit Rekursion theoretisch möglich sein müsste!)
Zum Vergrößern anklicken....
Rekursion gehört nicht in regulare Expression rein, weil diese keinen Speicher haben ;).
RegEx mit Speicher=~Kellerautomat (kann natürlich mehr erkennen) :)
 
(??{ code })

This is a "postponed" regular subexpression. The code is evaluated at run time, at the moment this subexpression may match. The result of evaluation is considered as a regular expression and matched as if it were inserted instead of this construct.
Zum Vergrößern anklicken....
Naja, es ist ja kein-random perlcode, der ausgeführt wird, sondern es handelt sich schon um einen regulären Ausdruck. Und damit kann man dann halt rekursiv matchen \o/
(Nicht, dass mans brauchen würde, aber toll isses.)

Und da perl die dicksten Eier hat was reguläre Ausdrücke angeht, finde ich darf perl auch entscheiden, was ein Regulärer Ausdruck ist und was nicht. Und im perl 5.8.8 Sinne ist es (mein leider dysfunktionales Beispiel) eine.

Mir gings ja auch nur ums klugshicen. Und da die regex-Engine an sich keinen Rekursionsstack hat (respektive natürlich schon, nämlich fürs backtracken, aber halt nicht in dem hier gemeinten Sinne) muss ich dir wohl Recht geben.
 
Original von MontyPerl
Und da perl die dicksten Eier hat was reguläre Ausdrücke angeht, finde ich darf perl auch entscheiden, was ein Regulärer Ausdruck ist und was nicht.
Zum Vergrößern anklicken....

Warum? Ein regulärer Ausdruck hat per se ja nichts mit irgendwelchen Programmiersprachen zu tun, sondern ist ein Begriff der theoretischen Informatik und gültiger BB-Code ist keine reguläre Grammatik(Typ 3 der Chomsky-Hierarchie), daher auch nicht als regulärer Ausdruck darstellbar, egal was Perl dazu sagt.
 
Warum? Ein regulärer Ausdruck hat per se ja nichts mit irgendwelchen Programmiersprachen zu tun, sondern ist ein Begriff der theoretischen Informatik
Zum Vergrößern anklicken....
Oha, du hast Recht. Mir ist entfallen, dass wir uns hier im Theoretische-Informatik-Subforum befinden und nicht etwa in einem Kontext in dem "RegExp" sich eher auf konkrete Implementierungen von Regexes bezieht als auf die Lehrbuchdefinition selbiger (welche btw bereits von sed mit seinen backreferences transzendiert wird).

Larry (teh) Wall zum Thema:
Many features found in modern regular expression libraries provide an expressive power that far exceeds the regular languages. [...]
However, many tools, libraries, and engines that provide such constructions still use the term regular expression for their patterns. This has led to a nomenclature where the term regular expression has different meanings in formal language theory and pattern matching. For this reason, some people have taken to using the term regex or simply pattern to describe the latter. Larry Wall (author of Perl) writes in Apocalypse 5:
? 'Regular expressions' [...] are only marginally related to real regular expressions. Nevertheless, the term has grown with the capabilities of our pattern matching engines, so I'm not going to try to fight linguistic necessity here. I will, however, generally call them "regexes" (or "regexen", when I'm in an Anglo-Saxon mood).?
Zum Vergrößern anklicken....
Zum Vergrößern anklicken....
Das in diesem Thread nur die Lehrbuchdefinition gültig ist hätte man eventuell im Initialpost erwähnen sollen um dieser linguistischen Ambivalenz präventiv entgegen zu wirken.
 
Ok, wenn wir schon anfangen zu klugscheiß0rn ;) :
http://perldoc.perl.org/perlre.html
Recursing deeper than 50 times without consuming any input string will result in a fatal error. The maximum depth is compiled into perl, so changing it requires a custom build.
Zum Vergrößern anklicken....
d.h real und produktiv sollte man das noch nicht einsetzen.

Es geht ja nun letzendlich nicht darum, ob man nun ums Verrecken das mit einem RegEx hinkriegt - sondern um die Frage, ob (?)die Theorie in der Praxis eine Rolle spielt. Monty hat zwar eindrucksvoll bewiesen, dass Perl inzwischen sehr viel mit RegEx anfangen kann - allerdings scheint auch mit Perls Features die Lösung mittels "RegEx" nicht so ganz optimal zu funktionieren und nur schwer auf Richtigkeit überprüfbar zu sein ;).
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben