{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,15]],"date-time":"2024-08-15T21:48:28Z","timestamp":1723758508664},"reference-count":18,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2009,3,1]],"date-time":"2009-03-01T00:00:00Z","timestamp":1235865600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Funct. Prog."],"published-print":{"date-parts":[[2009,3]]},"abstract":"Abstract<\/jats:title>Regular-expression derivatives are an old, but elegant, technique for compiling regular expressions to deterministic finite-state machines. It easily supports extending the regular-expression operators with boolean operations, such as intersection and complement. Unfortunately, this technique has been lost in the sands of time and few computer scientists are aware of it. In this paper, we reexamine regular-expression derivatives and report on our experiences in the context of two different functional-language implementations. The basic implementation is simple and we show how to extend it to handle large character sets (e.g., Unicode). We also show that the derivatives approach leads to smaller state machines than the traditional algorithm given by McNaughton and Yamada.<\/jats:p>","DOI":"10.1017\/s0956796808007090","type":"journal-article","created":{"date-parts":[[2009,2,10]],"date-time":"2009-02-10T06:59:03Z","timestamp":1234249143000},"page":"173-190","source":"Crossref","is-referenced-by-count":84,"title":["Regular-expression derivatives re-examined"],"prefix":"10.1017","volume":"19","author":[{"given":"SCOTT","family":"OWENS","sequence":"first","affiliation":[]},{"given":"JOHN","family":"REPPY","sequence":"additional","affiliation":[]},{"given":"AARON","family":"TURON","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2009,3,1]]},"reference":[{"key":"S0956796808007090_ref5","unstructured":"Appel A. W. , Mattson J. S. & Tarditi D. R. (1994Oct.) A Lexical Analyzer Generator for Standard ML. Available at: http:\/\/smlnj.org\/doc\/ML-Lex\/manual.html."},{"key":"S0956796808007090_ref4","volume-title":"Modern Compiler Implementation in ML","author":"Appel","year":"1998"},{"key":"S0956796808007090_ref2","volume-title":"Compilers: Principles, Techniques, and Tools","author":"Aho","year":"1986"},{"key":"S0956796808007090_ref1","volume-title":"The Design and Analysis of Computer Algorithms","author":"Aho","year":"1974"},{"key":"S0956796808007090_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90088-5"},{"key":"S0956796808007090_ref6","doi-asserted-by":"crossref","unstructured":"Baxter I. , Pidgeon C. , & Mehlich M. (2004) DMS: Program transformations for practical scalable software evolution. In International Conference on Software Engineering.","DOI":"10.1109\/ICSE.2004.1317484"},{"key":"S0956796808007090_ref12","volume-title":"Crafting a Compiler","author":"Fisher","year":"1988"},{"key":"S0956796808007090_ref18","volume-title":"The Unicode Standard, Version 4","year":"2003"},{"key":"S0956796808007090_ref7","unstructured":"Berry G. (1999) The Esterel v5 Language Primer Version 5.21 Release 2.0. Available at: ftp:\/\/ftp-sop.inria.fr\/meije\/esterel\/papers\/primer.pdf."},{"key":"S0956796808007090_ref9","doi-asserted-by":"publisher","DOI":"10.1145\/321239.321249"},{"key":"S0956796808007090_ref14","doi-asserted-by":"publisher","DOI":"10.1147\/rd.32.0114"},{"key":"S0956796808007090_ref3","volume-title":"The Theory of Parsing, Translation, and Compiling","author":"Aho","year":"1972"},{"key":"S0956796808007090_ref11","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796801004208"},{"key":"S0956796808007090_ref15","unstructured":"Schmidt Martin . (2002) Design and Implementation of a Validating XML Parser in Haskell. Master's thesis, Computer Science Department, University of Applied Sciences Wedel."},{"key":"S0956796808007090_ref13","doi-asserted-by":"publisher","DOI":"10.1109\/TEC.1960.5221603"},{"key":"S0956796808007090_ref16","first-page":"226","volume-title":"Proceedings of Runtime Verification (RV'03)","author":"Sen","year":"2003"},{"key":"S0956796808007090_ref17","doi-asserted-by":"publisher","DOI":"10.1145\/363347.363387"},{"key":"S0956796808007090_ref10","unstructured":"English J. (1999) How to Validate XML. Available at: http:\/\/www.flightlab.com\/~joe\/sgml\/validate.html. (Accessed 24 November 2008)."}],"container-title":["Journal of Functional Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0956796808007090","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,3]],"date-time":"2019-04-03T16:11:00Z","timestamp":1554307860000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0956796808007090\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,3]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,3]]}},"alternative-id":["S0956796808007090"],"URL":"https:\/\/doi.org\/10.1017\/s0956796808007090","relation":{},"ISSN":["0956-7968","1469-7653"],"issn-type":[{"value":"0956-7968","type":"print"},{"value":"1469-7653","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,3]]}}}