Mathias Ricken

Resume

Work Blog

A Concurrent Affair

Research Projects

Concutest: A Framework for Testing Concurrent Programs

Personal Website

superscalar.org

During the fall of 2004, Dr. Dung Nguyen, Dr. Stephen Wong, and I developed an object-oriented formulation of predictive recursive descent parsing.

The paper has been accepted to the SIGCSE 2005 conference held in St. Louis, Missouri, February 23-27, 2005, and was published in the conference proceedings. The presentation was on Saturday, February 27.

Abstract

We provide a systematic transformation of an LL(1) grammar to an object model that consists of

• an object structure representing the non-terminal symbols and their corresponding grammar production rules,
• a union of classes representing the terminal symbols (tokens).

We present a variant form of the visitor pattern and apply it to the above union of token classes to model a predictive recursive descent parser on the given grammar. Parsing a non-terminal is represented by a visitor to the tokens. For non-terminals that have more than one production rule, the corresponding visitors are chained together according to the chain of responsibility pattern in order to be processed correctly by a valid token. The abstract factory pattern, where each concrete factory corresponds to a non-terminal symbol, is used to manufacture appropriate parsing visitors.
Our object-oriented formulation for predictive recursive descent parsing eliminates the traditional construction of the predictive parsing table and yields a parser that is declarative and has minimal conditionals. It not only serves to teach standard techniques in parsing but also as a non-trivial exercise of object modeling for objects-first introductory courses.

Download

Here are the paper and the presentation:

Kooprey: Automatic Parser Generator

Our formulation of the parser is very easy and systematic. We demonstrate this in a simple parser generator called Kooprey. A kouprey is a Cambodian forest ox, Bos sauveli, which is in the same genus as the yak. Our misspelling suggests that the parser is object-oriented.

Source download.