Output details
11 - Computer Science and Informatics
Royal Holloway, University of London
GLL parse-tree generation
<08>This paper provides the formal reference definition of our GLL algorithm, and specifies the mechanisms for derivation forest construction. The algorithm is fast and general, returning the (potentially infinite) set of derivations in worst case cubic time, but achieving linear performance on LL(1) parts of the grammar. GLL is thus becoming the algorithm of choice for developers of generalised parser generators. Rascal, the successor to the well known ASF+SDF from CWI Amsterdam, uses GLL, and Technical University Eindhoven are developing a framework for metamodelling based on GLL. Our own implementation underpins Royal Holloway's contribution to the PLanCompS project (EPSRC EP/I032657/1).