examples/Kaleidoscope/Chapter2/toy.cpp

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