vorkommen von regulären ausdrücken in anderen regulären ausdrücken
-
Hallo,
ich möchte gerne prüfen, ob ein regulärer ausdruck k in einem regulären ausdruck v "vorkommt". formal:
k kommt in v vor, falls gilt:
es gibt wörter l,r in L(v) so dass gilt: L(l)L(k)L(r) ist teilmenge von L(v)Nun möchte ich bei allen vorkommen von k in v eine "abkürzung" a (ist buchstabe) einbauen, d.h:
ich möchte den regulären ausdruck v zu v' so erweitern, dass gilt:
1. L(v) ist teilmenge von L(v')
2. für irgendwelche wörter l und r, für die gilt:
L(l)L(k)L(r) ist teilmenge von L(v)
soll das wort lar in L(v') enthalten sein.Kann mir einer einen tipp geben, wie ich dieses problem am besten lösen kann? Brauche das für die entwicklung eines editors.
vielen dank im voraus!
Gruß
mathik
-
Also, wenn du das Ganze eh programmieren willst, empfehle ich dir Scanner oder Parser Programme wie Flex, Yacc oder Bison zu benutzen.
Flex (http://www.cs.princeton.edu/~appel/modern/c/software/flex/flex_toc.html) ist beispielsweise ein freies Programm mit der man Strings in Tokens zerlegen kann. Mittels regulären Ausdrücken spezifiziert man die einzelnen Tokens. Weiterhin kann man festlegen, wie das Programm beim Finden eines Tokens reagieren soll.
-
@Bitte ein Bit
ich will ja nichts parsen....ich denke, ich habe eine lösung für mein problem gefunden. man muss einfach einen graphmorphismus von dem automaten (minimierter DFA) zu einem regulären ausdruck in den automaten des anderen regulären ausdrucks konstruieren können....
Gruß
mathik
-
Leider ist Subgraph-Isomorphism NP-schwer...
