examples/Kaleidoscope/Chapter2/toy.cpp

   1 #include <cctype>
   2 #include <cstdio>
   3 #include <cstdlib>
   4 #include <map>
   5 #include <string>
   6 #include <vector>
   7
   8 //===----------------------------------------------------------------------===//
   9 // Lexer
  10 //===----------------------------------------------------------------------===//
  11
  12 // The lexer returns tokens [0-255] if it is an unknown character, otherwise one
  13 // of these for known things.
  14 enum Token {
  15   tok_eof = -1,
  16
  17   // commands
  18   tok_def = -2, tok_extern = -3,
  19
  20   // primary
  21   tok_identifier = -4, tok_number = -5
  22 };
  23
  24 static std::string IdentifierStr;  // Filled in if tok_identifier
  25 static double NumVal;              // Filled in if tok_number
  26
  27 /// gettok - Return the next token from standard input.
  28 static int gettok() {
  29   static int LastChar = ' ';
  30
  31   // Skip any whitespace.
  32   while (isspace(LastChar))
  33     LastChar = getchar();
  34
  35   if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]*
  36     IdentifierStr = LastChar;
  37     while (isalnum((LastChar = getchar())))
  38       IdentifierStr += LastChar;
  39
  40     if (IdentifierStr == "def") return tok_def;
  41     if (IdentifierStr == "extern") return tok_extern;
  42     return tok_identifier;
  43   }
  44
  45   if (isdigit(LastChar) || LastChar == '.') {   // Number: [0-9.]+
  46     std::string NumStr;
  47     do {
  48       NumStr += LastChar;
  49       LastChar = getchar();
  50     } while (isdigit(LastChar) || LastChar == '.');
  51
  52     NumVal = strtod(NumStr.c_str(), 0);
  53     return tok_number;
  54   }
  55
  56   if (LastChar == '#') {
  57     // Comment until end of line.
  58     do LastChar = getchar();
  59     while (LastChar != EOF && LastChar != '\n' && LastChar != '\r');
  60
  61     if (LastChar != EOF)
  62       return gettok();
  63   }
  64
  65   // Check for end of file.  Don't eat the EOF.
  66   if (LastChar == EOF)
  67     return tok_eof;
  68
  69   // Otherwise, just return the character as its ascii value.
  70   int ThisChar = LastChar;
  71   LastChar = getchar();
  72   return ThisChar;
  73 }
  74
  75 //===----------------------------------------------------------------------===//
  76 // Abstract Syntax Tree (aka Parse Tree)
  77 //===----------------------------------------------------------------------===//
  78
  79 /// ExprAST - Base class for all expression nodes.
  80 class ExprAST {
  81 public:
  82   virtual ~ExprAST();
  83 };
  84
  85 /// NumberExprAST - Expression class for numeric literals like "1.0".
  86 class NumberExprAST : public ExprAST {
  87 public:
  88   NumberExprAST(double val) {}
  89   virtual ~NumberExprAST();
  90 };
  91
  92 /// VariableExprAST - Expression class for referencing a variable, like "a".
  93 class VariableExprAST : public ExprAST {
  94   std::string Name;
  95 public:
  96   VariableExprAST(const std::string &name) : Name(name) {}
  97   virtual ~VariableExprAST();
  98 };
  99
 100 /// BinaryExprAST - Expression class for a binary operator.
 101 class BinaryExprAST : public ExprAST {
 102 public:
 103   BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs) {}
 104   virtual ~BinaryExprAST();
 105 };
 106
 107 /// CallExprAST - Expression class for function calls.
 108 class CallExprAST : public ExprAST {
 109   std::string Callee;
 110   std::vector<ExprAST*> Args;
 111 public:
 112   CallExprAST(const std::string &callee, std::vector<ExprAST*> &args)
 113     : Callee(callee), Args(args) {}
 114   virtual ~CallExprAST();
 115 };
 116
 117 // Provide out-of-line definitions to prevent weak vtables.
 118 ExprAST::~ExprAST() {}
 119 NumberExprAST::~NumberExprAST() {}
 120 VariableExprAST::~VariableExprAST() {}
 121 BinaryExprAST::~BinaryExprAST() {}
 122 CallExprAST::~CallExprAST() {}
 123
 124 /// PrototypeAST - This class represents the "prototype" for a function,
 125 /// which captures its name, and its argument names (thus implicitly the number
 126 /// of arguments the function takes).
 127 class PrototypeAST {
 128   std::string Name;
 129   std::vector<std::string> Args;
 130 public:
 131   PrototypeAST(const std::string &name, const std::vector<std::string> &args)
 132     : Name(name), Args(args) {}
 133
 134 };
 135
 136 /// FunctionAST - This class represents a function definition itself.
 137 class FunctionAST {
 138 public:
 139   FunctionAST(PrototypeAST *proto, ExprAST *body) {}
 140 };
 141
 142 //===----------------------------------------------------------------------===//
 143 // Parser
 144 //===----------------------------------------------------------------------===//
 145
 146 /// CurTok/getNextToken - Provide a simple token buffer.  CurTok is the current
 147 /// token the parser is looking at.  getNextToken reads another token from the
 148 /// lexer and updates CurTok with its results.
 149 static int CurTok;
 150 static int getNextToken() {
 151   return CurTok = gettok();
 152 }
 153
 154 /// BinopPrecedence - This holds the precedence for each binary operator that is
 155 /// defined.
 156 static std::map<char, int> BinopPrecedence;
 157
 158 /// GetTokPrecedence - Get the precedence of the pending binary operator token.
 159 static int GetTokPrecedence() {
 160   if (!isascii(CurTok))
 161     return -1;
 162
 163   // Make sure it's a declared binop.
 164   int TokPrec = BinopPrecedence[CurTok];
 165   if (TokPrec <= 0) return -1;
 166   return TokPrec;
 167 }
 168
 169 /// Error* - These are little helper functions for error handling.
 170 ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;}
 171 PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }
 172 FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }
 173
 174 static ExprAST *ParseExpression();
 175
 176 /// identifierexpr
 177 ///   ::= identifier
 178 ///   ::= identifier '(' expression* ')'
 179 static ExprAST *ParseIdentifierExpr() {
 180   std::string IdName = IdentifierStr;
 181
 182   getNextToken();  // eat identifier.
 183
 184   if (CurTok != '(') // Simple variable ref.
 185     return new VariableExprAST(IdName);
 186
 187   // Call.
 188   getNextToken();  // eat (
 189   std::vector<ExprAST*> Args;
 190   if (CurTok != ')') {
 191     while (1) {
 192       ExprAST *Arg = ParseExpression();
 193       if (!Arg) return 0;
 194       Args.push_back(Arg);
 195
 196       if (CurTok == ')') break;
 197
 198       if (CurTok != ',')
 199         return Error("Expected ')' or ',' in argument list");
 200       getNextToken();
 201     }
 202   }
 203
 204   // Eat the ')'.
 205   getNextToken();
 206
 207   return new CallExprAST(IdName, Args);
 208 }
 209
 210 /// numberexpr ::= number
 211 static ExprAST *ParseNumberExpr() {
 212   ExprAST *Result = new NumberExprAST(NumVal);
 213   getNextToken(); // consume the number
 214   return Result;
 215 }
 216
 217 /// parenexpr ::= '(' expression ')'
 218 static ExprAST *ParseParenExpr() {
 219   getNextToken();  // eat (.
 220   ExprAST *V = ParseExpression();
 221   if (!V) return 0;
 222
 223   if (CurTok != ')')
 224     return Error("expected ')'");
 225   getNextToken();  // eat ).
 226   return V;
 227 }
 228
 229 /// primary
 230 ///   ::= identifierexpr
 231 ///   ::= numberexpr
 232 ///   ::= parenexpr
 233 static ExprAST *ParsePrimary() {
 234   switch (CurTok) {
 235   default: return Error("unknown token when expecting an expression");
 236   case tok_identifier: return ParseIdentifierExpr();
 237   case tok_number:     return ParseNumberExpr();
 238   case '(':            return ParseParenExpr();
 239   }
 240 }
 241
 242 /// binoprhs
 243 ///   ::= ('+' primary)*
 244 static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
 245   // If this is a binop, find its precedence.
 246   while (1) {
 247     int TokPrec = GetTokPrecedence();
 248
 249     // If this is a binop that binds at least as tightly as the current binop,
 250     // consume it, otherwise we are done.
 251     if (TokPrec < ExprPrec)
 252       return LHS;
 253
 254     // Okay, we know this is a binop.
 255     int BinOp = CurTok;
 256     getNextToken();  // eat binop
 257
 258     // Parse the primary expression after the binary operator.
 259     ExprAST *RHS = ParsePrimary();
 260     if (!RHS) return 0;
 261
 262     // If BinOp binds less tightly with RHS than the operator after RHS, let
 263     // the pending operator take RHS as its LHS.
 264     int NextPrec = GetTokPrecedence();
 265     if (TokPrec < NextPrec) {
 266       RHS = ParseBinOpRHS(TokPrec+1, RHS);
 267       if (RHS == 0) return 0;
 268     }
 269
 270     // Merge LHS/RHS.
 271     LHS = new BinaryExprAST(BinOp, LHS, RHS);
 272   }
 273 }
 274
 275 /// expression
 276 ///   ::= primary binoprhs
 277 ///
 278 static ExprAST *ParseExpression() {
 279   ExprAST *LHS = ParsePrimary();
 280   if (!LHS) return 0;
 281
 282   return ParseBinOpRHS(0, LHS);
 283 }
 284
 285 /// prototype
 286 ///   ::= id '(' id* ')'
 287 static PrototypeAST *ParsePrototype() {
 288   if (CurTok != tok_identifier)
 289     return ErrorP("Expected function name in prototype");
 290
 291   std::string FnName = IdentifierStr;
 292   getNextToken();
 293
 294   if (CurTok != '(')
 295     return ErrorP("Expected '(' in prototype");
 296
 297   std::vector<std::string> ArgNames;
 298   while (getNextToken() == tok_identifier)
 299     ArgNames.push_back(IdentifierStr);
 300   if (CurTok != ')')
 301     return ErrorP("Expected ')' in prototype");
 302
 303   // success.
 304   getNextToken();  // eat ')'.
 305
 306   return new PrototypeAST(FnName, ArgNames);
 307 }
 308
 309 /// definition ::= 'def' prototype expression
 310 static FunctionAST *ParseDefinition() {
 311   getNextToken();  // eat def.
 312   PrototypeAST *Proto = ParsePrototype();
 313   if (Proto == 0) return 0;
 314
 315   if (ExprAST *E = ParseExpression())
 316     return new FunctionAST(Proto, E);
 317   return 0;
 318 }
 319
 320 /// toplevelexpr ::= expression
 321 static FunctionAST *ParseTopLevelExpr() {
 322   if (ExprAST *E = ParseExpression()) {
 323     // Make an anonymous proto.
 324     PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>());
 325     return new FunctionAST(Proto, E);
 326   }
 327   return 0;
 328 }
 329
 330 /// external ::= 'extern' prototype
 331 static PrototypeAST *ParseExtern() {
 332   getNextToken();  // eat extern.
 333   return ParsePrototype();
 334 }
 335
 336 //===----------------------------------------------------------------------===//
 337 // Top-Level parsing
 338 //===----------------------------------------------------------------------===//
 339
 340 static void HandleDefinition() {
 341   if (ParseDefinition()) {
 342     fprintf(stderr, "Parsed a function definition.\n");
 343   } else {
 344     // Skip token for error recovery.
 345     getNextToken();
 346   }
 347 }
 348
 349 static void HandleExtern() {
 350   if (ParseExtern()) {
 351     fprintf(stderr, "Parsed an extern\n");
 352   } else {
 353     // Skip token for error recovery.
 354     getNextToken();
 355   }
 356 }
 357
 358 static void HandleTopLevelExpression() {
 359   // Evaluate a top-level expression into an anonymous function.
 360   if (ParseTopLevelExpr()) {
 361     fprintf(stderr, "Parsed a top-level expr\n");
 362   } else {
 363     // Skip token for error recovery.
 364     getNextToken();
 365   }
 366 }
 367
 368 /// top ::= definition | external | expression | ';'
 369 static void MainLoop() {
 370   while (1) {
 371     fprintf(stderr, "ready> ");
 372     switch (CurTok) {
 373     case tok_eof:    return;
 374     case ';':        getNextToken(); break;  // ignore top-level semicolons.
 375     case tok_def:    HandleDefinition(); break;
 376     case tok_extern: HandleExtern(); break;
 377     default:         HandleTopLevelExpression(); break;
 378     }
 379   }
 380 }
 381
 382 //===----------------------------------------------------------------------===//
 383 // Main driver code.
 384 //===----------------------------------------------------------------------===//
 385
 386 int main() {
 387   // Install standard binary operators.
 388   // 1 is lowest precedence.
 389   BinopPrecedence['<'] = 10;
 390   BinopPrecedence['+'] = 20;
 391   BinopPrecedence['-'] = 20;
 392   BinopPrecedence['*'] = 40;  // highest.
 393
 394   // Prime the first token.
 395   fprintf(stderr, "ready> ");
 396   getNextToken();
 397
 398   // Run the main "interpreter loop" now.
 399   MainLoop();
 400
 401   return 0;
 402 }