Programmiererpraxis

Der Aufstieg von Roslyn

Joe Hummel
Ted Neward

Schon seit einigen Jahren haben eine Reihe von Computerprofis, Ideengebern und Experten die Idee von domänenspezifischen Sprachen (DSLs, Domain-Specific Languages) als Möglichkeit, Lösungen für Softwareprobleme zu finden, propagiert. Dies scheint besonders angebracht zu sein, wenn die DSL-Syntax so beschaffen ist, dass sie auch von "Gelegenheitsbenutzern" verwendet werden kann, um die Geschäftsregeln in einem System anzupassen und zu verändern. Das stellt für viele Entwickler den Heiligen Gral der Software dar – das Erstellen eines Systems, das von den Benutzern selbst geändert werden kann, wenn sich die Geschäftsanforderungen ändern.

Einer der grundsätzlichen Kritikpunkte bei DSL leitet sich allerdings aus der Tatsache ab, dass das Schreiben von Compilern eine "verlorene Kunst" ist. Es ist nicht ungewöhnlich, dass Programmierer jeder Couleur das Erstellen eines Compilers oder Interpreters als eine Art schwarzer Kunst ansehen.

Bei der Build 2014-Konferenz in diesem Jahr kündigte Microsoft formell eines der am schlechtesten gehüteten Gemeinmisse im Ökosystem der Microsoft .NET Framework-Entwicklung an – den Übergang von Roslyn zu Open Source. Die ist das aufpolierte/umgearbeitete Compilersystem, das den Sprachen C# und Visual Basic zugrundeliegt. Für einige ist dies eine Chance für Microsoft, seine Sprachen in der Open Source-Community zu verankern und sich die Vorteile zu sichern – Programmfehlerbehebungen, Verbesserungen, öffentliche Kritik neuer Sprachfeatures usw. Für Entwickler bietet sich so die Gelegenheit, sich einmal genauer anzusehen, wie Compiler (und Interpreter, obwohl der Schwerpunkt bei Roslyn für die genannten Sprachen auf Kompilierung liegt) intern funktionieren.

Mehr Hintergrundinformationen (und Hinweise zur Installation) finden Sie auf der Roslyn-CodePlex-Seite unter roslyn.codeplex.com. Wie immer bei noch nicht veröffentlichter Software, empfiehlt es sich, das auf einem virtuellen Computer oder einem Computer auszuprobieren, der Ihnen nicht so wichtig ist.

Roslyn-Grundlagen

Auf einer hohen Ebene besteht die Aufgabe eines Compilers darin, die Eingabe eines Programmierers (den Quellcode) in eine ausführbare Ausgabe, wie etwa eine .NET-Assembly oder eine systemeigene EXE-Datei, zu übersetzen. Während die genauen Namen der Module in Compilern sich unterscheiden können, stellen wir uns doch normalerweise einen Compiler als aus zwei Teilen bestehend vor: einer Eingangsseite und einer Ausgangsseite (siehe Abbildung 1).

Abbildung 1 Compilerentwurf auf hoher Ebene

Eine der wichtigsten Zuständigkeiten der Eingangsseite ist die Überprüfung der Formateinhaltung beim eingehenden Quellcode. Wie bei allen Programmiersprachen, gibt es ein bestimmtes Format, an das sich Programmierer halten müssen, um die Dinge für den Computer klar und unzweideutig zu halten. Betrachten Sie beispielsweise die folgende C#-Anweisung:

if x < 0   <-- syntax error!
  x = 0;

Dies ist syntaktisch falsch, da IF-Bedingungen in Klammern eingeschlossen sein müssen, wie hier:

if (x < 0)
  x = 0;

Sobald der Code analysiert wurde, ist die Ausgangsseite für die tiefer gehende Überprüfung der Quelle zuständig, wie etwa Verletzungen der Typsicherheit:

string x = "123";
if (x < 0)                   <-- semantic error!
  x = 0;                     <-- semantic error!

Wie es der Zufall will, sind diese Beispiele willkürliche Entwurfsentscheidungen seitens des Implementierers der Sprache. Sie unterliegen langen Debatten, in denen sich alles um die Frage dreht, was "besser" ist als die anderen Optionen. Wenn Sie mehr darüber wissen möchten, suchen Sie ein beliebiges Onlineforum über Programmierung auf, und geben Sie "D00d ur language sux" ein. Sie werden sich schon bald in einer "erzieherischen" Sitzung gefangen sehen, die es sicherlich wert ist, sich an sie zu erinnern.

Unter der Voraussetzung, dass keine syntaktischen oder semantischen Fehler vorliegen, wird die Kompilierung fortgesetzt, und die Ausgangsseite übersetzt die Eingabe in ein äquivalentes Programm in der gewünschten Zielsprache.

Tiefer in die Tiefe

Zwar kann der Zwei-Teile-Ansatz bei den einfachsten Sprachen funktionieren, meistens unterteilen sich Compiler/Interpreter für Sprachen jedoch sehr viel stärker. Auf der nächsten Komplexitätsstufe arbeiten die meisten Compiler in sechs Hauptphasen, zwei an der Eingangs- und vier an der Ausgangsseite (siehe Abbildung 2). 

Abbildung 2 Die Hauptphasen eines Compilers

Die Eingangsseite führt die zwei ersten Phase aus: lexikalische Analyse und Analyse/Zerlegung. Das Ziel der lexikalischen Analyse besteht darin, das eingegebene Programm zu lesen und die Token auszugeben – die Schlüsselwörter, Interpunktionszeichen, Bezeichner usw. Der Ort jedes Tokens bleibt dabei erhalten, sodass das Format des Programms nicht verloren geht. Angenommen, das folgende Programmfragment beginnt am Anfang der Quelldatei:

// Comment
if (score>100)
  grade = "A++";

Die Ausgabe der lexikalischen Analyse wäre dann diese Folge von Token:

IfKeyword                       @ Span=[12..14)
OpenParenToken              @ Span=[15..16)
IdentifierToken                  @ Span=[16..21), Value=score
GreaterThanToken             @ Span=[21..22)
NumericLiteralToken           @ Span=[22..25), Value=100
CloseParenToken              @ Span=[25..26)
IdentifierToken                  @ Span=[30..35), Value=grade
EqualsToken                    @ Span=[36..37)
StringLiteralToken             @ Span=[38..43), Value=A++
SemicolonToken               @ Span=[43..44)

Jedes Token trägt weitere Informationen, wie etwa die Start- und Endposition (Spanne), gemessen vom Anfang der Quelldatei. Hinweis "IfKeyword" beginnt mit der Zählung an Position 12. Das liegt an dem Kommentar, der [0..10) umfasst und den Zeilenendezeichen, die [10..12) abdecken. Auch wenn es sich technisch gesehen nicht um Token handelt, enthält die Ausgabe der lexikalischen Analyse normalerweise Informationen zu Whitespace, einschließlich Kommentaren. Im .NET-Compiler wird Whitespace als Nebensächlichkeit der Syntax mit übertragen. 

Die zweite Phase des Compilers ist die Analyse/Zerlegung. Der Parser, der die Analyse/Zerlegung durchführt, arbeitet mit der syntaktischen Analyse Hand in Hand, um die Syntaxanalyse durchzuführen. Der Parser führt mit Abstand den größten Teil der Arbeit aus, fordert Token bei der lexikalischen Analyse an, während er das Eingabeprogramm auf Einhaltung der verschiedenen Grammatikregeln der Quellsprache hin überprüft. Beispielsweise kennen alle C#-Programmierer die Syntax einer IF-Anweisung:

if  (  condition  )  then-part  [ else-part ]

Das [ … ] steht für den optionalen ELSE-Teil. Der Parser setzt diese Regel durch das Zuordnen von Token und das Anwenden weiterer Regeln für die komplexeren Syntaxelemente, wie Bedingung und THEN-Teil, durch:

void if( )
{
  match(IfKeyword);
  match(OpenParenToken);
  condition();
  match(CloseParenToken);
  then_part();
  if (lookahead(ElseKeyword))
  else_part();
}

Die Funktion "match(T)" ruft die lexikalische Analyse auf, um das nächste Token abzurufen, und überprüft, ob dieses Token T entspricht. Die Kompilierung wird normalerweise fortgesetzt, wenn das der Fall ist. Andernfalls wird ein Syntaxfehler gemeldet. Die einfachsten Parser verwenden eine Zuordnungsfunktion, um bei einem Syntaxfehler eine Ausnahme auszugeben. Dadurch wird die Kompilierung effektiv angehalten. Hier ist eine solche Implementierung:

void match(SyntaxToken T)
{
  var next = lexer.NextToken();
  if (next == T)
  ;  // Keep going, all is well:
  else
  throw new SyntaxError(...);
}

Zum Glück für uns enthält der .NET-Compiler einen viel höher entwickelten Parser. Er kann die Arbeit auch bei groben Syntaxfehlern fortsetzen.

Unter der Annahme, dass es keine Syntaxfehler gab, hat die Eingangsseite ihre Arbeit im Wesentlichen abgeschlossen. Es verbleibt nur noch eine Aufgabe – das Ergebnis seiner Mühen an die Ausgangsseite zu übergeben. Die Form, in der dieses intern gespeichert wird, nennt man Zwischendarstellung (IR, Intermediate Representation). (Ungeachtet der ähnlichen Begrifflichkeit hat IR nichts mit der .NET Common Intermediate Language zu tun.) Der Parser im .NET-Compiler erstellt einen AST (Abstract Syntax Tree, abstrakte Syntaxstruktur) als IR und übergibt der Ausgangsseite diese Struktur.

Baumstrukturen stellen eine natürliche Form von IR dar, angesichts der hierarchischen Natur von C#- und Visual Basic-Programmen. Ein Programm enthält eine oder mehrere Klassen. Eine Klasse enthält Eigenschaften und Methoden, Eigenschaften und Methoden enthalten Anweisungen, Anweisungen enthalten oft Blöcke, und Blöcke enthalten weitere Anweisungen. Das Ziel eines AST besteht darin, das auf seiner syntaktischen Struktur basierende Programm darzustellen. Das "abstrakt" in AST weist auf die Abwesenheit von syntaktischem "Fleisch", wie ";" und "( )" hin. Betrachten Sie z. B. die folgende Sequenz von C#-Anweisungen (angenommen, sie werden ohne Fehler kompiliert):

sum = 0;
foreach (var x in A)   // A is an array:
  sum += x;
avg = sum / A.Length;

Auf einer hohen Ebene sieht der AST für dieses Codefragment dann wie Abbildung 3 aus.

Abbildung 3 Abstract Syntax Tree auf hoher Ebene für ein C#-Codefragment (aus Gründen der Einfachheit ohne Details)

Der AST erfasst die notwendigen Informationen zum Programm: die Anweisungen, die Reihenfolge der Anweisungen, die Teile jeder einzelnen Anweisung usw. Die nicht erforderliche Syntax wird verworfen, wie etwa alle Semikola. Das Schlüsselfeature, das es beim AST in Abbildung 3 zu verstehen gibt, ist, dass er die syntaktische Struktur des Programms erfasst.

Anders gesagt, dies ist die Weise, in der das Programm geschrieben ist, nicht die, in der es ausgeführt wird. Betrachten Sie die FOREACH-Anweisung, die bei der Iteration durch eine Symmlung null oder mehr Male eine Schleife durchläuft. Der AST erfasst die Bestandteile der FOREACH-Anweisung – die Schleifenvariable, die Sammlung und den Programmkörper. Was AST nicht transportiert, ist die Tatsache, dass FOREACH immer wieder wiederholt werden kann. Wenn Sie sich die Baumstruktur ansehen, gibt es keinen Pfeil, der anzeigt, wie FOREACH ausgeführt wird. Die einzige Möglichkeit, das zu wissen, besteht darin, zu wissen, dass das Schlüsselwort FOREACH == Schleife ist.

ASTs eignen sich bestens als IR, mit einem wichtigen Vorteil: Sie sind leicht zu erstellen und zu verstehen. Der Nachteil ist, dass höher entwickelte Analysen, wie diejenigen, die auf der Ausgangsseite des Compilers ausgeführt werden, auf einem AST schwieriger durchzuführen sind. Aus diesem Grund verwenden Compiler oft mehrere IRs, einschließlich einer gängigen Alternative zum AST. Diese Alternative ist der Kontrollflussgraph (CFG, Control Flow Graph), der ein Programm basierend auf dessen Kontrollfluss darstellt: Schleifen, IF-THEN-ELSE-Anweisungen, Ausnahmen usw. (Wir behandeln das in der nächsten Kolumne ausführlicher.)

Die beste Möglichkeit, die Verwendung des AST im .NET-Compiler kennenzulernen, bietet der Roslyn Syntax Visualizer. Dieser wird als Teil des Roslyn-SDKs installiert. Öffnen Sie nach der Installation ein beliebiges C#- oder Visual Basic-Programm in Visual Studio 2013, positionieren Sie den Cursor in der Quellcodezeile, die Sie interessiert, und öffnen Sie den Visualizer. Sie sehen das Menü "Ansicht", andere Fenster und den Roslyn Syntax Visualizer (siehe Abbildung 4).

Abbildung 4: Der Roslyn Syntax Visualizer in Visual Studio 2013

Betrachten Sie als konkretes Beispiel die IF-Anweisung, die wir weiter oben analysiert hatten:

 

// Comment
  if (score>100)
    grade = "A++";

Abbildung 5 zeigt das entsprechende AST-Fragment, das vom .NET-Compiler erstellt wird.

Abbildung 5 Abstrakte Syntaxstruktur, die vom .NET-Compiler für die IF-Anweisung generiert wird

Wie bei so vielem, sieht die Struktur im ersten Moment ein bisschen zu herausfordernd aus. Bedenken Sie jedoch zwei Dinge. Erstens ist die Struktur lediglich eine Erweiterung der früheren Quellanweisungen, sodass es eigentlich recht einfach ist, sich schrittweise durch die Struktur zu arbeiten und zu sehen, wie sie sich in der ursprünglichen Quelle abbildet. Zweitens ist der AST für den Gebrauch durch die Maschine bestimmt, nicht für Menschen. Im Allgemeinen ist der einzige Zeitpunkt, wann Menschen einen Blick auf den AST werfen, beim Debuggen von Parsern. Bedenken Sie außerdem, dass ein etwas vollständigerer Kurs zu Syntaxanalyse und Parsing weit mehr Platz erfordern würde, als wir hier zur Verfügung haben. Für alle, die tiefer in diese Übung eintauchen möchten, ist eine Vielzahl von Ressourcen verfügbar. Das Ziel hier war, die Oberfläche zu streifen, nicht mit einem Hechtsprung einzutauchen.

Zusammenfassung

Wir sind mit Roslyn in gar keiner Weise am Ende, also bleiben Sie dran. Wenn Sie sich näher mit Roslyn befassen möchten, empfehlen wir Ihnen, Roslyn zu installieren. Sehen Sie sich anschließend einen Teil der Dokumentation an, beginnend mit der Roslyn-CodePlex-Seite.

Wenn Sie mehr über Parsing und Lexing erfahren möchten, sehen Sie sich bei den vielen verfügbaren Büchern um. Da gibt es das alterwürdige "Dragon Book", auch bekannt als "Compilers: Principles, Techniques & Tools" (Addison Wesley, 2006). Wenn Sie sich für einen stärker auf .NET konzentrierten Ansatz interessieren, ziehen Sie "Compiling for the .NET Common Language Runtime (CLR)" von by John Gough (Prentice Hall, 2001) oder Ronald Maks "Writing Compilers and Interpeters: A Software Engineering Approach" (Wiley, 2009) in die engere Wahl. Viel Spaß beim Programmieren!

---

Joe Hummel ist forschender Privatdozent an der University of Illinois, Chicago, Autor von Inhalten für Pluralsight.com, MVP in Visual C++ MVP und privater Berater. Er hat einen Ph.D. der UC Irvine auf dem gebiet des Hochleistungscomputings und ist an Allem interessiert, was damit zu tun hat. Er wohnt in der Umgebung von Chicago, und wenn er nicht segelt, ist er zu erreichen unter joe@joehummel.net.

Ted Neward ist CTO bei iTrellis, einer Beratungsfirma. Er hat mehr als 100 Artikel geschrieben und als Autor ein Dutzend Bücher verfasst, darunter "Professional F# 2.0" (Wrox 2010). Er ist ein F#-MVP und spricht auf Konferenzen in der ganzen Welt. Er berät und hilft regelmäßig. Bei Interesse erreichen Sie Ihn unter ted@tedneward.com oder ted@itrellis.com.

Unser Dank gilt dem folgenden technischen Experten von Microsoft für die Durchsicht dieses Artikels: Dustin Campbell