Generator für einen Parser implementieren

lam_tr

Top Contributor
Hallo zusammen,

ich einen Generator implementieren, der je nach Definition einen Parser generiert.

Wenn ich zum Beispiel eine kleine Grammatik Definition in Form von EBNF habe, Wie erstelle ich dann zum Beispiel anhand von dem am Besten einen Parser?
Bevor ich überhaupt an den Parser rangehe, ist es zuerst sinnvoller die Texteingabe oder das zum einlesende Dokument zu tokenizen über eine Lexer.

Ich habe im Netz und ein bisschen Erfahrung bekommen wie man einen Text einliest. Da gibt es e.g.:
- Scanner
- StringTokenizer
- Apache Files#readLines(String filepath) und über einen Split kann ich dann Zeile für Zeile tokenizen

Was ist an der Stelle der einfachste und beste Weg die Tokens zu bestimmen?

Ich weiß das ist ein sehr großes Thema, was nicht in ein Thread abgearbeitet werden kann. Aber ich möchte gerne TIpps und best practises von euch holen.

Background warum ich das machen will ist, ich will einen Editor Framework implementieren der mithilfe von so ein Generator das Ganze darstellt. Und ja zu dem Punkt kenne ich auch schon viele Frameworks die das machen, e.g. JavaFX Code Compensator https://tomsondev.bestsolution.at/2...and-a-code-dev-environment-written-in-javafx/, Xtext und vermutlich noch mehr...

Sagen wir so, mein Framework soll nicht abhängig von Eclipse sein und zu dieser Corona Zeit kann ich auch in so ein schönes Thema einsteigen.

Grüße
lam

P.S. Lange rede kurzer Sinn, erster Schritt, wie tokenize ich am Besten?
 

CSHW89

Bekanntes Mitglied
Es gibt z.b. Flex (Lexer-) und Java-Cup (Parser-Generator). Diese sind quellenoffen. Wenn du es komplett selbst implementieren willst, kann ich dir zumindest grob sagen, wie sie funktionieren. Lexer-Generatoren benutzen RegEx's für jeden Tokentyp und ermitteln anhand der Reihenfolge der Tokentypen das nächste Token. Parser-Generatoren arbeiten meist mit Hilfe von LALR(1)- oder LL(1)-Parsern. Ich bevorzuge LALR(1)-Parser, da ich die Konflikte dort verständlicher finde. Ein sehr gutes Buch dazu ist dies hier:
 

lam_tr

Top Contributor
@CSHW89
Vielen Dank erstmal für die Documentationen und Begrifflichkeiten.

Ich will komplett Lexer and Parser selber schreiben, das ist zumindest der erste Schritt, danach anhand von Templates etwas generischer machen und als letzter Schritt es komplett generieren lassen.

Ich habe hier diesen Artikel gelesen dass der StringTokenizer schon sinnvoller ist https://www.developer.com/java/data/exploring-the-java-string-tokenizer.html.

Also wenn ich mithilfe von StringTokenizer hätte ich zumindest die Strings gesplittet und über eine Klasse TokenInfo zum Beispiel kann ich sagen was das genau ist

class Token{
String value;
TokenType type;
}

Ist das soweit in Ordnung und verständlich?
 

httpdigest

Top Contributor
Der java.util.StringTokenizer ist hierfür nicht sinnvoll. Du willst ja nicht den gesamten Text nur anhand einzelner Delimiter in Token auftrennen, sondern du willst pro Token per RegEx beschrieben, wie ein Token jeweils identifiziert wird.
Du willst also nicht einfach sagen: "Ein Token ist alles das, was durch Leerzeichen getrennt ist", sondern "Eine Zahl ist [0-9]+, ein String ist ein doppeltes Anführungszeichen, dann beliebige Zeichen _inklusive_ Leerzeichen und dann doppeltes Anführungszeichen".
 

lam_tr

Top Contributor
Ich glaube ich habe das Ganze zu einfach gedacht.

Wenn ich das hier ausführe, dann kann es einfach gesplittet werden in 3 Tokens. Wenn keine Leerzeichen da sind, kann man das sowieso vergessen
Code:
public class LexerExample {

    public static void main(String[] args) {
        StringTokenizer tokenizer = new StringTokenizer("5 + 5");
        while (tokenizer.hasMoreElements()) {
            String tokenValue = tokenizer.nextToken();
            System.out.println(tokenValue);
        }
    }
}

Dieses Beispiel zeigt dass "(5" als ein Token betrachtet wird. Wahrscheinlich ist es schon besser über RegEx das anzugehen. Wie geht man da am Besten vor mit RegEx?
Code:
public class LexerExample {

    public static void main(String[] args) {
        StringTokenizer tokenizer = new StringTokenizer("(5 + 5 ) * 5");
        while (tokenizer.hasMoreElements()) {
            String tokenValue = tokenizer.nextToken();
            System.out.println(tokenValue);
        }
    }
}
 

lam_tr

Top Contributor
Der java.util.StringTokenizer ist hierfür nicht sinnvoll. Du willst ja nicht den gesamten Text nur anhand einzelner Delimiter in Token auftrennen, sondern du willst pro Token per RegEx beschrieben, wie ein Token jeweils identifiziert wird.
Du willst also nicht einfach sagen: "Ein Token ist alles das, was durch Leerzeichen getrennt ist", sondern "Eine Zahl ist [0-9]+, ein String ist ein doppeltes Anführungszeichen, dann beliebige Zeichen _inklusive_ Leerzeichen und dann doppeltes Anführungszeichen".
Ja Danke, ich bin gerade selber auf die Nase gefallen als ich das umsetzen wollte. RegEx ist nicht meine Stärke... wie kann man das angehen? wenn ich ein Muster als Token beschreiben möchte?
 

temi

Top Contributor
Also gleich vorweg: Ich habe keine Ahnung davon. Nur ein kleiner Gedanke meinerseits. Nehmen wir den Ausdruck "(5+ 5 ) * 5". Daran sieht man sehr schön, dass es keine eigentlichen Trennzeichen gibt, sondern jedes Zeichen einzeln betrachtet werden muss.

Das erste Zeichen ist eine "(", das ist ein eigenes Token. Das nächste Zeichen ist die "5". Das kann ein eigenes Token sein, es könnten aber auch noch weitere Ziffern folgen, die noch zur 5 gerechnet werden müssen, usw. Das nächste Token beginnt demnach, wenn ein Zeichen kommt, dass nicht mehr zum vorherigen Token gehört (gehören kann), wie das "+" das später folgt.

Edit: Wenn du Zeichen für Zeichen durchgehst sollte am Ende sowas wie das haben:

Tokentype: "ParenthesisOpen"
Tokentype: "Literal" Value: 5
Tokentype: "Plus"
usw.

Wie gesagt keine Ahnung davon...
 
Zuletzt bearbeitet:

lam_tr

Top Contributor
Also gleich vorweg: Ich habe keine Ahnung davon. Nur ein kleiner Gedanke meinerseits. Nehmen wir den Ausdruck "(5+ 5 ) * 5". Daran sieht man sehr schön, dass es keine eigentlichen Trennzeichen gibt, sondern jedes Zeichen einzeln betrachtet werden muss.

Das erste Zeichen ist eine "(", das ist ein eigenes Token. Das nächste Zeichen ist die "5". Das kann ein eigenes Token sein, es könnten aber auch noch weitere Ziffern folgen, die noch zur 5 gerechnet werden müssen, usw. Das nächste Token beginnt demnach, wenn ein Zeichen kommt, dass nicht mehr zum vorherigen Token gehört (gehören kann), wie das "+" das später folgt.

Wie gesagt keine Ahnung davon...
Also an sich muss ich noch bestimmen wann ein Token beginnt und endet. Okay so langsam wirds kompliziert.
 

lam_tr

Top Contributor
Hier habe ich ein richtig cooles Example gefundem, womit ich Tokens per Regex definieren kann http://giocc.com/writing-a-lexer-in-java-1-7-using-regex-named-capturing-groups.html

Code:
import java.util.ArrayList;
import java.util.regex.Pattern;
import java.util.regex.Matcher;

public class Lexer {
  public static enum TokenType {
    // Token types cannot have underscores
    NUMBER("-?[0-9]+"), BINARYOP("[*|/|+|-]"), WHITESPACE("[ \t\f\r\n]+");

    public final String pattern;

    private TokenType(String pattern) {
      this.pattern = pattern;
    }
  }

  public static class Token {
    public TokenType type;
    public String data;

    public Token(TokenType type, String data) {
      this.type = type;
      this.data = data;
    }

    @Override
    public String toString() {
      return String.format("(%s %s)", type.name(), data);
    }
  }

  public static ArrayList<Token> lex(String input) {
    // The tokens to return
    ArrayList<Token> tokens = new ArrayList<Token>();

    // Lexer logic begins here
    StringBuffer tokenPatternsBuffer = new StringBuffer();
    for (TokenType tokenType : TokenType.values())
      tokenPatternsBuffer.append(String.format("|(?<%s>%s)", tokenType.name(), tokenType.pattern));
    Pattern tokenPatterns = Pattern.compile(new String(tokenPatternsBuffer.substring(1)));

    // Begin matching tokens
    Matcher matcher = tokenPatterns.matcher(input);
    while (matcher.find()) {
      if (matcher.group(TokenType.NUMBER.name()) != null) {
        tokens.add(new Token(TokenType.NUMBER, matcher.group(TokenType.NUMBER.name())));
        continue;
      } else if (matcher.group(TokenType.BINARYOP.name()) != null) {
        tokens.add(new Token(TokenType.BINARYOP, matcher.group(TokenType.BINARYOP.name())));
        continue;
      } else if (matcher.group(TokenType.WHITESPACE.name()) != null)
        continue;
    }

    return tokens;
  }

  public static void main(String[] args) {
    String input = "11 + 22 - 33";

    // Create tokens and print them
    ArrayList<Token> tokens = lex(input);
    for (Token token : tokens)
      System.out.println(token);
  }
}

Wenn ich das Beispiel erweitern möchte mit Keywords "public", "private", "protectec" machen möchte, wie nehme ich das als RegEx auf und muss das als jeweils ein TokenType aufgezählt werden oder kann ich das als KEYWORD hinzufügen?
 

LimDul

Top Contributor
Im Endeffekt besteht eine EBNF aus ganz ganz vielen verschiedenen Token. Das heißt, was du brauchst ist:
- Für jedes Token einen exakt passenden regulären Ausdruck
- Einen Parser, der einen Zustand und weiß, welche Token als nächstes erlaubt sind
 

lam_tr

Top Contributor
An sich kann ich mich an das Beispiel von oben mich halten und für jeden Token wie LimDul schon sagt eine RegEx erstellen und natürlich die If Bedingung weiter unten erweitern. Und für Keywords die ich oben beschrieben habe einfach ein TokenType mit hardcoded keywords

Code:
package helloworld;

import java.util.ArrayList;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Lexer {
    public static enum TokenType {
        // Token types cannot have underscores
        NUMBER("-?[0-9]+"),
        BINARYOP("[*|/|+|-]"),
        KEYWORDS("class|function|static|this|return"),
        WHITESPACE("[ \t\f\r\n]+");

        public final String pattern;

        private TokenType(String pattern) {
            this.pattern = pattern;
        }
    }

    public static class Token {
        public TokenType type;

        public String data;

        public Token(TokenType type, String data) {
            this.type = type;
            this.data = data;
        }

        @Override
        public String toString() {
            return String.format("(%s %s)", type.name(), data);
        }
    }

    public static ArrayList<Token> lex(String input) {
        // The tokens to return
        ArrayList<Token> tokens = new ArrayList<Token>();

        // Lexer logic begins here
        StringBuffer tokenPatternsBuffer = new StringBuffer();
        for (TokenType tokenType : TokenType.values()) {
            tokenPatternsBuffer.append(String.format("|(?<%s>%s)", tokenType.name(), tokenType.pattern));
        }
        Pattern tokenPatterns = Pattern.compile(new String(tokenPatternsBuffer.substring(1)));

        // Begin matching tokens
        Matcher matcher = tokenPatterns.matcher(input);
        while (matcher.find()) {
            if (matcher.group(TokenType.NUMBER.name()) != null) {
                tokens.add(new Token(TokenType.NUMBER, matcher.group(TokenType.NUMBER.name())));
                continue;
            } else if (matcher.group(TokenType.BINARYOP.name()) != null) {
                tokens.add(new Token(TokenType.BINARYOP, matcher.group(TokenType.BINARYOP.name())));
                continue;
            } else if (matcher.group(TokenType.KEYWORDS.name()) != null) {
                tokens.add(new Token(TokenType.KEYWORDS, matcher.group(TokenType.KEYWORDS.name())));
                continue;
            } else if (matcher.group(TokenType.WHITESPACE.name()) != null) {
                continue;
            }
        }

        return tokens;
    }

    public static void main(String[] args) {
        String input = "11 + 22 - 33 class static final";

        // Create tokens and print them
        ArrayList<Token> tokens = lex(input);
        for (Token token : tokens) {
            System.out.println(token);
        }
    }
}

Cool, ich bin auf jeden Fall schon mal ein Schritt weiter.
 

lam_tr

Top Contributor
Guten morgen zusammen,

wie kann ich einen Token für Multiline String machen? Der String sieht dann so aus

Code:
"""
Heute ist Donnerstag.
Morgen ist Freitag.
Übermorgen ist Samstag.
"""
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
1 Name Generator für Videos Allgemeine Java-Themen 1
D Parser-generator für mathematische Funktionen Allgemeine Java-Themen 12
Buroto Arrays generator Allgemeine Java-Themen 10
E Random Generator Allgemeine Java-Themen 6
S QR-Code generator Allgemeine Java-Themen 2
A Audio Rechteck Generator Allgemeine Java-Themen 5
borobudur MVC Model Generator Allgemeine Java-Themen 2
boxi Registartions CodeBild generator Allgemeine Java-Themen 2
G Scanner-Generator zur Erkennung von Java Tokens Allgemeine Java-Themen 7
B Von neumann generator Allgemeine Java-Themen 7
Karl_Der_Nette_Anfänger Hat wer ne Lösung für verknüpfte Postleitzahlen? (Baum/Wurzel Struktur) Allgemeine Java-Themen 11
R 11 GB File lesen ohne zu extrahieren Filedaten Bereich für Bereich adressieren dann mit Multi-Thread id die DB importieren Allgemeine Java-Themen 3
G KeyListener für JTextField Allgemeine Java-Themen 5
webracer999 Library für Textsuche (z. B. include/exclude, and/or)? Allgemeine Java-Themen 5
I Module-Info für Jar erzeugen Allgemeine Java-Themen 7
krgewb Java-Bibliothek für ONVIF Allgemeine Java-Themen 1
B Simpler Eventlistener für Tastaturtaste bauen? Allgemeine Java-Themen 13
_user_q Eingegebenen Text Zeile für Zeile ausgeben lassen Allgemeine Java-Themen 11
E Key für TOTP Algorythmus(Google Authentificator) Allgemeine Java-Themen 0
S Formel für Sonnenwinkel in ein Programm überführen Allgemeine Java-Themen 11
M pfx-Zertifikat in Tomcat für SSL-Verschlüsselung nutzen Allgemeine Java-Themen 14
R Best Practice Erfahrungswerte für eine Migration von JSF nach Angular (oder anderes JS-Framework) Allgemeine Java-Themen 1
B HeapSort für Array of Strings funktioniert nur teilweise Allgemeine Java-Themen 3
jhCDtGVjcZGcfzug Klassen Was genau passiert hier? Kann mir das jemand bitte Zeile für Zeile erklären? Allgemeine Java-Themen 1
rosima26 Bester Sortieralgorithmus für kurze Arrays Allgemeine Java-Themen 40
S Mit Methoden kann man definieren für was <T> steht. Geht das auch irgendwie für Variablen? Allgemeine Java-Themen 12
MangoTango Operatoren while-Schleife für Potenz Allgemeine Java-Themen 3
B Lottospiel, genug Reihen tippen für 3 Richtige (Spaß mit Arrays)? Allgemeine Java-Themen 46
B Mit welchen Datentypen und Strukturierung am Besten dutzende Baccaratspiele Shcritt für Schritt durchsimulieren? Allgemeine Java-Themen 26
D Klassendesign für einen Pascal Interpreter Allgemeine Java-Themen 6
I OCR Library für Belegerkennung Allgemeine Java-Themen 7
farah GetterMathod für Farbkanäle Allgemeine Java-Themen 6
B Welcher Datentyp für sehr große Zahlenbereiche? Allgemeine Java-Themen 1
S Webservices für binäre Daten? Allgemeine Java-Themen 5
G Licence-Header für InHouse entwickelten Source Allgemeine Java-Themen 8
M Schleife für einen TicTacToe Computer Allgemeine Java-Themen 5
O git ignore für Intellji braucht es die .idea Dateien? Allgemeine Java-Themen 8
F Java Script für das Vorhaben das richtige? Allgemeine Java-Themen 9
M wiviel Java muss ich für die Berufswelt können ? Allgemeine Java-Themen 5
Robertop Datumsformat für GB ab Java 16 Allgemeine Java-Themen 1
Thallius Verschiedene entities für gleichen Code…. Allgemeine Java-Themen 8
OnDemand Zentrale "Drehscheibe" für verschiedene APIs Allgemeine Java-Themen 14
S Übergabe eines Sortierkriteriums für ein Artikel Array mittels BiPredicate<Artikel, Artikel> Allgemeine Java-Themen 13
F Streams als Alternative für dieses Problem ? Allgemeine Java-Themen 15
D SHA-3 für Java-version 1.8 Allgemeine Java-Themen 1
N Validator für einen SQL-Befehl Allgemeine Java-Themen 22
Muatasem Hammud Erstellung von Testdaten für Arrays Allgemeine Java-Themen 6
B Logikfehlersuche, das perfekte Lottosystem für 3 Richtige mit Arraylists? Allgemeine Java-Themen 61
G Methoden für die Zukunft sinnvoll? Allgemeine Java-Themen 4
M API für PLZ Umkreissuche Allgemeine Java-Themen 3
1Spinne JDK 8 für Eclipse installieren Allgemeine Java-Themen 5
Tobero Meine Funktion für das beinhalten eines Punktes in einem Kreis funktioniert nicht Allgemeine Java-Themen 5
L Methoden Parser für gängige Datumsformate? Allgemeine Java-Themen 1
H Interface PluginSystem ClassNotFound exception für library Klassen Allgemeine Java-Themen 10
N relativier Pfad für sqlite-Datenbank in Gradle/IntelliJ Allgemeine Java-Themen 2
buchfrau Anagram für beliebiges Wort Allgemeine Java-Themen 2
TonioTec Api für Datenaustausch zwischen Client und Server Allgemeine Java-Themen 0
W Suche Ursache für NPE - woher kommt sie? (Hilfe beim Debugging) Allgemeine Java-Themen 19
Kirby.exe Distanz Map für die Distanztransformation erstellen Allgemeine Java-Themen 1
F PI Regler für Heizung Allgemeine Java-Themen 7
8u3631984 Generelle Log4j.xml für alle Module Allgemeine Java-Themen 5
M Wie übergebe ich den Zähler für die Anzahl Rekursionsschritte korrekt? Allgemeine Java-Themen 2
B Login für User, der im Hintergrund Schedules ausführt Allgemeine Java-Themen 16
L RegEx für Teile einer Berechnung Allgemeine Java-Themen 14
S Java-Task-Management-Tool für Windows und Mac selber programmieren Allgemeine Java-Themen 4
M Java 2D Array für ein Grid erstellen ? Allgemeine Java-Themen 2
Z Welches GUI Framework für Java ist aktuell? Allgemeine Java-Themen 16
N Convert.FromBase64 von C# für Java Allgemeine Java-Themen 11
N fixed-keyword von C# für Java Allgemeine Java-Themen 6
O Suche Scripter für alt:V Project! Allgemeine Java-Themen 0
S Interface Design von HookUp oder Callback Methoden für eigenes Framework Allgemeine Java-Themen 9
O Suche Unterstützung für ein OpenSource-Projekt (grafischer Editor) Allgemeine Java-Themen 13
Kirby.exe Software für Graphische Visualisierung Allgemeine Java-Themen 20
B OOP Auslöser für NullPointerException Allgemeine Java-Themen 3
DonMalte Ambitioniertes Projekt für Einsteiger & Motivierte Allgemeine Java-Themen 0
Kirby.exe Movement System für Spiel Allgemeine Java-Themen 13
Kirby.exe Framework für Game Design Allgemeine Java-Themen 8
W Alternative für Threads Allgemeine Java-Themen 6
S Rückgabe einer HttpURLConnection für eine Seite einlesen bei der man eingeloggt ist..? Allgemeine Java-Themen 5
Elyt Compiler-Fehler Datei kann nicht erstellt werden. Die Syntax für den Dateinamen etc. ist falsch. Allgemeine Java-Themen 2
Thallius Rätsel für Windows Profis Allgemeine Java-Themen 8
D OOP Gemeinsamen ID-Raum für zwei Klassen implementieren Allgemeine Java-Themen 7
D Input/Output Implementierung eines CommandHandlers/Parsers für viele Eingaben Allgemeine Java-Themen 26
Thallius Alternative für SwingWorker Allgemeine Java-Themen 5
I Lohnt sich heutzutage der Aufwand einer Portierung für MacOS Allgemeine Java-Themen 8
L Klassen Algorithmus für das folgende Problem entwickeln? Allgemeine Java-Themen 30
J Datenstruktur für eine Map erstellen Allgemeine Java-Themen 2
H OOP Setting(config) für Applikation sicheren? Allgemeine Java-Themen 9
OnDemand PDF Libary für Formulare Allgemeine Java-Themen 7
S Warmup für Lineare-Suche mit Zeitmessung Allgemeine Java-Themen 2
T Allgemeine Frage: GUI für 3D-Visualisierung Allgemeine Java-Themen 5
M Brainstorming für mein Projekt Allgemeine Java-Themen 30
K OOP Suche Hilfe + Erklärung für eine Hausaufgabe Allgemeine Java-Themen 1
F Was ist der Dateityp meines Parameters für die Main Methode. Allgemeine Java-Themen 6
C Bibliotheken für Algorithmische Geometrie Allgemeine Java-Themen 2
C Daten für Klassifikationsverfahren gewinnen Allgemeine Java-Themen 6
C code oder Bibliotheken für 2-Center Problem Allgemeine Java-Themen 4
I Overlay für Spiele Allgemeine Java-Themen 5
B Suche nach einem Testprogramm für meine BA Allgemeine Java-Themen 0
I GUI für kleine Pop-Ups unter Windows Allgemeine Java-Themen 1

Ähnliche Java Themen

Neue Themen


Oben