r/java • • 4d ago

Regex Parser for Static Analysis

https://google.github.io/mug/apidocs/com/google/common/labs/regex/RegexPattern.html

This is a parser that I created a while back, in order to build some regex static analysis tools (detecting ReDos, validating supported regex features etc.).

I built it because I didn't find an OSS regex parser that produces and exposes the AST for custom analysis (the regex engines I looked at all keep their parser internal, and only execute the regex).

The parser supports advanced features such as back references, lookarounds, unicode properties, posix char classes, inline and global comment mode (a.k.a free-spacing mode) etc.

Using it with pattern matching is easy:

switch (RegexPattern.of("\\w+:\\d+")) {
  case Sequence(var elements) -> ...;
  case Alternation(var alternatives) -> ...;
  ...
  default -> ...;
}

To keep it simple, A few obscure features are omitted: such as \12 being parsed differently depending on the number of capture groups defined (\1 followed by literal 2 if no 12 capture groups are present).

The code is combinator-based, mostly pair-programmed by AI and me. It's actually what I built the dot-parse library for: to be able to have AI do the chores of generating readable parser for the wide surface area and arcane regex grammar rules; so I don't have to get a degree in regex.

It has served the purpose of static analysis well.

Feedbacks are welcome!

javadoc

repo

13 Upvotes

5 comments sorted by

3

u/v4ss42 4d ago

Holy shit I’ve been putting off writing one of these, despite needing it for a while, because it seemed like a pita. I’ll be checking this out for sure!

1

u/DelayLucky 3d ago edited 3d ago

Oh yeah it's a pain.

The regex has so many grammar rules and some very bizarre edge cases. What I know in my head is only a small subset. I wouldn't want to do it again if I can't offload the drudgery to AI.

1

u/v4ss42 3d ago

Can you clarify how much AI generated code is part of this logic?

4

u/DelayLucky 3d ago edited 3d ago

The AST is mechanical. Design is by human; the conrete types are mostly generated by AI.

You can get a sense of the grammar surface size by the size of the AST code

The workflow of getting readable parser

Me: Agent, help me generate parser for this grammar using dot-parse, follow the AGENTS.md, with full test coverage.

Agent: (asking a bunch of questions), here's the parser code with tests.

Me: What's with this complex piece of code? I don't like it. What grammar rule needs this?

Agent: it's such and such...

Me: Can it be done using this equivalent idiom?

Agent: Yes. That's much simpler.

Rinse and repeat...

The workflow of getting optimal parser

Me: Agent, create benchmark for the parser. What's making it so slow compared to JDK?

Agent: it's the backtracking anyOf() does for this grammar rule...

Me: oh, I see. Why can't you use OperatorTable, or optionallyFollowedBy() etc. for it, that way there is no backtracking?

Agent: refactored and benchmark showed x% improvement.

Rinse and repeat...