Match Example

It is instructive to look at how the matcher handles the string "aba" for the regular expression (a + ab)(a + b).

The greedy match is to peel off an a. That eventually fails and the matcher has to try ab instead.
Let's look at that evaluation/search in cartoon form (i.e., using abbreviated notation):

        accept (a + ab)(a + b) "aba" 

  ==    match (a + ab)(a + b) [a,b,a] List.null     

[Times]
  ==    match (a + ab) [a,b,a] (fn cs' => match (a + b) cs' List.null)

[Plus]
  ==    match a [a,b,a] (fn cs' => match (a + b) cs' List.null)
                  orelse
        match ab [a,b,a] (fn cs' => match (a + b) cs' List.null)

Now let's examine the first half of that orelse:

        match a [a,b,a] (fn cs' => match (a + b) List.null)

[Char]
  ==    (a=a) andalso (fn cs' => match (a + b) cs' List.null)([b,a])

  ==    match (a + b) [b,a] List.null

[Plus]
  ==    (match a [b,a] List.null)  orelse  (match b [b,a] List.null)

[Char]
  ==    ((a=b) andalso List.null[a])  orelse  (match b [b,a] List.null)

  ==    false  orelse  (match b [b,a] List.null)

[Char]
  ==    (b=b) andalso List.null[a]

  ==    true  andalso false

  ==    false

So that is how the matcher sees that the greedy match fails.

Now let's examine the second half of the orginal orelse:

        match ab [a,b,a] (fn cs' => match (a + b) cs' List.null)

[Times]
  ==    match a [a,b,a] (fn cs'' => match b cs'' (fn cs' => match (a + b) cs' List.null))

[Char]
  ==    (a=a) andalso (fn cs'' => match b cs'' (fn cs' => match (a + b) cs' List.null))([b,a])

  ==    match b [b,a] (fn cs' => match (a + b) cs' List.null)

[Char]
  ==    (b=b) andalso (fn cs' => match (a + b) cs' List.null)([a])

  ==    match (a + b) [a] List.null

[Plus]
  ==    (match a [a] List.null)  orelse  (match b [a] List.null)

[Char]
  ==    ((a=a) andalso List.null[])  orelse  (match b [a] List.null)

  ==    (true andalso true)  orelse  (match b [a] List.null)

  ==    true

And that is how the matcher recognizes that the string "aba" lies in the language of the regular expression (a + ab)(a + b).