Alexander Birman, William H. Joyner
IEEE TSE
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.
Alexander Birman, William H. Joyner
IEEE TSE
Jeffrey D. Ullman
IEEE Trans. Inf. Theory
Jeffrey D. Ullman, Moshe Y. Vardi
SIGMOD/PODS/ 1988
Raghu Ramakrishnan, Yehoshua Sagiv, et al.
Journal of Computer and System Sciences