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 namespace {
  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 };
  90
  91 /// VariableExprAST - Expression class for referencing a variable, like "a".
  92 class VariableExprAST : public ExprAST {
  93   std::string Name;
  94 public:
  95   VariableExprAST(const std::string &name) : Name(name) {}
  96 };
  97
  98 /// BinaryExprAST - Expression class for a binary operator.
  99 class BinaryExprAST : public ExprAST {
 100 public:
 101   BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs) {}
 102 };
 103
 104 /// CallExprAST - Expression class for function calls.
 105 class CallExprAST : public ExprAST {
 106   std::string Callee;
 107   std::vector<ExprAST*> Args;
 108 public:
 109   CallExprAST(const std::string &callee, std::vector<ExprAST*> &args)
 110     : Callee(callee), Args(args) {}
 111 };
 112
 113 /// PrototypeAST - This class represents the "prototype" for a function,
 114 /// which captures its name, and its argument names (thus implicitly the number
 115 /// of arguments the function takes).
 116 class PrototypeAST {
 117   std::string Name;
 118   std::vector<std::string> Args;
 119 public:
 120   PrototypeAST(const std::string &name, const std::vector<std::string> &args)
 121     : Name(name), Args(args) {}
 122
 123 };
 124
 125 /// FunctionAST - This class represents a function definition itself.
 126 class FunctionAST {
 127 public:
 128   FunctionAST(PrototypeAST *proto, ExprAST *body) {}
 129 };
 130 } // end anonymous namespace
 131
 132 //===----------------------------------------------------------------------===//
 133 // Parser
 134 //===----------------------------------------------------------------------===//
 135
 136 /// CurTok/getNextToken - Provide a simple token buffer.  CurTok is the current
 137 /// token the parser is looking at.  getNextToken reads another token from the
 138 /// lexer and updates CurTok with its results.
 139 static int CurTok;
 140 static int getNextToken() {
 141   return CurTok = gettok();
 142 }
 143
 144 /// BinopPrecedence - This holds the precedence for each binary operator that is
 145 /// defined.
 146 static std::map<char, int> BinopPrecedence;
 147
 148 /// GetTokPrecedence - Get the precedence of the pending binary operator token.
 149 static int GetTokPrecedence() {
 150   if (!isascii(CurTok))
 151     return -1;
 152
 153   // Make sure it's a declared binop.
 154   int TokPrec = BinopPrecedence[CurTok];
 155   if (TokPrec <= 0) return -1;
 156   return TokPrec;
 157 }
 158
 159 /// Error* - These are little helper functions for error handling.
 160 ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;}
 161 PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; }
 162
 163 static ExprAST *ParseExpression();
 164
 165 /// identifierexpr
 166 ///   ::= identifier
 167 ///   ::= identifier '(' expression* ')'
 168 static ExprAST *ParseIdentifierExpr() {
 169   std::string IdName = IdentifierStr;
 170
 171   getNextToken();  // eat identifier.
 172
 173   if (CurTok != '(') // Simple variable ref.
 174     return new VariableExprAST(IdName);
 175
 176   // Call.
 177   getNextToken();  // eat (
 178   std::vector<ExprAST*> Args;
 179   if (CurTok != ')') {
 180     while (1) {
 181       ExprAST *Arg = ParseExpression();
 182       if (!Arg) return 0;
 183       Args.push_back(Arg);
 184
 185       if (CurTok == ')') break;
 186
 187       if (CurTok != ',')
 188         return Error("Expected ')' or ',' in argument list");
 189       getNextToken();
 190     }
 191   }
 192
 193   // Eat the ')'.
 194   getNextToken();
 195
 196   return new CallExprAST(IdName, Args);
 197 }
 198
 199 /// numberexpr ::= number
 200 static ExprAST *ParseNumberExpr() {
 201   ExprAST *Result = new NumberExprAST(NumVal);
 202   getNextToken(); // consume the number
 203   return Result;
 204 }
 205
 206 /// parenexpr ::= '(' expression ')'
 207 static ExprAST *ParseParenExpr() {
 208   getNextToken();  // eat (.
 209   ExprAST *V = ParseExpression();
 210   if (!V) return 0;
 211
 212   if (CurTok != ')')
 213     return Error("expected ')'");
 214   getNextToken();  // eat ).
 215   return V;
 216 }
 217
 218 /// primary
 219 ///   ::= identifierexpr
 220 ///   ::= numberexpr
 221 ///   ::= parenexpr
 222 static ExprAST *ParsePrimary() {
 223   switch (CurTok) {
 224   default: return Error("unknown token when expecting an expression");
 225   case tok_identifier: return ParseIdentifierExpr();
 226   case tok_number:     return ParseNumberExpr();
 227   case '(':            return ParseParenExpr();
 228   }
 229 }
 230
 231 /// binoprhs
 232 ///   ::= ('+' primary)*
 233 static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) {
 234   // If this is a binop, find its precedence.
 235   while (1) {
 236     int TokPrec = GetTokPrecedence();
 237
 238     // If this is a binop that binds at least as tightly as the current binop,
 239     // consume it, otherwise we are done.
 240     if (TokPrec < ExprPrec)
 241       return LHS;
 242
 243     // Okay, we know this is a binop.
 244     int BinOp = CurTok;
 245     getNextToken();  // eat binop
 246
 247     // Parse the primary expression after the binary operator.
 248     ExprAST *RHS = ParsePrimary();
 249     if (!RHS) return 0;
 250
 251     // If BinOp binds less tightly with RHS than the operator after RHS, let
 252     // the pending operator take RHS as its LHS.
 253     int NextPrec = GetTokPrecedence();
 254     if (TokPrec < NextPrec) {
 255       RHS = ParseBinOpRHS(TokPrec+1, RHS);
 256       if (RHS == 0) return 0;
 257     }
 258
 259     // Merge LHS/RHS.
 260     LHS = new BinaryExprAST(BinOp, LHS, RHS);
 261   }
 262 }
 263
 264 /// expression
 265 ///   ::= primary binoprhs
 266 ///
 267 static ExprAST *ParseExpression() {
 268   ExprAST *LHS = ParsePrimary();
 269   if (!LHS) return 0;
 270
 271   return ParseBinOpRHS(0, LHS);
 272 }
 273
 274 /// prototype
 275 ///   ::= id '(' id* ')'
 276 static PrototypeAST *ParsePrototype() {
 277   if (CurTok != tok_identifier)
 278     return ErrorP("Expected function name in prototype");
 279
 280   std::string FnName = IdentifierStr;
 281   getNextToken();
 282
 283   if (CurTok != '(')
 284     return ErrorP("Expected '(' in prototype");
 285
 286   std::vector<std::string> ArgNames;
 287   while (getNextToken() == tok_identifier)
 288     ArgNames.push_back(IdentifierStr);
 289   if (CurTok != ')')
 290     return ErrorP("Expected ')' in prototype");
 291
 292   // success.
 293   getNextToken();  // eat ')'.
 294
 295   return new PrototypeAST(FnName, ArgNames);
 296 }
 297
 298 /// definition ::= 'def' prototype expression
 299 static FunctionAST *ParseDefinition() {
 300   getNextToken();  // eat def.
 301   PrototypeAST *Proto = ParsePrototype();
 302   if (Proto == 0) return 0;
 303
 304   if (ExprAST *E = ParseExpression())
 305     return new FunctionAST(Proto, E);
 306   return 0;
 307 }
 308
 309 /// toplevelexpr ::= expression
 310 static FunctionAST *ParseTopLevelExpr() {
 311   if (ExprAST *E = ParseExpression()) {
 312     // Make an anonymous proto.
 313     PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>());
 314     return new FunctionAST(Proto, E);
 315   }
 316   return 0;
 317 }
 318
 319 /// external ::= 'extern' prototype
 320 static PrototypeAST *ParseExtern() {
 321   getNextToken();  // eat extern.
 322   return ParsePrototype();
 323 }
 324
 325 //===----------------------------------------------------------------------===//
 326 // Top-Level parsing
 327 //===----------------------------------------------------------------------===//
 328
 329 static void HandleDefinition() {
 330   if (ParseDefinition()) {
 331     fprintf(stderr, "Parsed a function definition.\n");
 332   } else {
 333     // Skip token for error recovery.
 334     getNextToken();
 335   }
 336 }
 337
 338 static void HandleExtern() {
 339   if (ParseExtern()) {
 340     fprintf(stderr, "Parsed an extern\n");
 341   } else {
 342     // Skip token for error recovery.
 343     getNextToken();
 344   }
 345 }
 346
 347 static void HandleTopLevelExpression() {
 348   // Evaluate a top-level expression into an anonymous function.
 349   if (ParseTopLevelExpr()) {
 350     fprintf(stderr, "Parsed a top-level expr\n");
 351   } else {
 352     // Skip token for error recovery.
 353     getNextToken();
 354   }
 355 }
 356
 357 /// top ::= definition | external | expression | ';'
 358 static void MainLoop() {
 359   while (1) {
 360     fprintf(stderr, "ready> ");
 361     switch (CurTok) {
 362     case tok_eof:    return;
 363     case ';':        getNextToken(); break;  // ignore top-level semicolons.
 364     case tok_def:    HandleDefinition(); break;
 365     case tok_extern: HandleExtern(); break;
 366     default:         HandleTopLevelExpression(); break;
 367     }
 368   }
 369 }
 370
 371 //===----------------------------------------------------------------------===//
 372 // Main driver code.
 373 //===----------------------------------------------------------------------===//
 374
 375 int main() {
 376   // Install standard binary operators.
 377   // 1 is lowest precedence.
 378   BinopPrecedence['<'] = 10;
 379   BinopPrecedence['+'] = 20;
 380   BinopPrecedence['-'] = 20;
 381   BinopPrecedence['*'] = 40;  // highest.
 382
 383   // Prime the first token.
 384   fprintf(stderr, "ready> ");
 385   getNextToken();
 386
 387   // Run the main "interpreter loop" now.
 388   MainLoop();
 389
 390   return 0;
 391 }