http://www.oopsla.org/2006/2006/index.php?option=com_content&task=view&id=137&Itemid=369

program registration submissions committee lodging portland

oops--Discovering LL(1) through objects

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.

Axel Schreiner, Computer Science, Rochester Institute of Technology
James Heliotis, Computer Science, Rochester Institute of Technology

 
Related Onward! Papers
Related Panels
Related Practitioner Reports
Related Research Papers
Related Tutorials
Related Workshops

While Space Available
Search
program registration submissions committee lodging portland
For comments and questions about the web site
please contact us at support@oopsla.org
© 2005 OOPSLA