Parsing algorithms with backtrack
Alexander Birman, Jeffrey David Ullman · 1970
Two classes of restricted top down parsing algorithms using backtrack are considered. We show that the smaller class recognizes all deterministic context free languages, and that both classes can be simulated in linear time on a random access machine. Certain generalizations of these parsing algorithms are shown equivalent to the larger class. Finally, some decision and closure properties of the classes of languages defined are given.