Πώς να γράψετε έναν μεταγλωττιστή στο Go: ένας γρήγορος οδηγός

Οι μεταγλωττιστές είναι φοβεροί! ; ; ; Συνδυάζουν τη θεωρία και την εφαρμογή και αγγίζουν πολλά θέματα που σχετίζονται με το λογισμικό, όπως η ανάλυση και η κατασκευή γλωσσών. Στον πυρήνα τους, οι μεταγλωττιστές είναι ένα πρόγραμμα που κάνει ένα πρόγραμμα αναγνώσιμο από τον υπολογιστή.

Η έμπνευση για αυτό βγήκε από ένα πρόγραμμα μεταγλωττιστών που πήρα αυτό το παρελθόν Φθινόπωρο και την αγάπη μου για τον Go

Αυτός είναι ο οδηγός που εύχομαι να είχα όταν ξεκινούσα το ταξίδι μου σε μεταγλωττιστές. Υπάρχουν πολλά βιβλία, βίντεο και σεμινάρια σχετικά με τον τρόπο δημιουργίας μεταγλωττιστών. Ο στόχος αυτής της ανάρτησης είναι να επιτύχει μια ισορροπία μεταξύ της παροχής ενός μη ασήμαντου παραδείγματος για ορισμένα από τα πράγματα που μπορεί να κάνει ένας μεταγλωττιστής, αποφεύγοντας να κολλήσετε στα ζιζάνια. ;

Το αποτέλεσμα θα είναι ένας μεταγλωττιστής που μπορεί να εκτελέσει μια μικρή γλώσσα. Για την ολοκλήρωση της αγοράς και την εκτέλεση του τελικού έργου, δείτε τις παρακάτω οδηγίες. ;

Σημείωση: Να θυμάστε ότι το Go είναι αυστηρό σχετικά με τις απόλυτες διαδρομές όταν το εκτελείτε

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

Περίγραμμα του μεταγλωττιστή

  • Lexer / Parser
  • Γεννήτρια AST
  • Τύπος Checker
  • Δημιουργία κώδικα

Η γλώσσα

Ο στόχος αυτής της ανάρτησης είναι να σας εξοικειώσει με τους μεταγλωττιστές όσο το δυνατόν γρηγορότερα, ώστε να διατηρήσουμε τη γλώσσα απλή. Για τύποι θα συνεργαστεί με strings, integersκαι bools. Θα έχει καταστάσεων που περιλαμβάνουν func, if, else, let, και return. Αυτό θα πρέπει να είναι αρκετό για να διασκεδάσετε δουλεύοντας με μερικές από τις πολυπλοκότητες ενός μεταγλωττιστή.

Ο πρώτος μεταγλωττιστής που δημιούργησα, ολοκλήρωσα μέσα σε δύο μήνες και πήρα χιλιάδες γραμμές κώδικα. Πήρα μερικές συντομεύσεις σε αυτήν την ανάρτηση για να σας δείξω τις βασικές αρχές.

Δύο κοινά στοιχεία που λείπουν η γλώσσα μας είναι classesκαι arrays. Αυτά προσθέτουν πρόσθετες επιπλοκές που δεν έχουμε χρόνο αυτήν τη στιγμή. Εάν αποδειχθεί ότι οι άνθρωποι θέλουν πραγματικά να μάθουν πώς να χειριστούν αυτά τα στοιχεία, θα γράψω μια συνέχεια.

Κάποιο παράδειγμα κώδικα:

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);

Γρήγορη εγκατάσταση

Το μόνο εξωτερικό πακέτο που χρειαζόμαστε είναι gocc, το οποίο θα βοηθήσει στην κατασκευή του lexer και του parser.

Για να το εκτελέσετε:

go get github.com/goccmack/gocc

Βεβαιωθείτε ότι ο φάκελος του κάδου όπου βρίσκεται το gocc βρίσκεται στο PATH:

export PATH=$GOPATH/bin:$PATH

Σημείωση: Εάν αντιμετωπίζετε προβλήματα σε αυτό το στάδιο, δοκιμάστε να εκτελέσετε go envγια να βεβαιωθείτε ότι έχετε $GOROOTκαι $GOPATHέχει εκχωρηθεί σωστά.

Ωραία, ας δούμε έναν κώδικα.

Κατασκευάζοντας το Lexer

Η δουλειά του lexer είναι να διαβάσει το πρόγραμμα και να εξάγει μια ροή διακριτικών που καταναλώνονται από τον αναλυτή. Καθένα Tokenπεριέχει typeαυτό που αντιπροσωπεύει το διακριτικό στη γλώσσα και τη συμβολοσειρά αυτού Literalτου διακριτικού.

Για να προσδιορίσουμε τα κομμάτια του προγράμματος θα χρησιμοποιούμε κανονικές εκφράσεις. Στη συνέχεια, το gocc θα μετατρέψει αυτές τις κανονικές εκφράσεις σε DFA ( Deterministic Finite Automata ) που μπορεί θεωρητικά να εκτελεστεί σε γραμμικό χρόνο.

Η σημείωση που θα χρησιμοποιήσουμε είναι η BNF ( φόρμα Backus – Naur ). Μην το συγχέετε με EBNF ( εκτεταμένη μορφή Backus – Naur ) ή ABNF ( επαυξημένη μορφή Backus – Naur ) που έχουν κάποια πρόσθετα χαρακτηριστικά. Λάβετε υπόψη αυτό κατά την εξέταση άλλων παραδειγμάτων στο διαδίκτυο που θα μπορούσαν να χρησιμοποιούν άλλες μορφές που παρέχουν περισσότερη συντακτική ζάχαρη.

Ας ξεκινήσουμε με τα βασικά και ορίστε πώς stringsκαι πώς integersθα μοιάζει.

Σημειώστε ότι:

  • Όλα τα ονόματα των διακριτικών πρέπει να είναι πεζά
  • Οποιοδήποτε κλειδί προηγείται «!» θα αγνοηθεί
  • Οποιοδήποτε κλειδί προηγείται του «_» δεν θα μετατραπεί σε διακριτικό
  • Οποιαδήποτε έκφραση που περικλείεται από το "{" expression"}" μπορεί να επαναληφθεί 0 ή περισσότερες φορές

Στο παρακάτω παράδειγμα αγνοούμε όλο το κενό διάστημα και έχουμε ορίσει ένα intκαι string_literaltoken.

Κάθε γλώσσα έχει ενσωματωθεί σε keywordsδεσμευμένες λέξεις που προσφέρουν ειδική λειτουργικότητα. Όμως, πώς θα ξέρει ο lexer εάν δημιουργήθηκε stringa keywordή χρήστης identifier; Αντιμετωπίζει αυτό δίνοντας προτεραιότητα στη σειρά με την οποία ορίζονται τα διακριτικά. Επομένως, ας ορίσουμε το keywordsεπόμενο.

Θα το ολοκληρώσουμε προσθέτοντας τα σημεία στίξης που είναι απαραίτητα για τις εκφράσεις.

Δροσερός! Ας δούμε αν αυτό κάνει ό, τι θέλουμε με κάποιες δοκιμές μονάδας . Μη διστάσετε να επικολλήσετε αυτό το μέρος στο IDE σας. ;

Σημείωση: Είναι γενικά καλή πρακτική στο Go να τοποθετείτε δοκιμαστικά αρχεία στον σχετικό υποκατάλογο, αλλά για απλότητα τοποθετώ όλες τις δοκιμές στη ρίζα.

Για να δοκιμάσετε την εκτέλεση του σαρωτή μας :

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

Τέλεια, έχουμε τώρα δουλειά Lexer;

Δημιουργία του Parser

Η οικοδόμηση του Parserείναι παρόμοια με το πώς χτίσαμε το Lexer. Θα φτιάξουμε ένα σύνολο ακολουθιών στοιχείων που όταν ταιριάζουν σωστά με μια ροή διακριτικών παράγουν μια γραμματική. Αυτό θα τρέξει επίσης σε γραμμικό χρόνο μετατρέποντας εσωτερικά τη γραμματική NFA ( Non-Deterministic Automaton ) σε DFA ( Deterministic Finite Automaton ).

Ας κρατήσουμε τα πράγματα απλά. Τι είναι το πρόγραμμά μας; Λοιπόν, είναι ένα σωρό Statementsστο οποίο το καθένα Statementμπορεί να περιέχει ένα σύνολο Statementsή / και Expressions. Αυτό φαίνεται σαν ένα καλό μέρος για να ξεκινήσουμε τη γραμματική μας.

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.

Αντίθετα, ένα AST περιέχει μόνο τις πληροφορίες που σχετίζονται με τον έλεγχο τύπου και τη δημιουργία κώδικα και παραλείπει οποιοδήποτε άλλο επιπλέον περιεχόμενο που χρησιμοποιείται κατά την ανάλυση του κειμένου.

Μην ανησυχείτε αν αυτός ο ορισμός δεν έχει νόημα αυτήν τη στιγμή. Πάντα μαθαίνω καλύτερα με την κωδικοποίηση, οπότε ας περάσουμε σε αυτό!

Δημιουργήστε έναν νέο κατάλογο και δύο νέα αρχεία. ast.goθα περιέχει τις λειτουργίες δημιουργίας AST και types.goθα έχει τους τύπους κόμβων δέντρων .

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.

Για να βρείτε κάποια δοκιμαστικά προγράμματα για να μεταβείτε στη διεύθυνση github.com/Lebonesco/go-compiler/examples.

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

Και εκεί το έχετε! Έχουμε ολοκληρώσει έναν πλήρως επεξεργαστή στο Go!

Σας ευχαριστούμε που αφιερώσατε χρόνο για να διαβάσετε αυτό το άρθρο.

Εάν το θεωρήσατε χρήσιμο ή ενδιαφέρον, ενημερώστε με ???