[js regex] juiste haakjes matchen

[Verwijderd]

ik heb

code:

\sqrt {blaat{foo}bar} {foep{etc}}

en dat moet omgezet worden naar:

code:

<msqrt>{blaat{foo}bar}</msqrt> {foep{etc}}

de tag moet dus precies om het juiste set haakjes heen, nu is de vraag hoe ik dat met een regex voor elkaar krijg, want als ik iets doe als

code:

/\\sqrt \{.+?\}/

dan is ie dus non greedy en stopt ie bij de eerste } (na foo).
Maar als ik 'm wel greedy maak, dan gaat ie door tot de laatste } en da's ook niet wat ik wil

[ Voor 6% gewijzigd door Verwijderd op 29-01-2005 16:52 ]

[Verwijderd]

Als ik mijn colleges Formele Talen en Berekenbaarheid goed herinner (en dat zou wel moeten, ik geloof dat ik er 5 keer tentamens van heb moeten maken ) is dit niet mogelijk met reguliere expressies. Ik ga wel even wat dingen opzoeken...

[edit]
Ahh. Ik weet het weer. Dit was het stuk waarop ik altijd zakte: bewijzen dat een taal niet regulier is. Vage concepten als 'the pigeonhole principle' en 'the pumping lemma' schieten te binnen. Informeel gezegd: een taal is regulier als bij het verwerken ervan gegarandeerd maar een beperkte hoeveelheid geheugen nodig is. In dit geval is dat niet zo, omdat het aantal haakjes dat moet worden verwerkt voordat de juiste, sluitende is gevonden niet te voorspellen is.

In dit geval is een contextvrije grammatica nodig.

Misschien dat de mensen bij P&W die hun studie hebben afgemaakt hier meer over kunnen vertellen dan ik.

[ Voor 60% gewijzigd door Verwijderd op 29-01-2005 17:07 ]

[Verwijderd]

Dit zijn dingen die met regular expressions heel moeilijk zo niet onmogelijk zijn. Het is wellicht beter om de boel te verdelen in tokens, en die af te lopen, en een stack bij te houden waarmee je de diepte van de nesting kunt bepalen.

[crisp]

In feite heb je daarvoor een vorm van recursie nodig, en JS regexpen ondersteunen dat niet.
Je kan beter gaan tokenizen...

edit: spuit-12

[ Voor 10% gewijzigd door crisp op 29-01-2005 17:01 ]

[Verwijderd]

tokenizing? da's nieuw voor me, eens kijken hoe ik dat ga aanpakken. Soort van nested array dus die dieper gaat elke keer als ik een { tegenkom en terug als ik een } zie

/me gaat zoeken

[T-MOB]

Zoals ik het hier zie staan voldoet je voorbeeld wel aan *insert blues' geschoolde verhaal*. Omdat je achter je "sluit-accolade" een spatie hebt. Daar zou je op kunnen matchen als dit in real-life situaties ook zo is.

[Verwijderd]

nee, die spaties hoeven er niet te staan (ik ga uit van TeX), daar heb je ook zoiets als

code:

\frac{{3\alpha }}{g}$

om maar iets te noemen en dat moet worden omgezet naar

code:

<mfrac>{{3\alpha }}{g}</mfrac>

om maar eens mee te beginnen, hier loop ik dus tegen haakjesproblemen aan

Iemand info over tokenizing? want ik wordt niet echt veel wijzer van wat ik vind

[Clay]

Op zich kan je er wel met regexen doorheen lopen, en adh daarvan een stack maken. Wbt het "roeien met de riemen die je hebt" heb ik op de onderstaande manier een keer een xml tidy script gemaakt met js. voor tex zou dat iets als dit worden dan:

code:

var tex = "\\frac{{3\\alpha}}{g}$";
tex.replace(/(\\\[a-z0-9]+)|(\{|\})|[a-z0-9]+|.+?/gi, function($1){
    alert($1);
});

per replace is $1 dan een entity, haak, of wat anders. Xml is eenvoudiger, daar hoef je alleen maar <[^>]+> (n.b. versimpeld, is natuurlijk niet handig zo) te matchen, maar het principe werkt overal wel voor 't is gewoon met net iets meer dan teken voor teken erdoorheen lopen.