1//===- DefSymParser.cpp ---------------------------------------------------===// 2// 3// The MCLinker Project 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9#include <mcld/Support/DefSymParser.h> 10#include <mcld/Support/MsgHandling.h> 11#include <mcld/LD/LDSymbol.h> 12 13using namespace llvm; 14using namespace mcld; 15 16DefSymParser::DefSymParser(const Module& pModule) 17 : m_Module(pModule) { 18} 19 20// passing a valid operator will return a number whose quantity relative 21// to other such obtained quantities will give the priority of the operator 22static inline int precedence(const char* x) 23{ 24 switch (*x) { 25 case '-' : 26 case '+' : return 0; 27 case '/' : 28 case '*' : return 1; 29 default : assert("Unsupported operator specified"); 30 } 31 return 0; 32} 33 34bool DefSymParser::parse(StringRef pExpr, uint64_t& pSymVal) 35{ 36 std::stack<const char*> operatorStack; 37 std::stack<unsigned long> operandStack; 38 unsigned long operand1 = 0, 39 operand2 = 0, 40 result = 0; 41 std::string token; 42 std::vector<std::string> postfixString; 43 std::vector<std::string>::iterator it; 44 llvm::StringRef::iterator si = pExpr.begin(); 45 46 // Implement a modified Shunting Yard algorithm to form a RPN of the 47 // given expression 48 while (si != pExpr.end()) { 49 if (*si == '+' || *si == '-' || *si == '*' || *si == '/') { 50 if (token.empty() && (*si == '+' || *si == '-')) 51 // we have a case such as a++b or a+-b or a-+b 52 // pushing 0 when a token begins with a + or - operator 53 // solves unary operator problem 54 token = "0"; 55 // An operator encountered means a token ended, push it to 56 // postfix string queue. 57 postfixString.push_back(token); 58 token.clear(); 59 60 if (operatorStack.empty()) { 61 operatorStack.push(si); 62 } 63 else { 64 if (precedence(si) <= precedence(operatorStack.top())) { 65 // if the precedence of incoming operator is less or equal to 66 // top of stack, we clear stack till top is lower precedence 67 // or its empty 68 while (!operatorStack.empty()) { 69 if (precedence(si) <= precedence(operatorStack.top())) { 70 postfixString.push_back(std::string(operatorStack.top(),1)); 71 operatorStack.pop(); 72 } 73 else { 74 break; 75 } 76 } 77 } 78 operatorStack.push(si); 79 } 80 si++; 81 continue; 82 } 83 // keep reading the token when there is no operator encountered 84 token += *si; 85 si++; 86 } 87 postfixString.push_back(token); 88 // pop off any remaining operators from operator stack 89 while (!operatorStack.empty()) { 90 postfixString.push_back(std::string(operatorStack.top(),1)); 91 operatorStack.pop(); 92 } 93 //evaluate the postfix expression written above 94 95 for (it=postfixString.begin(); it != postfixString.end(); it++) { 96 switch (*((*it).c_str())) { 97 case '*': 98 case '-': 99 case '+': 100 case '/': 101 // when postfix string has an operator, pop first two operands from 102 // operand stack, use them in evaluate expression and push result 103 // back to stack 104 assert(!operandStack.empty() && "Invalid expression: extra operand"); 105 operand2 = operandStack.top(); 106 operandStack.pop(); 107 operand1 = operandStack.top(); 108 operandStack.pop(); 109 if (*((*it).c_str()) == '*') 110 result = operand1 * operand2; 111 else if (*((*it).c_str()) == '/') 112 result = operand1 / operand2; 113 else if (*((*it).c_str()) == '-') 114 result = operand1 - operand2; 115 else 116 result = operand1 + operand2; 117 operandStack.push(result); 118 break; 119 default: 120 // if the string encountered in postfix queue is a string 121 // try converting it to integer. 122 llvm::StringRef stringOperand(*it); 123 if(stringOperand.getAsInteger(0,result)) { 124 // the integer conversion failed means the token is a symbol 125 // or its invalid if the NamePool has no such symbol; 126 const LDSymbol* symbol = 127 m_Module.getNamePool().findSymbol(stringOperand); 128 129 if (!symbol) 130 fatal(diag::fail_sym_resolution) 131 << __FILE__ << __LINE__ 132 << "mclinker@googlegroups.com" ; 133 result = symbol->value(); 134 } 135 operandStack.push(result); 136 } 137 } 138 // once complete queue is processed, stack top is result 139 pSymVal = operandStack.top(); 140 return true; 141} 142