examples/Kaleidoscope/Chapter2/toy.cpp

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