Lambda ist der Parser
-Generator der Intersult.
Anwendung#
Einige Anwendungen können nicht in Java oder XML geschrieben werden, es wäre geschickter wenn man eine eigene Sprache hätte. Lambda vereinfacht die Implementierung einer Sprache extrem, zu wenigen Zeilen Code. Der Parser erzeugt einen Abstract-Syntax-Tree, also eine Baumstruktur mit den im Eingabestring gefundenen Elementen.Der Parser enthält bereits eine Reihe von Parsern für bestimmte Ausdrücke, die durch eine Metasprache angewendet werden können.
Metasprache#
Diese Metasprache (auch Parser-Parser) ist eine Sprache zur Erzeugung von Sprachen und an die Backus-Naur-Form angelehnt.
Die grundlegenden Elemente sind:
| Symbol | Parser | Beschreibung |
|---|---|---|
| " | quote-literal | Ein String (auch Literal) kann von zwei Quotes '"' (Anrührungsstrichen) umschlossen sein. |
| ' | apos-literal | Ein String kann von zwei Apos "'" (Apostrophenzeichen) umschlossen sein. |
| | | choice-expression | Definiert eine Entscheidung dass entweder der linke oder der rechte Teil neben dem Symbol verwendet werden darf. |
| + | sequence-expression | Legt fest, dass zuerst der linke Teil und dann der rechte Teil neben dem Symbol kommen muss. |
| # | delimiter-repetition-parser | Drückt aus dass der linke Teil beliebig oft wiederholt werden darf, wenn sich zwischen den Wiederholungen jeweils der rechte Teil befindet. |
| ! | simple-repetition-parser | Drückt aus, dass der linke Teil beliebig oft wiederholt werden darf. |
| . | terminal-parser-expression | Zeigt an, dass der linke Teil am Ende der Eingabe stehen muss. |
| ; | parser-set | Trennt zwei Parser-Definitionen voneinander ab. |
| := | parser-definition | Ordnet dem linken Teil "Parsernamen" die Definition auf der rechten Seite zu. |
Ergebnis#
Das Ergebnis ist ein Abstract-Syntax-Tree mit Nodes vom Typ ParseNode. Die Klasse ParseNode ist abstrakt und hat folgende Methoden:- parser: Gibt den Parser zurück, der diese Node geparsed hat.
- length: Liefert die Anzahl der Zeichen des von diesem Parser akzeptierten Ausdrucks.
- value: Gibt den Ausdruck zurück, der von diesem Parser akzeptiert wurde.
ParseNode hat zwei Implementierungen:
- Terminal: Zeigt an, dass es sich um eine Zeichenfolge handelt, die nicht weiter herunter gebrochen werden kann.
- NonTerminal: Wurde von einem Parser erzeugt, der sich selbst aus anderen Parsern zusammensetzt (Operator ':='). NonTerminal enthält zwei weitere Methoden:
- count: Anzahl der untergeordneten ParseNode-Elemente.
- get: Liefert die ParseNode einer bestimmten Position zurück. Die Position n liegt dabei zwischen 0 <= n < count.
Beispiel#
Parsers parsers = Parsers.getGlobal().clone();
parsers.create("test := operation-low + eof;");
parsers.create("bracket-expression := '(' + operation-low + ')';");
parsers.create("operand-high := symbol | bracket-expression;");");
parsers.create("operation-high := operand-high #1 ('*'| '/');");
parsers.create("operand-low := operation-high | symbol;");
parsers.create("operation-low := operand-low #1 ('+' | '-')");)";
Die Anwendung sieht dann so aus:
Scanner scanner = new Scanner("(x+y)*(a+b)+z");
ParseNode tree = parsers.parse("test", scanner);
System.out.println(tree);
Das Ergebnis ist ein Abstract-Syntax-Tree (oft als AST bezeichnet) mit der Wurzel bei der lokalen Variable tree vom Typ ParseNode.
ParseNode hat zu Debug-Zwecken eine toString-Methode, die folgendes Ergebnis liefert:
test(
operation-low(
operand-low(
operation-high(
operand-high(
bracket-expression(
"(",
operation-low(
operand-low(
operation-high(
operand-high("x")
)
),
"+",
operand-low(
operation-high(
operand-high("y")
)
)
),
")"
)
),
"*",
operand-high(
bracket-expression(
"(",
operation-low(
operand-low(
operation-high(
operand-high("a")
)
),
"+",
operand-low(
operation-high(
operand-high("b")
)
)
),
")"
)
)
)
),
"+",
operand-low(
operation-high(
operand-high("z")
)
)
),
"eof"
)
Eigene Parser-Klassen#
Parser können nicht nur über die Metasprache, sondern auch über Java-Klassen erzeugt werden. In der Praxis braucht man das nur, falls die Metasprache erweitert werden soll.
new ChoiceParser(parsers, "sequence-element", "repetition-parser", "sequence-expression", "parser-element");
Die Implementierung sieht dann so aus:
public class ChoiceParser extends Parser {
private String[] choices;
public ChoiceParser(Parsers parsers, String name, String... choices) {
super(parsers, name);
this.choices = choices;
}
@Override
public ParseNode parse(Scanner scanner) {
int position = scanner.position;
for (int i = 0; i < choices.length; ++i) {
String parser = choices[i];
ParseNode child = parse(parser, scanner);
if (child != null) {
if (name() == null || name().charAt(0) == '_')
return child;
return new NonTerminal(this, child);
}
scanner.position(position);
}
scanner.error(this, position);
return null;
}
@Override
public String toString() {
String result = name() + " := ";
for (int i = 0; i < choices.length; ++i) {
if (i > 0) result += " | ";
result += "\"" + choices[i] + "\"";
}
return result;
}
}
Compiler#
Üblicher Weise wird der Syntaxbaum nicht direkt verwendet, sondern durch Compile-Methoden. Üblich ist jeden (komplexen) Ausdruck der Metasprache auf eine Compile-Methode abzubilden.Beispiel#
Folgendes Beispiel ist ein Parser für eine Lisp-ähnliche Sprache, der ein Konstrukt von Klassen des Types "Atom" zurück gibt:
public abstract class Atom {
private static Parsers parsers;
public class Test {
public void test() {}
}
static {
try {
parsers = Parsers.getGlobal().clone();
parsers.create("list := '(' + object #0 space + ')'");
parsers.create("value := '+' | '-' | '*' | '/' | 'true' | 'false' | 'not' | 'rule'");
parsers.create("expression := object + eof; object := value | float | integer | symbol | list");
} catch (ParseException exception) {
exception.printStackTrace();
}
}
public String name() {
return null;
}
public Object value() {
return null;
}
public Atom left() {
return null;
}
public Atom right() {
return null;
}
public boolean pair() {
return false;
}
public static Atom parse(String expression) throws ParseException {
Scanner scanner = new Scanner(expression);
ParseNode tree = parsers.parse("expression", scanner);
if (tree == null)
throw new ParseException(scanner.error());
Atom atom = compile(tree);
return atom;
}
private static Atom compile(ParseNode node) {
String name = node.parser().name();
if (name.equals("symbol"))
return new Symbol(node.value());
if (name.equals("value"))
return new Value(((NonTerminal)node).get(0).value());
if (name.equals("integer"))
return new Value(new Integer(node.value()));
if (name.equals("float"))
return new Value(new Double(node.value()));
if (name.equals("list"))
return compileList((NonTerminal)node);
return compile(((NonTerminal)node).get(0));
}
private static Atom compileList(NonTerminal node) {
return compileListContent((NonTerminal)node.get(1), 0);
}
private static Atom compileListContent(NonTerminal node, int index) {
if (index >= node.count())
return null;
return new Pair(compile(node.get(index)), compileListContent(node, index + 2));
}
}
Pair:
public class Pair extends Atom {
private Atom left;
private Atom right;
private int hash = -1;
public Pair(Atom left, Atom right) {
super();
this.left = left;
this.right = right;
}
public Atom left() {
return left;
}
public Atom right() {
return right;
}
public boolean pair() {
return true;
}
}
Symbol:
public class Symbol extends Atom {
private String name;
public Symbol(String name) {
super();
this.name = name;
}
public String name() {
return name;
}
public int hashCode() {
return name.hashCode();
}
public boolean equals(Object object) {
if (object == null || !(object instanceof Symbol))
return false;
return name.equals(((Symbol)object).name);
}
public String toString() {
return name;
}
}
Value:
public class Value extends Atom {
private Object value;
public Value(Object value) {
super();
this.value = value;
}
public Object value() {
return value;
}
public int hashCode() {
return value.hashCode();
}
public boolean equals(Object object) {
if (object == null || !(object instanceof Value))
return false;
return value == null && ((Value)object).value == null || value.equals(((Value)object).value);
}
public String toString() {
return String.valueOf(value);
}
}
Der Parser kann zum Beispiel folgende Ausdrücke übersetzen:
Atom.parse("((- x (- y)) (+ x y) 1.0)")
Atom.parse("((+ x y) (+ y x) 1.0)")
Atom.parse("((* x y) (* y x) 1.0)")
Atom.parse("((- x x) 0 1.0)")
Atom.parse("((/ x x) 1 1.0)")
Atom.parse("((+ x x) (* 2 x) 1.0)")
Atom.parse("((* x 0) 0 1.0)")
Atom.parse("((* x 1) x 1.0)")
Atom.parse("((+ (+ x y) z) (+ x y z) 1.0)")
Atom.parse("(0 (* x 0) 1.0)")
Atom.parse("(true (not false) 1.0)")
Atom.parse("(false (not true) 1.0)")
Atom.parse("(false (not true) 1.0)")
Bemerkung: Das Beispiel ist Bestandteil eines Logik-Resolvers.