
\documentclass[12pt]{article}
\usepackage[T2A,OT1]{fontenc}
\usepackage[default]{cantarell}
\usepackage[a4paper, top=20mm, bottom=20mm, left=20mm, right=20mm]{geometry}
\usepackage[utf8]{inputenc}
\usepackage[russian, english]{babel}
\usepackage{tabu}
\usepackage{hyperref}
\usepackage{parskip}
\usepackage{graphicx}
\usepackage{tabularx}
\usepackage{float}
\floatstyle{boxed}
\restylefloat{figure}
\usepackage{setspace}
\onehalfspacing
\author{Artyom Bologov}
\date{\today}
\title{5 (Wrong) Regex To Parse Parentheses}
\makeatletter
\def\endenv{\expandafter\end\expandafter{\@currenvir}}
\makeatother
\begin{document}
\maketitle

\includegraphics[width=\textwidth,height=\textheight,keepaspectratio]{./assets/paren-regex.png}

I'm trying to write
\href{https://github.com/aartaka/modal.ed}{Modal.ed, a compiler} from
\href{https://wiki.xxiivv.com/site/modal.html}{Modal} to
\href{https://www.man7.org/linux/man-pages/man1/ed.1p.html}{ed(1)} scripts.
Which is quite a story of its own, I guess?
I'll leave it for later.

One part of this project is reliably parsing Modal syntax.
Here are some examples of Modal rules:
\begin{figure}[h!]\begin{verbatim}
<> ((unwrap ?x)) (unwrap ?x)
<> (q ?x) (q ?x)
<> (`?: ?0 ?1) ((Int ?:))
<> (?: print ') (?:)
<> (iterating ?x ?y ?n    (1) ?a ?b) (?((?:) ?:) ss)
<> (?0 ?1 `?:) ?:
<> rule0 data
\end{verbatim}\caption{Modal rules in all their diversity}\end{figure}

The general pattern (hopefully apparent from the snippets) is:

\begin{itemize}\item Rules are starting with \verb|<>|
\item  Rules have a left hand side (pattern) and a right hand side (replacement.)
\item  Both sides are wrapped in parentheses, but parens are sometimes omitted for obvious single-symbol cases.
\item  The pattern/replacement can get as complex as the programmer wishes. But (hopefully) the parentheses are reliably balanced.
\end{itemize}

So all we need is to parse balanced parentheses in ed.
Easy, right?
This post is an exercise of desperation trying to parse parentheses with regex.
A journey that has a happily ever after, unfortunately.
But here's a bit of boring stuff first:

\section*{Pragmatic: Recursive Regex} \label{pragmatic}

The search for perfect regex led me to StackOverflow.
\href{https://stackoverflow.com/questions/546433/regular-expression-to-match-balanced-parentheses}{To the "Regular expression to match balanced parentheses" question in particular}.
A place where the best minds of the industry were either:

\begin{itemize}\item "No, it's not possible.", or
\item  Suggesting non-portable vendor-specific regex extensions.
\end{itemize}

.NET and Perl regex are suggested multiple times, with a recurring form of
\begin{figure}[h!]\begin{verbatim}
((?:[^)(]+|(?R))*+)
\end{verbatim}\caption{Perl recursive regex for parentheses matching}\end{figure}

Perl is nice, but
\href{run:the-regex}{There Is No Such Thing As The Regex},
and I have a soft spot for ed regex, and POSIX BREs in particular.
These don't have recursive matching.
So I was bored out of my mind reading all these StackOverflow exercises in conformity.
And I decided to prove them wrong:
One does not need .NET or Perl to parse parentheses properly.
<span id=my-approach>POSIX BREs and text substitution are more than enough</span> to work with parentheses and Modal rules.

\section*{Naive: It Is Balanced, Right?} \label{naive}

So the simplest way to match parentheses is to... match parentheses.
And nothing/anything else in between:
\begin{figure}[h!]\begin{verbatim}
(.*)
\end{verbatim}\caption{Implying parentheses are balanced, because they must be?}\end{figure}

There are multiple cases where this regex breaks:

\begin{description}\item[(...) (...)]      Is matched as one piece due to regex greediness.
\item[()))))))<dt><dd> Is matched too, because we actually don't look for balance.]
\item[()(((((()<dt><dd> A variation on the previous too, but ugly enough to include.]
\end{description}

We need more structure to paren matching.
And we'll have it:

\section*{Restrictive: I Will Be Correct Whatever the Cost} \label{restrictive}

So we don't want stray parens and we need balanced parentheses.
We can arrange exactly that:
\begin{figure}[h!]\begin{verbatim}
([^()]*)
\end{verbatim}\caption{A regex to match a parenthesised list with no nested lists}\end{figure}

So we match two parentheses and some number of non-parentheses inside.
Which doesn't give us false positives like in the first iteration.
But doesn't scale to more nested patterns.

\section*{Pedantic: Hardcoding Patterns} \label{pedantic}

There has to be a way that covers most of the practical cases.
I'm ready to cut corners, like too deeply nested parentheses.
Which means most cases can be hard-coded:
\begin{figure}[h!]\begin{verbatim}
# Level one
([^()]*)
# Level two
(([^() ]{0,1}(([^()]*)){0,1})*)
# Level three
(([^() ]{0,1}((([^() ]{0,1}(([^()]*)){0,1})*)){0,1})*)
# Et cetera
\end{verbatim}\caption{Hard-coded nested parentheses regex}\end{figure}

The second and third ones look weird, but it's a way of saying:
there must be a monolythic symbol (like \verb|hello|)
or a parenthesised list of symbols (like \verb|(hello there)|) inside these two parentheses.
This is due to BREs having no alternation pattern, \verb|||.
These rules can be conveniently rewritten in POSIX EREs
(that's the last time I employ such a bloated regex format in this post!)
\begin{figure}[h!]\begin{verbatim}
(([^()]+|([^()]*))*)
\end{verbatim}\caption{POSIX ERE for two-levels-deep parentheses}\end{figure}

Elegant, but less portable than BREs.
I need to run it on BSD, UNIX, and GNU ed, so begone EREs!

\section*{Lispy: Looking for Tiger Tails} \label{lispy}

Another way to ensure the balance is to restrict the inputs.
Say, we can require Modal rules to be Lisp-like in only having prefix operators.
With all the argument at the tail.
This would result in a dreaded "tiger tail" or parentheses at the end.
But it also makes the parsing problem irrelevant: just match the tail and you're golden:
\begin{figure}[h!]\begin{verbatim}
((*[^)]*)*)
\end{verbatim}\caption{Lispy parentheses matching}\end{figure}

Most of Modal codebases are somewhat lispy already.
So this regex has a higher success/LoC ratio than, for example, hardcoded rules.
But I can see why one might be uneasy about it—it's not really structural.
Unlike...

\section*{Recursive, But Not That One} \label{recursive}

The structure of the Modal rules is:

\begin{itemize}\item It's a symbol or register.
\item  Or it's a list of symbols/registers.
\item  Or it's a list of symbols/registers and other lists.
\item  And so on.
\end{itemize}

So it dawned on me: we can isolate symbols,
then use these to highlight the simple lists and then propagate up the list ladder.
So the algorithm I came up with is:

\begin{itemize}\item Wrap all simple symbols in Russian quotes: «». (Because they are distinctive and unique enough for parsing, and because I'm ethnically Russian.)
\item  If the list consists entirely of quoted forms or is empty, remove all quotes inside and wrap the list itself into quotes.
\item  Repeat until there's nothing to substitute and the quoted list is the toplevel one.
\end{itemize}

And here's (an arguably ugly) code that does this in my ed script:
\begin{figure}[h!]\begin{verbatim}
# Wrap every symbol/nil into quotes
g/[^() ]{1,}/s//«&»/g
g/()/s//«&»/g
# Actual parsing: if the current layer of parens is all quoted, quote it and unquote contents
g/(«([^»]*)» «([^»]*)» «([^»]*)» «([^»]*)» «([^»]*)» «([^»]*)» «([^»]*)» «([^»]*)» «([^»]*)»)/s//«(1 2 3 4 5 6 7 8 9)»/g
g/(«([^»]*)» «([^»]*)» «([^»]*)» «([^»]*)» «([^»]*)» «([^»]*)» «([^»]*)» «([^»]*)»)/s//«(1 2 3 4 5 6 7 8)»/g
g/(«([^»]*)» «([^»]*)» «([^»]*)» «([^»]*)» «([^»]*)» «([^»]*)» «([^»]*)»)/s//«(1 2 3 4 5 6 7)»/g
g/(«([^»]*)» «([^»]*)» «([^»]*)» «([^»]*)» «([^»]*)» «([^»]*)»)/s//«(1 2 3 4 5 6)»/g
g/(«([^»]*)» «([^»]*)» «([^»]*)» «([^»]*)» «([^»]*)»)/s//«(1 2 3 4 5)»/g
g/(«([^»]*)» «([^»]*)» «([^»]*)» «([^»]*)»)/s//«(1 2 3 4)»/g
g/(«([^»]*)» «([^»]*)» «([^»]*)»)/s//«(1 2 3)»/g
g/(«([^»]*)» «([^»]*)»)/s//«(1 2)»/g
g/(«([^»]*)»)/s//«(1)»/g
# Repeating second time for recursive case
# Ad infinitum
\end{verbatim}\caption{Recursive parentheses matching}\end{figure}

You may say I'm cheating, because it's not only regex, it's also substitution rules.
\pageref{my-approach}{But I warned you!}
The results are relatively good:

\begin{itemize}\item The parsed depth is at worst the number of copy-pasted ladders.
\item  And at best the number of inidividual substitutions.
\item  The average lies somewhere around the number I don't know how to compute, but it should be good enough.
\item  The algorithm would be perfect if there were looping constructs in ed.
But there aren't.
I might've used
\href{https://www.man7.org/linux/man-pages/man1/sed.1p.html}{sed(1)} for looping, but...
\href{run:sed-ed}{I despise sed}.
\end{itemize}

So I have my parsing rules happily chewing on Modal code.
\href{https://github.com/aartaka/modal.ed}{In Modal.ed},
check it out!
Thanks for lending me a ear and embracing the power of regex 🖤

\par\noindent\rule{\textwidth}{0.4pt}
Copyright 2022-2025 Artyom Bologov (aartaka).
Any and all opinions listed here are my own and not representative of my employers; future, past and present.

\end{document}
