This page (revision-8) was last changed on 20-Jun-2014 20:54 by Dieter Käppel

This page was created on 26-Apr-2012 14:22 by Dieter Käppel

Only authorized users are allowed to rename pages.

Only authorized users are allowed to delete pages.

Page revision history

Version Date Modified Size Author Changes ... Change note
8 20-Jun-2014 20:54 11 KB Dieter Käppel to previous
7 20-Jun-2014 20:54 11 KB Dieter Käppel to previous | to last
6 20-Jun-2014 20:52 11 KB Dieter Käppel to previous | to last
5 20-Jun-2014 20:48 10 KB Dieter Käppel to previous | to last
4 20-Jun-2014 20:30 9 KB Dieter Käppel to previous | to last
3 01-Nov-2012 00:11 5 KB Dieter Käppel to previous | to last
2 26-Apr-2012 14:43 2 KB Dieter Käppel to previous | to last
1 26-Apr-2012 14:22 2 KB Dieter Käppel to last

Page References

Incoming links Outgoing links

Version management

Difference between version and

At line 4 changed one line
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.
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.
At line 16 changed 7 lines
|~| |__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.
|~| |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.
At line 24 added 40 lines
__Hinweis:__ Die Reihenfolge der Parserregeln ist für die Priorität ausschlaggebend. Falls nicht das gewünschte Ergebnis erreicht wird, ist meist die Klammerung und Reihenfolge der Regeln zu überdenken.
!!!Integrierte Parser
Einige viel gebrauchte Parser sind bereits integriert:
||Symbol||Implementierung||Bedeutung
|lower-symbol|<native>|Buchstabenfolge von a-z
|upper-symbol|<native>|Buchstabenfolge von A-Z
|letters|<native>|Buchstabenfolge von a-z oder A-Z
|symbol|<native>|Buchstabe von a-z oder A-Z gefolgt von Buchstabenfolge von a-z, A-Z, 0-9, - oder _
|string|<navtive>|Beliebige Zeichenkette (von einem anderen Parser beendet)
|comment-string|<native>|/*<string>*/
|quote-string|<native>|"<string>"
|apos-string|<native>|'<string>'
|integer|<native>|0-9
|space|<native>|Space, Tab, Return oder Linefeed
|white-space|<native>|Zeichenfolge aus space
|comma|<native>|white-space,whitespace
|semicolon|<native>|white-space;whitespace
|dot|<native>|white-space.whitespace
|apos|<native>|Apostroph (')
|quote|<native>|Quote (")
|number|number := ('+' ~| '-')? + integer.|Ganzzahl
|float|float := ('+' ~| '-')? + integer + '.' + integer?.|Fließkommazahl
|qualifier|qualifier := symbol #1 '.'.|Qualifizierendes Symbol gefolgt von einem Punkt
!!!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.
At line 37 changed one line
!!!Parser-Klassen
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
At line 152 added 217 lines
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.