ROSE  0.11.50.0
SymbolicExprParser.h
1 #ifndef ROSE_BinaryAnalysis_SymbolicExprParser_H
2 #define ROSE_BinaryAnalysis_SymbolicExprParser_H
3 #include <featureTests.h>
4 #ifdef ROSE_ENABLE_BINARY_ANALYSIS
5 
6 #include <Rose/BinaryAnalysis/InstructionSemantics2/BaseSemantics.h>
7 #include <Rose/BinaryAnalysis/SymbolicExpr.h>
8 #include <Rose/Exception.h>
9 #include <Sawyer/BiMap.h>
10 #include <Sawyer/CommandLine.h>
11 #include <Sawyer/Message.h>
12 #include <Sawyer/SharedPointer.h>
13 
14 namespace Rose {
15 namespace BinaryAnalysis {
16 
31 public:
33 
34  class SyntaxError: public Rose::Exception {
35  public:
36  std::string inputName;
37  unsigned lineNumber;
38  unsigned columnNumber;
39  SyntaxError(const std::string &mesg, const std::string &inputName, unsigned lineNumber, unsigned columnNumber);
40  ~SyntaxError() throw () {}
41  void print(std::ostream&) const;
42  };
43 
46  public:
47  SubstitutionError(const std::string &mesg)
48  : Rose::Exception(mesg) {}
49  ~SubstitutionError() throw () {}
50  void print(std::ostream&) const;
51  };
52 
54 
55  class Token {
56  public:
58  enum Type {
59  NONE = 0,
65  };
66 
67  private:
68  Type tokenType_;
69  std::string lexeme_; // lexeme
70  SymbolicExpr::Type exprType_; // type for expression
71  Sawyer::Container::BitVector bits_; // bits representing constant terms
72  unsigned lineNumber_, columnNumber_; // for start of token
73 
74  public:
77  : tokenType_(NONE), lineNumber_(0), columnNumber_(0) {}
78 
80  Token(Type tokenType, const SymbolicExpr::Type &exprType, const std::string &lexeme,
81  unsigned lineNumber, unsigned columnNumber)
82  : tokenType_(tokenType), lexeme_(lexeme), exprType_(exprType),
83  lineNumber_(lineNumber), columnNumber_(columnNumber) {
84  ASSERT_forbid(BITVECTOR == tokenType);
85  }
86 
88  Token(const Sawyer::Container::BitVector &bv, const SymbolicExpr::Type &exprType, const std::string &lexeme,
89  unsigned lineNumber, unsigned columnNumber)
90  : tokenType_(BITVECTOR), lexeme_(lexeme), exprType_(exprType), bits_(bv),
91  lineNumber_(lineNumber), columnNumber_(columnNumber) {
92  ASSERT_require(exprType.nBits() == bv.size());
93  }
94 
96  SymbolicExprParser::SyntaxError syntaxError(const std::string &mesg, const std::string &name="input") const {
97  return SymbolicExprParser::SyntaxError(mesg, name, lineNumber_, columnNumber_);
98  }
99 
101  Type tokenType() const { return tokenType_; }
102 
104  const std::string &lexeme() const { return lexeme_; }
105 
107  SymbolicExpr::Type exprType() const { return exprType_; }
108 
110  const Sawyer::Container::BitVector& bits() const { return bits_; }
111 
113  unsigned lineNumber() const { return lineNumber_; }
114 
116  unsigned columnNumber() const { return columnNumber_; }
117  };
118 
120 
124  class TokenStream {
125  std::istream &input_;
126  std::string name_;
127  unsigned lineNumber_, columnNumber_;
128  const Token endToken_;
129  std::vector<Token> tokens_;
130  int readAhead_;
131 
132  public:
137  explicit TokenStream(std::istream &input, const std::string &name="input",
138  unsigned lineNumber=1, unsigned columnNumber=0)
139  : input_(input), name_(name), lineNumber_(lineNumber), columnNumber_(columnNumber), readAhead_(EOF) {
140  init();
141  }
142 
144  const std::string& name() const { return name_; }
145 
147  unsigned lineNumber() const { return lineNumber_; }
148 
150  unsigned columnNumber() const { return columnNumber_; }
151 
153  const Token& operator[](size_t idx);
154 
156  void shift(size_t n=1);
157 
159  int nextCharacter();
160 
163  int consumeCharacter();
164 
166  void consumeWhiteSpace();
167 
169  int consumeEscapeSequence();
170 
173  void consumeInlineComment();
174 
177 
184  std::string consumeTerm();
185 
191 
194  Token scan();
195 
196  private:
197  void init();
198 
199  // Try to fill the token vector so it contains tokens up through at least [idx]
200  void fillTokenList(size_t idx);
201  };
202 
204 
206  std::string title_;
207  std::string docString_;
208  public:
209  virtual ~Expansion() {}
210 
213 
217  const std::string& title() const { return title_; }
218  void title(const std::string &s) { title_ = s; }
226  const std::string& docString() const { return docString_; }
227  void docString(const std::string &s) { docString_ = s; }
240  return src;
241  }
242  };
243 
245 
246  class AtomExpansion: public Expansion {
247  public:
250 
257  virtual SymbolicExpr::Ptr immediateExpansion(const Token &name) = 0;
258  };
259 
261  typedef std::vector<AtomExpansion::Ptr> AtomTable;
262 
264 
265  class OperatorExpansion: public Expansion {
266  public:
269 
270  protected:
271  SmtSolverPtr solver; // may be null
272 
273  explicit OperatorExpansion(const SmtSolverPtr &solver);
274 
275  public:
276  virtual ~OperatorExpansion();
277 
281  virtual SymbolicExpr::Ptr immediateExpansion(const Token &name, const SymbolicExpr::Nodes &operands) = 0;
282  };
283 
285  typedef std::vector<OperatorExpansion::Ptr> OperatorTable;
286 
288 
294  public:
297 
298  private:
300 
301  protected:
303  : ops_(ops) {}
304 
305  public:
308 
309  // internal
311  };
312 
314 
322  public:
325 
326  // internal
328 
329  private:
330  const RegisterDictionary *regdict_;
331  RegToVarMap reg2var_;
333 
334  protected:
336  : regdict_(regdict) {}
337 
338  public:
340  static Ptr instance(const RegisterDictionary*);
341 
349  return ops_;
350  }
352  ops_ = ops;
353  }
356  // internal
358  SymbolicExpr::Ptr delayedExpansion(const SymbolicExpr::Ptr&, const SymbolicExprParser*) ROSE_OVERRIDE;
359  };
360 
362 
367  public:
370 
371  // internal
372  typedef Sawyer::Container::Map<SymbolicExpr::Ptr /*placeholder*/, SymbolicExpr::Ptr /*address*/> ExprToMem;
373 
374  private:
375  ExprToMem exprToMem_;
377 
378  protected:
379  MemorySubstituter(const SmtSolver::Ptr &solver /*=NULL*/)
380  : OperatorExpansion(solver) {}
381 
382  public:
384  static Ptr instance(const SmtSolver::Ptr &solver /*=NULL*/);
385 
393  return ops_;
394  }
396  ops_ = ops;
397  }
400  // internal
401  virtual SymbolicExpr::Ptr immediateExpansion(const Token &name, const SymbolicExpr::Nodes &operands) ROSE_OVERRIDE;
402  virtual SymbolicExpr::Ptr delayedExpansion(const SymbolicExpr::Ptr&, const SymbolicExprParser*) ROSE_OVERRIDE;
403  };
404 
406 
411  class TermPlaceholders: public AtomExpansion {
412  public:
415 
418 
419  private:
420  NameToVarMap name2var_;
421 
422  protected:
423  TermPlaceholders() {}
424 
425  public:
427  static Ptr instance();
428 
430  const NameToVarMap& map() const { return name2var_; }
431 
432  // internal
433  SymbolicExpr::Ptr immediateExpansion(const SymbolicExprParser::Token&) ROSE_OVERRIDE;
434  };
435 
437 
441  class SymbolicExprCmdlineParser: public Sawyer::CommandLine::ValueParser {
442  protected:
445  : Sawyer::CommandLine::ValueParser(valueSaver) {}
446 
447  public:
450 
451  static Ptr instance() {
452  return Ptr(new SymbolicExprCmdlineParser);
453  }
454 
455  static Ptr instance(const Sawyer::CommandLine::ValueSaver::Ptr &valueSaver) {
456  return Ptr(new SymbolicExprCmdlineParser(valueSaver));
457  }
458 
459  static std::string docString();
460 
461  private:
462  virtual Sawyer::CommandLine::ParsedValue operator()(const char *input, const char **rest,
463  const Sawyer::CommandLine::Location &loc) ROSE_OVERRIDE;
464  };
465 
466  static SymbolicExprCmdlineParser::Ptr symbolicExprParser(SymbolicExpr::Ptr &storage);
467  static SymbolicExprCmdlineParser::Ptr symbolicExprParser(std::vector<SymbolicExpr::Ptr> &storage);
468  static SymbolicExprCmdlineParser::Ptr symbolicExprParser();
469 
471 private:
472  AtomTable atomTable_;
473  OperatorTable operatorTable_;
474  SmtSolverPtr solver_; // optional solver for simplifications
475 
476 public:
477  static Sawyer::Message::Facility mlog;
478 
479 public:
482 
486  explicit SymbolicExprParser(const SmtSolverPtr &solver);
487 
489 
490  // used internally to initialize the diagnostics system
491  static void initDiagnostics();
492 
497  SymbolicExpr::Ptr parse(const std::string&, const std::string &inputName="string");
498 
502  SymbolicExpr::Ptr parse(std::istream &input, const std::string &filename,
503  unsigned lineNumber=1, unsigned columnNumber=0);
504 
508  SymbolicExpr::Ptr parse(TokenStream&);
509 
512 
515 
519  const AtomTable& atomTable() const { return atomTable_; }
520  AtomTable& atomTable() { return atomTable_; }
526  const OperatorTable& operatorTable() const { return operatorTable_; }
527  OperatorTable& operatorTable() { return operatorTable_; }
534  std::string docString() const;
535 
553  SymbolicExpr::Ptr delayedExpansion(const SymbolicExpr::Ptr&) const;
554 
555 private:
556  void init();
557 };
558 
559 std::ostream& operator<<(std::ostream&, const SymbolicExprParser::SyntaxError&);
560 std::ostream& operator<<(std::ostream&, const SymbolicExprParser::SubstitutionError&);
561 
562 } // namespace
563 } // namespace
564 
565 #endif
566 #endif
const OperatorTable & operatorTable() const
Return all operator expansion functors.
Virtual base class for atom and operator expansion.
SmtSolverPtr Ptr
Reference counting pointer for SMT solvers.
Definition: SmtSolver.h:39
const Token & operator[](size_t idx)
Returns the specified token without consuming it.
boost::shared_ptr< RiscOperators > RiscOperatorsPtr
Shared-ownership pointer to a RISC operators object.
size_t nBits() const
Property: Total width of values.
Definition: SymbolicExpr.h:335
virtual SymbolicExpr::Ptr immediateExpansion(const Token &name)=0
Expand a parsed atom into some other expression.
void shift(size_t n=1)
Consume the specified number of tokens.
Expand register name to placeholder variables.
Collection of streams.
Definition: Message.h:1606
int nextCharacter()
Returns the next character.
Token(const Sawyer::Container::BitVector &bv, const SymbolicExpr::Type &exprType, const std::string &lexeme, unsigned lineNumber, unsigned columnNumber)
Construct a token for a numeric constant.
SymbolicExpr::Type consumeType()
Parse and consume a type specification.
unsigned lineNumber() const
Line number for start of token.
std::string inputName
Name of input, usually a file name.
Sawyer::SharedPointer< SymbolicExprCmdlineParser > Ptr
Shared-ownership pointer.
OperatorTable & operatorTable()
Return all operator expansion functors.
SymbolicExpr::Ptr immediateExpansion(const SymbolicExprParser::Token &) ROSE_OVERRIDE
Expand a parsed atom into some other expression.
unsigned columnNumber() const
Current column number.
virtual SymbolicExpr::Ptr delayedExpansion(const SymbolicExpr::Ptr &src, const SymbolicExprParser *parser)
Substitute one expression with another.
std::vector< OperatorExpansion::Ptr > OperatorTable
Ordered operator table.
Tokens generated by the lexical analysis.
Type of symbolic expression.
Definition: SymbolicExpr.h:225
Sawyer::SharedPointer< AtomExpansion > Ptr
Shared-ownership pointer to an AtomExpansion.
void consumeInlineComment()
Skip over angle-bracket comments.
Main namespace for the ROSE library.
Parses symbolic expressions from text.
SymbolicExpr::Type exprType() const
Type of expression.
int consumeCharacter()
Consume the next character.
Reference-counting intrusive smart pointer.
Definition: SharedPointer.h:68
const std::string & name() const
Name of this input stream.
Name space for the entire library.
Definition: FeasiblePath.h:787
Token(Type tokenType, const SymbolicExpr::Type &exprType, const std::string &lexeme, unsigned lineNumber, unsigned columnNumber)
Constructs a specific token from a string.
Token()
Constructs an end-of-input token with no position information.
Token scan()
Parse and consume the next token.
Virtual base class for expanding operators.
void docString(const std::string &s)
Property: Documentation string.
size_t size() const
Size of vector in bits.
Definition: BitVector.h:189
Information about a parsed switch value.
AtomTable & atomTable()
Return all atom expansion functors.
Expand register names to register values.
virtual SymbolicExpr::Ptr immediateExpansion(const Token &name, const SymbolicExpr::Nodes &operands)=0
Operator to expand a list into an expression tree.
std::string consumeTerm()
Parse and consume a term.
SymbolicExprParser()
Default constructor.
const std::string & lexeme() const
Lexeme from which token was parsed.
Sawyer::SharedPointer< OperatorExpansion > Ptr
Shared-ownership pointer.
void consumeWhiteSpace()
Skip over characters until a non-white-space character is encountered.
void defineRegisters(const InstructionSemantics2::BaseSemantics::RiscOperatorsPtr &)
Add definitions for registers.
Sawyer::SharedPointer< RegisterSubstituter > Ptr
Shared-ownership pointer.
SymbolicExprParser::SyntaxError syntaxError(const std::string &mesg, const std::string &name="input") const
Creates a syntax error from a token plus message.
unsigned lineNumber() const
Current line number.
const std::string & docString() const
Property: Documentation string.
void title(const std::string &s)
Property: Title to use for documentation.
Expand unrecognized terms to placholder variables.
void print(std::ostream &) const
Print error message to stream.
void appendOperatorExpansion(const OperatorExpansion::Ptr &)
Append a new functor for expanding operators into symbolic expressions.
Sawyer::Container::BiMap< std::string, SymbolicExpr::Ptr > NameToVarMap
Mapping between term names and placeholder variables.
Sawyer::SharedPointer< TermPlaceholders > Ptr
Shared-ownership pointer.
Base class for reference counted objects.
Definition: SharedObject.h:64
void consumeWhiteSpaceAndComments()
Skip over white space and/or inline comments.
InstructionSemantics2::BaseSemantics::RiscOperatorsPtr riscOperators() const
Property: Semantic state used during delayed expansion.
int consumeEscapeSequence()
Skip over an escape sequence and return the escaped character.
std::vector< AtomExpansion::Ptr > AtomTable
Ordered atom table.
Position within a command-line.
Sawyer::SharedPointer< Expansion > Ptr
Shared-ownership pointer to an Expansion.
void riscOperators(const InstructionSemantics2::BaseSemantics::RiscOperatorsPtr &ops)
Property: Semantic state used during delayed expansion.
Base class parsing a value from input.
const std::string & title() const
Property: Title to use for documentation.
InstructionSemantics2::BaseSemantics::RiscOperatorsPtr riscOperators() const
Property: Semantic state used during delayed expansion.
const Sawyer::Container::BitVector & bits() const
Bit vector for numeric constants.
void riscOperators(const InstructionSemantics2::BaseSemantics::RiscOperatorsPtr &ops)
Property: Semantic state used during delayed expansion.
Defines registers available for a particular architecture.
Definition: Registers.h:37
TokenStream(std::istream &input, const std::string &name="input", unsigned lineNumber=1, unsigned columnNumber=0)
Scan tokens from a character stream.
Sawyer::SharedPointer< RegisterToValue > Ptr
Shared-ownership pointer.
Parse a symbolic expression from the command-line.
static Ptr instance(const InstructionSemantics2::BaseSemantics::RiscOperatorsPtr &)
Allocating constructor.
Base class for all ROSE exceptions.
Definition: Rose/Exception.h:9
Sawyer::SharedPointer< MemorySubstituter > Ptr
Shared-ownership pointer.
unsigned columnNumber() const
Column number for start of token.
SymbolicExpr::Ptr parse(const std::string &, const std::string &inputName="string")
Create a symbolic expression by parsing a string.
Container associating values with keys.
Definition: Sawyer/Map.h:66
const NameToVarMap & map() const
Mapping between terms and variables.
std::shared_ptr< class SmtSolver > SmtSolverPtr
Reference-counting pointer for SMT solvers.
Definition: SmtSolver.h:25
void appendAtomExpansion(const AtomExpansion::Ptr &)
Append a new functor for expanding atoms into symbolic expressions.
const AtomTable & atomTable() const
Return all atom expansion functors.