So schreiben Sie einen Compiler in Go: eine Kurzanleitung

Compiler sind großartig! ? ? ? Sie kombinieren Theorie und Anwendung und berühren viele softwarebezogene Themen wie Parsen und Sprachkonstruktion. Compiler sind im Kern ein Programm, das ein Programm für den Computer lesbar macht.

Die Inspiration dafür kam von einem Compilerkurs, den ich im vergangenen Herbst absolviert habe, und meiner Liebe zu Go.

Dies ist der Leitfaden, den ich mir wünschte, als ich meine Reise zu Compilern begann. Es gibt viele Bücher, Videos und Tutorials zum Erstellen von Compilern. Das Ziel dieses Beitrags ist es, ein Gleichgewicht zwischen der Bereitstellung eines nicht trivialen Beispiels für einige der Dinge zu finden, die ein Compiler tun kann, ohne im Unkraut stecken zu bleiben. ?

Das Ergebnis ist ein Compiler, der eine kleine erfundene Sprache ausführen kann. Informationen zum Auschecken und Ausführen des endgültigen Projekts finden Sie in den folgenden Anweisungen. ?

Hinweis: Denken Sie daran, dass Go beim Ausführen dieses Vorgangs strenge Angaben zu absoluten Pfaden macht

cd $GOPATH/src/github.com/Lebonescogit clone //github.com/Lebonesco/go-compiler.gitcd go-compilergo test -vgo run main.go ./examples/math.bx

Gliederung des Compilers

  • Lexer / Parser
  • AST-Generator
  • Typprüfung
  • Codegenerierung

Die Sprache

Ziel dieses Beitrags ist es, Sie so schnell wie möglich mit Compilern vertraut zu machen, damit die Sprache einfach bleibt. Für Typen werden mit denen wir arbeiten strings, integersund bools. Es müssen Aussagen , die einschließen func, if, else, let, und return. Dies sollte ausreichen, um Spaß an der Arbeit mit einigen der Komplexitäten eines Compilers zu haben.

Den ersten Compiler, den ich erstellt habe, habe ich innerhalb von zwei Monaten fertiggestellt und Tausende von Codezeilen belegt. Ich habe in diesem Beitrag einige Verknüpfungen verwendet, um Ihnen die wichtigsten Grundlagen zu zeigen.

Zwei gemeinsame Komponenten, die unserer Sprache fehlen, sind classesund arrays. Dies führt zu zusätzlichen Komplikationen, für die wir derzeit keine Zeit haben. Wenn sich herausstellt, dass die Leute wirklich wissen wollen, wie sie mit diesen Elementen umgehen sollen, schreibe ich ein Follow-up.

Ein Beispielcode:

func add(a Int, b int) Int { return a + b;}
func hello(name String) String { return "hello:" + " " + name;}
let num = add(1, 2);let phrase = string hello("Jeff");let i = int 0;let result = "";
if (i == 2) { result = hello("cat");} else { result = hello("dog");}
PRINT(result);

Schnelleinrichtung

Das einzige außerhalb Paket , das wir brauchen ist gocc, welche Build die Lexer und Parser helfen.

Um es zum Laufen zu bringen:

go get github.com/goccmack/gocc

Stellen Sie sicher, dass sich der Ordner bin, in dem sich gocc befindet, in Ihrem Ordner befindet PATH:

export PATH=$GOPATH/bin:$PATH

Hinweis: Wenn Sie zu diesem Zeitpunkt Probleme haben, versuchen Sie auszuführen go env, um sicherzustellen, dass Ihre $GOROOTund $GOPATHkorrekt zugewiesen sind.

Cool, lass uns in einen Code eintauchen.

Den Lexer bauen

Die Aufgabe des Lexers besteht darin, das Programm zu lesen und einen Strom von Token auszugeben, die vom Parser verbraucht werden. Jedes Tokenenthält das type, was das Token in der Sprache darstellt, und die Zeichenfolge Literaldieses Tokens.

Um die Teile des Programms zu identifizieren, werden wir reguläre Ausdrücke verwenden. gocc konvertiert diese regulären Ausdrücke dann in ein DFA ( Deterministic Finite Automata ), das theoretisch in linearer Zeit ausgeführt werden kann.

Die Notation, die wir verwenden werden, ist BNF ( Backus-Naur-Form ). Verwechseln Sie dies nicht mit EBNF ( erweiterte Backus-Naur-Form ) oder ABNF ( erweiterte Backus-Naur-Form ), die einige zusätzliche Funktionen aufweisen. Denken Sie daran, wenn Sie sich andere Beispiele online ansehen, die andere Formen verwenden könnten, die mehr syntaktischen Zucker liefern.

Beginnen wir mit den Grundlagen und definieren, wie stringsund integerswie sie aussehen werden.

Beachten Sie, dass:

  • Alle Token-Namen müssen in Kleinbuchstaben geschrieben werden
  • Jeder Schlüssel mit vorangestelltem '!' wird ignoriert
  • Ein Schlüssel, dem '_' vorangestellt ist, wird nicht in ein Token umgewandelt
  • Jeder von '{' expression'}' eingeschlossene Ausdruck kann 0 oder mehrmals wiederholt werden

Im folgenden Beispiel ignorieren wir alle Leerzeichen und haben ein intund definiert string_literaltoken.

In jede Sprache keywordssind reservierte Wörter eingebaut , die besondere Funktionen bieten. Aber woher weiß der Lexer, ob a stringein keywordoder ein Benutzer erstellt wurde identifier? Dabei wird die Reihenfolge bevorzugt, in der Token definiert werden. Definieren wir daher als keywordsnächstes.

Zum Abschluss fügen wir die für Ausdrücke erforderliche Interpunktion hinzu.

Cool! Mal sehen, ob dies mit einigen Unit-Tests tatsächlich das tut, was wir wollen . Fühlen Sie sich frei, diesen Teil einfach in Ihre IDE einzufügen. ?

Hinweis: In Go ist es im Allgemeinen eine gute Praxis, Testdateien im entsprechenden Unterverzeichnis abzulegen. Der Einfachheit halber platziere ich alle Tests im Stammverzeichnis.

So testen Sie unseren Scannerlauf :

$ gocc grammer.bnf$ go test -v=== RUN TestToken--- PASS: TestToken (0.00s)PASSok github.com/Lebonesco/compiler 0.364s

Großartig, wir haben jetzt eine Arbeit Lexer?

Parser erstellen

Das Bauen Parserist ähnlich wie das Bauen Lexer. Wir werden eine Reihe von Elementsequenzen erstellen, die bei korrekter Übereinstimmung mit einem Token-Stream eine Grammatik erzeugen. Dies wird auch in linearer Zeit ausgeführt, indem unsere NFA - Grammatik ( Non-Deterministic Automaton ) intern in DFA ( Deterministic Finite Automaton ) konvertiert wird .

Lassen Sie uns die Dinge einfach halten. Was ist eigentlich unser Programm? Nun, es ist eine Reihe von, Statementsin denen jeder Statementeine Reihe von Statementsund / oder enthalten kann Expressions. Dies scheint ein guter Ort zu sein, um unsere Grammatik zu beginnen.

Below is the beginning recursive hierarchy of the program. Statements is a sequence of zero or more Statements and Functions is a list of functions. Our languages requires functions to be defined before other Statement types. This will reduce some headache during the type checking phase. empty is a keyword in BNF that represents an empty space.

But wait! What is a Statement? It’s a unit of code that doesn’t return a value. This includes: if, let, and return statements. This is opposed to Expressions which do return values. We will get to those next.

Below is our grammar for Statement and Function. A StatementBlock is a larger abstraction that encapsulates a list of Statements with braces {}.

Next lets build out our Expression which handles all infix operations such as +, -, *, <, >, ==, and, and or.

Almost done with a fully working grammar! Let’s wrap things up by defining our parameter insertion. Each function can accept any amount of values. When defining a function we need to label the argument types in the signature while a called function can accept any amount of Expressions.

Now that our parser is completed let’s add some code to our driver, main.go.

As we progress through the compiler we will add more functionality to this driver.

One of the things challenging about building a parser is that there’re many different ways to define the grammar. ?

We won’t really know how well we did until we get into the next section which uses the output we just generated. The difficulty of building the static type checker will be strongly influenced by our grammar design. Keep your fingers crossed ?.

Test Parser

We’ll keep this simple because at this point our parser can still produce false positives. Once we start working on the AST we can check its accuracy.

go test -v=== RUN TestParser--- PASS: TestParser (0.00s)=== RUN TestToken--- PASS: TestToken (0.00s)PASSok github.com/Lebonesco/go-compiler 7.295s

Congrats ? ? ?! You now have a fully working Lexer and Parser. Time to move onto the AST (Abstract Syntax Tree).

Abstract Syntax Tree

The best way to understand an abstract syntax tree is in relation to a parse tree which is what we generated in the last post. A parse tree represents each part of the program that is matched in our grammar.

Im Gegensatz dazu enthält ein AST nur die Informationen zur Typprüfung und Codegenerierung und überspringt alle anderen zusätzlichen Inhalte, die beim Parsen des Texts verwendet werden.

Machen Sie sich keine Sorgen, wenn diese Definition derzeit keinen Sinn ergibt. Ich lerne immer am besten, indem ich tatsächlich codiere, also lasst uns hineinspringen!

Erstellen Sie ein neues Verzeichnis und zwei neue Dateien. ast.goenthält unsere AST-Generierungsfunktionen und verfügt types.goüber die Baumknotentypen .

mkdir astcd asttouch ast.gotouch types.go

Like with the parse tree, we will define our structure from top to bottom. Every node will either be a Statement or Expression. Go isn’t object oriented so we’ll use a composition pattern utilizing interface and struct to represent our node categories. Our AST will return a Program node that contains the rest of the program. From now on, any struct we created with a TokenLiteral() method is a node. If that node has a statementNode() method it will fit the Statement interface and if it has a expressionNode() method it’s an Expression.

In addition, we’ll be adding json tags to each struct field to make it easier when we convert our AST into json for testing purposes.

Now let’s start building our Statement structs based off of the Statement and Node interfaces.

Note:json:"-" means that the field will be omitted from our json.

Next we need some hooks to connect our nodes and parser. The code below allows our Statement nodes to fit the Node and Statement interfaces.

We then need the hooks that will be called by the parser.

As you can see, most of our code is checking and casting our input type.

These hooks will then be called by the parser in grammar.bnf. To access these functions we’ll need to import "github.com/Lebonesco/go-compiler/ast.

Now when a piece of grammar is identified, it calls an AST hook and passes in the necessary data to construct a node.

As you could imagine, there is a lot of flexibility in how you want to generate your AST. There are design strategies that reduce the amount of unique nodes in the AST . However, having more node types will make your life easier when we get to the typechecker and code generation. ?

This part has a lot of code. However, it’s not very difficult and mostly all the same. The error handling in Go can feel a bit tedious, but in the long run it’ll be worth it when we make a silly mistake. Safety First ?

We’re not going to do anything too crazy with our error handling because I want to save on lines of code. However, if you feel so inclined you can add more descriptive and useful errors.

Let’s move on to Expressions!

Fit them into the Node and Expression interfaces.

And create the Expression hooks.

Finally, insert the hooks into the parser.

Test AST Generator

The test cases for the AST generator are the most tedious to write. But trust me, this is not a part you want to mess up on. If you have problems here, those bugs will rollover into your type checker and code generator. ?

In my opinion, if code doesn’t have tests it’s broken

In our AST test we will construct what our final result should look like. To avoid comparing elements such as tokens, that could create false negatives, we convert our result and expected output into json before comparing with a deep comparison function, reflect.DeepEqual().

Run Test:

go test -v=== RUN TestAST--- PASS: TestAST (0.00s)=== RUN TestParser--- PASS: TestParser (0.00s)=== RUN TestToken--- PASS: TestToken (0.00s)PASSok github.com/Lebonesco/go-compiler 9.020s

Half way to a working compiler! ? While you give this post some ? ? ? don’t forget to give yourself a hand for making it this far.

Let’s add some more code to the driver.

Now onto my favorite part, the Type Checker.

Type Checker

Our type checker will make sure that users don’t write code that conflicts with our statically typed language.

The core backbone of our type checker will be a combination of data structures that track identifier types, initialization, and valid type operations. This can get vastly more complicated once we start dealing with different levels of scope and classes. However, we’re keeping it as simple as possible. ?

To start:

touch checker_test.gomkdir checkercd checkertouch checker.gotouch environment.go

environment.go will contain all of our helper functions that will be used by our checker and code generator to access and manipulate our set of variables and corresponding types. Our environment is simple so this will be straight forward.

We’ll begin by setting all of our constant values including operation types, variable types, and mapping of each type to its valid methods.

Note: If we had classes in our language our checker would handle this third part rather than us doing it by hand.

The rest of environment.go are basic getters and setters that handle identifiers and functions.

The foundation of our type checker will be a single dispatch function, checker(), that takes in a Node and fires the corresponding checker function

I felt like saving lines of code so we’ll be using a global environment to store our variable types.

Note: This wouldn’t be possible if we allowed Block Statements and Functions to have their own scope or if we were abiding by best practices.

Now eval Statements. Block Statements are the only statement in which we return a type in order to handle the case when it is inside a function. If there is a Return Statement inside the Block Statement its type is returned. Otherwise, the Nothing_Type is returned.

Onto evaluating Expressions. The most complicated part will be evalFunctionCall() because it could either be a built in function such as PRINT() or user defined.

Note: Currently, there is only one builtin function. However, more could be easily added given the framework that we’ve built.

Awesome! Let’s add a small snippet to our driver.

Test Type Checker

go test -v=== RUN TestAST--- PASS: TestAST (0.00s)=== RUN TestOperations--- PASS: TestOperations (0.00s)=== RUN TestIdents--- PASS: TestIdents (0.00s)=== RUN TestFunctions--- PASS: TestFunctions (0.00s)=== RUN TestParser--- PASS: TestParser (0.00s)=== RUN TestToken--- PASS: TestToken (0.00s)PASSok github.com/Lebonesco/go-compiler 9.020s

I made some deliberate choices to leave things out of this language such as classes, for loops, and function scope. Most of the complexities that arise from these occur in the checker and code generator. If I added those elements this post would be a lot lot longer. ?

Code Generation

We have finally made it to the last stage! ? ? ?

In order to handle the most cases with the least amount of hassle every expression will be assigned to a temporary variable. It might make our generated code look bloated, but it will solve for any nested expressions.

Bloated code won’t have any impact on final program speed because the optimizer will remove any redundancy when we compile our final generated C++ code.

Our generator will look similar to the type checker. The main difference is that we’ll be passing down a buffer to store the generated code.

While I chose to compile into C++, you can substitute in any language . The main purpose of this Go Compiler Guide was to enable you to be able to understand the pieces well enough to go out and create your own.

To start:

touch gen_test.gomkdir gencd gentouch gen.go

We’ll begin by importing all of the necessary packages and defining three utility functions, write() to write generated code to a buffer, check()to do error handling, and freshTemp()to generate unique variable names for temporary variables we create on the fly.

Note: It’s generally bad practice to use panic()for normal error handling in Go, but I’m tired of writing if statements.

Similar to the checker, our generator has a core dispatch function that accepts a Node and calls the corresponding gen function.

Let’s generate some Statements. genProgram() generates necessary headers and main() function.

Generating Expressions will look very similar to the code above. The main difference is that a temp variable is returned representing that expression. This helps us handle more complex Expression nesting.

The final piece of code will be our C++ Builtin types. Without this nothing will work.

Test Code Generator

Bringing It All Together

We’re now going to combine our lexer, parser, AST generator, type checker, and code generator into a final runnable program, main.go.

Note: I’m running this on a Windows so my C++ compiles into main.exe. If this doesn’t work for you remove the .exe extension.

To find some test programs to run go to github.com/Lebonesco/go-compiler/examples.

go run main.go ./example/function.bxhello Jeff3

And there you have it! We have completed a fully working compiler in Go!

Thank you for taking the time to read this article.

If you found it helpful or interesting please let me know ???.