Reguläre Ausdrücke für Syntax-Erkennung

[LuckerKing]

Hi,
wie man vielleicht der Überschrift entnimmt bin ich gerade dabei ein bisschen an meinen eigenen Editor zu Basteln.
Eigtl hat der auch schon ohne Reguläre Ausdrücke funktioniert, aber leider extrem langsam.
Nun wollte ich komplett auf Reguläre Ausdrücke umsteigen.
Leider fehlt mir dazu das nötig Experten wissen (, das ich hoffentlich hier finde :D)

Nehmen wir mal an ich habe diesen Satz:
Sie sagt:"Hallo", er sagt "Hey"
Ich möchte jetzt gerne "Hallo" und "Hey" haben.
Leider finde ich mit dem Regex ".*" den ganzen Satz, da er mit " anfängt und aufhört.
Die nächste Stufe wäre dann, das bestimmte Zeichen innerhalb andere Zeichen nciht erkannt werden, aber außerhalb.
Nehem wir als Beispiel die Spache VB:
Msgbox("Hallo ich gebe hier ein ' aus ", "Msgbox") ' gibt aus:"Hallo ich gebe hier ein ' aus "
Wer die Sprache VB kennt, weiß dass das Komma innerhalb des Strings nicht als Kommentar gewertet wird und das ein String innerhalb eines Kommentar auch nicht gewertet wird.

Ist dies überhaupt möglich (auch wenn es schwierig sein sollte)?
Wenn es nicht möglich sein sollte, wie könnte ich dies sonst realisieren?
Gibt es vielleicht dazu schon irgendwo Beispiele?


Ich freue mich schon auf Eure Antworten
Gruß LuckerKing

PS: Ich mache das alles mit VB.Net

[claW]

anregungen könntest du dir ja vom sourcecode von notepad++ (http://notepad-plus.sourceforge.net/de/site.htm) holen, denn das empfinde ich als eines der besten und schnellsten ( klar, kommerzielle sachen sind z.t. schneller, allerdings kommst du da ja nicht an den code :) ). gibt natürlich noch viele weitere open source editoren mit syntax highlighting...

allerdings würde ich sagen dass reguläre ausdrücke erheblich länger brauchen als "normale" string operationen. theoretisch musst du doch einfach nur die syntax am aktuellen wort überprüfen und dann daraus jeweils deine schlüsse ziehen. wenn du jedes mal ( d.h. bei jedem tippen der tastatur ) reguläre ausdrücke anwenden willst, dann würde ich schätzen dass es bei dateien > 500kb schon arg zäh wird.

[LuckerKing]

Ich glaube schon , das Reguläre Ausdrücke schneller sind, als normale String-Such Methoden, weil dann fällt das zuordnen Weg.
Beim meinem bisherigen Code durchsuche ich z.B. alles nach " und '
und dann ordne ich die einander zu, was natürlich etwas dauert.
Aber ich werde mal gucken wie notepad++ das geregelt hat.
Danke

Achja ich hab grad mal einen Code in Csharp gefunden, für Syntaxhighlighting.
Regex r = new Regex("([ \\t{}():;])");
Wonach sucht er denn da bitte:confused::mauer:

[claW]

"([ \\t{}():;])"

heißt er such nach den bestimmten zeichen die in der eckigen klammer stehen, inkl. tab-stops ( \t = tab? hab nix anderes gefunden )

Ich glaube schon , das Reguläre Ausdrücke schneller sind, als normale String-Such Methoden, weil dann fällt das zuordnen Weg.

was denkst du denn wie reguläre ausdrücke intern funktionieren? :)

kleiner ansatz vielleicht vorneweg:

wieso willst du den ganzen text beim tippen durchsuchen? nimm doch einfach nur ab dem text der gerade getippt wurde, die zeile, das wort, ... -> um ein vielfaches schneller, da nicht der komplette immer wieder erneut ausgewertet werden muss.

[LuckerKing]

"([ \\t{}():;])"

heißt er such nach den bestimmten zeichen die in der eckigen klammer stehen, inkl. tab-stops ( \t = tab? hab nix anderes gefunden )



aber irgendwie passt der C# Code nicht zum Regex:
http://www.c-sharpcorner.com/UploadFile/duncanharris/SyntaxHighlightInRichTextBoxP112012005050840AM/SyntaxHighlightInRichTextBoxP1.aspx


Eigentlich ist das gar keine so schlechte Idee, wenn ich den gerade getippten Text nur Durchsuche.
Eigentlich hatte ich gedacht, dass ich das nicht machen kann, da es ja sein kann, das ein Suchezeichlänger ist als ein Buchstabe (z.B. /* ) ist.
(Ich überprüf ja jedesmal nach jedem Tastedruck)
Aber jetzt ist mir grad eingefallen, das ich ja nur die aktuelle Zeile immer aktualisieren muss.

Das wird mein Editor auf jedenfall sehr viel schneller machen.


Zum Regex:

Ich dachte mir Regex ist eine Funktion, die sehr komplex ist, aber auch gut strukturiert, so das sie schnell ausgeführt werden kann.

Werde aber jetzt auf Regex verzichten.

Achja hab mir mal den Quellcode von notepad++ geholt....
Du kannst mir nicht zufällig sagen, wo sich die Syntaxmakierung versteckt:confused:


Danke du hast mir sehr weiter geholfen:)

Gruß LuckerKing

[claW]

Achja hab mir mal den Quellcode von notepad++ geholt....
Du kannst mir nicht zufällig sagen, wo sich die Syntaxmakierung versteckt:confused:

hm, schau mal in /scintilla/src/lex*.cxx rein, ich glaub das könnte was sein

[Jan Krüger]

Nur, um das kurz zu erwähnen: es ist nicht möglich, mit regulären Ausdrücken nicht-reguläre Grammatiken (und das sind quasi alle Programmiersprachen) korrekt zu verarbeiten. Perl hat in seinem Dialekt regulärer Ausdrücke entsprechende Erweiterungen, aber VB.NET hat die höchstwahrscheinlich nicht. Außerdem sind sie hässlich.

[eViL_oNe]

Syntax ist normalerweise Domäne der kontextfreien Sprachen und nicht die von regulären. Mag sein, dass man gewisse einfache Strukturen durchaus auch mit einem Regex erkennen kann. Pretty-Printer sind aber im allg. auch nichts besseres als simple Tokenizer.

Für dein gepostetes Beispiel (ich nehme an, du willst Strings highlighten oder so was) reicht durchaus ein endlicher Automat. Am einfachsten ist so was umzusetzen, indem man sich das Ganze tatsächlich als einen Automaten skizziert und erst danach in Code umsetzt. Besondere Programmiertechniken wie etwa das State-Pattern erlauben sogar eine 1:1 Übernahme des Automaten in den Quälcode -- es gibt sogar Code-Generatoren dafür ;).

Stell dir einfach die möglichen Eingaben und den daraus resultierenden Folgezustand vor (die Eingabe EOF führt btw zum Endzustand).

Noch schneller geht es natürlich mit einer C-like-Vorgehensweise, nur ist das viel diffiziler. Mit regulären Ausdrücken stellst du dir leider ein Bein, denn das wird die mit Abstand langsamste Lösung sein.

[LuckerKing]

Ok, ich habs schon aufgegeben das Syntax-Highlighting mit Regulären Ausdrücken zu realisieren.

Leider musste ich auch feststellen, das es nicht reicht, wenn ich nur die aktuelle Zeile neu makiere, denn es gibt ja z.B. mehrzeilige Kommentar, die sich auf den ganzen Text auswirken und nicht nur auf eine Zeile.

Ich versuche dies jetzt irgendwie anders zu Realisieren, so dass ich nicht immer den ganzen Textdurchsuchen muss.

Wenn jemand dafür einen guten Ansatz hat bitte melden.

Ich bin grad am übelegen, ob ich nicht jede Zeile die ich gerade geschrieben habe, mit den anderen Vergleiche, wenn ein mehrzeiliger "Container" (Container z.B. " " oder /* */) darin vorkommt und dann irgendwie den zu durchsuchenden Text erweitere.
Da dies Alles noch in meinem Kopf stattfindet ist es schwirig zu erklären und ich weiß nicht, ob es überhaupt klappt.

@eViL_oNe: Kannst du mir mal bitte eine "C-like-Vorgehensweise" beschrieben oder erklären.
Ich kann mir darunter nichts vorstellen.


Danke für die Antworten
Gruß LuckerKing

[LuckerKing]

Ich hab hier noch einen Thread über Syntaxmakierung gefunden:
http://www.coding-board.de/board/showthread.php?t=24851&highlight=editor
Dort steht etwas von Suchbäumen, kann mir das jemand genau erklären?

[eViL_oNe]

@eViL_oNe: Kannst du mir mal bitte eine "C-like-Vorgehensweise" beschrieben oder erklären.
Ich kann mir darunter nichts vorstellen.


sorry, das war natürlich zu knapp erwähnt. Die Operation die man braucht, ist eine, die die Eingabe schrittweise in Symbole oder auch Tokens zerlegt. Diese Tokens haben mindestens einen Typ und einen inneren Wert. Indem man diese Tokenizer-Operation dann über die Eingabe laufen lässt, erhält man Tokens, bis man irgendwann ein EOF als Token bekommt. Das ist dann der richtige Zeitpunkt, um aufzuhören.

Pseudo-Code in Java für den Aufruf:

Tokenizer tokenizer = new Tokenizer( System.in ); // oder eine Datei oder ein String oder was auch immer ;)
Token t;
do
{
t = tokenizer.getNextToken();
if ( t.getType() != TokenType.Eof )
{
System.out.print( t.getValue() ); // hier wäre natürlich eine farbige Darstellung des Tokens sinnvoller ;)
}
} while ( t != TokenType.Eof );

Man bastelt sich eine Tokenizer-Funktion (getNextToken), die den Eingabestrom solange durchsucht, bis sie ein passendes Token findet. Für ein simples Highlighting von Strings langen da die Tokens string, eof und other (wobei das letzte ein simpler Behälter für alles, was unbekannt ist ist ;)). Wir nehmen mal an, wir haben eine Operation read() und eine Operation compare(), die uns ein Zeichen aus der Eingabe holen bzw mit etwas anderem vergleichen. Deren Umsetzung ist mir jetzt zu blöde für das Beispiel ;). Die Eingabe ist hier nicht als Benutzerinteraktion, sondern als eine Quelle für Daten zu interpretieren. Eine weitere Operation error() bringt uns Fehlermeldungen.

Java-Code, es geht auch mit jeder anderen imperativen Sprache!


Token getNextToken()
{
boolean inString = false;
StringBuilder stringBuffer = null;
int currentChar;

while ( true )
{
currentChar = read(); // read muss die Eigenschaft haben, am Ende beliebig oft EOF zurückzuliefern!!!!
if ( compare( currentChar, CharacterClasses.Eof ) )
{
// sofern wir in einem String sind, haben wir einen Fehler gefunden, denn der String wurde nicht beendet! Der Fehler wird registriert, das aktuell fehlerhafte Token wird ignoriert
if ( inString )
{
error( "unterminated string at EOF" );
}
// das Token ist ein EOF
return new Token( TokenType.Eof, null );
}
else if ( compare( currentChar, CharacterClasses.StringDelimiter ) )
{
// wir können nun in 2 Zuständen sein. Innerhalb oder außerhalb eines Strings
if ( inString ) // Stringende entdeckt
{
inString = false;
Token ret = new Token( TokenType.String, stringBuffer.ToString() );
// hier Puffer leeren!
stringBuffer = null;
return ret;
}
else // Stringanfang entdeckt
{
inString = true;
stringBuffer = new StringBuilder();
}
}
else // sonst
{
if ( inString ) // Im Stringpuffer Daten sammeln
{
// Der Puffer könnte hier noch nicht initialisiert sein!
if ( stringBuffer == null )
{
stringBuffer = new StringBuilder();
}
stringBuffer.append( (char)currentChar );
}
else // sonst ein unbekanntes Token zurückgeben
{
return new Token( TokenType.Undefined, "" + currentChar );
}
}
}
}

Die Verwendung davon ist nun relativ einfach:

man füttert den Scanner mit der Eingabe, und liest mit scan solange, bis man zu einem EOF stösst. Die Erhaltenen Tokens kann man dann etwa unterschiedlich farbig darstellen (EOF stellt man gar nicht dar, Strings etwa grün, alles andere schwarz).

Man könnte das ganze natürlich noch beliebig verkomplizieren. Man könnte etwa Tokentypen wie Delimiter (so was wie ,.(] etc), Whitespace (Space, LF, CR, Tab etc), Zahlen (Int und Floats) , reservierte Schlüsselwörter (so was wie int, boolean, char, void, for, if etc in Java) einlesen. Für einen Pretty-Printer könnte sogar ein Tokentyp ein Kommentar sein ;).

das Ganze soll nur als Demonstration dienen und ist auch nicht getestet. Spätestens bei Erweiterungen merkt man schnell, dass diese Art der Umsetzung eines endlichen Automaten sehr schwer wartbar und leicht kapputzumachen ist ;). Hier empfiehlt sich halt eher das State-Pattern. Das obige Beispiel soll eher ein abschreckendes Muster dafür dienen, wie man so was typischerweise in C macht: man merkt sich in tausenden von Zwischenvariablen die Zustände und hat lauter if-Tiraden in einem einzigen imperativen Block.

Ein etwas komplizierteres Beispiel habe ich vor längerer Zeit als Formeltaschenrechner in Java geschrieben. Hier befindet sich eine Scanner.java, die nichts anderes als das obige, jedoch natürlich weitaus komplexer macht ;)

http://www.panzerpunze.de/blog/downloads/java-code/

PS: natürlich kann man auch gleich so was wie LEX nehmen ;)

PS2: spätestens wenn man etwa fehlerhafte Klammern erkennen will, muss man schon etwas mehr als einen lexikalischen Scanner (oder auch Tokenizer genannt) erstellen ;)

[LuckerKing]

Wow, sieht alles sehr kompliziert aus ...
Aber mir war von vorne rein schon klar, dass das ne harte Nuss wird ;)
Erstmal Danke für die schöne Erklärung.
Ich hab zwar noch ein bisschen Probleme den ganzen Code zu verstehen, aber ich denke ich bin schon die ganze Zeit dabei, das C-Like mäßig zu machen.
D.h. ich benutzte viele If Abfragen und durch laufe immer den aktuell geschrieben Text (aktuelle Zeile).
Ich bin hier auf ein paar Fachwörter gestoßen, die ich noch nicht verstehe, die werd ich dann wohl mal alle nachschlagen müssen.
Könntest du mir kurz und knapp erklären, was ein Tokenizer genau ist, dazu finde ich leider bis jetzt noch nicht genauers.
Ich glaub ich hab meinen eigen Tokenizer gebaut. :D

Freut mich aber sehr, dass ich hier so ne ausführlich Erklärung bekomme.

Gruß und herzliche Dank LuckerKing

PS: Netter Scanner, werd mir den nochmal genau anschauen.


Edit: Wikipeda hilft http://de.wikipedia.org/wiki/Parser
Ich glaub da find ich alle Informationen, die ich brauche

[LuckerKing]

Ich versuch mal meine Vorgehensweise zu beschreiben.
Mit Container meine ich z.B " " oder { }

Aktuelle Zeile wird eingelesen(Reader)
Durchsuchte Zeilen werden ausgeweitet (z.B wegen mehrzeiligen Containern)
Scanbereich wird durchsucht nach Schlüsselsymbolen (/*"'{} ....) (Lexikanischer Scanner?/Tokenizer?)
Später sollen dann bei manchen Containern die Logischen zusammenhänge gefunden werden(Parser?)

Dann wird der ganze Text makiert und nebenbei die Schlüsselwörter gesucht und makiert.
Wobei ich noch am überlegen bin, ob ich die Schlüsselwort-Suche nicht auch mit in den Lexikanischen Scanner einbaue. (Wäre bestimmt besser)

Ich werde den Editor jetzt erstmal ohne Parser bauen, oder später ihn dann erweitern.

[Jan Krüger]

Schlüsselwörter werden normalerweise im Lexer (Scanner) in Tokens umgesetzt, ja. Ich kann dir übrigens z.B. ANTLR empfehlen; das ist eine Java-Anwendung, die dir aus einer Grammatik den passenden Lexer und Parser in C, Java oder diversen anderen Sprachen generiert. Mit ANTLRWorks gibt es dazu sogar eine kleine Entwicklungsumgebung, die dir aus deiner Grammatik Diagramme erzeugen kann und mit der du den Parser live an Beispieleingaben testen kannst.