Reguliere expressie kan geen malafide vierkante haken aan

Dankzij de smarties hier in het verleden heb ik deze verbazingwekkende recursieve reguliere expressie die me helpt bij het transformeren van aangepaste BBCode-achtige tags in een tekstblok.

/// 
/// Static class containing common regular expression strings.
/// 
public static class RegularExpressions
{
    /// 
    /// Expression to find all root-level BBCode tags. Use this expression recursively to obtain nested tags.
    /// 
    public static string BBCodeTags
    {
        get
        {
            return @"
                    (?>
                      \[ (?[^][/=\s]+) \s*
                      (?: = \s* (?[^][]*) \s*)?
                      ]
                    )

                    (?
                      (?>
                        \[(?[^][/=\s]+)[^][]*]
                        |
                        \[/(?<-innertag>\k)]
                        |
                        [^][]+
                      )*
                      (?(innertag)(?!))
                    )

                    \[/\k]
                    ";
        }
    }
}

Deze regex werkt prachtig, recursief matchen op alle tags. Zoals dit:

[code]  
    some code  
    [b]some text [url=http://www.google.com]some link[/url][/b]  
[/code]

De regex doet precies wat ik wil en komt overeen met de code [code] . Het verdeelt het in drie groepen: tag, optionele waarde en inhoud. Tag is de tagnaam (in dit geval "code"). Optionele waarde die een waarde is na de gelijk aan ( = ) teken als er een is. En inhoud is alles tussen de openende en de sluitende tag.

De regex kan recursief worden gebruikt om overeen te komen met geneste tags. Dus na het matchen op [code] zou ik het opnieuw uitvoeren tegen de inhoudsgroep en zou het overeenkomen met de [b] -tag. Als ik het opnieuw zou uitvoeren in de volgende inhoudsgroep, zou het overeenkomen met de tag [url] .

Dat is allemaal heerlijk en heerlijk, maar het hapert om één kwestie. Het kan geen malafide vierkante haken aan.

[code]This is a successful match.[/code]

[code]This is an [ unsuccessful match.[/code]

[code]This is also an [unsuccessful] match.[/code]

Ik zuig echt aan reguliere expressies, maar als iemand weet hoe ik deze regex kan aanpassen om kwaadwillende haakjes correct te negeren (haakjes die geen openingstag vormen en/of geen overeenkomende sluitingstag hebben), zodat deze nog steeds overeenkomt met de omringende tags , Zou ik zeer dankbaar zijn: D

Bij voorbaat dank!

Bewerk

Als u geïnteresseerd bent in het zien van de methode waarop ik deze uitdrukking gebruik bent u welkom .

3
stackoverflow.com/questions/7018321/… daar ga je. Dat is de vraag waar deze regex oorspronkelijk voor was :)
toegevoegd de auteur Chev, de bron
@Jon, ik begrijp niet waarom mensen denken dat ik het oneens ben. Ik ben niet. Ik sta open voor alternatieven. Ik probeerde echter een handmatige parser te schrijven en het ging vrij snel boven mijn hoofd. Als je een goed begin hebt met een alternatief, kun je het gerust plaatsen. Tot die tijd bent u van harte welkom bij " Pass ".
toegevoegd de auteur Chev, de bron
@CodeJockey Helaas is mij dit gegeven door iemand anders op SO. Ik ga op zoek naar de vraag. Misschien is daar meer detail.
toegevoegd de auteur Chev, de bron
Ik denk echt niet dat ik een -1 verdien voor deze vraag. Alleen omdat je niet van reguliere expressies houdt, wil dat nog niet zeggen dat er iets mis was met mijn vraag. Ik was heel duidelijk en nam de tijd om deze vraag samen te stellen. Dat is hetzelfde als duimen die een vraag verlagen, omdat de auteur code schrijft in een taal die niet jij favoriet is. Als je denkt dat er iets mis is met mijn vraag, reageer dan alsjeblieft en vertel me wat het is.
toegevoegd de auteur Chev, de bron
Anders dan de schurken vierkante haken die de wedstrijd breken werkt het perfect.
toegevoegd de auteur Chev, de bron
@MiguelAngelo Ik probeerde dit in het verleden handmatig te ontleden, maar het leek volledig uit de hand gelopen te zijn en in complexiteit te groeien. Iemand zei me om het tegenovergestelde te doen van wat je allemaal suggereert en deze uitdrukking gebruikt. Misschien als je me een staaltje kon laten zien om me in de juiste richting te wijzen.
toegevoegd de auteur Chev, de bron
Als iemand van jullie codevoorbeelden heeft die jouw voorkeursmethode laten zien, sta ik er voor open. Dit was de enige manier om dit te laten werken en het heeft tot nu toe geweldig gewerkt. Dus tenzij ik een betere oplossing voorleg, zal ik er waarschijnlijk aan vasthouden.
toegevoegd de auteur Chev, de bron
U lijkt te proberen .net te gebruiken "Evenwichtsgroepdefinities" construeren , en mogelijk omdat ik niet erg vertrouwd ben met dit specifieke construct, begrijp ik niet wat de (? <- innertag> \ k ) -groep hoort te zijn, anders dan mogelijk "vergeet de innertag-groep, maar sla de wedstrijd niet op in een nieuwe groep", die ik nergens gedocumenteerd zie. Dit is een erg obscure en moeilijk te begrijpen constructie om mee te beginnen, nog minder met vreemde veranderingen - de meeste mensen hebben meer informatie nodig om je te helpen.
toegevoegd de auteur Code Jockey, de bron
Trouwens, ik denk dat ik je misschien kan helpen, omdat dit construct is toegevoegd aan de .Net Regex Implementatie specifiek voor het ontleden van geneste grammatica's zoals HTML en BBCode, maar ik heb meer tijd nodig, omdat ik geen platform heb dat is opgezet om het testen en debuggen van dit construct af te handelen (mijn emulator ondersteunt dit niet) - succes tot (of als ik niet) terug kom met een antwoord!
toegevoegd de auteur Code Jockey, de bron
@AlexFord Welkom bij het onderdeel de regexes zijn niet de tool voor deze taak. Zelfs als je dit oplost, hoe zou je dan omgaan met [[[[]]]]]] enz? Sorry, het werkt niet. Gebruik in plaats hiervan een lexer/parser-combo. Perfect is iets dat goed is voor alle mogelijke situaties en dit niet.
toegevoegd de auteur FailedDev, de bron
@AlexFord: als ik naar dat antwoord kijk, zie ik iets vreselijks: een magische zwarte doos die perfect lijkt te werken, maar die ik niet in staat ben te begrijpen of uit te leggen. Mocht ik dit duistere geschenk accepteren, dan is het slechts een kwestie van tijd voordat het zich niet gedraagt ​​zoals ik het zou willen. En dan is het arm tegenover de onheilige mystieke krachten van de regex. Pass .
toegevoegd de auteur Jon, de bron
@AlexFord: Unmaintainable, not buggy.
toegevoegd de auteur Jon, de bron
@MiguelAngelo - Debuggen is naar mijn mening niet de belangrijkste vereiste, unit testing is dat wel. De regex-engine is een zwarte doos, net zoals elke bibliotheek die je gaat gebruiken.
toegevoegd de auteur Kobi, de bron
Dit is een niet-verdedigbare code ... verwijder het en gebruik het in plaats daarvan met imperatieve codelogica. =)
toegevoegd de auteur Miguel Angelo, de bron
Ik weet dat het werkt ... maar als een regex klaar is, weet alleen God wat het betekent! Regexes zijn niet te onderhouden, het is een do-once-and-forget ding. Als je het moet veranderen, is het een hel om het helemaal opnieuw te begrijpen. Als u van plan bent deze code te onderhouden, vertel ik u dat u deze moet vervangen door iets dat stapsgewijs foutopspoorbaar is, zodat u het in de toekomst eenvoudig kunt verfijnen, als u dat wilt.
toegevoegd de auteur Miguel Angelo, de bron

3 antwoord

Ik heb een programma gemaakt dat je snaren kan ontleden op een debugeerbare, ontwikkelaarvriendelijke manier. Het is geen kleine code zoals die regexes, maar het heeft een positieve kant: je kunt het debuggen en het precies afstemmen als je het nodig hebt.

De implementatie is een afdaling recursieve parser , maar als u een soort van contextuele gegevens nodig heeft, kunt u deze plaatsen alles binnen de klasse ParseContext .

Het is vrij lang, maar ik beschouw het als beter dan een op regex gebaseerde oplossing.

Als u dit wilt testen, maakt u een consoletoepassing en vervangt u alle code in Program.cs door de volgende code:

using System.Collections.Generic;
namespace q7922337
{
    static class Program
    {
        static void Main(string[] args)
        {
            var result1 = Match.ParseList("[code]This is a successful match.[/code]");
            var result2 = Match.ParseList("[code]This is an [ unsuccessful match.[/code]");
            var result3 = Match.ParseList("[code]This is also an [unsuccessful] match.[/code]");
            var result4 = Match.ParseList(@"
                        [code]  
                            some code  
                            [b]some text [url=http://www.google.com]some link[/url][/b]  
                        [/code]");
        }
        class ParseContext
        {
            public string Source { get; set; }
            public int Position { get; set; }
        }
        abstract class Match
        {
            public override string ToString()
            {
                return this.Text;
            }
            public string Source { get; set; }
            public int Start { get; set; }
            public int Length { get; set; }
            public string Text { get { return this.Source.Substring(this.Start, this.Length); } }
            protected abstract bool ParseInternal(ParseContext context);
            public bool Parse(ParseContext context)
            {
                var result = this.ParseInternal(context);
                this.Length = context.Position - this.Start;
                return result;
            }
            public bool MarkBeginAndParse(ParseContext context)
            {
                this.Start = context.Position;
                var result = this.ParseInternal(context);
                this.Length = context.Position - this.Start;
                return result;
            }
            public static List ParseList(string source)
                where T : Match, new()
            {
                var context = new ParseContext
                {
                    Position = 0,
                    Source = source
                };
                var result = new List();
                while (true)
                {
                    var item = new T { Source = source, Start = context.Position };
                    if (!item.Parse(context))
                        break;
                    result.Add(item);
                }
                return result;
            }
            public static T ParseSingle(string source)
                where T : Match, new()
            {
                var context = new ParseContext
                {
                    Position = 0,
                    Source = source
                };
                var result = new T { Source = source, Start = context.Position };
                if (result.Parse(context))
                    return result;
                return null;
            }
            protected List ReadList(ParseContext context)
                where T : Match, new()
            {
                var result = new List();
                while (true)
                {
                    var item = new T { Source = this.Source, Start = context.Position };
                    if (!item.Parse(context))
                        break;
                    result.Add(item);
                }
                return result;
            }
            protected T ReadSingle(ParseContext context)
                where T : Match, new()
            {
                var result = new T { Source = this.Source, Start = context.Position };
                if (result.Parse(context))
                    return result;
                return null;
            }
            protected int ReadSpaces(ParseContext context)
            {
                int startPos = context.Position;
                int cnt = 0;
                while (true)
                {
                    if (startPos + cnt >= context.Source.Length)
                        break;
                    if (!char.IsWhiteSpace(context.Source[context.Position + cnt]))
                        break;
                    cnt++;
                }
                context.Position = startPos + cnt;
                return cnt;
            }
            protected bool ReadChar(ParseContext context, char p)
            {
                int startPos = context.Position;
                if (startPos >= context.Source.Length)
                    return false;
                if (context.Source[startPos] == p)
                {
                    context.Position = startPos + 1;
                    return true;
                }
                return false;
            }
        }
        class Tag : Match
        {
            protected override bool ParseInternal(ParseContext context)
            {
                int startPos = context.Position;
                if (!this.ReadChar(context, '['))
                    return false;
                this.ReadSpaces(context);
                if (this.ReadChar(context, '/'))
                    this.IsEndTag = true;
                this.ReadSpaces(context);
                var validName = this.ReadValidName(context);
                if (validName != null)
                    this.Name = validName;
                this.ReadSpaces(context);
                if (this.ReadChar(context, ']'))
                    return true;
                context.Position = startPos;
                return false;
            }
            protected string ReadValidName(ParseContext context)
            {
                int startPos = context.Position;
                int endPos = startPos;
                while (char.IsLetter(context.Source[endPos]))
                    endPos++;
                if (endPos == startPos) return null;
                context.Position = endPos;
                return context.Source.Substring(startPos, endPos - startPos);
            }
            public bool IsEndTag { get; set; }
            public string Name { get; set; }
        }
        class TagsGroup : Match
        {
            public TagsGroup()
            {
            }
            protected TagsGroup(Tag openTag)
            {
                this.Start = openTag.Start;
                this.Source = openTag.Source;
                this.OpenTag = openTag;
            }
            protected override bool ParseInternal(ParseContext context)
            {
                var startPos = context.Position;
                if (this.OpenTag == null)
                {
                    this.ReadSpaces(context);
                    this.OpenTag = this.ReadSingle(context);
                }
                if (this.OpenTag != null)
                {
                    int textStart = context.Position;
                    int textLength = 0;
                    while (true)
                    {
                        Tag tag = new Tag { Source = this.Source, Start = context.Position };
                        while (!tag.MarkBeginAndParse(context))
                        {
                            if (context.Position >= context.Source.Length)
                            {
                                context.Position = startPos;
                                return false;
                            }
                            context.Position++;
                            textLength++;
                        }
                        if (!tag.IsEndTag)
                        {
                            var tagGrpStart = context.Position;
                            var tagGrup = new TagsGroup(tag);
                            if (tagGrup.Parse(context))
                            {
                                if (textLength > 0)
                                {
                                    if (this.Contents == null) this.Contents = new List();
                                    this.Contents.Add(new Text { Source = this.Source, Start = textStart, Length = textLength });
                                    textStart = context.Position;
                                    textLength = 0;
                                }
                                this.Contents.Add(tagGrup);
                            }
                            else
                            {
                                textLength += tag.Length;
                            }
                        }
                        else
                        {
                            if (tag.Name == this.OpenTag.Name)
                            {
                                if (textLength > 0)
                                {
                                    if (this.Contents == null) this.Contents = new List();
                                    this.Contents.Add(new Text { Source = this.Source, Start = textStart, Length = textLength });
                                    textStart = context.Position;
                                    textLength = 0;
                                }
                                this.CloseTag = tag;
                                return true;
                            }
                            else
                            {
                                textLength += tag.Length;
                            }
                        }
                    }
                }
                context.Position = startPos;
                return false;
            }
            public Tag OpenTag { get; set; }
            public Tag CloseTag { get; set; }
            public List Contents { get; set; }
        }
        class Text : Match
        {
            protected override bool ParseInternal(ParseContext context)
            {
                return true;
            }
        }
    }
}

Als u deze code gebruikt en op een dag vindt dat u optimalisaties nodig hebt omdat de parser dubbelzinnig is geworden, probeert u dan een woordenboek in de ParseContext, kijk hier voor meer informatie: http://en.wikipedia.org/wiki/Top-down_parsing in het onderwerp Tijd- en ruimtecomplexiteit van top-down parsing . Ik vind het erg interessant.

3
toegevoegd
Ik zal mijn lunchpauze bekijken en kijken of ik het kan begrijpen. Zo niet, dan zal ik je waarschijnlijk weer lastigvallen! Je bent een enorme hulp geweest.
toegevoegd de auteur Chev, de bron
Dit werkt gedeeltelijk. Het lijkt niet te gaan om de "optionele waarden" na het gelijkteken, zoals in [url = http: //www.google.com] een link [/ url] , maar ik verwacht niet je moet alles voor me doen (tenzij je zo geneigd bent: P). Wanneer ik wat tijd krijg, zal ik proberen te debuggen en erachter te komen wat er hier in godsnaam aan de hand is, zodat ik het kan aanpassen om met optionele waarden te werken. Nogmaals bedankt voor de moeite. Als ik je route verlaat, markeer ik graag het volgende :)
toegevoegd de auteur Chev, de bron
Hallo, ik heb de optionele waarden niet laten ontleden. = \ ... maar het is heel eenvoudig om deze regel in de code op te nemen. Heeft u vragen over de code, ik help u graag zo snel mogelijk!
toegevoegd de auteur Miguel Angelo, de bron

The first change is pretty simple - you can get it by changing [^][]+, which is responsible for matching the free text, to .. This seems a little crazy, perhaps, but it's actually safe, because you are using a possessive group (?> ), so all the valid tags will be matched by the first alternation - \[(?[^][/=\s]+)[^][]*] - and cannot backtrack and break the tags.
(Remember to enable the Singleline flag, so . matches newlines)

De tweede vereiste, [onsuccesvol] , lijkt tegen uw doel in te gaan. Het hele idee vanaf het begin is niet om deze niet-gesloten tags te evenaren. Als u niet-gesloten tags toestaat, worden alle overeenkomsten van het formulier \ [(. *?) \]. *? [/ \ 1] geldig . Niet goed. In het beste geval kunt u proberen een aantal tags op de witte lijst te plaatsen die niet mogen overeenkomen.

Een voorbeeld van beide wijzigingen:

(?>
\[ (?[^][/=\s]+) \s*
(?: = \s* (?[^][]*) \s*)?
\]
)
  (?
    (?>
       \[(?:unsuccessful)\]  # self closing
       |
       \[(?[^][/=\s]+)[^][]*]
       |
       \[/(?<-innertag>\k)]
       |
       .
    )*
    (?(innertag)(?!))
  )
\[/\k\]

Voorbeeld van werk over Regex Hero

1
toegevoegd
"De tweede vereiste, [onsuccesvol], lijkt tegen uw doel in te gaan. Het hele idee vanaf het begin is niet om deze niet-gesloten tags te evenaren" --- Laat me verhelderen. Ik zou graag zien dat de uitdrukking overeenkomt met de buitenste tag ([code]), waarbij het [niet-succesvolle] stuk wordt herkend als gewone inhoud van de tag [code], zich realiserend dat [onsuccesvolle] geen [/ niet-succesvolle] afsluitende tag heeft. Wat er gebeurt, is dat de tag [code] niet overeenkomt wanneer [onsuccesvol] deel uitmaakt van de inhoud.
toegevoegd de auteur Chev, de bron
@Alex - Dat soort parsen vereist meestal het ontleden van het hele document, begin tot het einde. Ik zal daar een beetje over nadenken ...
toegevoegd de auteur Kobi, de bron
@AlexFord - Ik heb een ander antwoord toegevoegd, voor de sport. Ik heb niet teveel uitgelegd, vrees ik. Veel succes :) . (oh, en het kostte me de helft van de tijd om het patroon te schrijven, en de andere helft om het antwoord te schrijven ...)
toegevoegd de auteur Kobi, de bron

OK. Hier is nog een poging. Deze is een beetje ingewikkelder.
Het idee is om de hele tekst van start tot ext te matchen en te parseren tot een enkele overeenkomst . Hoewel u ze zelden als zodanig gebruikt, kunt u met .Net Balancing Groups uw opnames verfijnen, alle posities onthouden en precies zo vastleggen als u wilt.
Het patroon dat ik bedacht is:

\A
(?)
(?:
    # Open tag
    (?)          # capture the content between tags
    (?)                      # Keep the starting postion of the tag
    (?>\[(?[^][/=\s]+)[^\]\[]*\])     # opening tag
    (?)                  # start another content capture
    |
    # Close tag
    (?)          # capture the content in the tag
    \[/\k\](?)  # closing tag, keep the content in the  group
    (?<-TagName>)
    (?)                  # start another content capture
    |
    .           # just match anything. The tags are first, so it should match
                # a few if it can. (?(TagName)(?!)) keeps this in line, so
                # unmatched tags will not mess with the resul
)*
(?)          # capture the content after the last tag
\Z
(?(TagName)(?!))

Remember - the balancing group (?) captures into A all text since B was last captured (and pops that position from B's stack).

Nu kun je de string ontleden met:

Match match = Regex.Match(sample, pattern, RegexOptions.Singleline |
                                           RegexOptions.IgnorePatternWhitespace);

Uw interessante gegevens staan ​​op match.Groups ["Tag"]. Captures , die alle tags bevat (waarvan sommige in andere), en match.Groups ["Content"] .Captures , die de inhoud van de tag en de inhoud tussen de tags bevat. Zonder alle lege cellen bevat het bijvoorbeeld:

  • een code
  • wat tekst
  • Dit is ook een geslaagde overeenkomst.
  • Dit is ook een [mislukte overeenkomst.
  • Dit is ook een [niet-succesvolle] overeenkomst.

Dit is vrij dicht bij een volledig geparseerd document, maar je zult nog steeds met indices en lengte moeten spelen om de exacte volgorde en structuur van het document te achterhalen (hoewel het niet complexer is dan alle opnames te sorteren)

Op dit punt zal ik aangeven wat anderen hebben gezegd - het is misschien een goed moment om een ​​parser te schrijven, dit patroon is niet mooi ...

0
toegevoegd
@Kobi Ik geloof niet dat je antwoord een -1 verdient. Het is waarschijnlijk niet de ideale oplossing, maar het geeft direct antwoord op de vraag die ik heb gesteld. Ik zou zeggen dat voor zover een antwoord is het goed doordacht en behulpzaam was.
toegevoegd de auteur Chev, de bron
-1: Ik neem aan dat het werkt, maar ik wil graag schreeuwen
toegevoegd de auteur John Saunders, de bron
Trouwens, was je van plan om twee antwoorden te krijgen?
toegevoegd de auteur John Saunders, de bron
@John - Dat lijkt eerlijk, het behandelen van a -1 is een klein ongemak in vergelijking met het gevoel dat je :) beschrijft. Ik was van plan om twee antwoorden achter te laten, ik denk dat ze anders genoeg zijn.
toegevoegd de auteur Kobi, de bron