Montag, 12. August 2013

Ein Parsergenerator für die Westentasche

Code-Ebenen

Häufig bin ich beim Entwickeln daran, den gerade geschriebenen Code in verschiedene Implementierungstiefen zu separieren: Auf der höheren Ebene soll der Code möglichst intentional sein, meine Absicht möglichst lesbar ausdrücken. Redundanzen und durch die Programmiersprache erzwungenes "syntaktisches Rauschen" will ich hier so niedrig wie möglich halten. Von höherer Ebene aus spreche ich Code aus niederen Ebenen an. Diese niederen Ebenen enthalten die Implementierungsdetails, die zahllosen Antworten auf die immerwährende Frage "Wie mach ich's?".

Einen Anfänger erkennt man daran, dass er diese technische Ebene überschätzt, dass er die vielen kleinen Antworten auf die vielen kleinen Fragen für die eigentliche Programmierkunst hält. Weil es ihn viel Schweiss gekostet hat, dieses oder jenes technische Detail zu lösen (und es ist wahr: die Details sind anstrengend), stellt er es nun stolz in den Vordergrund seines Codes.

Aber wirklich gut wird sein Code nur, wenn er es schafft, diese technischen Lösungen in ihre Schranken zu verweisen. Ihnen eine nette Heimat im Code zu verschaffen - etwa in Form einer gut geschnittenen Methode - mit einem Namen, der genau das gelöste Problem beschreibt. Dann schwingt er sich hinauf zu der Ebene, in der er nur noch Gebrauch von seinen Lösungen macht.

Das ist ähnlich dem Übergang von einer "niederen" zu einer "höheren" Programmiersprache: Lösungen für spezifische, häufige, nützliche Aufgaben wurden zuerst als Sequenzen von CPU-Anweisungen gefunden - und in Form einer Anweisung oder eingebauten Funktion der Hochsprache verfügbar gemacht. In der Hochsprache lässt sich die Aufgabe nun problemorientiert formulieren. Man hätte auch auf der Assemblerebene bleiben können, um die Lösungen nur als eine Bibliothek von Unterprogrammen anzubieten. Schliesslich bietet bereits Assembler die Möglichkeit, sprechende symbolische Namen für Unterprogramme und Variablen zu wählen - im Kern bringt der Übergang zu einer höheren Sprache ja nichts Neues. Dennoch war die Schaffung einer Sprache mit besser an das Problem angepasster Grammatik die bessere Wahl. Der Komfort geht einher mit besserer Lesbarkeit, Nachvollziehbarkeit und Wartbarkeit. Man macht sich die Maschine erst dann richtig nutzbar, wenn man die Möglichkeit schafft, Problemlösungen in der Sprache des Problems zu formulieren.

Der nächste Schritt: Problemspezifische Syntax

Wenn man diesen Übergang von 2GL- zu 3GL-Programmiersprachen extrapoliert, so geht es offenbar darum, sich den Freiheitsgrad der Syntax nutzbar zu machen, um eine Problemlösung möglichst angemessen formulieren zu können. Man bleibt also nicht bei der Hochsprache stehen, sondern schafft neue "Vorstufen" mit eigenen Syntaxregeln - seien es eingeschränkte der einbettenden Sprache oder eine völlig neue Sprache. Ein Beispiel der ersten Sorte sind die editierbaren Quelltextfragmente. Die zweite Kategorie (die "externen DSL" in der Terminologie Martin Fowlers) erfordern immer eine Transformation: Die neue Syntax muss dem bestehenden Programmkontext bekannt gemachen werden, indem sie entweder in Datenstrukturen oder in Code der Zielsprache transformiert wird. Deswegen sind Transformationssprachen wie XSLT oder oMeta wichtig.

Mit oMeta steht mir ein handlicher, in JavaScript implementierter Parsergenerator zur Verfügung [1] - wirklich ein Parsergenerator für die Westentasche. Mit ein bisschen Übung kann man sich schnell eine adhoc-Syntax für alltägliche Probleme schafen, um sich lästige und wiederkehrende Routinearbeiten zu vereinfachen.

Die Selenium-IDE

Ich will das am Beispiel von Testfällen für die Selenium-IDE demonstrieren. Solche Testfälle sind Sequenzen von Benutzeraktionen und zu prüfenden Erwartungen, die sich im Firefox-Browser auf Knopfdruck abspielen lassen. Man kann sie mit einer Recorderfunktion aufzeichnen, muss aber noch massive Nacharbeiten vornehmen:
  • Eine stark mit Ajax arbeitende Webanwendung erfordert während der Testausführung Synchronisationspunkte.
  • Die Objektidentifikation der Recorderfunktion ist oft nicht die glücklichste Wahl und kann häufig robuster gemacht werden.
  • Last not least, schreibt man einen Testfall, um gewisse Erwartungen zu prüfen. Dafür sind assert- und verify-Anweisungen nötig, die von Hand nach (oder auch während) Aufzeichnung des Testfalls eingefügt werden.

So sieht ein Testfall in der Selenium IDE aus:

Technisch werden Testfälle als XHTML-Dokumente mit einer dreispaltigen Tabelle abgelegt. Hier ein Ausschnitt aus dem im Bild dargestellten Testfall:

<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
  <head profile="http://selenium-ide.openqa.org/profiles/test-case">
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
    <link rel="selenium.base" href="[...base URL...]" />
    <title>boss_lines_from_popup</title>
  </head>
  <body>
    <table cellpadding="1" cellspacing="1" border="1">
      <thead>
      <tr><td rowspan="1" colspan="3">boss_lines_from_popup</td></tr>
      </thead>
      <tbody>
        ...
        <!--Mittelbereich ausblenden-->
        <tr>
         <td>type</td>
         <td>id=ofrName</td>
         <td>Test</td>
        </tr>
        <tr>
         <td>clickAndWait</td>
         <td>id=rb_Boss</td>
         <td></td>
        </tr>
        <tr>
         <td>selectAndWait</td>
         <td>id=ofrBdwelt</td>
         <td>value=01</td>
        </tr>
        <tr>
         <td>selectAndWait</td>
         <td>id=ofrBdbereich</td>
         <td>value=0101</td>
        </tr>

Das in der Selenium-Architektur beabsichtigte Vorgehen ist es, diese Selenium-IDE als Steinbruch zur Aufzeichnung von Testfällen zu nutzen, diese dann aber in eine Programmiersprache wie Perl, Ruby, C# oder Java zu exportieren und dort als Unit Test auszuführen:

Die IDE bietet den Export als Menüpunkt standardmässig an. Technisch ist es eine Transformation von XHTML in ein Quelltextfragment von Java, Groovy oder einer anderen der genannten Sprachen [3]

Da dies das geplante Vorgehen ist, hat man bewusst auf gewisse - eigentlich erwartbare - Eigenschaften der IDE verzichtet. So sind die Testfälle der Selenium-IDE standardmässig nicht wiederverwendbar, auch nicht Teile daraus. Eine bestimmte Sequenz von Anweisungen, um einen normalisierten Anfangszustand der Applikation herzustellen, muss daher per Copy/Paste in jeden neuen Testfall hineinkopiert werden.[2]

Wenn wir im Besitz eines Parsergenerators sind, können wir den Fluss vorverlagern. Statt die XHTML-Dokumente in die Zielsprache zu transformieren, können wir uns eine eigene Sprache zur Notation von Testfällen ausdenken, in dieser Sprache dann die vermissten Konstrukte einbauen (z.B. eine include-Anweisung für die Wiederverwendbarkeit) - und diese in XHTML transformieren:

Wie wäre es z.B. mit folgendem Artefakt:

title = Test
baseURL = http://test.com
standard = "value=001"
/* Produkthierarchie auswählen */
clickAndWait id=rb_Boss
selectAndWait id=ofrBdwelt     value=01
selectAndWait id=ofrBdbereich  value=0101   
selectAndWait id=ofrPromotype  standard   // standard -> value=001
Mit dieser Syntax ist der Testfall auf das Wesentliche reduziert und wird so notiert, wie man die Ausführung erwartet.

Grammatikdefinition mit oMeta/JS

Wie ist die Grammatik eines solchen Codes zu beschreiben?
  • Anweisungen werden durch Zeilenumbruch begrenzt, es gibt keinen expliziten Zeilenbegrenzer
  • Es gibt Kommentare im C-Stil: Von // bis Zeilenende, oder eingeschlossen in /* ... */
  • Literale können Folgen von Zeichen sein, die keinen Leerraum enthalten,
  • Literale können aber auch in Anführungszeichen eingeschlossen sein.
  • Es gibt zwei Typen von Anweisungen: Zuweisungen und TestSteps.
  • Zuweisungen an Variable sind von der Form Symbol = Literal
  • TestSteps sind von der Form: Symbol Argument Argument, mit optionalen Argumenten
  • Die Argumente sind entweder Variablen, die in Zuweisungen deklariert wurden, oder Literale

Einige dieser Sprach-Designentscheidungen bilden ein gutes Grundgerüst nicht nur für diese konkrete Selenium-Sprache, sondern auch für andere DSLs. Dies motiviert als erstes also eine Oben-Unten-Trennung:

  • Ich führe einen Satz von Grammatikregeln ein, den ich "Vanilla-Parser" nenne und der nichts Selenium-Spezifisches enthält.
  • Im eigentlichen Selenium-Parser beziehe ich mich dann durch Vererbung auf den Vanilla-Parser
Hier ist die Grammatik des Parsers für die "Selenium-Vorstufe":
ometa Selenium <: VanillaParser {
  action         = symbol,
  arg            = var | literal,
  testStep       = action                  spacesNoCR 
                   arg:arg1 ?{arg1 != '='} spacesNoCR 
                   arg?,               
  stmnt          = ( testStep | assignment ) stmntEnd 
                   | comment                 spaces,
  document       = stmnt*
  }

  • Mit dem Zusatz <: VanillaParser beziehe ich mich durch Vererbung auf die bereits bestehende Grammatik VanillaParser
  • Die Anweisung action = symbol sagt, dass der action-Operand einer Testanweisung nach den Regeln eines symbolischen Namens gebildet werden soll: symbol ist eine Regel des VanillaParsers.
  • Die Argumente einer Aktion können dagegen Literale oder (zuvor deklarierte) Variablen sein (var und literal sind wieder oben definiert.
  • Nun kommt die Definition von Statements vom Typ testStep: Sie bestehen aus einer Aktion und keinem, einem oder zwei Argumenten. Da die Definition eines Arguments bewusst sehr lax ist (fast alles ist schliesslich ein Literal), muss hier mit dem semantischen Prädikat ?{arg1!='='} ausgeschlossen werden, dass eine Zuweisung fälschlich als testStep erkannt wird.
  • Weitere mögliche Anweisungen sind Zuweisungen (assignment) und Kommentare (comment), die ich wegen der Häufigkeit auf der oberen Ebene implementiert habe (also im Vanilla Parser).
  • Zuweisungen und TestSteps müssen mit einem Zeilenumbruch abgeschlossen werden. Kommentare können dagegen an beliebiger Stelle im Code eingestreut werden. Das definiert die Regel stmnt.
  • Ein Dokument schliesslich besteht aus einer Folge solcher Statements. Das besagt die letzte Regel: document = stmnt*. Der *-Operator funktioniert hier wie bei regulären Ausdrücken - auch ein leeres Textfile ist demnach ein gültiges Dokument.

Der Vanilla-Parser

Nun sei auch die obere Ebene nicht vorenthalten, der Vanilla-Parser mit den verallgemeinerungswürdigen Statements. Ich zeige die Grammatik gleich mit den semantischen Aktionen, die hinter dem Pfeil -> notiert werden. Auf die meisten dieser Regeln erhebe ich keinen Anspruch von Originalität - ich habe Elemente aus der JavaScript-Grammatik von Alex Warth übernommen - und so angepasst, wie mir das für einen Vanilla Parser nützlich schien.

ometa VanillaParser <: Parser {
  fromTo :x :y   = seq(x) (~seq(y) char)*:s seq(y) -> s.join(''),
  comment        = fromTo('//', '\n') | fromTo('/*', '*/'),
  spacesNoCR     = (~'\n' space)*,
  token :tt      = spaces seq(tt) -> tt,
  symbolFirst    = letter | '_' | '$',
  symbolRest     = symbolFirst | digit,  
  symbol         = symbolFirst:x symbolRest*:y -> (x+y.join('')),
  escapeChar     = '\\' char:c   -> unescape('\\' + c),
  delimitedExpression :delim = seq(delim) (escapeChar | ~seq(delim) char)*:x seq(delim) -> x.join(''),
  quotedLiteral  = delimitedExpression('"') | delimitedExpression('\''),
  bareLiteral    = (~space anything)*:x -> x.join(''),
  literal        = quotedLiteral | bareLiteral,
  var            = symbol:n ?{self.vars.hasOwnProperty(n)} -> (self.vars[n]),
  assignment     = symbol:n "=" spaces literal:v -> {self.vars[n] = v;{name:n,value:v}},
  stmntEnd       = spacesNoCR ('\n' spaces | end | ~~comment)
  }

VanillaParser.initialize = function() { this.vars = { } }

Die erste Regel fromTo ist eine parametrisierte Regel mit zwei Parametern: Sie erkennt Folgen, die mit x beginnen und mit y aufhören - wobei x und y die Parameter sind. Die nächste Regel comment zeigt die Anwendung.

spacesNoCR erkennt Leerraum, wie er zur Trennung zwischen zwei Elementen der Sprache verwendet wird, wobei Zeilenumbrüche ausgenommen werden. Für Grammatiken, die kein explizites Zeichen zur Beendigung eines Statements haben (wie die obige Selenium-Grammatik), sondern den Zeilenumbruch dafür verwenden, ist das wichtig.

Mit symbol sollen Variablennamen erkannt werden: "Vanilla"-geeignet ist die Konvention, sie mit einem Buchstaben, Dollarzeichen oder Unterstrich anfangen zu lassen, während ab der zweiten Stelle zusätzlich auch noch Ziffern erlaubt sind.

Fluchtsequenzen werden wie in C, Java oder JavaScript mit einem Backslash eingeleitet. Die Regel escapeChar wertet das dadurch spezifizierte Zeichen gleich aus (unescape('\\'+c), wobei c das angegebene einzelne Zeichen ist).

Die Regel quotedLiteral definiert in Anführungszeichen oder Hochkommata angegebene Ausdrücke. Zurückgegeben wird in beiden Fällen die innerhalb des Begrenzers angegebene Zeichenfolge.

Vielleicht will man sich in der Sprachdefinition auch den Luxus erlauben, bare words zuzulassen - wie das in Perl möglich (aber nicht mehr empfohlen) ist: Daher gibt es auch eine Regel bareLiteral, die einfach eine Folge von Zeichen ohne Leerraum erkennt.

Mit der Regel assignment wird einer Variablen ein Wert zugewiesen. Das Statement beginnt mit einem symbolischen Namen, es folgt ein Gleichheitszeichen und danach der Wert - ein Literal. Wird ein solches Statement erkannt, so wird im internen Parser-Attribut vars (ein Hash) ein Eintrag mit diesem Namen und Wert angelegt.

Dieser Wert kann nun auch erkannt werden: Eine Variable, die zuvor bereis deklariert wurde und daher im internen Objekt vars enthalten ist, wird durch die Regel var erkannt. Dafür sorgt der JavaScript-Ausdruck self.vars.hasOwnProperty(n), der hier in Form eines semantischen Prädikats in die Regel eingefügt wurde. Wenn dieser Ausdruck zu true evaluiert, ist die Regel als Ganzes erfüllt, und die zugeordnete semantische Aktion bringt als Ergebnis den in vars gespeicherten Wert dieser Variablen zurück.

Schliesslich kann die Regel stmntEnd zur Definition eines Anweisungs-Endes verwendet werden: Sie trifft ein, wenn - nach allfälligen Leerzeichen - ein Zeilenumbruch erfolgt, oder das Quelldokument beendet ist, oder ein Kommentar folgt. Der Kommentar wird hierbei nicht "konsumiert", wozu der doppelt verneinende Operator '~~' als Vorausschau-Operator verwendet wird (auch die Negation konsumiert bereits keine Zeichen aus dem Quelldokument).

Der ganze VanillaParser ist nur als eine Art Halde gedacht, aus der man sich bei der Definition einer konkreten Syntax bedienen kann.

Die Transformation

Die oben beschriebene Grammatik war die reine Parser-Definition. Um sie zu einer Transformation zu machen, müssen für alle erkannten Komponenten die entsprechenden semantischen Aktionen hinzugefügt werden, die aus den Bestandteilen der Quelldokuments ein Fragment des Zieldokuments erzeugen. Es handelt sich also um genau dieselbe Grammatik wie oben - Selenium - jedoch mit angehängten semantischen Aktionen. Mit folgenden Aktionen verwandelt sich obiger Parser in ein HTML-Dokument: in eine gültige Instanz eines Selenium-IDE-Testfalls.

ometa Selenium <: VanillaParser {
  action         = symbol,
  arg            = var | literal,
  testStep       = action:a                spacesNoCR
                   arg:arg1 ?{arg1 != '='} spacesNoCR
                   arg?:arg2               -> SeleniumTransformer.TestStep(a,arg1,arg2),
  assignment     = ^assignment:a -> SeleniumTransformer.SetVar(a.name,a.value),
  comment        = ^comment:c -> SeleniumTransformer.Comment(c),
  stmnt          = ( testStep |assignment ):s stmntEnd -> s
                   | comment:c             spaces -> c,
  document       = stmnt*:s -> {SeleniumTransformer.Head()+s.join("\n")+SeleniumTransformer.Tail()}
  }

// Manches wird hier leicht umständlicher notiert als nötig.
// Das hat den Grund, dass wir den OMeta-JS-Parser überstehen müssen:
function _SeleniumTransformer() {
  var Comment = function(c) {
    return "<!-- " + c.replace(new RegExp("\\s*$"),"") + " -->"
    }
  var TestStep = function() {
    var args = Array.prototype.slice.call(arguments,0);
    return "<tr><td>"+args.join("</td><td>")+"</td></tr>"
    }
  var vars={};
  var SetVar = function(name,value) {
    vars[name] = value;
    }
  var Head = function() {
    var head = '<?xml version="1.0" encoding="UTF-8"?>\n'+
      '<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">\n'+
      '<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">\n'+
      '<head profile="http://selenium-ide.openqa.org/profiles/test-case">\n'+
      '<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />\n'+
      '<link rel="selenium.base" href="$baseURL" />\n'+
      '<title>$title</title>\n'+
      '</head>\n'+
      '<body>\n'+
      '<table cellpadding="1" cellspacing="1" border="1">\n'+
      '<thead>\n'+
      '<tr><td rowspan="1" colspan="3">$title</td></tr>\n'+
      '</thead><tbody>\n';
    return head.replace( new RegExp("\\$title","g"), vars.title || '' ).replace( new RegExp("\\$baseURL","g"), vars.baseURL || '' )
    }
  var Tail = function() {
    return '\n    </tbody></table>\n  </body>\n</html>';
    }

  return {
    Comment:Comment,
    TestStep:TestStep,
    Head:Head,
    Tail:Tail,
    SetVar:SetVar
    }
  }
var SeleniumTransformer = _SeleniumTransformer();

Ein gängiges Muster ist es, das Ergebnis einer Transformation zunächst in einem einfachen Zwischenformat zu speichern, das dann der eigentlichen Transformation als Input dient (das semantische Modell) - was ich hier nicht gemacht habe. Der Vorteil des Zwischenformats wäre die separation of concerns: Das Zwischenformat könnte auch von einer ganz anderen Quelle herkommen - z.B. von einem Programm automatisch erstellt worden sein. Die Transformation in das Zielformat kann dann trotzdem durchgeführt werden, unabhängig vom Parserschritt. Ich habe die Separierung hergestellt, indem ich den HTML-Codegenerator in eine eigene Funktion SeleniumTransformer ausgelagert habe. Damit habe ich auch ohne Zwischenformat die separation of concerns: Um die Transformation ohne Parser aufzurufen, muss ich nur die Funktion SeleniumTransformer verwenden.

Fussnoten

[1] Es gibt auch oMeta-Implementierungen in anderen Sprachen. Beliebt ist z.B. die C#-Version. Ich habe der Sprache einen kleinen Auftritt zum Experimentieren auf meiner Homepage gewidmet: oMeta @ ruediger-plantiko.net. Die Seite http://www.tinlizzie.org/ometa/ des oMeta-Erfinders Alessandro Warth gibt umfangreiche Informationen, insbesondere über Implementierungen in verschiedenen Hostsprachen.
[2] Es gibt aber immerhin ein Plugin, mit dem bis zu einem gewissen Umfang eine Include-Anweisung verfügbar ist.
[3] Es würde sich XSLT für diese Transformation anbieten, ich weiss allerdings nicht, wie der Export implementiert ist.

Keine Kommentare :