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