Parsing algorithms with backtrack
作者： Alexander Birman , Jeffrey D. Ullman
DOI: 10.1016/S0019-9958(73)90851-6
关键词:
摘要: 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 both can be simulated in linear time on a random access machine. Certain generalizations these shown equivalent to larger class. Finally, it is has property loops other “failures” always eliminated.
elsevier.com
sci-hub.se 参考文章(8)
Jeffrey D. Ullman, Alfred V. Aho, The Theory of Parsing, Translation, and Compiling ,(1972)
W. J. Chandler, Abstract families of deterministic languages symposium on the theory of computing. pp. 21- 30 ,(1969) , 10.1145/800169.805418
Seymour Ginsburg, Sheila Greibach, Deterministic context free languages Information & Computation. ,vol. 9, pp. 620- 648 ,(1966) , 10.1016/S0019-9958(66)80019-0
Jay Earley, An efficient context-free parsing algorithm Communications of the ACM. ,vol. 26, pp. 57- 61 ,(1983) , 10.1145/357980.358005
Alexander Birman, The tmg recognition schema Princeton University. ,(1970)
D. V. Schorre, META II a syntax-oriented compiler writing language Proceedings of the 1964 19th ACM national conference. pp. 41- ,(1964) , 10.1145/800257.808896
Alexander Birman, Jeffrey D. Ullman, Parsing algorithms with backtrack 11th Annual Symposium on Switching and Automata Theory (swat 1970). pp. 153- 174 ,(1970) , 10.1109/SWAT.1970.18
Jay Earley, An efficient context-free parsing algorithm Communications of the ACM. ,vol. 13, pp. 94- 102 ,(1970) , 10.1145/362007.362035