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