[RegEx] Bereiche überspringen

[uburoi]

Hallo zusammen!

Kurz vorweg: Ich bin reiner Hobbyprogrammierer und auch erst ganz frisch bei regulären Ausdrücken. Also die Bitte um Nachsicht, falls die Frage den Amateur verrät.

Momentan arbeite ich zu Lernzwecken an einem Texteditor, der auch rudimentäres Highlighting bieten soll (erstmal für Java-Dateien, aber der Code ist so modular aufgebaut, dass sich andere Sprachen später leicht ergänzen lassen). Die Highlighting-Methoden machen so einiges, aber ich dampfe das Vorgehen auf das Kernproblem ein, um das es mir geht.
Zuerst durchsuche ich den Text nach Kommentaren und färbe die entsprechenden Passagen grau; das Auffinden der Kommentare funktioniert sehr gut mit dem regulären Ausdruck:

^\/\*(?:(?!\*\/)(?:.|[\s]+))*\*\/$

Später durchsuche ich den Text zeilenweise nach Strings mit:

"[^"\s]*"

Jetzt das Problem: Nachdem ich die Kommentare bereits eingefärbt habe, ist das Durchsuchen dieser Teile nach Strings natürlich überflüssig (so wie ich in Kommentaren und Strings auch nicht mehr nach Keywords zu suchen brauche etc.); sie werden dort ohnehin nicht eingefärbt und es kostet sinnlos Performance. Zuerst habe ich die Positionen zwischengespeichert, die bereits markiert wurden, und dann nur noch die verbleibenden Textteile durchsucht, aber das ständige Abfragen, in welchem Textbereich ich gerade bin, hat mehr Performance gekostet, als es durch das Überspringen bereits gefärbter Textteile eingespart hat.

Daher wäre meine Frage an die RegEx-Kenner, ob ich nicht z.B. den vorausgegangenen regulären Ausdruck zur Suche der Kommentare so in die String-Suche einbinden kann, dass dort NICHT nach Strings gesucht wird? (Aber wie das aussehen könnte, übersteigt meine Vorstellungskraft…)

Aufgrund der späten Stunde werde ich wohl erst morgen wieder online sein, würde mich aber über Anregungen freuen!

Gruß Jens

PS: Ich will auch nicht ausschließen, dass ich mit meinem Vorgehen komplett auf dem Holzweg bin. Als Test habe ich eine Java-Datei mit gut 800 Codezeilen voller Keywords und Strings. Beim einfachen Tippen liegt die Dauer des Highlightens der aktuellen Zeile im einstelligen Millisekundenbereich, was mir reicht, aber die komplette Datei zu highlighten dauert etwa 120 Millisekunden, was als Verzögerung spürbar und mir deutlich zu lang ist. Und mit meinem bisherigen Vorgehen schaffe ich es auch nicht mehr, das noch merklich zu drücken (wobei ich dazu sagen muss, dass ich mit Xojo/Realbasic schreibe, das in Sachen Performance je nach Anwendung okay, aber nicht überragend ist, zumindest solange ich mit den "Bordmitteln" arbeite).

 

[Bagbag]

ob ich nicht z.B. den vorausgegangenen regulären Ausdruck zur Suche der Kommentare so in die String-Suche einbinden kann, dass dort NICHT nach Strings gesucht wird?

Das hört sich nach lookahead/lookbehind an, aber da du ja die Performance steigern willst: da bleibt dir wohl keine andere Wahl als zwischenzuspeichern was du schon hast. Wenn das bei dir zu viel Performance kostet, nutzt du wahrscheinlich falsche Datenstrukturen und/oder ineffiziente Algorithmen. Zeig uns hier am besten mal ein wenig Code.

Mit Regex wirst du es nicht schaffen, einen "richtigen" Highlighter (im Sinne von macht keine Fehler und lässt nichts aus) zu implementieren.
Ein einfacher Fall, der deine Bisherige Umsetzung schon ans Limit bringen würde:

// const codeInComment = "// comment in string literal in comment"

const comment = "/* block-comment in string literal */"

Suchst du zuerst nach Strings und lässt die danach aus, wird der Kommentar oben fälschlicherweise als String erkannt. Suchst du zuerst nach Kommentaren und lässt diese danach aus, wird der String unten nicht mehr erkannt und stattdessen als kommentar erkannt. Du könntest natürlich all diese Ausnahmen einbauen, aber das wird weder performant, noch spaßig bei der Umsetzung der Regulären Ausdrücke.
Zum Üben ist das aber zugegeben eine interessante Aufgabe, wo es viele Probleme zu lösen geben wird und man viel lernen kann - vorausgesetzt man ignoriert Fälle wie oben und hängt sich nicht daran auf.

Moderne Highlighter nutzen da bspw. Lexical Analysis in Kombination mit einem Abstract Syntax Tree. Beispiele: tree-sitter und acorn (das wird in den Chrome-DevTools benutzt).

 

[uburoi]

Vielen Dank für die ausführliche Rückmeldung!

Ja, diese von dir genannten "Ausnahmefälle" haben mir auch schon einiges Kopfzerbrechen bereitet. Vermutlich führt mein Ansatz da tatsächlich nicht weiter …

Interessant finde ich den anderen Ansatz, den du erwähnst. Einen Lexer habe ich tatsächlich schon mal programmiert (als ich mich einmal dafür interessiert habe, wie Programmiersprachen implementiert werden); der dürfte sich relativ leicht für mein Projekt umschreiben lassen.
Allerdings bin ich seinerzeit nicht weitergekommen, aus der Token-Liste einen AST zu generieren (und zu dem, was danach kommt, bin ich also gar nicht mehr gekommen). Ich muss gestehen, dass es daran gescheitert ist, dass ich nichts gefunden habe, das für mich kleinschrittig und nachvollziehbar genug erklärt, wie man einen Parser schreibt und nutzt; die Quellen im Internet, die ich durchgesehen hatte, setzten theoretisch zu viel voraus, was mir fehlte bzw. mein Verständnis überstieg. Ich vermute mal, dass mein AST für Highlighting nicht so komplex sein muss wie für das Parsen einer Programmiersprache (ich muss ja keine Operatoren etc. berücksichtigen), aber mir fehlt hier einfach ein Einstieg, von dem aus ich weiterdenken kann.
Nicht in Frage kommt aber die Nutzung einer fertigen Lösung, wie du sie verlinkst – ich möchte das schon selbst implementieren, da ich wissen will, wie es geht.

Gruß Jens

 

[Bagbag]

da ich wissen will, wie es geht.

Das könntest du, indem du z.B. in die von mir verlinkten Implementierungen reinschaust.

 

[uburoi]

Ich tue mich schwer damit, komplexen Code einfach zu lesen und zu verstehen. Etwas hinführende Grundlagen brauche ich da schon.

Beim Nachdenken über deinen ersten Post habe ich aber überlegt, ob ich überhaupt einen Parser brauche, da mir die Token-Liste ja eigentlich reicht, um dann die entsprechenden Textteile entsprechend einzufärben.
Ich habe jetzt gerade einen ersten Lexer fertig, der sicher noch an vielen Stellen verbessert werden kann, aber gegenüber meinen bisherigen Ansätzen zwei Vorzüge hat:
1. Er highlightet nun "richtig" im oben von dir beschriebenen Sinn (s. Screenshot).
2. Er arbeitet jetzt schon schneller als alle meine vorigen Ansätze. Meine Beispieldatei (ca. 27000 Zeichen, in denen etwa 1800 Tokens stecken) hat der Lexer in knapp 30 Millisekunden durch, was für mich schon mal ein vielversprechender Anfang ist.

Hier mal der Code, der – wie schon erwähnt – sicherlich noch nicht das Endprodukt ist:

Public Sub Tokenize(s As String, start As Integer, length As Integer)

  Me.TextColor = &c000000   // "Me" ist hier die Textarea
  Redim Tokens(-1)
  Dim tmp() As String = s.Split("")
  Dim ubd As Integer = tmp.Ubound
  Dim tok As String
  Dim isString, isChar, isOnelineComm, isMultiLineComm As Boolean = False
  Dim tmpStart As Integer
 
  For i As Integer = 0 To ubd
    If tmp(i) = EndOfLine And Not isMultiLineComm Then
      If isOnelineComm Then
        Tokens.Append(New Token("SINGLECOMMENT", tmpStart, i - tmpStart + 1, &c808080))
      End If
      isOnelineComm = False
      isChar = False
      isString = False
      tok = ""
    Elseif tmp(i) = " " Then
      tok = ""
    Elseif tmp(i) = "/" And Not isString And Not isChar And Not isOnelineComm And Not isMultiLineComm Then
      If i < ubd Then
        If tmp(i + 1) = "*" Then
          tmpStart = start + i
          isMultiLineComm = True
        Elseif tmp(i + 1) = "/" Then
          tmpStart = start + i
          isOnelineComm = True
        End If
      End If
    Elseif tmp(i) = "/" And i > 0 And tmp(i - 1) = "*" And isMultiLineComm Then
      Tokens.Append(New Token("MULTICOMMENT", tmpStart, i - tmpStart + 1, &c808080))
      isMultiLineComm = False
    Elseif (AscB(tmp(i)) >= 65 And AscB(tmp(i)) <= 90) Or (AscB(tmp(i)) >= 97 And AscB(tmp(i)) <= 122) Then
      tok = tok + tmp(i)
      If Not isString And Not isChar And Not isOnelineComm And Not isMultiLineComm And Highlight.Items.HasKey(tok) Then
        Tokens.Append(New Token("KEYWORD", start + i + 1 - tok.Len, tok.Len, Highlight.Items.Value(tok).ColorValue))
        tok = ""
      End If
    Elseif tmp(i) = "'" And Not isOnelineComm And Not isMultiLineComm And Not isString Then
      If Not isChar Then
        tmpStart = start + i
      Else
        Tokens.Append(New Token("SINGLEQUOTE", tmpStart, i - tmpStart + 1, &c006699))
      End If
      isChar = Not isChar
    Elseif tmp(i) = """" And Not isOnelineComm And Not isMultiLineComm And Not isChar Then
      If Not isString Then
        tmpStart = start + i
      Else
        Tokens.Append(New Token("DOUBLEQUOTE", tmpStart, i - tmpStart + 1, &c338000))
      End If
      isString = Not isString
    Else
      tok = ""
    End If
  Next
 
End Sub

Ein weiteres Problem ist nun noch, dass es vergleichsweise lange dauert (nochmal doppelt so lange wie der Lexer braucht), die entsprechenden Textteile beim Iterieren durch die Token-Liste zu färben, aber hier ist vermutlich einfach der Grenznutzen der nativen Textarea erreicht, da ich diesen Vorgang nicht beschleunigen kann …

Gruß Jens

 

[Bagbag]

Ich tue mich schwer damit, komplexen Code einfach zu lesen und zu verstehen.

Niemand sagte, dass das einfach wird Aber ja Grundlagen und einfache Beispiele wären da vielleicht durchaus eher angebracht: https://www.google.com/search?q=how+to+write+a+lexical+analyzer

aber hier ist vermutlich einfach der Grenznutzen der nativen Textarea erreicht, da ich diesen Vorgang nicht beschleunigen kann

Das ist gut möglich. Die ganzen neuen IDEs (manche nennen sie auch Texteditoren) wie Atom und Visual Studio Code rendern den Code mit HTML und CSS. Das scheint ganz gut zu klappen.

Aber das Ergebnis schaut doch schonmal ganz gut aus, auch wenn ich diese Sprachfamilie überhaupt nicht mag

 

[uburoi]

Das ist gut möglich. Die ganzen neuen IDEs (manche nennen sie auch Texteditoren) wie Atom und Visual Studio Code rendern den Code mit HTML und CSS. Das scheint ganz gut zu klappen.

Das wäre mir momentan zu aufwendig. Die Grundidee war ohnehin nur ein einfacher Texteditor für meine Zwecke. Dann dachte ich mir: So ein bisschen Keyword-Highlighting wäre doch auch nett – und dann fing der ganze Spaß erst an …

Aber das Ergebnis schaut doch schonmal ganz gut aus, auch wenn ich diese Sprachfamilie überhaupt nicht mag

Besten Dank! (Ich kann ja nochmal Code nachliefern, wenn es nennenswerte Fortschritte gibt.)
Ich finde bei bei der Basic-Familie manches auch ziemlich umständlich. Der Vorteil bei Xojo ist, dass ich aus dem gleichen Quellcode native MacOS- und (bei Bedarf) Windows-Programme kompilieren kann. Das war praktisch, weil ich mal für meinen Bruder ein Windows-Programm geschrieben habe, selbst aber nur mit MacOS und Linux arbeite. Und irgendwie bin ich dann dabei geblieben.

Gruß Jens

 

[Bagbag]

Der Vorteil bei Xojo ist, dass ich aus dem gleichen Quellcode native MacOS- und (bei Bedarf) Windows-Programme kompilieren kann.

Damit ist es aber bei weitem nicht alleine. Aber gut, das geht am Thema vorbei und sieht sowieso jeder zweite Entwickler anders.

Dann wünsche ich dir mal noch viel Spaß und Erfolg mit deinem Projekt