On the relative efficiencies of context-free grammar

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the relative efficiencies of context-free grammar

Full text

Pdf (1.60 MB)

Source

Communications of the ACM archive
Volume 8 , Issue 5 (May 1965) table of contents

Pages: 289 - 300

Year of Publication: 1965

ISSN:0001-0782

Authors

T. V. Griffiths	Air Force Cambridge Research Labs., Bedford, MA
S. R. Petrick	Air Force Cambridge Research Labs., Bedford, MA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 29, Citation Count: 44

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/364914.364943 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	CHOMSKY, N. Formal properties of grammars. In R. R. Bush, E. H. Galanter and R. D. Luck (Eds.), Handbook of Mathematical Psychology, Vol. 2, Ch. 12, Wiley, New York, 1962.
	2	BACKUS, J. The syntax and semantics of the proposed international algebraic language of the Zurich ACM-GAMM conference. Proc. Int. Conf. Inf. Proc., UNESCO, Paris, June, 1959.
	3	EVEY, J. The theory and application of pushdown store machines. Mathematical Linguistics and Automatic Translation, Rep. No. NSF-10, Harvard Conlp. Lab., Cambridge, 1963.
	4	GROSS, M. On the equivalence of models of language used in the fields of machine translation and information retrieval. Unpublished report, 1962.
	5	SCHMIDT, L. Implementation of a symbol manipulator for heuristic translation. Paper, 1963 ACM Natl. Conf., Denver, Colo.
	6	METCALFE, H. A parameterized compiler based on mechanical linguistics. 1963, ACM Natl. Conf., Deriver, Colo.
	7	CHOMSKY, N. On certain formal properties of grammars. Inform. Contr. 2, 2 (1959).
	8	KUNO, S., AND OETTINGER A. Multiple path syntactic analyzer. Information Processing 62, North-Holland, Amsterdam, 1963.
	9	SHERRY, M. Syntactic analysis in automatic translation. AFCRL-TR-61-100, Air Force Cambridge Research Labs., Bedford, Mass., 1901.
	10	Edgar T. Irons, A syntax directed compiler for ALGOL 60, Communications of the ACM, v.4 n.1, p.51-55, Jan. 1961 [doi>10.1145/366062.366083]
	11	--. Maintenance manual for psycho-part one. The Princeton Syntax Compiler, IDA Rep., Princeton, Jan. 1961.
	12	WARSHALL, S. A syntax-directed generator. Proc. 1961 Eastern Joint Comput. Conf., MacMillan Co., New York, 1961.
	13	BASTIAN, L. A phrase-structure language translator. AFCRL Rep. 62-549, AF Cambridge Research Labs., Bedford, Aug. 1962.
	14	WILLETT, H., AND HELWIG, F. Syntax processor. MITRE Working Pap. W-4677, Bedford, Jan. 1962.
	15	INGERMAN, P. A translation technique for languages whose syntax is expressible in extended Backus normal form. Proc. of the Int. Syrup. on Symbolic Languages in Data Processing, Rome, Italy, Apr. 1962, 741-758.
	16	James J. Baker, A note on multiplying Boolean matrices, Communications of the ACM, v.5 n.2, p.102, Feb. 1962 [doi>10.1145/366792.366825]
	17	Stephen Warshall, A Theorem on Boolean Matrices, Journal of the ACM (JACM), v.9 n.1, p.11-12, Jan. 1962 [doi>10.1145/321105.321107]
	18	PLATH, W. Mathematical linguistics. In Trends in European and American Linguistics 1930-1960, Spectrum Publ., Utrecht, Neth., 1961, 21-57.
	19	GREIBACH, S. Inverses of phrase structure generators. Mathematical Linguistics and Automatic Translation, Rep. No. NSF-11, Harvard Comput. Lab.
	20	GLENNIE, A. On the syntax machine and the construction of a universal compiler. Tech. Rep. No. 2, Contr. NR 049-141, Carnegie Inst. of Tech., Pittsburgh, July 1960.
	21	BROOKER, R., AND MORRIS, D. An assembly program for a phrase structure language. Comput. J. 3 (Oct. 1960).
	22	R. A. Brooker , D. Morris, A General Translation Program for Phrase Structure Languages, Journal of the ACM (JACM), v.9 n.1, p.1-10, Jan. 1962 [doi>10.1145/321105.321106]
	23	--. Trees and routines. Comput. J. 5, 1 (Apr. 1962).
	24	Robert S. Ledley , James B. Wilson, Automatic-programming-language translation through syntactical analysis, Communications of the ACM, v.5 n.3, p.145-155, March 1962 [doi>10.1145/366862.366872]
	25	ROBINSON, J. Preliminary codes and rules for the automatic parsing of English. RAND RM 3339, Santa Monies, Dec. 1962.
	26	Seymour Ginsburg , H. Gordon Rice, Two Families of Languages Related to ALGOL, Journal of the ACM (JACM), v.9 n.3, p.350-371, July 1962 [doi>10.1145/321127.321132]
	27	Robert W. Floyd, Syntactic Analysis and Operator Precedence, Journal of the ACM (JACM), v.10 n.3, p.316-333, July 1963 [doi>10.1145/321172.321179]
	28	GILBERT, P., HOSLER, J., AND SCHAGER, C. Automatic programming techniques. TDR-62-632, Rome Air Dev. Ctr., Rome, N. Y., Dec. 1962.
	29	M. P. Barnett , R. P. Futrelle, Syntactic analysis by digital computer, Communications of the ACM, v.5 n.10, p.515-526, Oct. 1962 [doi>10.1145/368959.368992]
	30	Ross, D. On the algorithmic theory of language. ESL-TM- 156, Elect. Systems Lab., MIT, Cambridge, Mass., Nov. 1962.
	31	BASTIAN, L., FOLEY, J., AND PETRICK, S. On the implementation and usage of a language for contract bridge bidding. Proc. of the Int. Symp. on Symbolic Languages in Data Processing, Rome, Italy, Apr. 1962, 741-758.
	32	J. W. Backus , F. L. Bauer , J. Green , C. Katz , J. McCarthy , A. J. Perlis , H. Rutishauser , K. Samelson , B. Vauquois , J. H. Wegstein , A. van Wijngaarden , M. Woodger , P. Naur, Revised report on the algorithm language ALGOL 60, Communications of the ACM, v.6 n.1, p.1-17, Jan. 1963 [doi>10.1145/366193.366201]
	33	MATTHEWS, H. Discontinuity and asymmetry in phrase structure grammars. Inform. Contr. 6, 2 (June 1963), 137- 146.
	34	KUNO, S., AND OETTINGER, A. Syntactic structure and ambiguity of English. Proc. 1963 Fall Joint Comput. Conf., Spartan Books, Baltimore, Md., 1953.
	35	----. New techniques for repetitive path elimination. Mathematical Linguistics and Automatic Translation, Sec. XI, Rep. No. NSF-13, Harvard Comput. Lab., Cambridge, Apr. 1964.
	36	ABBOTT, R. Right-to-left parsing using a predictive grammar. Mathematical Linguistics and Automatic Translation, Sec. VIII, Rep. No. NSF-13, Harvard Comput. Lab., Cambridge, Apr. 1964.
	37	KAY, M. A general procedure for rewriting strings. Paper, 1964 Ann. Mtg., Assoc. for Machine Translation and Computational Linguistics, U. of Indiana, Bloomington, 1964.
	38	GRIFFITHS, T. Turing machine recognizers for general rewriting systems. Proc. IEEE Symp. Switching Circuit Theory and Logical Design, Princeton, Nov. 1964, 47-56.

CITED BY 44

	Susumu Kuno , Anthony G. Oettinger, Computational linguistics in a Ph.D. computer science program, Communications of the ACM, v.11 n.12, p.831-836, Dec. 1968
	Jerome Feldman , David Gries, Translator writing systems, Communications of the ACM, v.11 n.2, p.77-113, Feb. 1968
	Jay Earley, An efficient context-free parsing algorithm, Communications of the ACM, v.13 n.2, p.94-102, Feb 1970
	Jacques Cohen, A view of the origins and development of Prolog, Communications of the ACM, v.31 n.1, p.26-36, Jan. 1988
	Jacques Cohen , Timothy J. Hickey, Parsing and compiling using Prolog, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.2, p.125-163, April 1987
	Susumu Kuno, The augmented predictive analyzer for context-free languages—its relative efficiency, Communications of the ACM, v.9 n.11, p.810-823, Nov. 1966
	Susan L. Graham , Michael Harrison and Walter L. Ruzzo, An Improved Context-Free Recognizer, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.3, p.415-462, July 1980
	Clarence A. Ellis, Parallel compiling techniques, Proceedings of the 1971 26th annual conference, p.508-519, January 1971
	William F. Atchison , Samuel D. Conte , John W. Hamblen , Thomas E. Hull , Thomas A. Keenan , William B. Kehl , Edward J. McCluskey , Silvio O. Navarro , Werner C. Rheinboldt , Earl J. Schweppe , William Viavant , David M. Young, Jr., Curriculum 68: Recommendations for academic programs in computer science: a report of the ACM curriculum committee on computer science, Communications of the ACM, v.11 n.3, p.151-197, March 1968
	S. R. Petrick, On the use of syntax-based translators for symbolic and algebraic manipulation, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.224-237, March 23-25, 1971, Los Angeles, California, United States
	R. A. Brooker, A note: Top-to-bottom parsing rehabilitated?, Communications of the ACM, v.10 n.4, p.223-224, April 1967
	Barry Lawrence Wolman, Operators for manipulating language structures, Proceedings of the first ACM symposium on Symbolic and algebraic manipulation, p.1601-1628, January 1966
	T. G. Evans, Man-machine interaction: Machine-aided design of context-free grammars, Proceedings of the 1965 20th national conference, p.344-353, August 24-26, 1965, Cleveland, Ohio, United States
	Kenneth M. Ross, An improved left-corner parsing algorithm, Proceedings of the 9th conference on Computational linguistics, p.333-338, July 05-10, 1982, Prague, Czechoslovakia
	T. Kasami , K. Torii, A Syntax-Analysis Procedure for Unambiguous Context-Free Grammars, Journal of the ACM (JACM), v.16 n.3, p.423-431, July 1969
	Stephen H. Unger, A global parser for context-free phrase structure grammars, Communications of the ACM, v.11 n.4, p.240-247, April 1968
	Brian Phillips , Michael J. Freiling , James H. Alexander , Steven L. Messick , Steve Rehfuss , Sheldon Nichollt, An eclectic approach to building natural language interfaces, Proceedings of the 23rd annual meeting on Association for Computational Linguistics, p.254-261, July 08-12, 1985, Chicago, Illinois
	T. V. Griffiths, Letters to the editor: on procedures for constructing structural descriptions for three parsing algorithms, Communications of the ACM, v.8 n.10, p.594, Oct. 1965
	J. G. Sanderson, Letters to the editor: On simple, low redundancy languages, Communications of the ACM, v.8 n.10, p.593, Oct. 1965
	Bruce W. Arden, The role of programming in a Ph.D. computer science program, Communications of the ACM, v.12 n.1, p.31-37, Jan. 1969
	James A. Hendler , Paul Roller Michaelis, The effects of limited grammar on interactive natural language, Proceedings of the SIGCHI conference on Human Factors in Computing Systems, p.190-192, December 12-15, 1983, Boston, Massachusetts, United States
	Reino Kurki-Suonio, On top-to-bottom recognition and left recursion, Communications of the ACM, v.9 n.7, p.527-528, July 1966
	Jay Earley, An efficient context-free parsing algorithm, Communications of the ACM, v.26 n.1, p.57-61, Jan. 1983
	G. Lindstrom, The design of parsers for incremental language processors, Proceedings of the second annual ACM symposium on Theory of computing, p.81-91, May 04-06, 1970, Northampton, Massachusetts, United States
	Alain Colmerauer, Total Precedence Relations, Journal of the ACM (JACM), v.17 n.1, p.14-30, Jan. 1970
	Robert G. Trout, A compiler—compiler system, Proceedings of the 1967 22nd national conference, p.317-322, January 1967, Washington, D.C., United States
	G. Salton, Information science in a Ph.D. computer science program, Communications of the ACM, v.12 n.2, p.111-117, Feb. 1969
	Mark Resnick , Jerome Sable, Inscan: A syntax-directed language processor, Proceedings of the 1968 23rd ACM national conference, p.423-432, August 27-29, 1968
	Daniel Chester, A parsing algorithm that extends phrases, Computational Linguistics, v.6 n.2, p.87-96, April-June 1980
	Brian Phillips , James A. Hendler, A message-passing control structure for text understanding, Proceedings of the 9th conference on Computational linguistics, p.307-312, July 05-10, 1982, Prague, Czechoslovakia
	Jacques Cohen , Martin S. Roth, Analyses of deterministic parsing algorithms, Communications of the ACM, v.21 n.6, p.448-458, June 1978
	B. A. Chartres , J. J. Florentin, A Universal Syntax-Directed Top-Down Analyzer, Journal of the ACM (JACM), v.15 n.3, p.447-464, July 1968
	D. Varga, Problems of improving the efficiency of parsing systems, Proceedings of the 1969 conference on Computational linguistics, p.1-30, September 01-04, 1969, Sång-Säby, Sweden
	Sylvie Billot , Bernard Lang, The structure of shared forests in ambiguous parsing, Proceedings of the 27th annual meeting on Association for Computational Linguistics, p.143-151, June 26-29, 1989, Vancouver, British Columbia, Canada
	Mats Wirén, A comparison of rule-invocation strategies in context-free chart parsing, Proceedings of the third conference on European chapter of the Association for Computational Linguistics, p.226-233, April 01-03, 1987, Copenhagen, Denmark
	Harry R. Tennant , Kenneth M. Ross , Richard M. Saenz , Craig W. Thompson , James R. Miller, Menu-based natural language understanding, Proceedings of the 21st annual meeting on Association for Computational Linguistics, June 15-17, 1983, Cambridge, Massachusetts
	Bernard Lang, Parallel non-deterministic bottom-up parsing, ACM SIGPLAN Notices, v.6 n.12, p.56-57, December 1971
	Jonathan Slocum, A practical comparison of parsing strategies, Proceedings of the 19th annual meeting on Association for Computational Linguistics, June 29-July 01, 1981, Stanford, California
	Bernard Lang, Parsing incomplete sentences, Proceedings of the 12th conference on Computational linguistics, p.365-371, August 22-27, 1988, Budapest, Hungry
	Robert C. Moore, Improved left-corner chart parsing for large context-free grammars, New developments in parsing technology, Kluwer Academic Publishers, Norwell, MA, 2004
	Jacques Cohen, A tribute to Alain Colmerauer, Theory and Practice of Logic Programming, v.1 n.6, p.637-646, November 2001
	Victor Schneider, Syntax-checking and parsing of context-free languages by pushdown-store automata, Proceedings of the April 18-20, 1967, spring joint computer conference, April 18-20, 1967, Atlantic City, New Jersey
	Arnold M. Zwicky , Joyce Friedman , Barbara C. Hall , Donald E. Walker, The mitre syntactic analysis procedure for transformational grammars, Proceedings of the November 30--December 1, 1965, fall joint computer conference, part I, November 30-December 01, 1965, Las Vegas, Nevada
	Brian Phillips, An object-oriented parser for text understanding, Proceedings of the Eighth international joint conference on Artificial intelligence, p.690-692, August 08-12, 1983, Karlsruhe, West Germany