When lexing, POSIX provides two rules:

• Longest match rule: longest initial substring matched by any regular expression is taken as the next token
• Rule priority: for a particular longest initial substring, the first regular expression that can match determines the token

Sulzmann & Lu Matcher

The Sulzmann & Lu Matcher works in two phases:

• Try to find the derivatives of a given string using a given regex then see if it’s nullable.
• Try to work backwards and understand how the last regex matched the string.

Example: Match the string $abc$ using $r_1$

$$\begin{array}{rl}{r}_1& :a\cdot (b\cdot c)\\ r_2& :1\cdot (b\cdot c)\\ r_3& :(0\cdot (b\cdot c))+(1\cdot c)\\ r_4& :(0\cdot (b\cdot c))+((0\cdot c)+1)\end{array}$$ $$\begin{array}{rl}{v}_1& :\text{Seq}(\text{Char}(a),\text{Seq}(\text{Char}(b),\text{Char}(c)))\\ v_2& :\text{Seq}(\text{Empty},\text{Seq}(\text{Char}(b),\text{Char}(c)))\\ v_3& :\text{Right}(\text{Seq}(\text{Empty},\text{Char}(c)))\\ v_4& :\text{Right}(\text{Right}(\text{Empty}))\end{array}$$ $$\begin{array}{rl}|v_1|& :\text{abc}\\ |v_2|& :\text{bc}\\ |v_3|& :\text{c}\\ |v_4|& :[]\end{array}$$

As opposed to the Brzozowski algorithm, this matcher will return a value.

This correlates directly to the definition of our regex:

Inductive definition of regular expression

Regular expressions are inductively defined as:

$$\begin{array}{rl}r& ::=\text{0}\\ & |\text{1}\\ & |c\\ & |r_1\cdot r_2\\ & |r_1+r_2\\ & |r^{\ast }\end{array}$$Link to original

Flatten

This function allows us to obtain the string underlying a value:

Mkeps

Finding a (posix) value for recognising the empty string:

Inject

The idea of the injection function is to do the reverse of the derivative function.

The injection function knows what string it should match and tries to figure out how the regular expression matched it. It takes three arguments, $r$, $c$, and $v_{\text{der}}$.

Lexing

As opposed to our previous matcher, our lexer will take a string and produce a value instead of a boolean.

Records

A record is an indicator within our regular expression which can be used to pull out some specific information we are looking for.

We have a new regex: $(x:r)$ and an associated value: $\text{Rec}(x,v)$.

Here is how records are implemented:

Example usage of records

We can use it to extract subpatterns:

• $(z:((x:ab)+(y:ba))$
• $(id:r_{id})$
• $(key:r_{key})$

Example: email address regex

$(\text{name}:[a-z0-9_{.}-{]}^{+})\cdot (\text{domain}:[a-z0-9.-{]}^{\ast })\cdot .\cdot (\text{top\_level}:[a-z.{]}^{\{2,6\}})$

We can generate a resulting environment: $[(\text{name}:\text{abc.def}),\dots ]$

While Tokens

$$\begin{array}{rlrl}\text{WHILE\_REGS}& \stackrel{\text{def}}{=}& & ({(}^{\prime }{k}^{\prime }:\text{KEYWORD})+\\ & & & {(}^{\prime }{i}^{\prime }:\text{ID})+\\ & & & {(}^{\prime }{o}^{\prime }:\text{OP})+\\ & & & {(}^{\prime }{n}^{\prime }:\text{NUM})+\\ & & & {(}^{\prime }{s}^{\prime }:\text{SEMI})+\\ & & & {(}^{\prime }{p}^{\prime }:(\text{LPAREN}+\text{RPAREN}))+\\ & & & {(}^{\prime }{b}^{\prime }:(\text{BEGIN}+\text{END}))+\\ & & & {(}^{\prime }{w}^{\prime }:\text{WHITESPACE}){)}^{\ast }\end{array}$$

Simplification

If we simplify after the derivative, then we are building the value for the simplified regular expression, but not for the original regular expression.

Example

For example, we would have $(0\cdot (b\cdot c))+((0\cdot c)+1)$ and answer how this regular expression matches the empty string with the value $\text{Right}(\text{Right}(\text{Empty}))$. But now we simplify this to $1$ and would produce $\text{Empty}$ (see mkeps).

Rectification

We want to reverse the simplification.

The old simp returns a rexp, the new simp returns a rexp and a rectification function.

Example

TODO

Rectification of _ + _

Rectification of _ . _

Lexing with Simplification

Environments

Obtaining the “recorded” parts of a value: