A minimalist LL(1) parser generator

Axel T. Schreiner
Department of Computer Science, RIT


oops3 is an object-oriented parser system for Java 5 based on LL(1) grammars and factory, observer, and visitor design patterns. Scanners, recognizers, tree builders, observer interfaces, and tree factories can be generated automatically.

Core algorithms (lookahead, parsing, code generation) are implemented as visitors. This allows oops3 to be bootstrapped with a hand-crafted tree, and the input language for grammars can easily be changed. The lookahead algorithm detects left recursion, unconnected rules, and ambiguous choices. The parsing algorithm is greedy and therefore deterministic.

The talk will discuss the architecture, the algorithms, and some surprising extensions to Extended BNF as it is commonly used in LL(1) systems.

web materials

Colloquia Series page.