Re: irregular expressions, syntax complexity

On 2023-02-21, Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
> You can translate regexps with & to a DFA, and don't lose any
> performance there. For an NFA-based implementation, the only way I
> see is that you process both sub-NFAs and check if they both accept
> the string, so it's somewhat slower; I guess that this is a major
> reason why such an operator has not been added to widely-used regexp
> syntaxes.
>
> Has anybody implemented such an operator at all?


I implemented & in the TXR language.


It's based on Brzozowski regex derivatives (described first in 1964,
IIRC).


Derivatives allow a regex syntax with & to be interpreted directly,
and without backtracking or trying sub-cases; effectively, the approach
is equivalent to an NFA.


(Derivatives can be used for compiling also. The problem you have to
solve is deciding when two regexes are equivalent, so that you can
close loops in the state machine graph. The better you can do this, the
tighter the graph will be,)


The idea behind a "derivative" is to take an input symbol S and a regex
R, and calculate a new expression R' which matches the rest of the input
after S.


E .g. the derivativre of "abc" with respect to "a" would be "bc".
Likewise with respect to "." (match any single character).


The derivative of "abc" with respect to d would be ∅, the nomatch regex
which describes/matches nothing: empty set of strings. (Not to be
confused with the empty regex that matches the empty string, denoting
the set { "" }).


To match a string of symbols, you simply take successive derivatives. If
you hit ∅, you can short-circuit to the conclusion that the input
doesn't match.


When you run out of input symbols, the remaining derivative must be
nullable: nullable means capable of matching the empty string. If it
isn't, it means the regex wants more characters, so you don't have
a match.


The empty set ∅ regex isn't nullable, needless to say; a regex is
nullable if the language (set of strings) contains the empty string.


Anyway, you can represent regexes in Lisp syntax and then the derivative
operation is just a functional syntax -> syntax calculation (which
generates a lot of garbage as we match strings).


The & operator is easily supported because the derivative operation
readily distributes into the & operatror according to an easy rule.


    d(S, R1 & R2) -> d(S, R1) & d(S, R2)


Basically you take the derivatives of the branches, and combine them
with & again.


The more familiar | operator distributes the same way.


IN an actual implementation, there are tricks you can pull, like
short-circuit evaluation. If you take the d(S, R1) derivative of the
left side of R1&R2, and that turns out to be ∅, you can short-circuit
to ∅, If you have way to detect that a regular expression A matches all
strings (like .*) then you know that A&R is equiavlent to R; you can
drop that branch, similarly A|R is A.


You can see that this is amenable to compilation, similar to the subset
construction; you can calculate a derivative with respect to all
possible input symbols and build a graph in which the regex syntax
itself (all the derivatives) are the states. To close loops in the
graph, you need to detect states you have seen before, which requires
equivalence test between two syntax fragments. The fewer false negatives
you have, the tighter the graph.


TXR's regex engine has a front end which checks whether the syntax
contains the "exotic operators" and chooses either the derivative-based
back end or compilation to NFA and simulation.


I haven't bothered implementing better compilation for either back end;
if a collaborator came along to explore those possibilities, that would
be great. Most of that work was done over a decade ago. There is now a
powerful Lisp dialect that would make easy work of writing a
derivative-based regex compiler.


--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca

Return to the comp.compilers page.
Search the comp.compilers archives again.