A basis for looping extensions to discriminating-reverse parsing

Abstract

We present a noncanonical extension to the Discriminating Reverse parsing method, which accepts non-LR grammars. In cases of parsing conflict, actions are deferred and a mark is virtually pushed onto the parsing stack. Then, locally-canonical DR parsing resumes until sufficient right context is read to resolve the initial conflict. Marks code coverings of the right contexts that are compatible with the actions in conflict. A suboptimal solution for such a coding is proposed, which is computed from the DR automaton itself. The stack vocabulary is enlarged with the mark set, but no new state is added to the basic DR automaton. Moreover, conflict resolution basically uses the DR parser. The method determines at construction time whether all the conflicts can be resolved, and only produces deterministic parsers.