owensRegularexpressionDerivativesReexamined2009:
  type: article
  title: Regular-expression derivatives re-examined
  author:
  - Owens, Scott
  - Reppy, John
  - Turon, Aaron
  date: 2009-03
  page-range: 173-190
  url:
    value: https://www.cambridge.org/core/product/identifier/S0956796808007090/type/journal_article
    date: 2024-04-29
  serial-number:
    doi: 10.1017/S0956796808007090
    issn: 0956-7968, 1469-7653
  abstract: Abstract 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.
  parent:
    type: periodical
    title: Journal of Functional Programming
    issue: 2
    volume: 19