On the use of regular expressions for searching text

ABSTRACT

The use of regular expressions for text search is widely known and well understood. It is then surprising that the standard techniques and tools prove to be of limited use for searching structured text formatted with SGML or similar markup languages. Our experience with structured text search has caused us to reexamine the current practice. The generally accepted rule of “leftmost longest match” is an unfortunate choice and is at the root of the difficulties. We instead propose a rule which is semantically cleaner. This rule is generally applicable to a variety of text search applications, including source code analysis, and has interesting properties in its own right. We have written a publicly available search tool implementing the theory in the article, which has proved valuable in a variety of circumstances.

REFERENCES

• 1: Karl Abrahamson, Generalized string matching, SIAM Journal on Computing, v.16 n.6, p.1039-1051, December 1, 1987 [doi>10.1137/0216067]
• 2: AHO, A. V. 1980. Pattern matching in strings. In Formal Language Theory Perspectives and Open Problems, R. V. Book, Ed. Academic Press, New York, 325-344.
• 3: Alfred V. Aho, Algorithms for finding patterns in strings, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 4: 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 [doi>10.1145/360825.360855]
• 5: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 6: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 7: R. L. Baeza-Yates, Efficient text searching, University of Waterloo, Waterloo, Ont., Canada, 1989
• 8: Ricardo Baeza-Yates , Gaston H. Gonnet, A new approach to text searching, Communications of the ACM, v.35 n.10, p.74-82, Oct. 1992 [doi>10.1145/135239.135243]
• 9: G. Berry , R. Sethi, From regular expressions to deterministic automata, Theoretical Computer Science, v.48 n.1, p.117-126, Dec., 1986
• 10: Robert S. Boyer , J. Strother Moore, A fast string searching algorithm, Communications of the ACM, v.20 n.10, p.762-772, Oct. 1977 [doi>10.1145/359842.359859]
• 11: Martin Bryan, Author's Guide to the Standard Generalized Markup Language, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 12: Janusz A. Brzozowski, Derivatives of Regular Expressions, Journal of the ACM (JACM), v.11 n.4, p.481-494, Oct. 1964 [doi>10.1145/321239.321249]
• 13: Chia-Hsiang Chang , Robert Paige, From Regular Expressions to DFA's Using Compressed NFA's, Proceedings of the Third Annual Symposium on Combinatorial Pattern Matching, p.90-110, April 29-May 01, 1992
• 14: CLARKE, C. L. A. AND CORMACK, G. V. 1996. Context grep. Tech. Rep. CS-96-41, Computer Science Dept., Univ. of Waterloo, Waterloo, Canada.
• 15: CLARKE, C. L. A., CORMACK, G. V., AND BURKOWSKI, F. J. 1995a. An algebra for structured text search and a framework for its implementation. Comput. J. 38, 1, 43-56.
• 16: CLARKE, C. L. A., CORMACK, G. V., AND BURKOWSKI, F. J. 1995b. Schema-independent retrieval from hetrogeneous structured text. In Proceedings of the ~th Annual Symposium on Document Analysis and Information Retrieval. UNLV, Las Vegas, Nev.
• 17: FISHER, M. AND PATTERSON, M. 1974. String matching and other products. In Proceedings of the SIAM-AMS Conference on Complexity of Computation, R. M. Karp, Ed. American Mathematical Society, Providence, R.I., 113-125.
• 18: HARGREAVES, K. A. AND BERRY, K. 1992. Regex. Free Software Foundation, Cambridge, Mass. Available from ftp://prep.ai.mit.edu/pub/gnu.
• 19: Donna Harman, Overview of the first TREC conference, Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval, p.36-47, June 27-July 01, 1993, Pittsburgh, Pennsylvania, United States [doi>10.1145/160688.160692]
• 20: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 21: HORSPOOL, R. N. 1980. Practical fast searching in strings. Softw. Pract. F, xper. 10, 501-506.
• 22: IEEE. 1992. Standard for information technology Portable Operating System Interface (POSIX) Part 2 (Shell and utilities) Section 2.8 (Regular expression notation). IEEE Std 1003.2, Institute of Electrical and Electronics Engineers, New York.
• 23: ISO. 1986. Information processing Text and office systems Standard Generalized Markup Language (SGML). ISO 8879, International Standards Organization, Geneva, Switzerland.
• 24: JAAKKOLA, J. AND KILPELAINEN, P. 1995. Sgrep home page. Dept. of Computer Science, Univ. of Helsinki, Helsinki, Finland. Available as http://www.cs.helsinki.fi/jjaakkol/sgrep.html.
• 25: Walter L. Johnson , James H. Porter , Stephanie I. Ackley , Douglas T. Ross, Automatic generation of efficient lexical processors using finite state techniques, Communications of the ACM, v.11 n.12, p.805-813, Dec. 1968 [doi>10.1145/364175.364185]
• 26: KNIGHT, J. R. AND MYERS, E. W. 1995. Super-pattern matching. Algorithmica 13, 211-243.
• 27: KNUTH, D. E., MORRIS, J. H., AND PRATT, V. R. 1977. Fast pattern matching in strings. SIAM J. Comput. 6, 2 (June), 323-350.
• 28: LESK, M. E. 1975. Lex -- A lexical analyzer generator. Computing Science Tech. Rep. 39, AT&T Bell Laboratories, Murray Hill, N.J.
• 29: Udi Manber , Ricardio Baeza-Yates, An algorithm for string matching with a sequence of don't cares, Information Processing Letters, v.37 n.3, p.133-136, Feb. 18, 1991 [doi>10.1016/0020-0190(91)90032-D]
• 30: MCNAUTHTON~ R. AND YAMADA~ H. 1960. Regular expressions and state graphs for automata. IRE Trans. Electronic Comput. EC-9, 1 (Mar.), 39-47.
• 31: Gail C. Murphy , David Notkin, Lightweight source model extraction, Proceedings of the 3rd ACM SIGSOFT symposium on Foundations of software engineering, p.116-127, October 12-15, 1995, Washington, D.C., United States
• 32: MYERS~ E. W. AND MILLER~ W. 1989. Approximate matching of regular expressions. Bull. Math. Biol. 51, 1, 5-37.
• 33: John K. Ousterhout, Tcl and the Tk toolkit, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1994
• 34: PIKE~ R. 1987a. Structural regular expressions. In Proceedings of the European UNIX User's Group Conference. EUUG, Helsinki, Finland.
• 35: Rob Pike, The text editor sam, Software—Practice & Experience, v.17 n.11, p.813-845, November 1, 1987 [doi>10.1002/spe.4380171105]
• 36: Ken Thompson, Programming Techniques: Regular expression search algorithm, Communications of the ACM, v.11 n.6, p.419-422, June 1968 [doi>10.1145/363347.363387]
• 37: Larry Wall , Randal L. Schwartz, Programming perl, O'Reilly & Associates, Inc., Sebastopol, CA, 1991
• 38: Wu~ S. AND MANBER~ W. 1992a. agrep A fast approximate pattern matching algorithm. In Proceedings of the USENIX Winter 1992 Technical Conference. USENIX Assoc., Berkeley, Calif, 153-162.
• 39: Sun Wu , Udi Manber, Fast text searching: allowing errors, Communications of the ACM, v.35 n.10, p.83-91, Oct. 1992 [doi>10.1145/135239.135244]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Specialized application languages

General Terms:
Algorithms

Keywords:
SGML, regular expressions, regular languages