[RegExp] Parsing van UBB-tags met korte eindtags

[Verwijderd]

Hallo devvers

Ik zit met een ontwerpprobleem waar ik niet zo heel snel uit kom. Ik hoop dat jullie me wat inzichten kunnen geven hoe ik dit probleem het beste kan tackelen.


Beoogd doel
Ik wil door middel van Perl Compatible Regular Expressions (PCRE) in PHP een parser maken die de volgende code omzet naar HTML-style tags, gebruikmakende van korte eindtags:

[b][i]bla[/][/]
naar:
<b><i>bla</i></b>


Het probleem
Bovenstaand voorbeeld is simpel zat en zonder gebruik te maken van korte eindtags is dat ook simpel te implementeren. Het probleem ontstaat wanneer ik korte eindtags wil gebruiken (dus: [/]) omdat de volgorde van parsing dan verkeerd kan lopen.

Gebruik ik greedy parsing, dus de regular expression grijpt zo'n lang mogelijke string, dan kan de parsing er zo uitzien wanneer de [i]-tag als eerste wordt geparsed:
<b><i>bla</b></i>

Andersom kan bij ungreedy parsing (zo'n kort mogelijke match) de [b]-tag ervoor zorgen dat het zaakje eveneens wordt geparsed als:
<b><i>bla</b></i>

Uiteraard wil ik de juiste volgorde aanhouden, het moet worden:
<b><i>bla</i></b>

Ook de volgorde van het parsen mag niets uitmaken. Het moet dus ook werken als ik:
[i][b]bla[/b][/i]
wil parsen naar:
<i><b>bla</b></i>


Mogelijke oplossingen
Greedy of ungreedy parsing gaat me hier niet bij helpen. De enige oplossing die ik kon verzinnen is om het parsen in meerdere stappen te doen, en de regexp zo te schrijven dat er tussen de [b]...[/b] geen andere tags zoals [i] mogen voorkomen. Het gevolg is dat tags eigenlijk seriëel geparsed moeten worden, totdat de laatste iteratie geen matches meer oplevert.

Dit is echter wel een complexere en tragere oplossing. Weten jullie een betere? Tweakers.net heeft dit zelf zo in gebruik. Ik hoef geen code te zien, maar wat hints voor ontwerp en aanpak zou wel welkom zijn!


Alvast heel erg bedankt voor het meedenken!

[R4gnax]

Verwijderd schreef op zaterdag 24 augustus 2013 @ 14:50:
Dit is echter wel een complexere en tragere oplossing. Weten jullie een betere? Tweakers.net heeft dit zelf zo in gebruik. Ik hoef geen code te zien, maar wat hints voor ontwerp en aanpak zou wel welkom zijn!

Rauwe regular expressions zijn hier niet toereikend voor. Een simpele recursive descent parser is wat je hier wilt hebben. (Eventueel kan deze nog deels via verschillende regular expressions zijn werk doen.)

[ Voor 13% gewijzigd door R4gnax op 24-08-2013 15:16 ]

[Verwijderd]

De oplossing die ik geef zou toch kunnen? Ik doe het natuurlijk niet allemaal in één regexp, maar gebruik PHP om de parsing in stapjes te doen met regexp-loops.

Wat bedoel je precies met een 'descent parser' ?

Recursief is denk ik wat ik bedoel met regexp in stapjes (serieel) totdat er geen matches meer zijn.

Simpel voorbeeld hoe mijn parsing nu werkt:

code:

 $patt[] = '/\[b\](.*)\[\/b\]/Usm';
 $repl[] = '<b>$1</b>';
 $msg = preg_replace($patt, $repl, $msg);

[Zoijar]

Schrijf gewoon zelf een parser die je text afgaat en vervangt zo nodig. Die kan dan zelf state bijhouden. Simpele regexen kunnen geen html-like input parsen. Nu parse je ook onnodig vaak je hele tekst; dat zal ook niet echt efficient zijn. Dan houd je in je parser de laatst geopende tag bij, en als je een [/] vindt en er is een tag open, dan sluit je die. (Dan hou je je open tags op een stack bij.)

Als je het echt 'pro' wilt doen kan je kijken naar iets als ANTLR. Geweldige software en helemaal niet zo moeilijk.

Dus in het simpelste geval:

in: <i><b>x</><b>y</></>
- ik zie een <i> schrijf <i> en push <i> : out <i>, stack </i>
- ik zie een <b> schijf <b> push <b> : out <i><b>, stack </i> </b>
- ik zie tekst schrijf : out <i><b>x, stack </i></b>
- ik zie closing tag, pop stack en close die : out <i><b>x</b>, stack </i>
- ik zie <b>, push en schrijf : out <i><b>x</b><b>, stack </i></b>
- ik zie tekst : out <i><b>x</b><b>y, stack </i></b>
- ik zie close tag, pop stack : out <i><b>x</b><b>y</b>, stack </i>
- ik zie close tag, pop stack: out <i><b>x</b><b>y</b></i>, stack leeg (succes)

(Het feit dat je op zo'n manier een stack gebruikt/nodig hebt is precies de rede dat een simpele regex dit niet kan.)

[ Voor 59% gewijzigd door Zoijar op 24-08-2013 16:14 ]

[Gomez12]

Het ontwerpprobleem zit in het feit dat je regex wilt gebruiken op iets wat niet regular is.

Je kunt zoals Zoijar aangeeft een stack-based parser gaan bouwen of je kan 1 van 1000'en bestaande UBB-parsers pakken.

[drm]

Gomez12:
Het ontwerpprobleem zit in het feit dat je regex wilt gebruiken op iets wat niet regular is.

[Verwijderd]

drm schreef op zaterdag 24 augustus 2013 @ 19:58:
[...]

Wikipedia: Chomsky hierarchy

[Voutloos]

Alhoewel veel regex implementaties stiekem meer kunnen dan dat, aangezien ze features als backreferences en lookahead/-behind hebben.

Hoewel het aanvankelijk meer werk dan 'ff een handjevol regexes bij elkaar prakken' lijkt, is een stack based parsertje the way to go. Bovendien kost t puntje bij paaltje echt niet meer tijd, en win je bij elke bug of change weer.

[Saven]

beetje n bump maar zou je niet zoiets kunnen doen? :

PHP:

    $patt[] = '/\[b\](.*)\[(\/b|\/)\]/Usm';

Dus dan geef je elke regex 2 opties om af te sluiten.

[CyBeR]

Nee, want dat houdt geen rekening met het kunnen nesten van tags. Dit is zoals gezegd iets waar regexp uitermate ongeschikt voor is.

[Verwijderd]

Zoijar schreef op zaterdag 24 augustus 2013 @ 15:36:
Schrijf gewoon zelf een parser die je text afgaat en vervangt zo nodig. Die kan dan zelf state bijhouden.

Dus een soort character-by-character parser ofzo? Het is me nog een beetje onbekend hoe ik dat nu moet uitwerken. Ik zou dan een soort pointer moeten hebben op welke locatie ik ben met parsen van de input text en 'vooruit' moeten kijken of ik iets kan matchen, ofzo.

Je voorbeeld van stack enzo is me wel duidelijk. Het voordeel is natuurlijk dat je maar één keer de hele tekst hoeft te doorlopen. Echter, ik zie wel een probleem met als er niet voldoende eindtags zijn. Bij regexp kan ik de tags dan gewoon als text parsen dus dan ziet de gebruiker dat er een foutje in zijn code zit, zoals een vergeten eindtag. Maar met zo'n stack parser blijf ik dan op het einde met een niet-lege stack zitten. Om het dan HTML-correct op te leveren kost ook weer wat complexiteit.

Ik zie wel de voordelen van dit systeem, maar ben ook huiverig. Voor mij is het iets meer onbekend terrein.

Ik blijf benieuwd naar de oplossing die ik zelf voor ogen had. Want ook met regexp is het mogelijk wat ik wil, maar dan niet in één keer.


Mogelijk alternatief
Hoe ik het wilde aanpakken was het parsen in fases te doen. Ik parse alleen tags die niet genest zijn. Dit betekent dat:

[b][i]bla[/][/]
alleen de [i]-tag geparsed wordt.

Pas bij de tweede iteratie wordt de [b]-tag geparsed. Bij de laatste iteratie zal er geen wijziging zijn uitgevoerd in de output, wat het signaal is om te stoppen met de iteraties (loop).

Voordeel van dit systeem is dat ik gewoon normale regexps blijf gebruiken. Het zal wel trager zijn, vooral als er veel genest wordt en er dus veel iteraties nodig zijn. Dat gezegd, sla ik de geparsede tekst op in database, dus parsing gebeurt alleen bij wijzigingen (POSTs) en niet bij normale leesacties.

Ik wil het vooral graag zelf doen. Eigenlijk wel beide manieren. Ik zou het leuk vinden om zowel een normale regexp parser te bouwen en een experimentele stack-based parser. Dan zou ik ook beide kunnen vergelijken qua efficiëntie.

Ik ga binnenkort maar eens aan de slag. Mijn bevinden zal ik hier wel posten zodra ik wat code heb. Kan me voorstellen dat meer mensen met dit soort problemen kampen en het nuttig kan zijn voor anderen.

Heren, alvast bedankt voor de input!

[kwaakvaak_v2]

Voor inspiratie, https://github.com/jbowens/jBBCode is een redelijk nette stack/node/visitor/traversing etc. parser in php.

[NMe]

Je kan ook altijd even spieken bij .oisyn. Die parser is ruim 9 jaar oud maar de gebruikte logica is in de basis nog steeds hetzelfde.

Je zegt dat je het leuk zou vinden om een parser met regexps te maken en eentje zonder, maar ik ga je net als de mensen hierboven dat eerste afraden. Een simpele reden daarvoor: nesting. [quote]Hoi.[quote]Hallo![/][/] gaat keihard fout met regular expressions. Dit nog naast het feit dat de groep expressions die je moet maken om alles te matchen dermate complex en onleesbaar wordt dat je het alleen al daarom beter niet kan doen.

[kwaakvaak_v2]

uuh... die van .oisyn gebruikt ook anders ook redelijk wat preg_* om de token tree op te bouwen.

[R4gnax]

kwaakvaak_v2 schreef op donderdag 29 augustus 2013 @ 08:52:
uuh... die van .oisyn gebruikt ook anders ook redelijk wat preg_* om de token tree op te bouwen.

Hij gebruikt ze in deelstukken van de parser waar de te verwachten taalconstructies wel te matchen zijn met een regexp. Dat is dus wat ik bedoelde met een simpele recursive descent parser die evt. intern gebruik maakt van regular expressions waar dat veilig kan.

Verwijderd schreef op zaterdag 24 augustus 2013 @ 15:19:
Wat bedoel je precies met een 'descent parser' ?

Wikipedia: Recursive descent parser, oftewel: de eerste hit als je op Google "recursive descent parser" intikt...

[NMe]

kwaakvaak_v2 schreef op donderdag 29 augustus 2013 @ 08:52:
uuh... die van .oisyn gebruikt ook anders ook redelijk wat preg_* om de token tree op te bouwen.

Niemand zie ooit dat regular expressions slecht zijn. Ze zijn op zichzelf alleen niet voldoende om dit probleem op te lossen. Je wil je tekst tokenizen en op basis van de tokens die je tegenkomt de overgebleven tekst goed stylen. Regular expressions kunnen daar een leuk hulpmiddel mee zijn, maar ze zijn niet je complete toolset, net zoals een timmerman meer gebruikt dan alleen een schroevendraaier.

[Snake]

To read: Parsing (X)HTML met Regex: http://stackoverflow.com/...ined-tags/1732454#1732454

Ook hierop van toepassing

[kwaakvaak_v2]

NMe schreef op donderdag 29 augustus 2013 @ 13:04:
[...]

Niemand zie ooit dat regular expressions slecht zijn. Ze zijn op zichzelf alleen niet voldoende om dit probleem op te lossen. Je wil je tekst tokenizen en op basis van de tokens die je tegenkomt de overgebleven tekst goed stylen. Regular expressions kunnen daar een leuk hulpmiddel mee zijn, maar ze zijn niet je complete toolset, net zoals een timmerman meer gebruikt dan alleen een schroevendraaier.

Op die manier klopt het idd Maar je andere comments interpreteerde ik zo, dat je het gebruiken van regex's per definitie niet goed vond.

Snake schreef op donderdag 29 augustus 2013 @ 13:07:
To read: Parsing (X)HTML met Regex: http://stackoverflow.com/...ined-tags/1732454#1732454

Ook hierop van toepassing

Iets met klokken en klepels imho, maar verklaar je anders even nader!

[ Voor 21% gewijzigd door kwaakvaak_v2 op 29-08-2013 13:59 . Reden: afvragen wtf Snake bedoelt. ]

[Verwijderd]

NMe schreef op woensdag 28 augustus 2013 @ 22:13:
Je kan ook altijd even spieken bij .oisyn. Die parser is ruim 9 jaar oud maar de gebruikte logica is in de basis nog steeds hetzelfde.

Ga ik doen!

Je zegt dat je het leuk zou vinden om een parser met regexps te maken en eentje zonder, maar ik ga je net als de mensen hierboven dat eerste afraden. Een simpele reden daarvoor: nesting. [quote]Hoi.[quote]Hallo![/][/] gaat keihard fout met regular expressions.

Als je alles in één ronde wilt doen wel. Maar het kan toch hoe ik het zou willen?

Je matcht eerst de binnenste tags. Dus je staat niet toe dat er [ .. ] tags binnen staan. Dan matcht alleen de binnenste geneste tag [quote]Hallo![/] de buitenste tag matcht dan niet. Die doe je in een tweede ronde, waarbij de binnenste tag al naar HTML-code is omgezet. Nadeel is de performance, je loopt hetzelfde document meerdere keren door.

Maar ik zou dus zeggen dat het wel degelijk mogelijk is met enkel regexps en PHP loops. Zal vast niet de beste optie zijn, maar wel één die ik 'kan' implementeren zonder heel veel inspiratie te moeten opdoen.

Dat gezegd, het idee was ook om er iets van te leren, dus een stack parsed parser en andere mogelijkheden wil ik ook graag onderzoeken. Enige probleem daarbij is dat ik nog niet zie hoe je niet-correct afgesloten tags kunt weren, iets wat met regexp wel heel goed kan omdat je alleen correct gesloten tags matcht.

[Voutloos]

Als je het in stukken doet, kan je dus net zo goed meteen met een stack maken he.

[RaZ]

Met short-tag zal je toch naar stack-based moeten kijken lijkt me.

Je zal immers een array moeten gaan opbouwen, en onthouden welke tags je tegenkomt.

code:

[u][i][url=linkje hier]naampje[/] lorum ipsum[/] ipsum lorem[/]

tag[0] = u
tag[1] = i
tag[2] = url

Dan kom je de sluit-tag tegen. adhv van je counter weet je welke er open is, de url, en weet je dat je die als een [ /url ] moet behandelen.

Je hoeft maar 1x de input door te lopen op die manier.

[Verwijderd]

Maar, het is toch ook gewoon mogelijk om het in regexp te doen?

Zoals: /\[i\]([^\[\]]*)\[\/\]/

Dan kan [i][url=linkje hier]naampje[/] lorum ipsum[/] niet matchen, dat kan pas nadat de URL-tag is gematcht, dan bij de tweede ronde (iteratie) krijg je wel een match:

[i]<a href="linkje hier">naampje</a> lorum ipsum[/]

[NMe]

kwaakvaak_v2 schreef op donderdag 29 augustus 2013 @ 13:57:
[...]

Iets met klokken en klepels imho, maar verklaar je anders even nader!

Leg mij eens uit wat het verschil is tussen [i]tekst[/i] en <i>tekst</i>?

Verwijderd schreef op donderdag 29 augustus 2013 @ 14:40:
[...]

Als je alles in één ronde wilt doen wel. Maar het kan toch hoe ik het zou willen?

Hoe ga je een makkelijk leesbare regexp maken die kan zien dat er überhaupt genest wordt? Een regular expression is niet op de hoogte van de state waarin je je bevindt in een tekst, een al dan niet stackbased parser is dat wel. Het is echt duizend keer simpeler om even over je string heen te loopen en op een stack bij te houden welke tags open zijn en welke niet.

[RobIII]

NMe schreef op donderdag 29 augustus 2013 @ 15:09:
Hoe ga je een makkelijk leesbare regexp maken die kan zien dat er überhaupt genest wordt?

Hij doelt op zoiets:

code:

var text = 'whooptie [b]doo![/]';
var myregexes = ['...regex here...', '...regex here...', '...regex here...', '...regex here...'];

foreach re in myregexes
  text = regex_execute(re, text, ...);

Lang verhaal kort: doe jezelf een plezier CiPHER en vergeet 't regex idee. Het valt vast (gammel, ducttape) aan de praat te krijgen maar bij de eerste-de-beste rariteit in de BBCode die niet goed geparsed wordt zit jij met de gebakken peren. En in de opzet zoals ik 'm hier demonstreer kom je weer een heel andere wespennest tegen: wat als de ene regex een resultaat oplevert die door de volgende regex (ten onrechte) gematched wordt en dus daardoor wéér omgezet wordt in iets anders?

[ Voor 43% gewijzigd door RobIII op 29-08-2013 15:58 ]

[Verwijderd]

Nou nee. Wel meerdere regexps ja (één per tag) maar niet allemaal in dezelfde ronde zoals in jouw voorbeeld. Zou je dat wel doen dan krijg je het probleem van verkeerde nesting qua eindtags, zoals in de startpost beschreven. Het kan wel op een manier met meerdere rondes.

Ik moet nu weg maar vanavond wil ik de code gaan schrijven en zal ik deze hier posten, voor de geïnteresseerden. Stack based parsers en andere stoerheden wil ik ook wel eens proberen, maar simpele regexps is iets wat ik het beste ken en ik volgens mij ook heel gemakkelijk kan realiseren. Enig nadeel dan de performance.

Wordt vervolgd!

[NMe]

Verwijderd schreef op donderdag 29 augustus 2013 @ 16:05:
Enig nadeel dan de performance.

...en de leesbaarheid...en het verlies aan bewegingsvrijheid...en het gebrek aan de mogelijkheid tot nesting...en de introductie van potentiële bugs omdat je allerlei complexe truukjes moet gaan verzinnen om deze beperkingen tot een minimum terug te brengen.

Je moet het natuurlijk zelf weten maar je bent echt je tijd aan het verspillen.

[kwaakvaak_v2]

NMe schreef op donderdag 29 augustus 2013 @ 15:09:
[...]

Leg mij eens uit wat het verschil is tussen [i]tekst[/i] en <i>tekst</i>?

In die context zit er geen verschil tussen, maar het artikel wat aangehaald werdt ging meer over mensen die content proberen te spideren met regex'es ipv via xpath of i.d. de content uit een document te vissen.

Als je een stack based tokinizer wilt bouwen om alle HTML tags in een document in een token-tree te zetten is een xpath weer een minder handige tool.

[crisp]

Onze signature-parser is een vrij eenvoudige stack-based parser (met ook weer heel beperkte features uiteraard). Ik zal eens kijken of ik daar een voorbeeldje van kan maken.

overigens was het heel vroeger ook een recursieve regexp-based parser, maar o.a. vanwege performance heb ik dat toen omgebouwd

[NMe]

kwaakvaak_v2 schreef op donderdag 29 augustus 2013 @ 16:32:
[...]

In die context zit er geen verschil tussen, maar het artikel wat aangehaald werdt ging meer over mensen die content proberen te spideren met regex'es ipv via xpath of i.d. de content uit een document te vissen.

Maakt in principe niet uit, je doet in beide gevallen hetzelfde. Of je nou in een pagina de <h1> wil zoeken en de waarde daarin in een string wil stoppen voor verdere verwerking of dat je nu een [i] wil zoeken om hem cursief te kunnen drukken maakt niet uit: in beide gevallen zoek je een bepaald patroon en wil je de waarde daarvan bewerken of verwerken.

[R4gnax]

Verwijderd schreef op donderdag 29 augustus 2013 @ 15:02:
Maar, het is toch ook gewoon mogelijk om het in regexp te doen?

Zoals: /\[i\]([^\[\]]*)\[\/\]/

Dan kan [i][url=linkje hier]naampje[/] lorum ipsum[/] niet matchen, dat kan pas nadat de URL-tag is gematcht, dan bij de tweede ronde (iteratie) krijg je wel een match:

[i]<a href="linkje hier">naampje</a> lorum ipsum[/]

Tegenvoorbeeld:

een code sample dat BBcode tags demonstreert. Eerst pass rendert het code sample uit. Tweede pass pikt foutief de tags in het code sample op en verwerkt die nog eens.

Dit ga je alleen oplossen door een stack-based parser te bouwen die context-aware is. Nogmaals: regexes zijn hier niet toereikend.

[Creepy]

Ik snap overigens ook niet zo goed dat een stack based parser moeilijker wordt gevonden dan een paar (of een hele lange) regexps?

Een stackbased parser is in de basis juist vrij simpel. Als je een start-tag tegenkomt zet ie die op de stack. Kom je een eind-tag tegen (de verkorte) dan haal je je laatste item van de stack af. Kom je een lange eindtag tegen dan controleer je of het laatste item op de stack hetzelfde item betreft voordat je hem eraf haalt(en zo niet dan is de code niet goed en kan je dat melden). Zo kan je altijd het laatste element van de stack bekijken om te weten met wat voor element je bezig bent.

Dat je dan regexps gebruikt om de volgende start of eind tag te vinden is natuurlijk prima.

[ Voor 8% gewijzigd door Creepy op 30-08-2013 14:11 ]