Publication
Information and Control
Paper

Parsing algorithms with backtrack

View publication

Abstract

Two classes of restricted top-down parsing algorithms modeling "recursive descent" 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, it is shown that the larger class has the property that loops and other "failures" can always be eliminated. © 1973 Academic Press, Inc.

Date

Publication

Information and Control

Authors

Share