oops--Discovering LL(1) through objects

A grammar is suitable for top-down recursive descent parsing if it is LL(1). Deriving the algorithm to test if a grammar is LL(1) usually involves inspection of a BNF version of the grammar, representing certain adjacency relations as matrices, and finally performing some subtle computations on the matrices. It is difficult to present the problem intuitively enough so that the algorithm can be discovered by students. oops is an LL(1) parser generator that represents an EBNF-based grammar as a tree of objects that are observed as they recognize input. The objects are also able to test if the grammar is LL(1). Distributing the algorithm over several classes makes it simple enough to be discovered during a classroom presentation. This paper discusses the new architecture of oops and the LL(1) checking and parsing algorithms and defines some extensions to EBNF which simplify some sticky language definition problems but are very simple to implement using inheritance.