Abstract | ||
---|---|---|
AbstractWe 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. |
Year | DOI | Venue |
---|---|---|
2005 | 10.1145/1047124.1047497 | SIGCSE |
Keywords | Field | DocType |
pedagogy,objects-first,modeling,modeling.,design patterns,parsing,grammar,cs1/cs2,algorithms,design,object oriented,design pattern,object model | Top-down parsing language,Recursive descent parser,Top-down parsing,Programming language,S-attributed grammar,Computer science,Bottom-up parsing,Parsing expression grammar,Artificial intelligence,Natural language processing,Parsing,Parser combinator | Conference |
Volume | Issue | ISSN |
37 | 1 | 0097-8418 |
ISBN | Citations | PageRank |
1-58113-997-7 | 4 | 0.64 |
References | Authors | |
0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Dung "Zung" Nguyen | 1 | 7 | 1.86 |
Mathias Ricken | 2 | 40 | 4.60 |
Stephen Wong | 3 | 4 | 0.64 |