Deterministic parsing algorithm for classes beyond CFLs

Abstract

Deterministic parsing strategies for subclasses of the so-called mildly context-sensitive languages are proposed. Mildly context-sensitive languages are generated by k-level grammars and have parsing algorithms of time complexity O(n) where n is the size of the input. The parsers proposed here are k-level extensions of the LL(1) and LR(1) parsers for deterministic context-free languages and run in time O(n) for k-level grammars. Implementation of these parsers appears to be feasible as their space requirements are not excessive and they can be generated by straightforward extensions to existing parser generator schemes. When specialized to the case k = 2, a new deterministic parsing algorithm is obtained for a subclass of Tree Adjoining Grammars.