Generator für einen Parser implementieren

Diskutiere Generator für einen Parser implementieren im Allgemeine Java-Themen Bereich.
L

lam_tr

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?
 
C

CSHW89

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:
 
L

lam_tr

@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?
 
H

httpdigest

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".
 
L

lam_tr

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);
        }
    }
}
 
L

lam_tr

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?
 
T

temi

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:
L

lam_tr

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.
 
L

lam_tr

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?
 
L

LimDul

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
 
L

lam_tr

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.
 
L

lam_tr

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.
"""
 
Thema: 

Generator für einen Parser implementieren

Passende Stellenanzeigen aus deiner Region:
Anzeige

Neue Themen

Anzeige

Anzeige
Oben