examples/Kaleidoscope/Chapter2/toy.cpp

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