[GoT smileys] Hoe worden deze geparsed?

[_eXistenZ_]

* _eXistenZ_ houdt er een weblog op na, dat draait op Simple PHP Blog.

Ik heb nu d.m.v. een simpel stukkie html een rijtje smileys toegevoegd, net als dat je hier zie @ GoT zodra je wat zit te typen. Deze worden op dezelfde manier dmv Javascript in het textveld opgenomen, en doormiddel van een vantevoren gebouwde functie in de blog geparst als een image. Het probleem is alleen, als ik de smileys

code:

:D en ?:D

heb,
en ik zet de zaak in de verkeerde volgorde met parsen, dan zal de

code:

:D

eerst geparsed worden, en zie je nooit de

code:

?:D

Mijn vraag is dus ook, hoe wordt de zaak hier geparsed, aangezien ik de GoT smileys gebruik op mijn weblog (Of mag dit niet, en overtreed ik nu de regels?)

Kan een persoon als Moto-Moi vertellen in welke volgorde de zaak hier geparsed wordt, dan kan ik dit zo overnemen in mijn weblog
Nu loop ik vaak tegen het probleem aan dat een bepaalde smiley niet geparsed wordt...

[ Voor 6% gewijzigd door _eXistenZ_ op 14-01-2006 14:05 ]

[RoD]

Ik heb geen _flauw_ idee hoe dat in zn werk gaat, maar informatie over GoT smileys kun je hier vinden.

[_eXistenZ_]

Ok, ik ben het niet eens met de voorwaarden dus zoek ik een stapel andere smileys
Nu is dit topic ook gelijk nutteloos, aangezien ik nu de volgorde van de GoT smileys niet meer nodig heb

[ Voor 40% gewijzigd door _eXistenZ_ op 14-01-2006 14:08 ]

[TRON]

De array met smilies wordt aflopend op grootte gesorteerd als ik me niet vergis

[Technicality]

De site waarop de smilies komen te staan is van non-commerciele aard en mag geen content bevatten die hier niet getolereerd zou worden. Denk hierbij aan warez, kinderporno, fascistisch gedachtegoed en andere verboden of anderszins ongewenste praktijken. Als je twijfelt, stuur ons dan een mailtje.

Ga jij een kinderporno/commerciele site hosten? Nee toch? Gewoon een vermelding en je mag ze gebruiken, muv dat hartje

[_eXistenZ_]

Als ik ze allemaal wil moet ik 6 man mailen, en dat hartje wil ik ook. Ik zoek dus wel een andere smileypack Bovendien wil ik geen vermelding naar t.net op mijn eigen weblog.

[ Voor 23% gewijzigd door _eXistenZ_ op 14-01-2006 14:12 ]

[Mr. Bondt]

Het is ingewikkelder dan je zou denken, want als ik dit doe:
()
":+"
" "
Tekst:+Tekst
Tekst Tekst

[NMe]

Mr. Bondt schreef op zaterdag 14 januari 2006 @ 14:12:
Het is ingewikkelder dan je zou denken, want als ik dit doe:
()
":+"
" "
Tekst:+Tekst
Tekst Tekst

Dat heeft te maken met het feit dat er een tokenizer gebruikt wordt om de smileys te parsen, en geen regexp. Dat heeft verder niets met de sortering van smileys te maken, maar meer het het leesbaar houden van zinnen waar waarschijnlijk hard genoeg over is nagedacht bij de mensen van Parse en T.net.

[Peter]

Een goed voorbeeld van stack-based smilie parsing vind je hier

[NMe]

.Peter schreef op zaterdag 14 januari 2006 @ 14:33:
Een goed voorbeeld van stack-based smilie parsing vind je hier

Als ik zo door die code heen blader, dan zou ik het niet echt een goed voorbeeld durven noemen. Ik heb er natuurlijk niet echt uitgebreid naar gekeken, maar ik zie een aantal dingen die sneller/beter zouden kunnen. Ik zou dus zelf een andere aanraden.

[Verwijderd]

Overigens zijn er in het verleden veel interessante topics geweest over stack based parsers, zoals deze:
[rml][ PHP] Tag Parser[/rml] (uit de oude doos met veel oude /14 rotten)

HTH

[ Voor 13% gewijzigd door Verwijderd op 14-01-2006 14:46 ]

[ACM]

-NMe- schreef op zaterdag 14 januari 2006 @ 14:18:
Dat heeft te maken met het feit dat er een tokenizer gebruikt wordt om de smileys te parsen, en geen regexp.

Ah... maar volgens mij kan dat ook prima met regexps en wordt dat in react dan ook gedaan Ik moet er wel de broncode op naslaan om zeker te weten of dat nog zo is, dus als jij recentere informatie dan ik heb kan het best kloppen wat je zegt

Overigens is die [norml]:D vs ?:D[/] ook prima te doen met regexps, gewoon bij de eerste kijken of de : niet voorafgegaan werd door een ?

[pasta]

eXistenZ_NL schreef op zaterdag 14 januari 2006 @ 14:11:
Als ik ze allemaal wil moet ik 6 man mailen, en dat hartje wil ik ook. Ik zoek dus wel een andere smileypack Bovendien wil ik geen vermelding naar t.net op mijn eigen weblog.

offtopic:
Nope, 1 man mailen, op [e-mail]

[Shuisman]

Het is vrij simpel, ze doen er volgens mij een spatie omheen

Hallo:+Hallo levert geen smiley maar met spaties eromeen wel;

een smiley is volgens mij:

code:

 " :+ "

(zonder de ") en niet

code:

 ":+"

[ Voor 33% gewijzigd door Shuisman op 14-01-2006 15:03 ]

[Verwijderd]

SHuisman schreef op zaterdag 14 januari 2006 @ 15:01:
Het is vrij simpel, ze doen er volgens mij een spatie omheen

Hallo:+Hallo levert een smiley

een smiley is volgens mij: " " (zonder de ") en niet ":+"

Zo simpel dat je het niet echt uit weet te leggen?

[TRON]

Sinds wanneer pasta? Uit Smiley-credits en gebruiksregels blijkt dat je meerdere mensen moet mailen als je alle smilies wil

[Shuisman]

Verwijderd schreef op zaterdag 14 januari 2006 @ 15:02:
[...]

Zo simpel dat je het niet echt uit weet te leggen?

Mijn g doet het slecht , net ff wat duidelijker gemaakt,

Als je een smiley toevoegd als je een reply typt, komen er ook automatisch spaties omheen.

[azteke]

pasta schreef op zaterdag 14 januari 2006 @ 14:58:
[...]

offtopic:
Nope, 1 man mailen, op [e-mail]

offtopic:
En als ie die anderen nou ook wil, die niet van GoT zijn? dan mag hij die eigenaars ook mailen

[crisp]

ACM schreef op zaterdag 14 januari 2006 @ 14:56:
[...]

Ah... maar volgens mij kan dat ook prima met regexps en wordt dat in react dan ook gedaan Ik moet er wel de broncode op naslaan om zeker te weten of dat nog zo is, dus als jij recentere informatie dan ik heb kan het best kloppen wat je zegt

Het klopt allebei; de uiteindelijke omzetting wordt wel met een regexp gedaan, maar dit gebeurd alleen voor content die buiten tags voorkomt. Om tags te scheiden van content wordt uiteraard een tokenizer gebruikt om een stack te bouwen.

SHuisman schreef op zaterdag 14 januari 2006 @ 15:01:
Het is vrij simpel, ze doen er volgens mij een spatie omheen

Hallo:+Hallo levert geen smiley maar met spaties eromeen wel;

een smiley is volgens mij:

code:

 " :+ "

(zonder de ") en niet

code:

 ":+"

Er wordt niet alleen naar spaties voor/na gekeken, maar ook naar begin/eind regel en bepaalde leestekens. Dit kan je in een reguliere expressie met look-behind en look-ahead realiseren

[EfBe]

het werkt met token matching. Je hebt de 2 patterns:

code:

:D

en

code:

?:D

Als een '?' gescanned wordt door de lexical analyzer gaat hij de state machine in van

code:

?:D

. Die komt op 2 dingen uit:
1) slaagt, wanneer de complete 3 characters zijn gezien achter elkaar
2) faalt wanneer er 1 ontbreekt.
Bij 1) wordt de string geaccepteert en wordt het token 'smileyABC' in de token stream geplaatst
bij 2) wordt de string als text gezien en verschuift de scanner 1 character naar rechts.

Dus

code:

:D

kan nooit leiden tot een andere smiley want het begin character is anders.

Wat nu te doen bij:

code:

:D

en

code:

:D!

(stel dit is ook een smiley)

De ':' zorgt ervoor dat de lexical analyzer een state machine ingaat en aan de hand van het volgende character (lookahead) bepaalt de lexical analyzer wat de eventuele uitslag zou kunnen zijn. In dit geval is dat een 'D' en er zijn dan nog 2 uitkomsten. Hij gaat dan het volgende character bekijken. Dit doet hij omdat er nog 2 of meer mogelijkheden zijn. Stel dit volgende character is een spatie. Dan kan

code:

:D!

dus niet matchen en zijn we klaar met wat we hebben, want dat is een matching character. Is het een '!', dan matchen we met het token

code:

:D!

. Omdat dit een match is en er geen andere zijn met dit pattern zijn we klaar.

Tokenization is niet zo makkelijk als het lijkt. Je kunt een heel eind komen met wat gekunstel maar wanneer lookaheads nodig zijn wordt het erg lastig zonder een duidelijk algorithme.

[wacco]

Ik zit me hier te vervelen op werk dus vond dit wel een geinig iets om te brainstormen.
In een tien minuutjes ben ik hier mee opgekomen, wie kan mij vertellen of deze pseudo code hopeloos is of zou kunnen werken? Of wie heeft er een mooiere oplossing?

code:

/* Tokanizer pseudo code - Sunday doodle wacco 15/jan/06 */

/* Smilies table, note the spaces around it */
TOsmiley Smilies = {
    " :) " , "location_a", /* smiley, url location */
    " :)! ", "location_b", /* Tokanize lookahead example */
    " ?:) ", "location_c", /* Other start as first */ 
    " 8| " , "location_d"  /* Something completely different */
}

/* Chruncher is a linked list with characters, which contain a pointer to a 'higher' list (next char) */
TOsmileytable *Chruncher = NULL;
TOsmileylinks *ChruncherOutput = NULL;

TOinit() {
    foreach smiley in Smilies {
        n = Chruncher
        foreach char in smileytag {
            is char not in n
                n.append(char) /* Append char */
            n = n->char->higherlist
        }
        ChruncherOutput.append(n, smileyurl)
    }       
}

TOdestroy() {
    recursively free everything in Chruncher & ChruncherOutput
}

TOparse(string m) {
    foreach char in m { /* BUG: url locations of inserted smileys will be parsed too! */
        TOparserec(substing of m from current char, Chruncher, 0);
    }
}

/* Recursively plus lotsa string copies (unless using pointers) equals SLOW! But you get the idea ;) */
TOparserec(string m, TOsmileytable n, deepness i) {
    is firstchar of m in n {
        if n->char->higherlist is NULL
            return ChruncherOutput.get(n) and i /* Add some img html too ;) */
        newString and i_max = TOparse(substring of m from current char, n->higherlist, i++)
        /* PONG! This is wrong, what if no smiley, and don't replace just yet since i might not be our first char */
        string replace in m from i till i_max with newString
        return m;
    }
    return false;
}

TweeDrie sidenotes:
0) Zie de bug, je kan er een kopie van maken en daar mee gaan spelen, zou je het wel mee op kunnen lossen
1) Ik doe niks met EOF checking, laat ik over aan de fanatiek die dit wil implementerenDat doe je maar met de foreach
1) Die twee waardes terug spelen kan lelijk worden, pointers naar argumenten enzow (i dus) zou het nog netjes kunnen houden, maar dan moet je i wel ff kopieren naar een var in de functie voordat je het doorspeelt naar de volgende recursieve aanroep.
2) Je kan je init tabellen natuurlijk een keer parsen, opslaan, en later hergebruiken (er van uit gaande dat je smileys niet elke keer veranderen)

Hope this helps (als er geen barst van klopt, don't blaim me (maar laat het me wel weten) )

[ Voor 21% gewijzigd door wacco op 15-01-2006 15:10 ]

[TheBlasphemer]

Je zou een "Aho-Corasick" String matching automaton kunnen schrijven
Beetje overkill, wel lekker snel, en hiermee krijg je ook zeker het effect wat je wilt:
http://en.wikipedia.org/wiki/Aho-Corasick_algorithm
http://www-sr.informatik....en.de/~buehler/AC/AC.html
http://www.cs.uku.fi/~kilpelai/BSA05/lectures/slides04.pdf

Je kan vantevoren je smileys array laten converten naar een AC-tree, en die dan in PHP laten gebruiken
Is lekker snel, en je hoeft maar 1 keer over je text heen (in tegendeel tot een regexp waarmee je voor elke smiley de text af moet zoeken)

[wacco]

Dus. Daar gaat mijn idee, ik heb dus gewoon een brakke implementatie van Aho-Corasick op papier gekladderd.

Je wordt bedankt TheBlasphemer!
(No really, weer wat nieuws te lezen hier op werk )

[TheBlasphemer]

wacco schreef op zondag 15 januari 2006 @ 15:16:
Dus. Daar gaat mijn idee, ik heb dus gewoon een brakke implementatie van Aho-Corasick op papier gekladderd.

Je wordt bedankt TheBlasphemer!
(No really, weer wat nieuws te lezen hier op werk )

You're welcome
Vind het zelf ook altijd leuk nieuwe algoritmes te ontdekken

[flowerp]

Kun je hier niet gewoon een lexical analyzer generator voor gebruiken? Bijvoorbeeld, flex wat bijna elke OS wel standaard wordt meegeleverd. Veel bekende software gebruikt flex wel op een of andere manier. Om te beginnen kun je gewoon de man page doorlezen. (man flex)