[PHP / UBB] Wat is nu het voordeel van stack-based parsen?

[Verwijderd]

Momenteel filter ik alle HTML die ingevoerd wordt op mijn (eigen geschreven) gastenboek uit de post. Nu wil ik mijn bezoekers graag de mogelijkheid geven beperkt HTML in te voeren. Dus moet er een UBB parser komen

Nu heb ik gevonden dat dat in principe op twee manieren kan: met preg_replace of "stack-based". Op het forum heb ik opgezocht wat stack-based betekent:

Een stack is een LIFO collectie. LIFO staat voor 'Last In First Out'. Een andere vorm van collecties is een FIFO stucture (First In First Out), bijvoorbeeld Queues. Een voorbeeld van een stack is een array in PHP waar je alleen een item afhaalt als dat als laatste is toegevoegd. [...]

Wanneer je bijvoorbeeld een openings- tegenkomt sla je die op in de stack (met een 'push' method). Hierna kun je natuurlijk alleen nieuwe openingstags tegenkomen, of een sluitings- tag. Iedere openingstag push je weer op de stack en bij een sluitingstag haal je weer een element van de stack af (en als het goed is, is dat altijd het bijbehorende element, je haalt ze weer in omgekeerde volgorde eraf). Een item van de stack halen doe je met een 'pop' method. Heb je heel je string doorlopen, dan moet je stack weer leeg zijn.

De loop is dan de engine van je parser en de stack gebruik je om de state in op te slaan. Je kunt zelf een LIFO stucture ontwerpen, maar je kunt ook gewoon een PHP array nemen en je bij het gebruik daarvan aan de regels houden die bij een stack horen.

Ik heb van beide soorten een aantal parsers gedownload, onder andere de stack-based versie van .oisyn. Om het verschil te vinden heb ik een hele zooi UBB ingetikt en het laten parsen door alle parsers, in de hoop dat niet-stack-based parsers zouden vastlopen en ik het voordeel van stack-based zou gaan zien, maar dat is niet echt gebeurd.

Daarom mijn vraag: wat is nu het grote voordeel van stack-based UBB parsers tegenover regex gebaseerde? Heeft iemand een concreet voorbeeld van code die door een regex parser zeker niet goed behandeld wordt en door een stack-based parser wel?

-- edit --

Ik heb een eenvoudige regex parser online gezet: http://www.examenhulp.com/?q=node/1

Let op: hij is in het nederlands. Gebruik dus [ plaatje] ipv [ img] en [ tabel], [ rij] en [ cel] ipv de engelse equivalenten Wie heeft er code die volledig voud geparsed wordt of die de site kunnen exploiten?

[ Voor 7% gewijzigd door Verwijderd op 02-08-2007 13:59 ]

[kokx]

Browsers gebruiken volgensmij stack-based HTML parsers. En volgensmij is geen 1 regex parser XHTML bestendig tegen deze ubb:

code:

[b][u]blaat[/b][/u]

Wat wel het geval is met een stack-based parser.

* kokx bookmarked, dit kan best nog wel interessant worden.

Edit: Jouw parser kan er iniedergeval niet tegen:

HTML:

<strong><u>blaat</strong></u>

[ Voor 28% gewijzigd door kokx op 02-08-2007 15:00 ]

[ValHallASW]

Regexps zijn niet te gebruiken voor recursieve talen, maar dat is bij bbcode niet zo'n groot probleem. Op het moment dat je iets als

[tag blaat=[andere tag]]

wilt ondersteunen dan wordt dat met een regexp een stuk lastiger. Overigens geldt dit ook voor bijvoorbeeld [plaatje][blaat][/blaat][/plaatje], maar daar kan je een regexp op het tussengedeelte uitvoeren. Daarnaast zijn regexps vergeleken met een echte parser nogal traag: je doorloopt je hele string in jouw geval 14 keer, als het niet vaker is. Een stack based parser doet dit maar één keer.

@kokx: dat hangt ook maar af van je parser. Bij een UBB-parser wil je dat er altijd zinnige output uitkomt, aan parse errors doe je i.h.a. niet. Sommige parsers zijn slim genoeg om van

code:

[b]a[i]b[/b]c[/i]d

abcd te maken, maar de parser van GoT maakt er bijvoorbeeld [b]ab[/b]cd van.

[kokx]

@ValHallASW: Zo te zien doet elke parser dat anders. Mijn parser zou er dit van maken:
ab[/b]c.

En zo zal elke parser er iets totaal anders van gaan maken.

Maar sommige regex parsers zijn weer sneller dan stack-based parsers. Maar dan ga je echt aan parsers denken die voor elke tag een regex hebben die niet te moeilijk doet.

[ Voor 51% gewijzigd door kokx op 02-08-2007 15:16 ]

[ACM]

Verwijderd schreef op donderdag 02 augustus 2007 @ 13:35:
Let op: hij is in het nederlands. Gebruik dus [ plaatje] ipv [ img] en [ tabel], [ rij] en [ cel] ipv de engelse equivalenten Wie heeft er code die volledig voud geparsed wordt of die de site kunnen exploiten?

Hoe goed kan jouw parser tegen geneste tabellen? Of tegen incorrecte structuren zoals [tabel][rij][/rij][/tabel] ? En kan jouw parser tegen een tag die wel/niet toegestaan is binnen een andere tag? Bijvoorbeeld zoals hier op GoT de code- of de norml-tag werkt?

[.oisyn]

Die van mij snapt, net als die hier op React, bovendien de syntax [tag=value1,value2,value3] en [tag attr1=value1 attr2=value2 attr3=value3], en herkent daarnaast quotes: [tag="value1,value2,value3"] zit ie niet als 3 verschillende values.

Waarschijnlijk kun je dat ook wel allemaal in een heel erg complexe regex modelleren, maar wat als er een bug in blijkt te zitten, of als je een keer je syntax uit wilt breiden? Complexe regexen zijn zo unmaintainable als wat, daar wordt je echt niet vrolijk van als je er na een half jaar oid weer naar moet kijken

[kokx]

Die kan daar niet zo goed tegen als GoT.

code:

[code][/code]

Werkt goed op got, bij hem komt de [/code] tag er achter.

Hij kan ook niet zo goed tegen geneste tabellen. Die lopen echt helemaal de soep in.

[crisp]

kokx schreef op donderdag 02 augustus 2007 @ 15:13:
@ValHallASW: Zo te zien doet elke parser dat anders. Mijn parser zou er dit van maken:
ab[/b]c.

En zo zal elke parser er iets totaal anders van gaan maken.

Klopt, er zijn verschillende tag-matching algorithmen die elk op een andere manier met misnested tags omgaan (o.a. adoption agency algorithme, incest algorithme, secret affair algorithme, Heisenberg algorithme). HTML5 beschrijft de eerste en zal dus zoveel mogelijk beschrijven hoe huidige browsers HTML parsen.

Error-correctie is echter nog niet zo eenvoudig in HTML (en dus ook in UBB) omdat content-model een grote rol speelt, en dat is een feature die ik nog in geen enkele UBB-parser ben tegengekomen.

[_Thanatos_]

Grootste voordeel van een stack-based parser, vind ik, is dat je tags op bepaalde plekken een andere (of juist geen) betekenis kan geven.

Bijv binnen een [code] tag worden geen andere UBB-tags meer geparst. Dat is met een regex bijna niet meer te doen. Of in een [html] opeens HTML niet meer encoden (en dus toelaten) zou ook haast niet te doen zijn met een regex-based parser...

Kortom, in een stack-based parser heb je veel meer (en duidelijkere) controle over de output, omdat je niet alleen weet welke tag je aan het parsen bent, maar je weet ook in welke context hij staat.

[Verwijderd]

_Thanatos_ schreef op donderdag 02 augustus 2007 @ 20:12:
Grootste voordeel van een stack-based parser, vind ik, is dat je tags op bepaalde plekken een andere (of juist geen) betekenis kan geven.

Bijv binnen een [code] tag worden geen andere UBB-tags meer geparst. Dat is met een regex bijna niet meer te doen. Of in een [html] opeens HTML niet meer encoden (en dus toelaten) zou ook haast niet te doen zijn met een regex-based parser...

Kortom, in een stack-based parser heb je veel meer (en duidelijkere) controle over de output, omdat je niet alleen weet welke tag je aan het parsen bent, maar je weet ook in welke context hij staat.

Mwah de dingen die je beschrijft zijn wel te doen hoor, gewoon eerst even met een regex de te parsen tekst splitsen in verschillende delen en dan die delen afzonderlijk parsen.

Neemt niet weg dat het grootste voordeel van een stack based parser de onderhoudbaarheid is.
De gemiddelde progger krijgt al genoeg hoofdpijn van regex'en, laat staan als er een rare bug in zit of je het na een half jaar nog eens moet bekijken.

[_Thanatos_]

Verwijderd schreef op donderdag 02 augustus 2007 @ 20:15:
[...]

Mwah de dingen die je beschrijft zijn wel te doen hoor, gewoon eerst even met een regex de te parsen tekst splitsen in verschillende delen en dan die delen afzonderlijk parsen.

Het gaat er juist om dat binnen die blokken je juist dingen *niet* moet doen. zoals html escapen/encoden. Dan heb je een blok te pakken waarin dat niet moet gebeuren, en dan? Je moet juist het stuk hebben waarin het wél moet gebeuren, en dat is knap lastig met meerdere van die blokken, en verschillende andere dingen die extra of juist niet moeten gebeuren.

Het kan misschien wel met een heleboel hele lange hele obscure regexen, maar zoals je al aanhaalt, het zit em in de onderhoudbaarheid. Ik ben gewend om onderhoudbare code te kloppen, dus als iets niet normaal onderhoudbaar gemaakt kan worden, dan zoek ik een andere manier. Vandaar dat ik regex-parsen "haast niet te doen" vind.

[Verwijderd]

_Thanatos_ schreef op vrijdag 03 augustus 2007 @ 21:26:
[...]


Het gaat er juist om dat binnen die blokken je juist dingen *niet* moet doen. zoals html escapen/encoden. Dan heb je een blok te pakken waarin dat niet moet gebeuren, en dan? Je moet juist het stuk hebben waarin het wél moet gebeuren, en dat is knap lastig met meerdere van die blokken, en verschillende andere dingen die extra of juist niet moeten gebeuren.

Het kan misschien wel met een heleboel hele lange hele obscure regexen, maar zoals je al aanhaalt, het zit em in de onderhoudbaarheid. Ik ben gewend om onderhoudbare code te kloppen, dus als iets niet normaal onderhoudbaar gemaakt kan worden, dan zoek ik een andere manier. Vandaar dat ik regex-parsen "haast niet te doen" vind.

Mwah het is niet zo moeilijk als ik denk dat jij denkt dat het is, het is op zich goed te doen. Splitsen en dan op bepaalde stukken wel toepassen en andere stukken niet toepassen is goed mogelijk, context awareness is te doen maar tot een beperkte mate natuurlijk. Het wordt al heel snel heel ingewikkeld.

Maar het onderhoud is echt een ramp, ook het oplossen van bugs is vaak hopeloos.

Dat zijn de voordelen van stack based parsen.

[ Voor 9% gewijzigd door Verwijderd op 04-08-2007 12:40 ]

[Verwijderd]

Voordeel van Stack Based parser:
- Je kan een engine maken die een grammatica snapt:
Grammatica beschrijft bijvoorbeeld nesting van elementen, verplichte child-elementen, optionele child elemeneten, verplichte/niet verplichte attributen, standaardwaardes voor attributen en dergelijke. Dit zonder rare reguliereexpressie-magie. Ook kan je dingen verbieden zoals: [norm][/]
- Ook kan je een gegarendeerde correcte uitvoer (HTML) maken.
- De grammatica kan je vervolgens per onderdeel uitkienen (bijvoorbeeld: afhankelijk van de rechten van een gebruiker een andere grammatica, afhankelijk van het site onderdeel verschillende grammatica's).

Parsers die reguliere expressies gebruiken hebben vrijwel altijd problemen met nesting, ingewikkelde attribuut-systemen en met het creëren van correcte HTML.