Czy istnieje wyrażenie regularne do wykrywania prawidłowego wyrażenia regularnego?

Czy można wykryć prawidłowe wyrażenie regularne za pomocą innego wyrażenia regularnego? Jeśli tak, proszę podać przykładowy kod poniżej.

/
^                                             # start of string
(                                             # first group start
  (?:
    (?:[^?+*{}()[\]\\|]+                      # literals and ^, $
     | \\.                                    # escaped characters
     | \[ (?: \^?\\. | \^[^\\] | [^\\^] )     # character classes
          (?: [^\]\\]+ | \\. )* \]
     | \( (?:\?[:=!]|\?<[=!]|\?>)? (?1)?? \)  # parenthesis, with recursive content
     | \(\? (?:R|[+-]?\d+) \)                 # recursive matching
     )
    (?: (?:[?+*]|\{\d+(?:,\d*)?\}) [?+]? )?   # quantifiers
  | \|                                        # alternative
  )*                                          # repeat content
)                                             # end first group
$                                             # end of string
/

Jest to wyrażenie rekurencyjne i nie jest obsługiwane przez wiele silników wyrażeń regularnych. Te oparte na PCRE powinny to obsługiwać.

Bez białych znaków i komentarzy:

/^((?:(?:[^?+*{}()[\]\\|]+|\\.|\[(?:\^?\\.|\^[^\\]|[^\\^])(?:[^\]\\]+|\\.)*\]|\((?:\?[:=!]|\?<[=!]|\?>)?(?1)??\)|\(\?(?:R|[+-]?\d+)\))(?:(?:[?+*]|\{\d+(?:,\d*)?\})[?+]?)?|\|)*)$/

.NET nie obsługuje bezpośrednio rekursji. ( (?1)I (?R)konstruuje.) Rekurencja musiałaby zostać przekonwertowana na liczenie grup zrównoważonych:

^                                         # start of string
(?:
  (?: [^?+*{}()[\]\\|]+                   # literals and ^, $
   | \\.                                  # escaped characters
   | \[ (?: \^?\\. | \^[^\\] | [^\\^] )   # character classes
        (?: [^\]\\]+ | \\. )* \]
   | \( (?:\?[:=!]
         | \?<[=!]
         | \?>
         | \?<[^\W\d]\w*>
         | \?'[^\W\d]\w*'
         )?                               # opening of group
     (?<N>)                               #   increment counter
   | \)                                   # closing of group
     (?<-N>)                              #   decrement counter
   )
  (?: (?:[?+*]|\{\d+(?:,\d*)?\}) [?+]? )? # quantifiers
| \|                                      # alternative
)*                                        # repeat content
$                                         # end of string
(?(N)(?!))                                # fail if counter is non-zero.

Zagęszczony:

^(?:(?:[^?+*{}()[\]\\|]+|\\.|\[(?:\^?\\.|\^[^\\]|[^\\^])(?:[^\]\\]+|\\.)*\]|\((?:\?[:=!]|\?<[=!]|\?>|\?<[^\W\d]\w*>|\?'[^\W\d]\w*')?(?<N>)|\)(?<-N>))(?:(?:[?+*]|\{\d+(?:,\d*)?\})[?+]?)?|\|)*$(?(N)(?!))

Z komentarzy:

Czy to potwierdzi podmiany i tłumaczenia?

Sprawdza poprawność tylko części wyrażeń regularnych podstawień i tłumaczeń. s/<this part>/.../

Teoretycznie nie jest możliwe dopasowanie wszystkich prawidłowych gramatyki wyrażeń regularnych do wyrażeń regularnych.

Jest to możliwe, jeśli silnik wyrażeń regularnych obsługuje rekurencję, taką jak PCRE, ale tak naprawdę nie można tego nazwać wyrażeniami regularnymi.

Rzeczywiście „rekurencyjne wyrażenie regularne” nie jest wyrażeniem regularnym. Ale to często akceptowane rozszerzenie silników wyrażeń regularnych ... Jak na ironię, to rozszerzone wyrażenia regularne nie pasują do rozszerzonych wyrażeń regularnych.

„Teoretycznie teoria i praktyka są takie same. W praktyce nie są”. Prawie każdy, kto zna wyrażenia regularne, wie, że wyrażenia regularne nie obsługują rekurencji. Ale PCRE i większość innych implementacji obsługuje znacznie więcej niż podstawowe wyrażenia regularne.

użycie tego ze skryptem powłoki w poleceniu grep pokazuje mi jakiś błąd .. grep: Niepoprawna treść {}. Tworzę skrypt, który mógłby grepować bazę kodu, aby znaleźć wszystkie pliki zawierające wyrażenia regularne

Ten wzorzec wykorzystuje rozszerzenie zwane rekurencyjnymi wyrażeniami regularnymi. Nie jest to obsługiwane przez POSIX-owe wyrażenie regularne. Możesz spróbować z przełącznikiem -P, aby włączyć smak regularny PCRE.

Sama regex „nie jest językiem regularnym i dlatego nie można go przeanalizować wyrażeniem regularnym ...”

Dotyczy to klasycznych wyrażeń regularnych. Niektóre nowoczesne implementacje pozwalają na rekursję, co czyni go językiem bezkontekstowym, chociaż jest to dość gadatliwe dla tego zadania.

Widzę, gdzie pasujesz []()/\. i inne specjalne znaki regularne. Gdzie dopuszczasz postacie inne niż specjalne? Wygląda na to, że to pasuje ^(?:[\.]+)$, ale nie ^abcdefg$. To jest poprawne wyrażenie regularne.

[^?+*{}()[\]\\|]dopasuje dowolny pojedynczy znak, nie będący częścią żadnej innej konstrukcji. Obejmuje to zarówno dosłownym ( a- z) oraz niektórych znaków specjalnych ( ^, $, .).

Mało prawdopodobne.

Oceń to w try..catchjakimkolwiek innym języku.

Nie, jeśli mówisz ściśle o wyrażeniach regularnych, a nie o niektórych implementacjach wyrażeń regularnych, które w rzeczywistości są gramatykami pozbawionymi kontekstu.

Istnieje jedno ograniczenie wyrażeń regularnych, które uniemożliwia napisanie wyrażenia regularnego pasującego do wszystkich wyrażeń regularnych. Nie można dopasować implementacji, takich jak sparowane nawiasy klamrowe. Regeksy używają wielu takich konstrukcji, weźmy []jako przykład. Ilekroć istnieje, [musi istnieć dopasowanie ], które jest wystarczająco proste dla wyrażenia regularnego "\[.*\]".

Wyrażenia regularne uniemożliwiają ich zagnieżdżenie. Jak napisać wyrażenie regularne pasujące do zagnieżdżonych nawiasów? Odpowiedź brzmi: nie możesz bez nieskończenie długiego wyrażenia regularnego. Możesz dopasować dowolną liczbę zagnieżdżonych nawiasów za pomocą brutalnej siły, ale nigdy nie możesz dopasować arbitralnie długiego zestawu zagnieżdżonych nawiasów.

Ta funkcja jest często określana jako liczenie, ponieważ liczy się głębokość zagnieżdżenia. Wyrażenie regularne z definicji nie ma możliwości liczenia.

Skończyło się na tym, że napisałem o tym „ Ograniczenia wyrażeń regularnych ”.

Dobre pytanie.

Prawdziwe zwykłe języki nie mogą zdecydować o głęboko zagnieżdżonym, dobrze uformowanym nawiasie. Jeśli Twój alfabet zawiera, '('a Twoim ')'celem jest zdecydowanie, czy ich ciąg ma dobrze uformowany pasujący nawias. Ponieważ jest to niezbędny wymóg dla wyrażeń regularnych, odpowiedź brzmi „nie”.

Jeśli jednak poluzujesz wymaganie i dodasz rekurencję, prawdopodobnie możesz to zrobić. Powodem jest to, że rekurencja może pełnić rolę stosu, umożliwiając „policzenie” bieżącej głębokości zagnieżdżenia poprzez wciśnięcie tego stosu.

Russ Cox napisał „ Dopasowywanie wyrażeń regularnych może być proste i szybkie ”, co jest wspaniałą rozprawą na temat implementacji silnika regex.

Nie, jeśli używasz standardowych wyrażeń regularnych.

Powodem jest to, że nie można zaspokoić pompującego lematu dla zwykłych języków. Stany pompowania Lemat że ciąg należące do języka „L” jest regularny, jeżeli istnieje liczba „n” taki, że po podzieleniu ciąg na trzy podciągi x, y, ztak, że |x|>=1 && |xy|<=Nmożna powtarzać ytyle razy, ile chcesz i cały ciąg nadal będzie należeć do L.

Konsekwencją lematu pompującego jest to, że nie możesz mieć regularnych łańcuchów w formie a^Nb^Mc^N, to znaczy dwóch podciągów o tej samej długości oddzielonych innym łańcuchem. W dowolny sposób podzielona takich ciągów w x, yi znie można „pompa” ybez uzyskania ciąg z innej liczby „a” i „c”, pozostawiając oryginalny język. Tak jest na przykład w przypadku nawiasów wyrażeń regularnych.

Chociaż jest możliwe użycie rekursywnego wyrażenia regularnego, jak napisał MizardX, dla tego rodzaju rzeczy jest znacznie bardziej użyteczny parser. Regeksy pierwotnie miały być używane z normalnymi językami, ponieważ rekurencja lub posiadanie grup równoważących to tylko łatka.

Język, który definiuje prawidłowe wyrażenia regularne, jest w rzeczywistości gramatyką bezkontekstową i do jego obsługi należy użyć odpowiedniego analizatora składni. Oto przykład uniwersyteckiego projektu analizującego proste wyrażenia regularne (bez większości konstrukcji). Korzysta z JavaCC. I tak, komentarze są w języku hiszpańskim, chociaż nazwy metod są dość oczywiste.

SKIP :
{
    " "
|   "\r"
|   "\t"
|   "\n"
}
TOKEN : 
{
    < DIGITO: ["0" - "9"] >
|   < MAYUSCULA: ["A" - "Z"] >
|   < MINUSCULA: ["a" - "z"] >
|   < LAMBDA: "LAMBDA" >
|   < VACIO: "VACIO" >
}

IRegularExpression Expression() :
{
    IRegularExpression r; 
}
{
    r=Alternation() { return r; }
}

// Matchea disyunciones: ER | ER
IRegularExpression Alternation() :
{
    IRegularExpression r1 = null, r2 = null; 
}
{
    r1=Concatenation() ( "|" r2=Alternation() )?
    { 
        if (r2 == null) {
            return r1;
        } else {
            return createAlternation(r1,r2);
        } 
    }
}

// Matchea concatenaciones: ER.ER
IRegularExpression Concatenation() :
{
    IRegularExpression r1 = null, r2 = null; 
}
{
    r1=Repetition() ( "." r2=Repetition() { r1 = createConcatenation(r1,r2); } )*
    { return r1; }
}

// Matchea repeticiones: ER*
IRegularExpression Repetition() :
{
    IRegularExpression r; 
}
{
    r=Atom() ( "*" { r = createRepetition(r); } )*
    { return r; }
}

// Matchea regex atomicas: (ER), Terminal, Vacio, Lambda
IRegularExpression Atom() :
{
    String t;
    IRegularExpression r;
}
{
    ( "(" r=Expression() ")" {return r;}) 
    | t=Terminal() { return createTerminal(t); }
    | <LAMBDA> { return createLambda(); }
    | <VACIO> { return createEmpty(); }
}

// Matchea un terminal (digito o minuscula) y devuelve su valor
String Terminal() :
{
    Token t;
}
{
    ( t=<DIGITO> | t=<MINUSCULA> ) { return t.image; }
}

Możesz przesłać wyrażenie regularne, do preg_matchktórego zwróci false, jeśli wyrażenie regularne jest nieprawidłowe. Nie zapomnij użyć, @aby ukryć komunikaty o błędach:

@preg_match($regexToTest, '');

• Zwraca 1, jeśli wyrażenie regularne jest //.
• Zwróci 0, jeśli wyrażenie regularne jest w porządku.
• W przeciwnym razie zwróci fałsz.

Poniższy przykład Paula McGuire'a, pierwotnie z wiki pyparsing, ale teraz dostępny tylko za pośrednictwem Wayback Machine , daje gramatykę do parsowania niektórych wyrażeń regularnych w celu zwrócenia zestawu pasujących ciągów. Jako taki, odrzuca te, które zawierają nieograniczone warunki powtórzeń, takie jak „+” i „*”. Ale powinien dać ci wyobrażenie o tym, jak skonstruować parser, który przetworzy re.

# 
# invRegex.py
#
# Copyright 2008, Paul McGuire
#
# pyparsing script to expand a regular expression into all possible matching strings
# Supports:
# - {n} and {m,n} repetition, but not unbounded + or * repetition
# - ? optional elements
# - [] character ranges
# - () grouping
# - | alternation
#
__all__ = ["count","invert"]

from pyparsing import (Literal, oneOf, printables, ParserElement, Combine, 
    SkipTo, operatorPrecedence, ParseFatalException, Word, nums, opAssoc,
    Suppress, ParseResults, srange)

class CharacterRangeEmitter(object):
    def __init__(self,chars):
        # remove duplicate chars in character range, but preserve original order
        seen = set()
        self.charset = "".join( seen.add(c) or c for c in chars if c not in seen )
    def __str__(self):
        return '['+self.charset+']'
    def __repr__(self):
        return '['+self.charset+']'
    def makeGenerator(self):
        def genChars():
            for s in self.charset:
                yield s
        return genChars

class OptionalEmitter(object):
    def __init__(self,expr):
        self.expr = expr
    def makeGenerator(self):
        def optionalGen():
            yield ""
            for s in self.expr.makeGenerator()():
                yield s
        return optionalGen

class DotEmitter(object):
    def makeGenerator(self):
        def dotGen():
            for c in printables:
                yield c
        return dotGen

class GroupEmitter(object):
    def __init__(self,exprs):
        self.exprs = ParseResults(exprs)
    def makeGenerator(self):
        def groupGen():
            def recurseList(elist):
                if len(elist)==1:
                    for s in elist[0].makeGenerator()():
                        yield s
                else:
                    for s in elist[0].makeGenerator()():
                        for s2 in recurseList(elist[1:]):
                            yield s + s2
            if self.exprs:
                for s in recurseList(self.exprs):
                    yield s
        return groupGen

class AlternativeEmitter(object):
    def __init__(self,exprs):
        self.exprs = exprs
    def makeGenerator(self):
        def altGen():
            for e in self.exprs:
                for s in e.makeGenerator()():
                    yield s
        return altGen

class LiteralEmitter(object):
    def __init__(self,lit):
        self.lit = lit
    def __str__(self):
        return "Lit:"+self.lit
    def __repr__(self):
        return "Lit:"+self.lit
    def makeGenerator(self):
        def litGen():
            yield self.lit
        return litGen

def handleRange(toks):
    return CharacterRangeEmitter(srange(toks[0]))

def handleRepetition(toks):
    toks=toks[0]
    if toks[1] in "*+":
        raise ParseFatalException("",0,"unbounded repetition operators not supported")
    if toks[1] == "?":
        return OptionalEmitter(toks[0])
    if "count" in toks:
        return GroupEmitter([toks[0]] * int(toks.count))
    if "minCount" in toks:
        mincount = int(toks.minCount)
        maxcount = int(toks.maxCount)
        optcount = maxcount - mincount
        if optcount:
            opt = OptionalEmitter(toks[0])
            for i in range(1,optcount):
                opt = OptionalEmitter(GroupEmitter([toks[0],opt]))
            return GroupEmitter([toks[0]] * mincount + [opt])
        else:
            return [toks[0]] * mincount

def handleLiteral(toks):
    lit = ""
    for t in toks:
        if t[0] == "\\":
            if t[1] == "t":
                lit += '\t'
            else:
                lit += t[1]
        else:
            lit += t
    return LiteralEmitter(lit)    

def handleMacro(toks):
    macroChar = toks[0][1]
    if macroChar == "d":
        return CharacterRangeEmitter("0123456789")
    elif macroChar == "w":
        return CharacterRangeEmitter(srange("[A-Za-z0-9_]"))
    elif macroChar == "s":
        return LiteralEmitter(" ")
    else:
        raise ParseFatalException("",0,"unsupported macro character (" + macroChar + ")")

def handleSequence(toks):
    return GroupEmitter(toks[0])

def handleDot():
    return CharacterRangeEmitter(printables)

def handleAlternative(toks):
    return AlternativeEmitter(toks[0])


_parser = None
def parser():
    global _parser
    if _parser is None:
        ParserElement.setDefaultWhitespaceChars("")
        lbrack,rbrack,lbrace,rbrace,lparen,rparen = map(Literal,"[]{}()")

        reMacro = Combine("\\" + oneOf(list("dws")))
        escapedChar = ~reMacro + Combine("\\" + oneOf(list(printables)))
        reLiteralChar = "".join(c for c in printables if c not in r"\[]{}().*?+|") + " \t"

        reRange = Combine(lbrack + SkipTo(rbrack,ignore=escapedChar) + rbrack)
        reLiteral = ( escapedChar | oneOf(list(reLiteralChar)) )
        reDot = Literal(".")
        repetition = (
            ( lbrace + Word(nums).setResultsName("count") + rbrace ) |
            ( lbrace + Word(nums).setResultsName("minCount")+","+ Word(nums).setResultsName("maxCount") + rbrace ) |
            oneOf(list("*+?")) 
            )

        reRange.setParseAction(handleRange)
        reLiteral.setParseAction(handleLiteral)
        reMacro.setParseAction(handleMacro)
        reDot.setParseAction(handleDot)

        reTerm = ( reLiteral | reRange | reMacro | reDot )
        reExpr = operatorPrecedence( reTerm,
            [
            (repetition, 1, opAssoc.LEFT, handleRepetition),
            (None, 2, opAssoc.LEFT, handleSequence),
            (Suppress('|'), 2, opAssoc.LEFT, handleAlternative),
            ]
            )
        _parser = reExpr

    return _parser

def count(gen):
    """Simple function to count the number of elements returned by a generator."""
    i = 0
    for s in gen:
        i += 1
    return i

def invert(regex):
    """Call this routine as a generator to return all the strings that
       match the input regular expression.
           for s in invert("[A-Z]{3}\d{3}"):
               print s
    """
    invReGenerator = GroupEmitter(parser().parseString(regex)).makeGenerator()
    return invReGenerator()

def main():
    tests = r"""
    [A-EA]
    [A-D]*
    [A-D]{3}
    X[A-C]{3}Y
    X[A-C]{3}\(
    X\d
    foobar\d\d
    foobar{2}
    foobar{2,9}
    fooba[rz]{2}
    (foobar){2}
    ([01]\d)|(2[0-5])
    ([01]\d\d)|(2[0-4]\d)|(25[0-5])
    [A-C]{1,2}
    [A-C]{0,3}
    [A-C]\s[A-C]\s[A-C]
    [A-C]\s?[A-C][A-C]
    [A-C]\s([A-C][A-C])
    [A-C]\s([A-C][A-C])?
    [A-C]{2}\d{2}
    @|TH[12]
    @(@|TH[12])?
    @(@|TH[12]|AL[12]|SP[123]|TB(1[0-9]?|20?|[3-9]))?
    @(@|TH[12]|AL[12]|SP[123]|TB(1[0-9]?|20?|[3-9])|OH(1[0-9]?|2[0-9]?|30?|[4-9]))?
    (([ECMP]|HA|AK)[SD]|HS)T
    [A-CV]{2}
    A[cglmrstu]|B[aehikr]?|C[adeflmorsu]?|D[bsy]|E[rsu]|F[emr]?|G[ade]|H[efgos]?|I[nr]?|Kr?|L[airu]|M[dgnot]|N[abdeiop]?|Os?|P[abdmortu]?|R[abefghnu]|S[bcegimnr]?|T[abcehilm]|Uu[bhopqst]|U|V|W|Xe|Yb?|Z[nr]
    (a|b)|(x|y)
    (a|b) (x|y)
    """.split('\n')

    for t in tests:
        t = t.strip()
        if not t: continue
        print '-'*50
        print t
        try:
            print count(invert(t))
            for s in invert(t):
                print s
        except ParseFatalException,pfe:
            print pfe.msg
            print
            continue
        print

if __name__ == "__main__":
    main()