0
$\begingroup$

A quick test shows what I'm describing:

> const text = 'foobarhelloworld'
> const pattern = /.+or/
> text.match(pattern) //=> 'foobarhellowor'

What is the basic algorithm for matching "anything up to some explicit text"?

The reason I ask is I am working on hacking together a spell checker / morphological analyzer, building off the ideas from Hunspell, and I want to say "match anything from the start of the word for as much as you can, then if the next character is NOT [aeiou], and the character after that is y, then make it ied." To do that I am creating a JSON DSL, which I need to implement a processor for like processing regular expressions. The DSL will be something like (very rough prototype, still have a lot of thinking/refining to do):

{
  load: [
    { name: 'base', base: true, form: 'walker', test: {
      form: 'pattern',
      text: '.'
    } },
    { name: 'note', form: 'not', test: { form: 'or', text: 'aeiou' } },
    { text: 'y', head: true }
  ],
  save: [
    { name: 'base' },
    { name: 'note' },
    { text: 'ied' },
  ]
}

You "load" the input text/word, and "save" the output. So we load "candy", and save "candied" in this case.

I just don't see how you would go about implementing this functionality without resorting to using regular expressions (I would like to basically learn how they are implemented, at least at a high level, for this situation). I would like to avoid using regular expressions other than possibly the . character for matching anything, or the other helpful character matching shortcuts \n and \w, etc..

The way I'm thinking about it:

  • We are on the first pattern we named "base". It is a "walker" on . pattern, meaning in regexp terms, .+. So we go to the first character, the second character, the next character, etc... Then we are at the end now!! Are we supposed now go onto the next rule, and backtrack? Or should we have not stepped forward each tick, and instead used the 2nd rule to check if it matches, only falling back down to the .+ rule #1 if rule #2 doesn't match?

So instead of something like this, which would simply get greedy with the first pattern all the way to the end:

let r_i = 0 # rule index
let rule = rules[r_i++]
let w_i = 0 # word index
while true
  let char = word[w_i]
  if rule.match(char)
    w_i++
  else
    raise 'error'
return true

Maybe it's more along these lines or something? Not sure:

let r_i = 0 # rule index
let rule = rules[r_i++]
let w_i = 0 # word index
while true
  let char = word[w_i]
  if rule.match(char)
    w_i++
  else
    let next_rule = rules[r_i]
    if next_rule.match(char)
      # because of this, will match twice, one more on next loop
      r_i++
    else
      raise 'error'
return true

But that seems like it would get stuck too:

> const text = 'foobarhelloworld'
> const pattern = /.+ow/
> text.match(pattern) //=> 'foobarhellow'
// could have got stuck at the first `o` in `foo`

So what is the basic high-level algorithm for implementing this regexp .+ functionality?

Related: What do 'lazy' and 'greedy' mean in the context of regular expressions?

$\endgroup$

1 Answer 1

2
$\begingroup$

This is probably the main difference between "regular expressions" as a formal language, and "regexes" as an implementation tool.

Extending a regular expression matching algorithm to support greedy capture (i.e. the maximal munch rule) is straightforward. Consider this DFA:

enter image description here

Essentially, you run this DFA as is, but whenever you hit the final state, you record the point in the input string where you were, but continue matching. When you reach the end of the input string, the last place where you were in a final state is the end of the match.

This approach is enough for a tool like lex/flex; lexical analysis always starts a lexeme exactly where the last one ended, and lexical languages are typically designed so that you don't need to scan to the end of the input file or line to find the end of a lexeme.

However, if you have multiple captures, as you find with capturing brackets in POSIX and Perl regexes, or an ambiguous start point, things get a little more complex. It's a broadly similar approach, but in general, finding substrings (as opposed to merely recognising them) may, in the general case, require backtracking.

This is one reason why POSIX/Perl regexes generally don't use deterministic automata, but rather compile to an abstract intermediate representation that supports backtracking execution. See, for example, the article by Russ Cox, Regular Expression Matching: the Virtual Machine Approach.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.