Kaleidoscope: Implementing a Parser and AST

Welcome to Chapter 2 of the "Implementing a language with LLVM" tutorial. This chapter shows you how to use the lexer, built in @@ -61,10 +61,10 @@ Tree.

The Abstract Syntax Tree (AST)

The AST for a program captures its behavior in such a way that it is easy for later stages of the compiler (e.g. code generation) to interpret. We basically @@ -84,7 +84,7 @@ public: class NumberExprAST : public ExprAST { double Val; public: - explicit NumberExprAST(double val) : Val(val) {} + NumberExprAST(double val) : Val(val) {} };

@@ -107,7 +107,7 @@ in the basic form of the Kaleidoscope language: class VariableExprAST : public ExprAST { std::string Name; public: - explicit VariableExprAST(const std::string &name) : Name(name) {} + VariableExprAST(const std::string &name) : Name(name) {} }; /// BinaryExprAST - Expression class for a binary operator. @@ -178,10 +178,10 @@ bodies in Kaleidoscope.

Parser Basics

Now that we have an AST to build, we need to define the parser code to build it. The idea here is that we want to parse something like "x+y" (which is @@ -239,11 +239,10 @@ piece of our grammar: numeric literals.

Basic Expression - Parsing

Basic Expression Parsing

We start with numeric literals, because they are the simplest to process. For each production in our grammar, we'll define a function which parses that @@ -333,9 +332,9 @@ static ExprAST *ParseIdentifierExpr() { ExprAST *Arg = ParseExpression(); if (!Arg) return 0; Args.push_back(Arg); - + if (CurTok == ')') break; - + if (CurTok != ',') return Error("Expected ')' or ',' in argument list"); getNextToken(); @@ -394,11 +393,10 @@ They are a bit more complex.

Binary Expression - Parsing

Binary Expression Parsing

Binary expressions are significantly harder to parse because they are often ambiguous. For example, when given the string "x+y*z", the parser can choose @@ -617,10 +615,10 @@ handle function definitions, etc.

Parsing the Rest

The next thing missing is handling of function prototypes. In Kaleidoscope, @@ -714,10 +712,10 @@ actually execute this code we've built!

The Driver

The driver for this simply invokes all of the parsing pieces with a top-level dispatch loop. There isn't much interesting here, so I'll just include the @@ -753,10 +751,10 @@ type "4+5;", and the parser will know you are done.

Conclusions

With just under 400 lines of commented code (240 lines of non-comment, non-blank code), we fully defined our minimal language, including a lexer, @@ -790,10 +788,10 @@ Representation (IR) from the AST.

Full Code Listing

Here is the complete code listing for this and the previous chapter. @@ -803,10 +801,10 @@ course.) To build this, just compile with:

-   # Compile
-   g++ -g -O3 toy.cpp 
-   # Run
-   ./a.out 
+# Compile
+clang++ -g -O3 toy.cpp
+# Run
+./a.out

@@ -833,7 +831,7 @@ enum Token { tok_def = -2, tok_extern = -3, // primary - tok_identifier = -4, tok_number = -5, + tok_identifier = -4, tok_number = -5 }; static std::string IdentifierStr; // Filled in if tok_identifier @@ -901,14 +899,14 @@ public: class NumberExprAST : public ExprAST { double Val; public: - explicit NumberExprAST(double val) : Val(val) {} + NumberExprAST(double val) : Val(val) {} }; /// VariableExprAST - Expression class for referencing a variable, like "a". class VariableExprAST : public ExprAST { std::string Name; public: - explicit VariableExprAST(const std::string &name) : Name(name) {} + VariableExprAST(const std::string &name) : Name(name) {} }; /// BinaryExprAST - Expression class for a binary operator. @@ -1004,9 +1002,9 @@ static ExprAST *ParseIdentifierExpr() { ExprAST *Arg = ParseExpression(); if (!Arg) return 0; Args.push_back(Arg); - + if (CurTok == ')') break; - + if (CurTok != ',') return Error("Expected ')' or ',' in argument list"); getNextToken(); @@ -1150,7 +1148,7 @@ static PrototypeAST *ParseExtern() { //===----------------------------------------------------------------------===// static void HandleDefinition() { - if (FunctionAST *F = ParseDefinition()) { + if (ParseDefinition()) { fprintf(stderr, "Parsed a function definition.\n"); } else { // Skip token for error recovery. @@ -1159,7 +1157,7 @@ static void HandleDefinition() { } static void HandleExtern() { - if (PrototypeAST *P = ParseExtern()) { + if (ParseExtern()) { fprintf(stderr, "Parsed an extern\n"); } else { // Skip token for error recovery. @@ -1169,7 +1167,7 @@ static void HandleExtern() { static void HandleTopLevelExpression() { // Evaluate a top-level expression into an anonymous function. - if (FunctionAST *F = ParseTopLevelExpr()) { + if (ParseTopLevelExpr()) { fprintf(stderr, "Parsed a top-level expr\n"); } else { // Skip token for error recovery. @@ -1207,7 +1205,9 @@ int main() { fprintf(stderr, "ready> "); getNextToken(); + // Run the main "interpreter loop" now. MainLoop(); + return 0; } @@ -1224,8 +1224,8 @@ int main() { src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"> Chris Lattner
- The LLVM Compiler Infrastructure
- Last modified: $Date: 2007-10-17 11:05:13 -0700 (Wed, 17 Oct 2007) $ + The LLVM Compiler Infrastructure
+ Last modified: $Date$