^(almost) murphy.de

(German translation on Ruby-Mine.)

Now, I’m about to write the Java Scanner for CodeRay (ticket #42 btw), and I thought it would be nice to have a list of built-in types highlighted – like String or IllegalStateException. I knew that TextMate had quite good highlighting for Java, so I checked the bundle for something to use.

Indeed, some smart guy included a very long regular expression into the token definitions, it looks like this:

support-type-built-ins-java = {
  name = 'support.type.built-ins.java';
  match = '\b(R(GBImageFilter|MI(S(ocketFactory|e(curity(Manager|Exception)|
    rver(SocketFactory|Impl(_Stub)?)?))|C(onnect(ion(Impl(_Stub)?)?|
    or(Server)?)|l(ientSocketFactory|assLoader(Spi)?))|IIOPServerImpl|
    JRMPServerImpl|FailureHandler)|SA(MultiPrimePrivateCrtKey(Spec)?|
    ...this goes on for several screens...

Apparently, they converted a long list of types into a minimal regexp, surely using a script for this. But that wasn’t exactly what I had searched for. How could I convert this back into the original plain list?¹

Recursive Descent Parser

What I needed was something like this:

srs = SimpleRegexpScanner.new('(A)?(B|C)')
srs.list  #=> ['AB', 'AC', 'B', 'C']

Something I remembered from my lecture about compiler construction three years ago were recursive descent parsers: It is possible to parse simple grammars (LL to be precise) with that approach, and the grammar of the regexp was simple enough.

So I wrote SimpleRegexpScanner in recursive form, of course in Ruby. After some refinement, the result became quite short:

class SimpleRegexpScanner < StringScanner

1. Returns an Array of all possible strings that would fit the given regexp.
   def list
   scan_union.uniq
   end

protected
def scan_group # :nodoc:
scan(/\(/) or return
options = scan_union
scan(/\)/) or raise ‘) expected at end of group’
options << ’’ if scan(/\?/)
options
end

end

It solved my problem: I can now restore the original word list from any regexp of this type in a matter of milliseconds :)

Download

I added tests and a bit of documentation, and you can play with it under LGPL as much as you want.

SimpleRegexpScanner

¹ I need a list because CodeRay uses a Hash-based approach for word lists, which should be much faster than using even optimized regexps. In addition, Ruby 1.8 refused the regexp as “too big”, and TextMate has problems with long one-line strings anyway.