1e3ba15c794839abe076e3e2bdf6c626396a19d4dWill Dietz#include <cctype> 231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar#include <cstdio> 331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar#include <cstdlib> 431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar#include <map> 54ca7e09b7c1e41535f2a1bd86915375d023daf27Chandler Carruth#include <string> 631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar#include <vector> 731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar//===----------------------------------------------------------------------===// 931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar// Lexer 1031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar//===----------------------------------------------------------------------===// 1131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 1231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar// The lexer returns tokens [0-255] if it is an unknown character, otherwise one 1331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar// of these for known things. 1431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarenum Token { 1531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar tok_eof = -1, 1631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 1731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // commands 1831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar tok_def = -2, tok_extern = -3, 1931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 2031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // primary 2131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar tok_identifier = -4, tok_number = -5 2231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar}; 2331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 2431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic std::string IdentifierStr; // Filled in if tok_identifier 2531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic double NumVal; // Filled in if tok_number 2631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 2731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// gettok - Return the next token from standard input. 2831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic int gettok() { 2931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar static int LastChar = ' '; 3031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 3131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Skip any whitespace. 3231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar while (isspace(LastChar)) 3331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar LastChar = getchar(); 3431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 3531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (isalpha(LastChar)) { // identifier: [a-zA-Z][a-zA-Z0-9]* 3631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar IdentifierStr = LastChar; 3731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar while (isalnum((LastChar = getchar()))) 3831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar IdentifierStr += LastChar; 3931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 4031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (IdentifierStr == "def") return tok_def; 4131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (IdentifierStr == "extern") return tok_extern; 4231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return tok_identifier; 4331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 4431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 4531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (isdigit(LastChar) || LastChar == '.') { // Number: [0-9.]+ 4631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar std::string NumStr; 4731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar do { 4831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar NumStr += LastChar; 4931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar LastChar = getchar(); 5031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } while (isdigit(LastChar) || LastChar == '.'); 5131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 5231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar NumVal = strtod(NumStr.c_str(), 0); 5331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return tok_number; 5431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 5531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 5631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (LastChar == '#') { 5731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Comment until end of line. 5831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar do LastChar = getchar(); 5931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar while (LastChar != EOF && LastChar != '\n' && LastChar != '\r'); 6031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 6131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (LastChar != EOF) 6231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return gettok(); 6331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 6431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 6531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Check for end of file. Don't eat the EOF. 6631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (LastChar == EOF) 6731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return tok_eof; 6831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 6931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Otherwise, just return the character as its ascii value. 7031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar int ThisChar = LastChar; 7131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar LastChar = getchar(); 7231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return ThisChar; 7331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 7431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 7531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar//===----------------------------------------------------------------------===// 7631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar// Abstract Syntax Tree (aka Parse Tree) 7731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar//===----------------------------------------------------------------------===// 789d7c776d32c8a4d64b37a91c2d627629cf1498efBill Wendlingnamespace { 7931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// ExprAST - Base class for all expression nodes. 8031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarclass ExprAST { 8131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarpublic: 829d7c776d32c8a4d64b37a91c2d627629cf1498efBill Wendling virtual ~ExprAST() {} 8331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar}; 8431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 8531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// NumberExprAST - Expression class for numeric literals like "1.0". 8631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarclass NumberExprAST : public ExprAST { 8731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarpublic: 885d3041f99d4a328afa104b3fb410a77faba68d09Rafael Espindola NumberExprAST(double val) {} 8931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar}; 9031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 9131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// VariableExprAST - Expression class for referencing a variable, like "a". 9231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarclass VariableExprAST : public ExprAST { 9331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar std::string Name; 9431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarpublic: 9531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar VariableExprAST(const std::string &name) : Name(name) {} 9631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar}; 9731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 9831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// BinaryExprAST - Expression class for a binary operator. 9931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarclass BinaryExprAST : public ExprAST { 10031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarpublic: 1015d3041f99d4a328afa104b3fb410a77faba68d09Rafael Espindola BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs) {} 10231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar}; 10331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 10431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// CallExprAST - Expression class for function calls. 10531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarclass CallExprAST : public ExprAST { 10631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar std::string Callee; 10731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar std::vector<ExprAST*> Args; 10831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarpublic: 10931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar CallExprAST(const std::string &callee, std::vector<ExprAST*> &args) 11031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar : Callee(callee), Args(args) {} 11131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar}; 11231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 11331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// PrototypeAST - This class represents the "prototype" for a function, 11431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// which captures its name, and its argument names (thus implicitly the number 11531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// of arguments the function takes). 11631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarclass PrototypeAST { 11731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar std::string Name; 11831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar std::vector<std::string> Args; 11931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarpublic: 12031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar PrototypeAST(const std::string &name, const std::vector<std::string> &args) 12131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar : Name(name), Args(args) {} 12231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 12331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar}; 12431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 12531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// FunctionAST - This class represents a function definition itself. 12631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarclass FunctionAST { 12731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarpublic: 1285d3041f99d4a328afa104b3fb410a77faba68d09Rafael Espindola FunctionAST(PrototypeAST *proto, ExprAST *body) {} 12931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar}; 1309d7c776d32c8a4d64b37a91c2d627629cf1498efBill Wendling} // end anonymous namespace 13131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 13231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar//===----------------------------------------------------------------------===// 13331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar// Parser 13431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar//===----------------------------------------------------------------------===// 13531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 13631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// CurTok/getNextToken - Provide a simple token buffer. CurTok is the current 13731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// token the parser is looking at. getNextToken reads another token from the 13831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// lexer and updates CurTok with its results. 13931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic int CurTok; 14031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic int getNextToken() { 14131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return CurTok = gettok(); 14231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 14331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 14431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// BinopPrecedence - This holds the precedence for each binary operator that is 14531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// defined. 14631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic std::map<char, int> BinopPrecedence; 14731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 14831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// GetTokPrecedence - Get the precedence of the pending binary operator token. 14931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic int GetTokPrecedence() { 15031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (!isascii(CurTok)) 15131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return -1; 15231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 15331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Make sure it's a declared binop. 15431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar int TokPrec = BinopPrecedence[CurTok]; 15531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (TokPrec <= 0) return -1; 15631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return TokPrec; 15731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 15831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 15931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// Error* - These are little helper functions for error handling. 16031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick TryzelaarExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;} 16131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick TryzelaarPrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; } 16231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 16331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic ExprAST *ParseExpression(); 16431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 16531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// identifierexpr 16631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// ::= identifier 16731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// ::= identifier '(' expression* ')' 16831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic ExprAST *ParseIdentifierExpr() { 16931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar std::string IdName = IdentifierStr; 17031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 17131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); // eat identifier. 17231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 17331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (CurTok != '(') // Simple variable ref. 17431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return new VariableExprAST(IdName); 17531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 17631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Call. 17731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); // eat ( 17831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar std::vector<ExprAST*> Args; 17931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (CurTok != ')') { 18031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar while (1) { 18131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar ExprAST *Arg = ParseExpression(); 18231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (!Arg) return 0; 18331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar Args.push_back(Arg); 18431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 18531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (CurTok == ')') break; 18631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 18731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (CurTok != ',') 18831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return Error("Expected ')' or ',' in argument list"); 18931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); 19031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 19131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 19231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 19331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Eat the ')'. 19431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); 19531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 19631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return new CallExprAST(IdName, Args); 19731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 19831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 19931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// numberexpr ::= number 20031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic ExprAST *ParseNumberExpr() { 20131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar ExprAST *Result = new NumberExprAST(NumVal); 20231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); // consume the number 20331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return Result; 20431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 20531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 20631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// parenexpr ::= '(' expression ')' 20731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic ExprAST *ParseParenExpr() { 20831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); // eat (. 20931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar ExprAST *V = ParseExpression(); 21031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (!V) return 0; 21131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 21231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (CurTok != ')') 21331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return Error("expected ')'"); 21431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); // eat ). 21531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return V; 21631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 21731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 21831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// primary 21931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// ::= identifierexpr 22031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// ::= numberexpr 22131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// ::= parenexpr 22231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic ExprAST *ParsePrimary() { 22331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar switch (CurTok) { 22431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar default: return Error("unknown token when expecting an expression"); 22531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar case tok_identifier: return ParseIdentifierExpr(); 22631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar case tok_number: return ParseNumberExpr(); 22731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar case '(': return ParseParenExpr(); 22831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 22931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 23031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 23131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// binoprhs 23231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// ::= ('+' primary)* 23331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) { 23431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // If this is a binop, find its precedence. 23531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar while (1) { 23631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar int TokPrec = GetTokPrecedence(); 23731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 23831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // If this is a binop that binds at least as tightly as the current binop, 23931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // consume it, otherwise we are done. 24031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (TokPrec < ExprPrec) 24131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return LHS; 24231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 24331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Okay, we know this is a binop. 24431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar int BinOp = CurTok; 24531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); // eat binop 24631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 24731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Parse the primary expression after the binary operator. 24831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar ExprAST *RHS = ParsePrimary(); 24931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (!RHS) return 0; 25031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 25131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // If BinOp binds less tightly with RHS than the operator after RHS, let 25231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // the pending operator take RHS as its LHS. 25331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar int NextPrec = GetTokPrecedence(); 25431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (TokPrec < NextPrec) { 25531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar RHS = ParseBinOpRHS(TokPrec+1, RHS); 25631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (RHS == 0) return 0; 25731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 25831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 25931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Merge LHS/RHS. 26031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar LHS = new BinaryExprAST(BinOp, LHS, RHS); 26131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 26231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 26331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 26431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// expression 26531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// ::= primary binoprhs 26631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// 26731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic ExprAST *ParseExpression() { 26831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar ExprAST *LHS = ParsePrimary(); 26931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (!LHS) return 0; 27031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 27131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return ParseBinOpRHS(0, LHS); 27231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 27331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 27431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// prototype 27531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// ::= id '(' id* ')' 27631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic PrototypeAST *ParsePrototype() { 27731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (CurTok != tok_identifier) 27831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return ErrorP("Expected function name in prototype"); 27931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 28031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar std::string FnName = IdentifierStr; 28131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); 28231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 28331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (CurTok != '(') 28431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return ErrorP("Expected '(' in prototype"); 28531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 28631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar std::vector<std::string> ArgNames; 28731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar while (getNextToken() == tok_identifier) 28831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar ArgNames.push_back(IdentifierStr); 28931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (CurTok != ')') 29031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return ErrorP("Expected ')' in prototype"); 29131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 29231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // success. 29331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); // eat ')'. 29431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 29531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return new PrototypeAST(FnName, ArgNames); 29631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 29731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 29831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// definition ::= 'def' prototype expression 29931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic FunctionAST *ParseDefinition() { 30031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); // eat def. 30131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar PrototypeAST *Proto = ParsePrototype(); 30231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (Proto == 0) return 0; 30331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 30431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (ExprAST *E = ParseExpression()) 30531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return new FunctionAST(Proto, E); 30631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return 0; 30731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 30831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 30931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// toplevelexpr ::= expression 31031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic FunctionAST *ParseTopLevelExpr() { 31131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (ExprAST *E = ParseExpression()) { 31231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Make an anonymous proto. 31331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>()); 31431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return new FunctionAST(Proto, E); 31531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 31631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return 0; 31731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 31831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 31931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// external ::= 'extern' prototype 32031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic PrototypeAST *ParseExtern() { 32131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); // eat extern. 32231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return ParsePrototype(); 32331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 32431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 32531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar//===----------------------------------------------------------------------===// 32631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar// Top-Level parsing 32731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar//===----------------------------------------------------------------------===// 32831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 32931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic void HandleDefinition() { 33031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (ParseDefinition()) { 33131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar fprintf(stderr, "Parsed a function definition.\n"); 33231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } else { 33331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Skip token for error recovery. 33431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); 33531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 33631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 33731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 33831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic void HandleExtern() { 33931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (ParseExtern()) { 34031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar fprintf(stderr, "Parsed an extern\n"); 34131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } else { 34231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Skip token for error recovery. 34331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); 34431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 34531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 34631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 34731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic void HandleTopLevelExpression() { 34831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Evaluate a top-level expression into an anonymous function. 34931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar if (ParseTopLevelExpr()) { 35031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar fprintf(stderr, "Parsed a top-level expr\n"); 35131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } else { 35231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Skip token for error recovery. 35331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); 35431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 35531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 35631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 35731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar/// top ::= definition | external | expression | ';' 35831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarstatic void MainLoop() { 35931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar while (1) { 36031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar fprintf(stderr, "ready> "); 36131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar switch (CurTok) { 36231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar case tok_eof: return; 36331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar case ';': getNextToken(); break; // ignore top-level semicolons. 36431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar case tok_def: HandleDefinition(); break; 36531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar case tok_extern: HandleExtern(); break; 36631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar default: HandleTopLevelExpression(); break; 36731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 36831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar } 36931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 37031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 37131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar//===----------------------------------------------------------------------===// 37231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar// Main driver code. 37331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar//===----------------------------------------------------------------------===// 37431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 37531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaarint main() { 37631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Install standard binary operators. 37731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // 1 is lowest precedence. 37831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar BinopPrecedence['<'] = 10; 37931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar BinopPrecedence['+'] = 20; 38031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar BinopPrecedence['-'] = 20; 38131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar BinopPrecedence['*'] = 40; // highest. 38231c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 38331c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Prime the first token. 38431c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar fprintf(stderr, "ready> "); 38531c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar getNextToken(); 38631c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 38731c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar // Run the main "interpreter loop" now. 38831c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar MainLoop(); 38931c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar 39031c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar return 0; 39131c6c5d58a6d2254063e8a18fd32b851a06e2ddfErick Tryzelaar} 392