article

Free access

A regular expression pattern matching processor for APL

Authors:

Mark R. Dempsey,

Leslie H. GoldsmithAuthors Info & Claims

ACM SIGAPL APL Quote Quad, Volume 12, Issue 1

Pages 94 - 100

https://doi.org/10.1145/390007.805341

Published: 01 September 1981 Publication History

PDF eReader

Abstract

Regular expressions are a powerful notation for expressing text patterns. This paper discusses classical regular expressions and their extension into the domain of APL. These extensions are manifest in terms of locator templates, which describe patterns to be searched for, and action templates, which specify an action to be performed when a match is encountered. An algorithm for implementing these concepts is briefly discussed. The algorithm compiles a template into code which is then interpreted in the context of a specific text vector to be searched. Numerous examples are espoused to demonstrate the utility of pattern matching over a wide range of problems.

References

[1]

Aho, Alfred V., J.E. Hopcroft, and J.D. Ullman. The Design and Analysis of Computer Algorithms, Addison-Wesley Publishing Company, Reading, Mass., 1974.

Digital Library

Google Scholar

[2]

Aho, Alfred V. and M.J. Corasick. "Efficient String Matching: An Aid to Bibliographic Search," Communications of the ACM, vol. 18, no. 6 (June 1975), pp. 333-340.

Digital Library

Google Scholar

[3]

Aho, Alfred V., B.W. Kernighan, and P.J. Weinberger. Awk—A Pattern Scanning and Processing Language, second edition, Bell Telephone Laboratories, Murray Hill, N.J., 1978.

Google Scholar

[4]

Backhouse, Roland C. Syntax of Programming Languages, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1979.

Digital Library

Google Scholar

[5]

Dempsey, Mark R. "Using an APL Macroprocessor to Implement Generalized Software Systems," APL79 Conference Proceedings and APL Quote Quad, vol. 9, no. 4 (June 1979), part 1, pp. 286-293.

Digital Library

Google Scholar

[6]

Goldsmith, Leslie H. Workspace Searching Using 777 WSSEARCH, second edition, I.P. Sharp Associates Limited, Toronto, Canada, 1979.

Google Scholar

[7]

Griswold, Ralph E., J.F. Poage, and I.P. Polonsky. The SNOBOL4 Programming Language, second edition, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1971.

Digital Library

Google Scholar

[8]

Iverson, Kenneth E. Elementary Analysis, APL Press, Swarthmore, Pa., 1976.

Google Scholar

[9]

Kernighan, Brian W. and P.J. Plauger. Software Tools, Addison-Wesley Publishing Company, Reading, Mass., 1976.

Digital Library

Google Scholar

[10]

The Multics Progammer's Manual, Massachusetts Institute of Technology, MIT Press, Cambridge, Mass., 1974.

Google Scholar

[11]

Richards, Martin. "A Compact Function for Regular Expression Pattern Matching," Software—Practice and Experience, vol. 9 (1979), pp. 527-534.

Crossref

Google Scholar

[12]

Thompson, Ken. "Regular Expression Search Algorithm," Communications of the ACM, vol. 11, no. 6 (June 1968), pp. 419-422.

Digital Library

Google Scholar

[13]

Thompson, Ken and D.M. Ritchie. The UNIX Programmer's Manual, Bell Telephone Laboratories, Murrary Hill, N.J., 1974.

Google Scholar

Cited By

View all

Allen DDempsey MGoldsmith L(1987)System development methodology using LOGOSACM SIGAPL APL Quote Quad10.1145/384282.2833117:4(138-150)Online publication date: 1-Jan-1987
https://dl.acm.org/doi/10.1145/384282.28331
Allen DDempsey MGoldsmith L(1987)System development methodology using LOGOSProceedings of the international conference on APL: APL in transition10.1145/28315.28331(138-150)Online publication date: 1-Jan-1987
https://dl.acm.org/doi/10.1145/28315.28331
Rasool GAsif N(2007)Software Artifacts Recovery using Abstract Regular Expressions2007 IEEE International Multitopic Conference10.1109/INMIC.2007.4557710(1-6)Online publication date: Dec-2007
https://doi.org/10.1109/INMIC.2007.4557710
Show More Cited By

Index Terms

A regular expression pattern matching processor for APL
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
2. Theory of computation
  1. Design and analysis of algorithms
    1. Data structures design and analysis
      1. Pattern matching
  2. Formal languages and automata theory
    1. Grammars and context-free languages

Recommendations

A regular expression pattern matching processor for APL
APL '81: Proceedings of the international conference on APL

Regular expressions are a powerful notation for expressing text patterns. This paper discusses classical regular expressions and their extension into the domain of APL. These extensions are manifest in terms of locator templates, which describe patterns ...
A Boyer--Moore-style algorithm for regular expression pattern matching

This paper presents a Boyer-Moore-type algorithm for regular expression pattern matching, answering an open problem posed by Aho in 1980 (Pattern Matching in Strings, Academic Press, New York, 1980, p. 342). The new algorithm handles patterns specified ...
Benchmarking Regular Expression Matching
Implementation and Application of Automata
Abstract
In this paper we benchmark the matching time of regular expression matching engines when they use either the Thompson or Glushkov regular expressions to state machine conversion algorithms, with or without using memoisation while matching, and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ACM SIGAPL APL Quote Quad Volume 12, Issue 1

September 1981

354 pages

ISSN:0163-6006

DOI:10.1145/390007

Issue’s Table of Contents

APL '81: Proceedings of the international conference on APL
October 1981
354 pages
ISBN:0897910354
DOI:10.1145/800142
Chairman:
Richard J. Orgass,
Editors:
William L. Anderson,
David G. Smith

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 September 1981

Published in SIGAPL Volume 12, Issue 1

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
500
Total Downloads

Downloads (Last 12 months)80
Downloads (Last 6 weeks)18

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Allen DDempsey MGoldsmith L(1987)System development methodology using LOGOSACM SIGAPL APL Quote Quad10.1145/384282.2833117:4(138-150)Online publication date: 1-Jan-1987
https://dl.acm.org/doi/10.1145/384282.28331
Allen DDempsey MGoldsmith L(1987)System development methodology using LOGOSProceedings of the international conference on APL: APL in transition10.1145/28315.28331(138-150)Online publication date: 1-Jan-1987
https://dl.acm.org/doi/10.1145/28315.28331
Rasool GAsif N(2007)Software Artifacts Recovery using Abstract Regular Expressions2007 IEEE International Multitopic Conference10.1109/INMIC.2007.4557710(1-6)Online publication date: Dec-2007
https://doi.org/10.1109/INMIC.2007.4557710
Allen DDempsey MGoldsmith L(1987)System development methodology using LOGOSACM SIGAPL APL Quote Quad10.1145/384282.2833117:4(138-150)Online publication date: 1-Jan-1987
https://dl.acm.org/doi/10.1145/384282.28331
Allen DDempsey MGoldsmith L(1987)System development methodology using LOGOSProceedings of the international conference on APL: APL in transition10.1145/28315.28331(138-150)Online publication date: 1-Jan-1987
https://dl.acm.org/doi/10.1145/28315.28331
Allen DGoldsmith LDempsey MHarrell K(1986)LOGOS: An APL programming environmentProceedings of the international conference on APL10.1145/22415.22054(314-325)Online publication date: 1-Dec-1986
https://dl.acm.org/doi/10.1145/22415.22054
Allen DGoldsmith LDempsey MHarrell K(1986)LOGOS: An APL programming environmentACM SIGAPL APL Quote Quad10.1145/22008.2205416:4(314-325)Online publication date: 1-May-1986
https://dl.acm.org/doi/10.1145/22008.22054
Brenner NPuckett T(1983)Extending APL for pattern matchingProceedings of the international conference on APL10.1145/800062.801227(275-280)Online publication date: 10-Apr-1983
https://dl.acm.org/doi/10.1145/800062.801227
Brenner N(1983)Extending APL for pattern matchingACM SIGAPL APL Quote Quad10.1145/390005.80122713:3(275-280)Online publication date: 1-Mar-1983
https://dl.acm.org/doi/10.1145/390005.801227

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.

Abstract

References

Cited By

Index Terms

Recommendations