article

Free access

Automatic generation of efficient lexical processors using finite state techniques

Authors:

Walter L. Johnson,

James H. Porter,

Stephanie I. Ackley,

Douglas T. RossAuthors Info & Claims

Communications of the ACM, Volume 11, Issue 12

Pages 805 - 813

https://doi.org/10.1145/364175.364185

Published: 01 December 1968 Publication History

PDF eReader

References

[1]

ROSS, D. T. The AED approach to generalized computeraided design. Proc. ACM 22nd Nat. Conf., 1967, pp. 367-385.

Digital Library

Google Scholar

[2]

An algorithmic theory of language. Rep. No. ESL- TM-156, Electron. Syst. Lab., MIT, Cambridge, Mass., Nov. 1962.

Google Scholar

[3]

CHEATHAM, T. E., JR. The TGS-II translator generator system. Proc. IFIP Cong., 1965, Vol. 2, pp. 592-593.

Google Scholar

[4]

CONWAY, M. E. Design of a separable transition-diagram compiler. Comm. ACM 6, 7 (July 1963), 396-408.

Digital Library

Google Scholar

[5]

FLOYD, R. W. The syntax of programming language-a survey. IEEE Trans. (Aug. 1964), 346-353.

Google Scholar

[6]

LEDLEY, R. S., AND WILSON, J. B. Automatic-programminglanguage translation through syntactical analysis. Comm. ACM 5, 3 (Mar. 1962), 145-155.

Digital Library

Google Scholar

[7]

McNAUGHTON, R. Techniques for manipulating regular expressions. MIT memo, Cambridge, Mass., Nov. 1965.

Google Scholar

[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.

Google Scholar

[9]

SHANNON, D. E., AND McCARTHY, J. Automata Studies. Princeton U. Press, Princeton, N. J., 1956.

Google Scholar

[10]

ROSS, D. T. A generalized technique for symbol manipulation and numerical calculation. Comm. ACM 4, 3 (Mar. 1961), 147-150.

Digital Library

Google Scholar

[11]

FELDMAN, J., AND GRIES, D. Translator writing systems. Comm. ACM 2, 2 (Feb. 1968), 77-113.

Digital Library

Google Scholar

Cited By

View all

Le Glaunec AKong LMamouras K(2024)HybridSA: GPU Acceleration of Multi-pattern Regex Matching using Bit ParallelismProceedings of the ACM on Programming Languages10.1145/36897718:OOPSLA2(1699-1728)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689771
Mamouras KChattopadhyay A(2024)Efficient Matching of Regular Expressions with Lookaround AssertionsProceedings of the ACM on Programming Languages10.1145/36329348:POPL(2761-2791)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632934
Riveros CVan Sint Jan NVrgoč D(2023)REmatch: A Novel Regex Engine for Finding All MatchesProceedings of the VLDB Endowment10.14778/3611479.361148816:11(2792-2804)Online publication date: 24-Aug-2023
https://dl.acm.org/doi/10.14778/3611479.3611488
Show More Cited By

Recommendations

State hierarchy for one-way finite automata

Quite recently, it has been shown that, for each n, and each d between n and 2ⁿ, there exists a regular language for which each optimal nondeterministic one-way finite state automaton (nfa) uses exactly n states, but its optimal deterministic ...
Magic numbers in the state hierarchy of finite automata

A number d is magic for n, if there is no regular language for which an optimal nondeterministic finite state automaton (nfa) uses exactly n states and, at the same time, the optimal deterministic finite state automaton (dfa) uses exactly d states. We ...
Magic numbers in the state hierarchy of finite automata
MFCS'06: Proceedings of the 31st international conference on Mathematical Foundations of Computer Science

A number d is magic for n, if there is no regular language for which an optimal nondeterministic finite state automaton (nfa) uses exactly n states, but for which the optimal deterministic finite state automaton (dfa) uses exactly d states. We show that,...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Communications of the ACM Volume 11, Issue 12

Dec. 1968

89 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/364175

Editor:
Gerard Salton
Cornell Univ., Ithaca, NY

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 1968

Published in CACM Volume 11, Issue 12

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

53
Total Citations
View Citations
938
Total Downloads

Downloads (Last 12 months)194
Downloads (Last 6 weeks)26

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Le Glaunec AKong LMamouras K(2024)HybridSA: GPU Acceleration of Multi-pattern Regex Matching using Bit ParallelismProceedings of the ACM on Programming Languages10.1145/36897718:OOPSLA2(1699-1728)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689771
Mamouras KChattopadhyay A(2024)Efficient Matching of Regular Expressions with Lookaround AssertionsProceedings of the ACM on Programming Languages10.1145/36329348:POPL(2761-2791)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632934
Riveros CVan Sint Jan NVrgoč D(2023)REmatch: A Novel Regex Engine for Finding All MatchesProceedings of the VLDB Endowment10.14778/3611479.361148816:11(2792-2804)Online publication date: 24-Aug-2023
https://dl.acm.org/doi/10.14778/3611479.3611488
(2023)BibliographyEngineering a Compiler10.1016/B978-0-12-815412-0.00023-1(793-813)Online publication date: 2023
https://doi.org/10.1016/B978-0-12-815412-0.00023-1
Cooper KTorczon L(2023)ScannersEngineering a Compiler10.1016/B978-0-12-815412-0.00008-5(27-84)Online publication date: 2023
https://doi.org/10.1016/B978-0-12-815412-0.00008-5
Nikitin DGolian V(2022)METHODS AND MODELS OF SOFTWARE DEVELOPMENT USING AUTOMATED APPROACHInterConf10.51582/interconf.19-20.04.2022.045(473-477)Online publication date: 20-Apr-2022
https://doi.org/10.51582/interconf.19-20.04.2022.045
Luo JChong J(2020)Review of Natural Language Processing in RadiologyNeuroimaging Clinics of North America10.1016/j.nic.2020.08.00130:4(447-458)Online publication date: Nov-2020
https://doi.org/10.1016/j.nic.2020.08.001
Karl J(2018)Mining location information from life- and earth-sciences studies to facilitate knowledge discoveryJournal of Librarianship and Information Science10.1177/096100061875941351:4(1007-1021)Online publication date: 25-Feb-2018
https://doi.org/10.1177/0961000618759413
Li JHe DLiu FWang H(2016)The Application of Regex in Advertisements Filtration and Performance Analysis2016 8th International Conference on Intelligent Human-Machine Systems and Cybernetics (IHMSC)10.1109/IHMSC.2016.36(28-32)Online publication date: Aug-2016
https://doi.org/10.1109/IHMSC.2016.36
(2012)BibliographyEngineering a Compiler10.1016/B978-0-12-088478-0.00024-4(765-785)Online publication date: 2012
https://doi.org/10.1016/B978-0-12-088478-0.00024-4
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

References

Cited By

Recommendations

State hierarchy for one-way finite automata

Magic numbers in the state hierarchy of finite automata

Magic numbers in the state hierarchy of finite automata

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations