Regex parsing without regexes

Posted on 2026-01-19 by Ernesto Hernández-Novich
Tags: ,

The practical knowledge students should have after completing CI3725 , can be summarized as:

  1. Most programming problems turn out to be «language manipulation» problems. Those that don’t look like language manipulation on the surface, are easier to approach if you transform them into language manipulation problems.

  2. Language manipulation problems can be tackled in a modular way as a sequence of analysis-synthesis steps. Going from high complexity representations to high abstraction representations, that in turn are higher complexity for even higher abstraction, until you fold down to the desired behavior.

  3. There are tools you must know how to use an understand, in order to be successful at language manipulation problems. Solving these problems by hand is definitiely possible, but it’s ill-advised. Unless you are solving the language manipulation problem of… language manipulation.

  4. There’s a limit to the tools. At some point in the problem, there’s no other way than understanding the language semantics, and writing their precise behavior.

Teaching the above in eleven weeks is challenging. We settled on a very simple, but essential model that every software writer should understand and try to follow, if only for their own sanity. Briefly stated using Haskell types

[Char] -> [Token] -> (AST,Symbols) -> Behavior

There’s a high-entropy source input stream, [Char]: a sequence of bytes. They must be transformed into a sequence of slightly higher level words or Tokens that have basic meaning. Then, Tokens must be grouped and hierarchically ordered into a tree-like recursive structure, the Abstract Syntax Tree, while simultaneously collecting symbols providing semantic context and establishing intra-tree relationships. Using AST and context Symbols, you produce the desired Behavior: it could be a new [Char] for machine representation, or IO () for machine interpretation.

The tools needed to accomplish all of the above are:

  1. A tokenizer usually built out of Regular Expressions, either part of a lexer generator, or as provided by the host programming language.

  2. A parser. We rather the student learns to use a LALR parser generator, than teach how to build parsers manually.

  3. Recursive data structures and their processing. Interleaving strategically written code with the parser generator generated code, such that trees are built, tables are kept, and behaviors are manifested.

Naturally, we start by teaching canonical Regular Expressions and their relationship with Regular Sets and set theory. Inevitably, a student will ask two similar but slightly different questions

How can I figure out what words will my regular expression match?

How can I be sure my regular expression will match the words I need?

answered with the completely correct but beffudling: you could write an interpreter that takes regular expression looking strings as programs, and simulates their behavior given a particular input word, right?

The attentive reader hopefully thinks «true, but… you’d be cheating if you used regular expressions to tokenize and parse regular expressions to simulate them, wouldn’t you?»

Indeed we would.

The remainder of this post will show a way to do the analysis part without using regular expressions nor LALR parser generators. These are things you should know how to do when there aren’t good tools around, or when you are in charge of writing those tools.

Data structures as bridges

We’re trying to solve this problem

StringLookingLikeAREGEX -> BehavesLikeAREGEX

and its simplest specification is to use canonical regular expressions over the alphabet of single characters.

What does our input look like?

Our StringLookingLikeAREGEX, an arbitrary character sequence ([Char], Text, ByteString, it does not matter), will be analyzed under the following rules:

  • Lowercase letters or digits, each handled as an individual symbol. They will be used not only for constructing the regular expression, but also for the input words to test against our regular expression.

  • ∅ denoting the empty regular expression.

  • λ denoting the empty word.

  • + denoting regular expression disjunction (the «or»).

  • Juxtaposition denoting regular expression concatenation. Indeed, there will not be a literal operator for this.

  • * denoting the Kleene closure operator («zero or more»).

  • Open and close parenthesis, used for grouping.

  • Open and close square brackers, denoting symbol ranges. Just a special case of +.

  • Whitespace will be ignored.

  • Anything else will be treated as an input error.

That is, we want to process inputs like

"  ∅ + (λ + a  +  a b* ) *c*  "

We need to write a piece of code able to identify these characters and group them following Regular Expression syntax and semantic conventions… without using regular expressions nor parser generators. The standard advice is for this piece of code to produce a higher level representation: we analyze the input, and produce one or more data structures representing the syntactic structure and any contextual information we might need.

Recursive Regular Expressions are Recursive

The textbook definition for canonical or algebraic regular expressions leads to this data type:

data RE = Empty             -- Empty set
        | Epsilon           -- Empty string
        | Symbol Char       -- A single letter
        | Alternate RE RE   -- RE0+RE1
        | Catenate RE RE    -- RE0 RE1
        | Kleene RE         -- RE *
        deriving (Eq,Show)

As mentioned before, ranges are no more than repeated Alternate, i.e. [abc] would be

Alternate (Alternate (Symbol 'a') (Symbol 'b'))
          (Symbol 'c')

the same as a+b+c. Note it has to be left associative, i.e. a+b+c shall be processed as if it were ((a+b)+c).

Kleene closures are postfix unary operator, i.e. a** would be

Kleene (Kleene (Symbol `a`))

We don’t need to represent whitespace, as it should be ignored during the analysis phase. We also don’t need to represent parenthesis, as they are used to group things to express precedence, so they will become an Alternate, Catenate, or Kleene, i.e. (a+b)* would be

Kleene (Alternate (Symbol 'a') (Symbol 'b'))

Finally, to keep things simple the program will work under the implicit alphabet assumption: only those tymbols appearing in the regular expression constitute the input alphabet. That means we don’t even need a symbol table.

That’s all we need to refine our problem from

StringLookingLikeAREGEX -> BehavesLikeAREGEX

to

[Char] -> RE -> BehavesLikeAREGEX

Let’s focus on the first part of the problem.

Handcrafting a «lexer-parser»

There’s a standard way to write a lexer without using regular expressions: read the input one character at a time, and have as many selectors as you need to decide if that character is enough, or if you need more to come up with a token; produce the token, rinse and repeat. A technique that works on any programming language regardless of paradigm.

Suppose you want to find «variable names» that must start with a letter and may continue with either letters or digits; also «numbers» that are a sequence of digits; and ignore whitespace. You could write (in Haskell pseudocode)

   n <- getChar
   case n of
     c | isLetter c -> getMoreLettersAndDigits
       | isDigit c  -> getMoreDigits
       | isSpace c  -> ignoreWhiteSpace
     -- other cases

Functions on the right side repeatedly use getChar to get more characters as needed, produce their correspoding token, and go back to the top: it is implied the above fragment is in a «forever loop» that exits when reaching the end of input.

The above definitely works. Its alphabet is characters, and the language it produces is tokens. But it still too low level in the sense that is tied to explicitly reading characters and explicitly producing tokens: it’s good, but not great.

Similarly, there’s a standard way to write a parser without using a parser generator: read the input one token at a time, and have as many selectors as you need to decide if that token is enough, or if you need more to come up with a syntactic group; produce the syntactic group, rinse and repeat. A technique that works on any programming language regardless of paradigm.

Suppose you want to parse expressions, possibly in parenthesis. You could write (in Haskell pseudocode)

parseExpr = do
   t <- getNextToken
   case t of
     t | t == OpenParens -> do e <- parseExpr
                               t <- getNextToken
                               when (t != CloseParens)
                                    syntaxError
                               return (Exp e)
       | t == Number n   -> return (Exp t)
     -- other cases

Note how parseExpr uses recursion for nested expressions, checks for matching opening and closing parentheses, and is always producing an expression (the Exp data constructor). Its alphabet is tokens, and the language it produces is a recursive data structure. But it is too high-level in the sense that we’ve hardcoded both tokens and type constructors: it’s good, but not great.

If it feels like I’m repeating myself, well… it’s because I am. Lexing and parsing are inherently recursive processes, regardless of what those afraid of recursion tell you: there are recursive data structures, and functions called recursively. The subtle difference, that we explain (and prove!) during class, is that lexical analysis only needs tail recursion, while parsing (syntactic analysis) requires non-tail recursion to handle nested structures.

It follows we can combine lexical and syntactic analysis in a single flow, as long as we express it as a collection of mutually recursive functions. Functions doing lexical analysis will be tail recursive, whilst functions doing syntactic analysis will be tail and non-tail recursive depending on the case.

Haskell provides several libraries containing polymorphic functions that implement lexical/syntactic parsing combinators. That is, functions that, depending on their argument, implicitly parse (lexically or syntactically). Arguments can be literal things, like characters, but they can also be other functions, parsers in particular: you use a parser combinator to make complex parsers out of simple parsers.

I’m using Parsec for this example. It’s my go to for manual parser building when there isn’t an existing parser for what I need. Parsec provides combinators such as the monomorphic

char :: Char -> Parser Char

such that

char '*'

produces a parser that parses (lexically!) exactly one * and returns it, or fails with an error. Parsec also provides the polymorphic

many1 :: Parser a -> Parser [a]

such that

many1 p

produces a parser that parses one or more of whatever p parses. Therefore

many1 (char '*')

produces a parser that will parse… one or more * in sequence.

The techinque informally described above is called Recursive Descent Parsing. It’s mentioned in passing during CI3725, but is actively taught on CI4721.

Recursive parsing is recursive

Using Parsec combinators and recursion, we can write a lexer/parser for regular expresion that reads (Unicode!) Char as input, and produces a recursive RE structure.

Writing Recursive Descent parsing usually requires identifying the syntactic groups in the language we are trying to analyze, and build from the bottom up. In our case, the bottom is comprised of the basic regular expressions that have intrinsinc meaning.

basic :: Parser RE
basic =  (char' '∅' >> pure Empty)
     <|> (char' 'λ' >> pure Epsilon)
     <|> (Symbol <$> (lower <|> digit)) <* spaces
     <|> between (char' '(') (char' ')') regex
     <|> between (char' '[') (char' ']') range

Parsec parser combinators are monadic (Monad), with their >> and >>= operators having the obvious meaning of sequencing and connecting them, while implicitly keeping track of the input (look ma, no getChar, no line counting!). Custom parsers such as basic, are built out of one or more alternatives separated by operator <|>. Alternatives are tried in order of appearance until one of them consumes at least one input character. That gives meaning to

     (char' 'λ' >> pure Epsilon)

as «if we can lexically parse a character λ, return a value Epsilon, one of RE value constructors». Simple enough.

Parsec parser combinators are also Functor and Applicative. That gives meaning to

     (Symbol <$> (lower <|> digit)) <* spaces

as «if we can lexically parse one lowercase letter or one digit followed by zero or more whitespaces, then return a value Symbol with the single character». We take advantage of Applicative because operator (<*) means

   keepThis <* doThisButIgnoreTheResult

and we take advantage of Functor because

   f <$> Parser v

results in

   Parser (f v)

When introducing the nested parenthesis technique before, the actual parenthesis where hard coded in the parser. Parsec provides the polymorphic

between :: Parser open -> Parser close -> Parser a -> Parser a

giving meaning to

     between (char' '(') (char' ')') regex

as «check for open parens, use regex recursively, check for close parens, and return whatever regex parsed», where regex is a parser I haven’t showed you yet. You should be able to figure out the meaning of

     between (char' '[') (char' ']') range

in the context of a basic regular expression.

The edges of parsing

The p <* spaces should be clear now: try and parse whatever p parses, then parse as many whitespaces as you can, finally returning whatever p actually parsed.

That’s why I wrote

char' :: Char -> Parser Char
char' c = char c <* spaces

as a wrapper to char, in order to parse a single character, yet ignore any trailing spaces.

How about the top level parser, where «parsing starts»? Again, taking advantage of Parsec being Applicative we write

top :: Parser RE
top = spaces *> regex <* spaces <* eof

Which is equivalent to

(((spaces *> regex) <* spaces) <* eof)

i.e. «try to parse spaces and then a regex, keep the latter», «try to parse spaces, keep the former», «try to parse end-of-input, keep the former».

But top is still an abstract parser built out of parsers. In order to «run it» to actually process an input string, we must use Parsec.parse. We write

parseRegex s = parse top ("from string '" ++ s ++ "'") s

where s is the input String that should be processed using the top parser. If all goes well, parse will return a RE wrapped in a Right. If there’s a lexical or syntax error, parse will return said error wrapped in a Left.

ghci> parseRegex " (a + b c) * "
Right (Kleene (Alternate (Symbol 'a')
                         (Catenate (Symbol 'b') (Symbol 'c'))))
ghci> parseRegex " (1 + b* "
Left "from string ' (1 + b* '" (line 1, column 10):
unexpected end of input
expecting "+" or ")"

Neat.

Precedence and associativity

Looking at the output from the parser for the proper parse, it is clear that Catenate has higher precedence than Alternate, because the former is contained in the latter. It’s also clear, and I’ve already mentioned, that both Catenate and Alternate are left-associative. These properties have to be encoded in the parser.

If we were using a LALR parser generator such as Happy, there would be single rule for all expressions, and a block establishing precedence and associativity for all operators. This is expressed with rules similar to

%left '+'
%left JUXTAPOSITION
%right '*'
regex : regex '+' regex
      | regex regex   %prec JUXTAPOSITION
      | regex '*'
      | basic

The parser generator would produce a parser following that. This is one of the many reasons why using a parser generator is better than hand crafting one. The astute reader should have noticed we cannot translate the above into a recursive parser using Parsec, because

regex = regex >> char' '+' >> regex
     <|> regex >> regex
     ...

would inevitable go into an infinite loop. Not to mention it is impossible for the parser to deterministically choose between first and second rules.

The standard technique we teach in CI3725 is to rewrite the beautiful but ambiguous left-recurisve grammar into a right-recursive form, while simultaneously keeping the precedence and associativiy rules. You can read about the technique which is sort of automatic, but requires actual intelligence and understanding of the underlying syntax to get precedences right. I will not go into details, and just show part of what you’d end up with

    Regex    -> Catenate '+' Regex
             -> Catenate
    Catenate -> Kleene Catenate
             -> Kleene
    Kleene   -> Basic LotsOfStars
             -> Basic

This preserves precedence: Kleene is contained (highest) into Catenate, contained into Regex (lowest). Unfortunately, both Regex and Catenate became right associative; think about this

    Regex -> Catenate '+' Regex
      { expand right side of -> Regex with rules }
    Regex -> Catenate '+' (Catenate '+' Regex)

This problem was identified in the early days of parsing theory and compiler construction and it’s a consequence of using hand crafted top-down parsers. Yet another reason to use LALR parser generators. There are two practical approaches for this: use generalized Pratt parsing, or come up with a shunting-yard variation appropriate for this case. Generalized Pratt parsing requires the grammar to be a full operator grammar, and we cannot (easily) use it because we use juxtaposition instead of an explicit operator. I’ll use a variant of the shunting yard technique combined with Haskell’s lazyness if only to show what others struggle to do in their non-lazy languages…

As said before, we use juxtaposition to express concatenation, i.e.

abcd

and the above should be parsed as if it were

(((ab)c)d)

Assume there’s a parser kleene that parses a basic regex and its nested postfix *. We can parse catenation and keep them left-associative with the surprisingly (for users of other languages) succint

catenate :: Parser RE
catenate = foldl1' Catenate <$> many1 kleene

As described before many1 kleene for abcd would produce

Parser [Symbol 'a', Symbol 'b', Symbol 'c', Symbol 'd']

and Parser being a Functor means

foldl1' Catenate <$> Parser [Symbol 'a', Symbol 'b', Symbol 'c', Symbol 'd']
  { <$> definition }
Parser (foldl1' Catenate [Symbol 'a', Symbol 'b', Symbol 'c', Symbol 'd'])
  { once foldl1' has done its thing }
Parser (Catenate (Catenate (Catenate (Symbol 'a') (Symbol 'b')) (Symbol 'c')) (Symbol 'd'))

beautifully left-associative. You could argue that if the sequence of juxtaposed characters is very long, then many1 would build a very long list. But that is not what happens, thanks to Haskell’s laziness.

In reality, elements will be generated lazily, one at a time: many1 will produce enough for foldl1 to work at each step. I’ve removed several unessential constructors for clarity.

foldl1' Catenate <$> many1 kleene
  { <$> definition }
Parser $ foldl1' Catenate (many1 kleene)
  { many1 is «forced» to produce to feed foldl1' and becomes many }
Parser $ foldl1' Catenate (Symbol 'a' : many kleene)
  { foldl1 can move one step and become foldl' }
Parser $ foldl' Catenate (Catenate (Symbol 'a')) (many kleene)
  { many is «forced» to produce to feed foldl' }
Parser $ foldl' Catenate (Catenate (Symbol 'a')) (Symbol 'b' : many kleene)
  { foldl can move one step }
Parser $ foldl' Catenate (Catenate (Symbol 'a') (Symbol 'b')) (many kleene)
  ...

Turns out foldl1' («one or more») is defined in terms of foldl' («zero or more»), and many1' («one or more») is defined in terms of many' («zero or more»). Look the definitions up.

Since foldl1 is defined in terms of foldl, it will force the first many1 kleene, and the subsequent many kleene, to parse one at a time, so it can feed the nested Catenate applications from left to right. There’s never a full intermediate list, just a tree being build from left to right. And we need the tree anyway, so this is efficient as it can be.

Understading the mechanics for the regex parser that handles alternation

regex :: Parser RE
regex = foldl1' Alternate <$> catenate `sepBy1` char' '+'

and writing the kleene parser in terms of basic, are left as exercises to the reader.

We heard you liked parsers within parsers…

The only other parser worth looking into is the one for range. We’ve decided that [a-d] shall be the same as having an explicit a+b+c+d. We’d also like to have things like [a-dz0-9] properly constructed as a+...+d+z+0+..+9. Therefore, our range parser has to build a Catenate out of the expanded set of elements.

If we think of a-z, z, and 0-9 as «groups», we can start with

range :: Parser RE
range = do
  es <- concat <$> many singleOrGroup
  pure $ if null es then Empty
                    else foldl1' Alternate $ map Symbol es
    where
      singleOrGroup :: Parser [Char]
      (...)

that is, we try to get zero or more singleOrGroup using many. Each group produces a list of characters in the group, so we concat them all to get a flat [Char]. Note there could be empty lists if you mistakenly write z-a or 4-1. If the flattened list is empty, then we return the Empty regular expression, otherwise we use the foldl1' Alternate trick already discussed, while wrapping each Symbol.

Collecting single characters or ranges requires a dependent syntactic group: a parser that’s local to the range parser

      singleOrGroup :: Parser [Char]
      singleOrGroup = do
        single <- (lower <|> digit) <* spaces
        extend single <|> pure [single]
          where
            extend :: Char -> Parser [Char]
            extend start = do
              char' '-'
              enumFromTo start <$> (lower <|> digit) <* spaces

After getting a single lowercase letter or digit, we need to decide if it is a single character, or the start of a range. The <|> operator commits to a rule if said rule has consumed at least one character, that means

        extend single <|> pure [single]

will commit to extend single only if the next character in the input is a -. If that’s the case, then extend start will get the «end of the range», and expand it taking advantage of enumFromTo given that both Char and Int are Enum instances. If the next character is not a -, extend single will fail, and we produce a singleton list.

Analysis complete

We’ve written an integrated lexer/parser

parseRegex :: [Char] -> Either ParseError RE

solving the analysis part of our tool: get the input String and produce an Abstract Syntax Tree in the form of a (recursive) RE value, or a controlled exception containing the first syntax error. It’s about 30 lines of Haskell code, including type signatures.

It’s a fully deterministic parser. The input string will be read from left to right exactly once, because there’s exactly one possible code path to follow at each point in the input. It’s possible to write «backtracking» parsers by hand, and Parsec provides combinators for selective «backtracking» but we did not need them. There’s value in writing deterministic parsers, both in efficiency as well as maintainability, and we stress that to CI3725 and CI4721 students. That’s why we prefer parser generators, because they usually produce deterministic parsers. That said, not every language can be parsed deterministically, so it’s good to have a way to express that when needed.

The parser is as memory efficient as it can be under the circumstances and requirements. It will require as much stack space as nested expressions, on account of the recursive calls needed: recall regex could go all the way down to basic, where there’s a recursive call to regex. Even though we had to implement a custom shunting-yard trick to keep left-associativity, the parser will build the recursive RE tree without creating intermediate lists, thanks to Haskell’s lazyness. Plot twist: Parsec already provides combinators chainl and chainr to handle generalized left and right associativity, but I wrote a specific implementation by hand Because I Can®.

Using Parsec also takes care of line and character tracking, and default syntax error reporting, as shown by the failed example above. Parsec has combinators to include our own error diagnostics, but they aren’t needed for a language as simple as this one. One thing we always mention during CI3725 is that recovering from syntax error is incredibly difficult, and impossible to automate, so students aren’t required to implement it. Students taking CI4721 would certainly have choice words about it.

Our first task is done: deterministically parse regular expressions without using regular expressions, and build recursive tree-like structures representing them. Recursion is part of Computer Science. Resistance is futile. Fear is the mind killer.

We’re half way to answering the students’ original questions. All that is left is analyzing languages having infinite words, by synthezising behaviors. Recursive behaviors.