Automatic generation of efficient lexical processors using finite state techniques

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Automatic generation of efficient lexical processors using finite state techniques

Full text

Pdf (1.12 MB)

Source

Communications of the ACM archive
Volume 11 , Issue 12 (December 1968) table of contents

Pages: 805 - 813

Year of Publication: 1968

ISSN:0001-0782

Authors

Walter L. Johnson	Ford Motor Co., Dearborn, MI
James H. Porter	Chevron Research Company, Richmond, CA
Stephanie I. Ackley	System Development Corp., Santa Monica, CA
Douglas T. Ross	Massachusetts Institute of Technology, Cambridge

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 34, Citation Count: 15

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/364175.364185 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	Douglas T. Ross, The AED approach to generalized computer-aided design, Proceedings of the 1967 22nd national conference, p.367-385, January 1967, Washington, D.C., United States [doi>10.1145/800196.806006]
	2	An algorithmic theory of language. Rep. No. ESL- TM-156, Electron. Syst. Lab., MIT, Cambridge, Mass., Nov. 1962.
	3	CHEATHAM, T. E., JR. The TGS-II translator generator system. Proc. IFIP Cong., 1965, Vol. 2, pp. 592-593.
	4	Melvin E. Conway, Design of a separable transition-diagram compiler, Communications of the ACM, v.6 n.7, p.396-408, July 1963 [doi>10.1145/366663.366704]
	5	FLOYD, R. W. The syntax of programming language-a survey. IEEE Trans. (Aug. 1964), 346-353.
	6	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]
	7	McNAUGHTON, R. Techniques for manipulating regular expressions. MIT memo, Cambridge, Mass., Nov. 1965.
	8	--, AND YAMADA, H. Regular expressions and state graphs for automata. In Moore, E. F. (Ed.), Sequential machinesselected papers, Bell Tel. Labs., Inc., Murray Hill, N.J.
	9	SHANNON, D. E., AND McCARTHY, J. Automata Studies. Princeton U. Press, Princeton, N. J., 1956.
	10	Douglas T. Ross, A generalized technique for symbol manipulation and numerical calculation, Communications of the ACM, v.4 n.3, p.147-150, March 1961 [doi>10.1145/366199.366256]
	11	Jerome Feldman , David Gries, Translator writing systems, Communications of the ACM, v.11 n.2, p.77-113, Feb. 1968 [doi>10.1145/362896.362902]

CITED BY 15

	Ravi Sethi, Control flow aspects of semantics directed compiling (Summary), ACM SIGPLAN Notices, v.17 n.6, p.245-260, June 1982
	D. Soda , G. W. Zobrist, A finite machine description of a lexical analysis using table look-up, Proceedings of the 17th conference on ACM Annual Computer Science Conference, p.309-312, February 21-23, 1989, Louisville, Kentucky
	Ravi Sethi, Control Flow Aspects of Semantics-Directed Compiling, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.4, p.554-595, Oct. 1983
	S. Ron Oliver , Nell D. Jones, Program control via transition matrices—a novel application of micro-programming, ACM SIGPLAN Notices, v.11 n.4, p.70-77, April 1976
	Alfred V. Aho , Margaret J. Corasick, Efficient string matching: an aid to bibliographic search, Communications of the ACM, v.18 n.6, p.333-340, June 1975
	Charles L. A. Clarke , Gordon V. Cormack, On the use of regular expressions for searching text, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.3, p.413-426, May 1997
	Yaohan Chu, Design of a microprogrammed lexical microprocessor, Proceedings of the 8th annual workshop on Microprogramming, p.26-39, September 21-23, 1975, Chicago, United States
	Mark W. Bailey , Jack W. Davidson, A formal model and specification language for procedure calling conventions, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.298-310, January 23-25, 1995, San Francisco, California, United States
	Nir Piterman , Moshe Y. Vardi, From bidirectionality to alternation, Theoretical Computer Science, v.295 n.1-3, p.295-321, 24 February 2003
	Mark W. Bailey , Jack W. Davidson, Automatic Detection and Diagnosis of Faults in Generated Code for Procedure Calls, IEEE Transactions on Software Engineering, v.29 n.11, p.1031-1042, November 2003
	Michael G. Main , David B. Benson, Denotational semantics for "natural" language question-answering programs, Computational Linguistics, v.9 n.1, p.11-21, January-March 1983
	Ernst Leiss, Constructing a finite automaton for a given regular expression, ACM SIGACT News, v.12 n.3, Fall 1980
	A. Ron Oliver , Neil D. Jones, Program control via transition matrices: a novel application of micro-programming, ACM SIGMICRO Newsletter, v.7 n.1, p.8-27, March 1976
	R. H. Bullen, Jr. , J. K. Millen, Microtext: the design of a microprogrammed finite state search machine for full-text retrieval, Proceedings of the December 5-7, 1972, fall joint computer conference, part I, December 05-07, 1972, Anaheim, California
	Howard L. Morgan , Robert A. Wagner, PL/C: the design of a high-performance compiler for PL/I, Proceedings of the May 18-20, 1971, spring joint computer conference, May 18-20, 1971, Atlantic City, New Jersey

INDEX TERMS

Keywords:
character string, compiler, finite-state automata, finite-state machine, lexical processor, nondeterministic machine, parsing, plex structure, regular expressions, sequential machine, syntatic analysis

Collaborative Colleagues:

Walter L. Johnson: colleagues

James H. Porter: colleagues

Stephanie I. Ackley: colleagues

Douglas T. Ross: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player