SGTDBF

This is the prototype implementation of the Scannerless General Top Down Binary Forest parser.

TODO: Elaborate on the motivation and intent.

It is not based on any existing algorithm. But it basically works like a 'normal' top down parser, with the difference that it is able to handle ambiguity, attempts to recognize all possible alternatives in parallel (in a breadth-first way) and uses a graph to model the parse stacks (in which the nodes are maximally shared, so it can contain cycles). Besides that there is some trickery in there to handle nullable related nastiness (like hidden-right-recursion), to be able to support the full range of context-free grammars.

Furthermore a lot of algorithmic and code optimizations were introduced into the implementation to make it blazingly fast, both in worst and general case scenarios.

It's still a work in progress and the code is fairly ... incomprehensible, so don't hurt yourself trying to read it ;-).

====== Scaling:

• O(N) for LL grammars.
• O(N) for LR grammars.
• O(N^3) worst case.
• Usually near O(N) on non-ambiguous or locally ambiguous grammars.

====== Performance:

• Not-all-that-much slower than commonly used non-general parsers written in Java (i.e. the overhead of being 'general' remains relatively in check).
• Somewhere between a lot and multiple orders of magnitude faster than most other general(ized) parsers, depending on the grammar. E.g. 16ms parse time for the 'S ::= SSS | SS | 'a' | epsilon' grammer @ 100 input chars, 396ms @ 300 input chars, 2.3 seconds @ 500 input char; vs somewhere in between 'my machine just exploded' and 'the sun has exploded and I'm still not done'.

====== Supported 'fancy' features:

• Native support for:
  • Star- and plus-lists.
  • Optionals.
  • Sequences.
  • Choices.
• Production prefix sharing
  • Overlapping productions are automatically merged for improved performance and scalability without affecting the produced AST.
• Build-in filtering support.
  • Scoping (e.g. for encoding priorities).
  • Restrictions (e.g. for encoding associativity).
  • Input based filtering (i.e. restrictions on preceding, following or matched characters), which can easily be extended by the user.

====== Wishlist:

• A tree you can work with (right now it's binarized).
• Better error reporting.
• A cleaner, more advanced method of defining grammars.
• Semantic actions to enable more advanced filtering.
• Even better performance.

====== Usage: TODO: Add some more information (like an overview of available constructs).

A basic example (see comments inline):

packagegtd.examples;
importgtd.Parser;
importgtd.generator.FromClassGenerator;
importgtd.generator.ParserStructure;
importgtd.grammar.structure.Alternative;
importgtd.grammar.symbols.Char;
importgtd.grammar.symbols.Literal;
importgtd.grammar.symbols.PlusList;
importgtd.grammar.symbols.Sort;
importgtd.result.AbstractNode;
publicclassHelloWorld {
publicstaticAlternative[] Exclamation() {
returnnewAlternative[] {
newAlternative(newSort("Word"), newPlusList(newSort("Whitespace")), newSort("Word"))
};
}
publicstaticAlternative[] Word() {
returnnewAlternative[] {
newAlternative(newLiteral("Hello")),
newAlternative(newLiteral("world"))
};
}
publicstaticAlternative[] Whitespace() {
returnnewAlternative[]{
newAlternative(newChar(' '))
};
}
publicstaticvoidmain(String[] args) {
// Convert the given class into a for the parser usable format.// Note that this structure is reusable between parser instances.ParserStructurestructure = newFromClassGenerator(HelloWorld.class).generate();
char[] input = "Hello world".toCharArray();
// Construct a new parser instance for the given input string.Parserparser = newParser(input, structure);
// Start the parser with the given sort as start symbol.AbstractNoderesult = parser.parse("Exclamation");
System.out.println(result);
}
}

Parser definitions can be extended:

packagegtd.examples;
importgtd.Parser;
importgtd.generator.FromClassGenerator;
importgtd.generator.ParserStructure;
importgtd.grammar.structure.Alternative;
importgtd.grammar.symbols.Literal;
importgtd.grammar.symbols.Sort;
importgtd.result.AbstractNode;
publicclassHierarchy {
publicstaticclassSuperClass {
publicstaticAlternative[] A() {
returnnewAlternative[] {
newAlternative(newLiteral("a"))
};
}
publicstaticAlternative[] S() {
returnnewAlternative[] {
newAlternative(newSort("A"))
};
}
}
publicstaticclassSubClassextendsSuperClass {
// Add a new sortpublicstaticAlternative[] B() {
returnnewAlternative[] {
newAlternative(newLiteral("b"))
};
}
// Replace the definition of SpublicstaticAlternative[] S() {
returnnewAlternative[] {
newAlternative(newSort("A")),
newAlternative(newSort("A"), newSort("B"))
};
}
}
publicstaticvoidmain(String[] args) {
// Generate a parser structure for the SubClassParserStructurestructure = newFromClassGenerator(SubClass.class).generate();
char[] input = "ab".toCharArray();
Parserparser = newParser(input, structure);
AbstractNoderesult = parser.parse("S");
System.out.println(result);
}
}

Additionally a public static array of classes called IMPORTS can be defined, which will be imported transitively, in order:

packagegtd.examples;
importgtd.Parser;
importgtd.generator.FromClassGenerator;
importgtd.generator.ParserStructure;
importgtd.grammar.structure.Alternative;
importgtd.grammar.symbols.Literal;
importgtd.grammar.symbols.Sort;
importgtd.result.AbstractNode;
publicclassImports {
publicstaticclassGenericStuff {
publicstaticAlternative[] A() {
returnnewAlternative[] {
newAlternative(newLiteral("a"))
};
}
publicstaticAlternative[] S() {
returnnewAlternative[] {
newAlternative(newSort("A"))
};
}
}
publicstaticclassSpec {
publicfinalstaticClass<?>[] IMPORTS = newClass<?>[]{GenericStuff.class};
publicstaticAlternative[] B() {
returnnewAlternative[] {
newAlternative(newLiteral("b"))
};
}
publicstaticAlternative[] S() {
returnnewAlternative[] {
newAlternative(newSort("A")),
newAlternative(newSort("A"), newSort("B"))
};
}
}
publicstaticvoidmain(String[] args) {
// Generate a parser structure for the SubClassParserStructurestructure = newFromClassGenerator(Spec.class).generate();
char[] input = "ab".toCharArray();
Parserparser = newParser(input, structure);
AbstractNoderesult = parser.parse("S");
System.out.println(result);
}
}

Restricted sorts (can be used to encode associativity):

packagegtd.examples;
importgtd.Parser;
importgtd.generator.FromClassGenerator;
importgtd.generator.ParserStructure;
importgtd.grammar.structure.Alternative;
importgtd.grammar.structure.IStructure;
importgtd.grammar.symbols.Char;
importgtd.grammar.symbols.CharRange;
importgtd.grammar.symbols.RSort;
importgtd.grammar.symbols.Sort;
importgtd.result.AbstractNode;
publicclassAssociativity {
publicstaticIStructure[] Number() {
returnnewIStructure[] {
newAlternative(newCharRange('0', '9'))
};
}
publicstaticIStructure[] Expr() {
returnnewIStructure[] {
// Restrict the nesting of the self recursive alternatives of this sort// on the right side.newAlternative(newSort("Expr"), newChar('+'), newRSort("Expr")),
newAlternative(newSort("Expr"), newChar('-'), newRSort("Expr")),
newAlternative(newSort("Number"))
};
}
publicstaticvoidmain(String[] args) {
ParserStructurestructure = newFromClassGenerator(Associativity.class).generate();
char[] input = "1+2-3".toCharArray();
Parserparser = newParser(input, structure);
AbstractNoderesult = parser.parse("Expr");
System.out.println(result);
}
}

Scoping (can be used for encoding priorities for example):

packagegtd.examples;
importgtd.Parser;
importgtd.generator.FromClassGenerator;
importgtd.generator.ParserStructure;
importgtd.grammar.structure.Alternative;
importgtd.grammar.structure.IStructure;
importgtd.grammar.structure.Scope;
importgtd.grammar.symbols.Char;
importgtd.grammar.symbols.CharRange;
importgtd.grammar.symbols.RSort;
importgtd.grammar.symbols.Sort;
importgtd.grammar.symbols.TLSort;
importgtd.result.AbstractNode;
publicclassPriority {
publicstaticIStructure[] Number() {
returnnewIStructure[] {
newAlternative(newCharRange('0', '9'))
};
}
publicstaticIStructure[] Expr() {
returnnewIStructure[] {
// Restricted sorts and scopes can be combined; note that// restrictions are only applied within the scope and not to any of// the alternatives inherited from nested scopes.newAlternative(newSort("Expr"), newChar('+'), newRSort("Expr")),
// Recursive sorts within a scope can only contain alternatives from// within that scope and scopes below it in the hierarchy.newScope(
newAlternative(newSort("Expr"), newChar('*'), newRSort("Expr")),
// The top-level version of the sort can be referenced from within// a scope using TLSorts instead of 'normal' ones.newAlternative(newChar('('), newTLSort("Expr"), newChar(')')),
newAlternative(newSort("Number"))
)
};
}
publicstaticvoidmain(String[] args) {
ParserStructurestructure = newFromClassGenerator(Priority.class).generate();
char[] input = "1+2*(3*4+5)".toCharArray();
Parserparser = newParser(input, structure);
AbstractNoderesult = parser.parse("Expr");
System.out.println(result);
}
}