TL;DR
This paper presents an object-oriented approach to building predictive recursive descent parsers for LL(1) grammars. By systematically transforming grammars into object models and leveraging design patterns like Visitor and Abstract Factory, they create parsers that are more flexible, extensible, and easier to teach in introductory programming courses compared to traditional procedural methods.
What Problem Does This Paper Address?
Traditional compiler construction, particularly the syntax analysis phase using predictive recursive descent parsing, often relies on manually constructed parsing tables and large, complex conditional statements based on token types. This approach is rigid, difficult to modify when grammars change, and doesn't align well with modern object-oriented programming principles. The authors aim to bridge this gap by demonstrating how object-oriented design patterns can be used to create a more declarative, modular, and extensible parsing framework suitable for introductory computer science curricula, specifically those following an "objects-first" approach.
Methods
The core of the paper lies in a systematic transformation of an LL(1) grammar into an object model. This model represents non-terminal symbols as classes/interfaces and their production rules using "is-a" (inheritance for branches) and "has-a" (composition for sequences) relationships, effectively modeling the parse tree structure.
Key design patterns are then applied:
- Visitor Pattern (variant): To decouple the parsing logic from the token itself. Tokens act as "hosts," and parsing algorithms are "visitors." A modified Visitor pattern is used to handle an open-ended number of token types, addressing a limitation of the standard pattern.
- Chain of Responsibility Pattern: To manage the selection of the correct visitor when a token is encountered, leveraging the LL(1) grammar's property that a single token uniquely determines the next parsing step.
- Abstract Factory Pattern: To manufacture the parsing visitors. Each non-terminal symbol is associated with a factory that creates its corresponding parsing visitor. This decouples the construction of visitors from the specific grammar details, making the system more robust and extensible. Factories are also designed to support lazy instantiation, crucial for handling recursive grammar structures.
Datasets
Not discussed in the paper. The paper uses a simple example grammar for arithmetic expressions and an extended version to illustrate its concepts.
Key Insights and Ideas
- Grammar as an Object Model: The fundamental idea is to represent the grammar's structure directly as an object model, using inheritance and composition to mirror the grammar's rules. This makes the parser's structure inherently tied to the grammar's definition.
- Token-Driven Parsing: By making tokens responsible for selecting the appropriate parsing action (via the Visitor pattern), the parser logic becomes more declarative. The token "knows" what to do when visited by a parsing visitor.
- Decoupling with Abstract Factories: The Abstract Factory pattern is crucial for managing the complexity of creating parsing visitors. It allows each grammar element (non-terminal) to be constructed independently, requiring only local knowledge of its immediate constituents, thus promoting modularity and extensibility.
- Pedagogical Value: The approach is presented as an excellent vehicle for teaching object-oriented design principles, design patterns, and abstract decomposition in introductory CS courses, moving beyond traditional procedural parsing techniques.
Key Results
The paper demonstrates the flexibility and extensibility of their approach through examples. They show that adding new tokens, non-terminals, or production rules to a grammar requires only minimal changes to the existing code, often just adding new classes and updating factory instantiations. The resulting parser is described as declarative, having minimal conditionals, and being robust and extensible.
Limitations and Future Work
- Grammar Scope: The approach is specifically designed for LL(1) grammars.
- Factory Nesting: For large grammars, the use of nested factory classes (to achieve lazy instantiation and avoid mutating setters for circular relationships) can lead to a single, unwieldy source file.
- Future Work: The authors suggest that the object structure of the parse tree can be extended with its own visitors to enable semantic analysis of the parsed input. They also note that this material is covered near the end of a CS2 (OO data structures and algorithms) course at their institution, implying it's a capstone topic for introductory OOP.
Summary updated