regulären Ausdruck für (lange) Strings

blueflash

Member of Honour
Hi,

ich suche dringend einen regulären Ausdruck, der lange Strings (auf java Art, d.h. etwas in der Art von "Hi, World \n this is a \"-quoted string.\n") matcht.

Ich habs bereits mit
Code:
((\\.)|[^"\\])*

versucht, aber aufgrund der Choice (|) wird in der Java Implementierung und auch in der Jakarta Engine ein Stack Overflow produziert, sobald mehr als 500 Zeichen geprüft werden sollen und das ist einfach nicht akzeptabel.

Hat jemand eine bessere Lösung zur Hand?
 

LX

Member of Honour
Äh, was willst du matchen? ?(

Code:
(.*)
 

blueflash

Member of Honour
Strings.

Also Anführungszeichen + alles was kein Anführungszeichen ist, oder per backslash escaped wurde und zwar beliebig oft + Anführungszeichen.
 

LX

Member of Honour
Das läuft wohl nur mittels Look Behind Assertions. Sowas in der Richtung könnte klappen:

Code:
(".*(?<!\\\\)")
 

Elderan

Moderator
Hallo,
also es sollte so gehen:
" ( \. | [^"] )* "

Das musst du nur richtig in den reg. Ausdrück für die entsprechen Sprache überführen.

(z.B. ist mit \. gemeint: Erst ein \, dann ein beliebiges Zeichen).


Wie man drauf kommt:
Erst den deterministischen endlichen Automaten aufzeichen der deinen String erkennt (ist trivial einfach) und dann daraus den reg. Ausdruck ableiten.

Der muss dann nur noch in die reguläre Semantik deiner Sprache überführt werden.
 

beavisbee

Member of Honour
Original von Elderan
" ( \. | [^"] )* "
[...]
(z.B. ist mit \. gemeint: Erst ein \, dann ein beliebiges Zeichen).

so escapest du nur den Punkt... d.h. also "entweder ein Punkt, oder ein Zeichen, was kein " ist "

Wenn du einen Backslash abfangen willst, musst du den Backslash auch escapen
Code:
"(\\.|[^"])*"
 

Chromatin

Moderator
Mitarbeiter
"Hi, World \n this is a \"-quoted string.\n"
Das bloede ist, man sollte ungefaehr wissen was man matchen will bei solchen Dingern.
Ansonsten kann ein byteweiser parser durchaus mehr Sinn machen.


Bei mir matcht zb folgende Reg (greedy) auf deinen String:

Code:
[\w\W\d\-\.\\", ]*

Steht der String denn in irgendeinem Kontext wo man ihn rausfiltern muss?
 

Elderan

Moderator
Hallo,
Original von beavisbee
Original von Elderan
" ( \. | [^"] )* "
[...]
(z.B. ist mit \. gemeint: Erst ein \, dann ein beliebiges Zeichen).

so escapest du nur den Punkt... d.h. also "entweder ein Punkt, oder ein Zeichen, was kein " ist "

Wenn du einen Backslash abfangen willst, musst du den Backslash auch escapen
Code:
"(\\.|[^"])*"


Das musst du nur richtig in den reg. Ausdrück für die entsprechen Sprache überführen.

Das ist der reguläre Ausdruck ohne Escapen ohne alles. Denn das Escapen hängt immer von der verwendeten Programmiersprache ab, nicht in jeder Sprache escaped man mit einem Backslash.
In C# könnte man beispielsweise einfach ein @ vor den String setzen und schon ist das escapen per \ abgeschaltet (d.h. in C# wäre @"\n" die beiden Character '\' 'n' und kein Zeilenumbruch).


Deswegen sollte man reguläre Ausdrücke in meinen Augen möglichst ohne Escape-Zeichen angeben (so wie man das bei formalen Sprachen für gewöhnlich macht), sofern es möglich ist, denn das erhöht deutlich die Lesbarkeit des Ausdruckes.

Klar, *, (, [ muss man escapen, da es für den regulären Ausdruck vorbehalten ist. Ein Backslash, sofern man es als regulären Ausdruck (als formale Sprahce) aufschreibt, muss aber nicht zwingend escaped werden.
 

valenterry

New member
Original von Elderan
Hallo,
also es sollte so gehen:
" ( \. | [^"] )* "

Eingabe: >>>" einbisschentext \\" nochetwastext"<<<

>>>" einbisschentext <<<

würde bei dir matchen. Dann kommt:

>>>\<<<

Das würde auch matchen, schließlich passt [^"] darauf. Danach:

>>>\"<<<

Trifft auch zu, wegen dem dem regex \. also ein Backslash und dann irgendwas, z.b. Anführungszeichen. Der Rest geht dann auch.

Eigentlich sollte der regex hier aber nicht matchen, weil ja der erste Backslash den zweiten escaped und das Anführungszeichen danach nicht mehr escaped ist und somit potentiell ein Syntaxfehler vorliegt.
Folglich muss sichergestellt werden, dass vor jedem Anführungszeichen, das zwischen dem ersten und dem letzten liegt, eine ungerade Anzahl an Backslashen steht.
 

MontyPerl

New member
" einbisschentext \\" nochetwastext"
Der Fall wird korrekt von Elderans Lösung geparst. Der erste Backslash wird vom literal backslash gematcht (weil immer zuerst der backslash probiert wird) und dann der nächste vom "dot".
Was allerdings auch matchen würde, ist das hier:
Code:
"foo\"
Der backslash wird dann durch die charclass [^"] gematcht (nach dem backtracking, weil die erste Variante (\.) zwar matchen würde, dann aber kein quote mehr am Ende steht.)

Man sollte vielleicht vor dem schließenden quote noch mal eine charclass "kein quote und kein backslash" hinpacken.

edit: oooder einfach die charclass direkt als [^"\\] ("mit" escape hier..) schreiben. Dann wären wir btw bei der Lösung des Threadstarters angelangt...
 

blueflash

Member of Honour
Erstmal danke für die rege Beteiligung, ich war schon drafu und dran den Lexer so aufzubohren, dass man eigene Matcher Klassen einbauen kann, dass _scheint_ jetzt nicht mehr nötig zu sein.

Hier ist das Testprogramm:

Code:
import java.io.Console;
import java.util.regex.Pattern;
import java.util.regex.Matcher;



public class Test {
	public static void main(String[] args) {
 	        
		Console console = System.console();
	        if (console == null) {
	            System.err.println("No console.");
	            System.exit(1);
	        }
        	
		String inputString = "\"";
		for (int i =0; i < 200; i++)
			inputString += "\\\"1234567890\\\"";
		inputString += "\"this is no valid stuff";
		console.format("Input string length: %d characters\n",inputString.length());
		Pattern pattern = Pattern.compile(args[0]);

           	Matcher matcher = pattern.matcher(inputString);

		if (matcher.lookingAt()) {
			console.format("lookingAt() yields true\n");
			console.format("end is: %d\n",matcher.end());
		} else {
			console.format("No match found.%n");
            	}
    	}
}

Zu den Ergebnissen:

@LX: Deine Regex hat scheinbar funktioniert, ich werd das gleich mal auf die ganze Library loslassen.

@Chromatin: Deine hat scheinbar auch funktioniert, ich muss mir aber erst noch darüber klar werden, was durch den Einsatz der Characterklassen da so rauskommt. Achja: Ich weiss ziemlich genau, was ich machen will. Eben Java artige Strings mit regulären Ausdrücken in Token verwandeln (vulgo Lexen).

@Elderan: Das war im Grunde auch meine Idee allerdings führt diese Art Regex ziemlich sicher zum Stack overflow. Kannst es gerne mal mit dem Testprogramm ausprobieren. (Achja, damit kann man eventuell auch die ein oder andere Webapp knacken ....) Die SUN Entwickler haben scheinbar eine rekursive Methode umgesetzt, hier zu matchen. Eine rekursion pro Zeichen oder so...
 

Elderan

Moderator
Hallo,
ansonsten den deterministischen endlichen Automaten bauen der dein Problem löst. Ist oftmal erheblich leichter als den reg. Ausdruck dazu zu finden und teilweise (je nach Sprache und Problem) auch noch schneller als ein reg. Ausdruck:

In Pseudo-Java-C#-Sprache:
Code:
//input: Char-Array mit deiner Eingabe
match = new StringBuffer();
for(int i=0;i<input.Length; i++) {
  if(input[i] != '"') //ein "
    continue;
  
  i++;
  match.Clear();

  //String auslesen
  for(; i<input.Length; i++) {
     if(input[i] == '"') //ein " 
       break;
     if(input[i] == '\\') { //ein \
        i++;
        match.Append('das \n z.B. in Zeilenumbruch umwandeln');
     }
      else
         match.Append(input[i]);
   }
   System.out.writeline(match.ToString());
}
 

blueflash

Member of Honour
Nachtrag: Beide "funktionierenden Lösungen haben den Nachteil, dass sie zu gierig sind, also über Stringgrenzen hinweg matchen.

Ich habe also LX' Ansatz erweitert, mal sehen, wie das läuft:

Code:
"[(?<=\\")"[^"]]*?(?<!\\)"

@Elderan: Ja, natürlich. Allerdings soll der Lexer ja auch von anderen benutzt werden können, man müsste also die Architektur so gestalten, dass beliebige Klassen dafür genutzt werden können. Kann man machen, wird wohl aber langsam. Wenns nicht anders geht, muss ich das halt machen.
 
Oben