Generalised Recursive Descent parsing and Fellow-Determinism

Abstract

This paper presents a construct for mapping arbitrary non-left recursive context-free grammars into recursive descent parsers that: handle ambiguous grammars correctly; perform with LL(1) efficiency on LL(1) grammars; allow straightforward implementation of both inherited and synthesized attributes; and allow semantic actions to be added at any point in the grammar. We describe both the basic algorithm and a tool, GRDP, which generates parsers which use this technique. Modifications of the basic algorithm to improve efficiency lead to a discussion of follow-determinism , a fundamental property that gives insights into the behaviour of both LL and LR parsers. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.