DR parsers: a generalization of LR parsers
Gennaro Costagliola, S.-K. Chang · 2002
A method is presented to construct a parser for a visual language whose specification can be done by a context-free grammar. The main idea is to allow a traditional LR parser to choose the next symbol to parse from a two-dimensional space. The positional grammar is defined, and some examples are given. The DR parser, along with the parsing algorithm and examples, is presented ('D' stands for driven scanning of the input, and 'R' for rightmost derivation in reverse.) The construction of DR(0) items and simple DR parsing tables are shown. Considerations of ambiguity are given, along with the construction of a simple DR parser for the arithmetic expression grammar. The results of a practical implementation using the Yacc tool are given.>