examples/Kaleidoscope/Chapter2/toy.cpp

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