ruby-mine

(Deutsche Übersetzung; Original auf murfy.de.)

Ich bin gerade dabei, den Java Scanner für CodeRay (Ticket #42 ^^) zu schreiben, und dachte, es wäre nett, eine Liste von eingebauten Typen zu haben, um sie hervorzuheben – wie String oder IllegalStateException. Ich wusste, dass TextMate recht gute Unterstützung für Java bietet, also schaute ich mir das Bundle genauer an.

Tatsächlich, irgendein schlauer Kerl hat dort einen ziemlich langen regulären Ausdruck in die Tokendefinitionen geschrieben:

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)?|
    ...und so weiter über mehrere Bildschirmseiten...

Offenbar haben sie eine lange Liste von Typen in eine minimale Regexp umgewandelt, sicher mit Hilfe eine Scripts. Das war nicht ganz das, wonach ich gesucht hatte. Wie komme ich jetzt an die ursprüngliche Liste?

Rekursiver Abstieg

Was ich brauchte¹, war ungefähr sowas:

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

Mir fiel ein, dass ich in meiner Vorlesung über Compilerbau vor drei Jahren etwas über Rekursive Abstiegsparser gehört habe: Man kann sehr einfache Grammatiken (LL(k) um genau zu sein) mit diesem Ansatz parsen, und dieser reguläre Ausdruck war einfach genug.

Also habe ich SimpleRegexpScanner in rekursiver Form geschrieben, natürlich in Ruby. Nach ein wenig Basteln ist der Code ziemlich kurz geworden:

class SimpleRegexpScanner < StringScanner

  # 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

  def scan_union  # :nodoc:
    options = scan_concatenation
    options += scan_union if scan(/\|/)
    options.uniq
  end

  def scan_concatenation  # :nodoc:
    options = scan_group || [scan(/[^(|)?]*/)]
    if check(/[^|)]/)
      suffixes = scan_concatenation
      options.map! do |option|
        suffixes.map { |suffix| option + suffix }
      end.flatten!
    end
    options
  end

end

Das löst mein Problem: Ich kann jetzt die Originalliste aus jeder einfachen Regexp in wenigen Millisekunden wiederherstellen :)

Download

Ich habe Tests und ein bisschen Dokumentation hinzugefügt, und ihr könnt damit unter LGPL spielen soviel ihr wollt:

SimpleRegexpScanner

¹ Ich brauche eine Liste, weil CodeRay einen Hash-basierten Ansatz für Wortlisten verfolgt, der noch schneller als optimierte reguläre Ausdrücke sein sollte. Zudem weist Ruby 1.8 die Regexp als “too big” zurück, und TextMate hat sowieso Probleme mit langen einzeiligen Strings.