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