ROSE  0.11.98.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/BasicTypes.h>
7 #include <Rose/BinaryAnalysis/InstructionSemantics/BaseSemantics.h>
8 #include <Rose/BinaryAnalysis/SymbolicExpr.h>
9 #include <Rose/Exception.h>
10 #include <Sawyer/BiMap.h>
11 #include <Sawyer/CommandLine.h>
12 #include <Sawyer/Message.h>
13 #include <Sawyer/SharedPointer.h>
14 
15 namespace Rose {
16 namespace BinaryAnalysis {
17 
32 public:
34 
35  class SyntaxError: public Rose::Exception {
36  public:
37  std::string inputName;
38  unsigned lineNumber;
39  unsigned columnNumber;
40  SyntaxError(const std::string &mesg, const std::string &inputName, unsigned lineNumber, unsigned columnNumber);
41  ~SyntaxError() throw () {}
42  void print(std::ostream&) const;
43  };
44 
47  public:
48  SubstitutionError(const std::string &mesg)
49  : Rose::Exception(mesg) {}
50  ~SubstitutionError() throw () {}
51  void print(std::ostream&) const;
52  };
53 
55 
56  class Token {
57  public:
59  enum Type {
60  NONE = 0,
66  };
67 
68  private:
69  Type tokenType_;
70  std::string lexeme_; // lexeme
71  SymbolicExpr::Type exprType_; // type for expression
72  Sawyer::Container::BitVector bits_; // bits representing constant terms
73  unsigned lineNumber_, columnNumber_; // for start of token
74 
75  public:
78  : tokenType_(NONE), lineNumber_(0), columnNumber_(0) {}
79 
81  Token(Type tokenType, const SymbolicExpr::Type &exprType, const std::string &lexeme,
82  unsigned lineNumber, unsigned columnNumber)
83  : tokenType_(tokenType), lexeme_(lexeme), exprType_(exprType),
84  lineNumber_(lineNumber), columnNumber_(columnNumber) {
85  ASSERT_forbid(BITVECTOR == tokenType);
86  }
87 
89  Token(const Sawyer::Container::BitVector &bv, const SymbolicExpr::Type &exprType, const std::string &lexeme,
90  unsigned lineNumber, unsigned columnNumber)
91  : tokenType_(BITVECTOR), lexeme_(lexeme), exprType_(exprType), bits_(bv),
92  lineNumber_(lineNumber), columnNumber_(columnNumber) {
93  ASSERT_require(exprType.nBits() == bv.size());
94  }
95 
97  SymbolicExprParser::SyntaxError syntaxError(const std::string &mesg, const std::string &name="input") const {
98  return SymbolicExprParser::SyntaxError(mesg, name, lineNumber_, columnNumber_);
99  }
100 
102  Type tokenType() const { return tokenType_; }
103 
105  const std::string &lexeme() const { return lexeme_; }
106 
108  SymbolicExpr::Type exprType() const { return exprType_; }
109 
111  const Sawyer::Container::BitVector& bits() const { return bits_; }
112 
114  unsigned lineNumber() const { return lineNumber_; }
115 
117  unsigned columnNumber() const { return columnNumber_; }
118  };
119 
121 
125  class TokenStream {
126  std::istream &input_;
127  std::string name_;
128  unsigned lineNumber_, columnNumber_;
129  const Token endToken_;
130  std::vector<Token> tokens_;
131  int readAhead_;
132 
133  public:
138  explicit TokenStream(std::istream &input, const std::string &name="input",
139  unsigned lineNumber=1, unsigned columnNumber=0)
140  : input_(input), name_(name), lineNumber_(lineNumber), columnNumber_(columnNumber), readAhead_(EOF) {
141  init();
142  }
143 
145  const std::string& name() const { return name_; }
146 
148  unsigned lineNumber() const { return lineNumber_; }
149 
151  unsigned columnNumber() const { return columnNumber_; }
152 
154  const Token& operator[](size_t idx);
155 
157  void shift(size_t n=1);
158 
160  int nextCharacter();
161 
164  int consumeCharacter();
165 
167  void consumeWhiteSpace();
168 
170  int consumeEscapeSequence();
171 
174  void consumeInlineComment();
175 
178 
185  std::string consumeTerm();
186 
192 
195  Token scan();
196 
197  private:
198  void init();
199 
200  // Try to fill the token vector so it contains tokens up through at least [idx]
201  void fillTokenList(size_t idx);
202  };
203 
205 
207  std::string title_;
208  std::string docString_;
209  public:
210  virtual ~Expansion() {}
211 
214 
218  const std::string& title() const { return title_; }
219  void title(const std::string &s) { title_ = s; }
227  const std::string& docString() const { return docString_; }
228  void docString(const std::string &s) { docString_ = s; }
241  return src;
242  }
243  };
244 
246 
247  class AtomExpansion: public Expansion {
248  public:
251 
258  virtual SymbolicExpr::Ptr immediateExpansion(const Token &name) = 0;
259  };
260 
262  typedef std::vector<AtomExpansion::Ptr> AtomTable;
263 
265 
266  class OperatorExpansion: public Expansion {
267  public:
270 
271  protected:
272  SmtSolverPtr solver; // may be null
273 
274  explicit OperatorExpansion(const SmtSolverPtr &solver);
275 
276  public:
277  virtual ~OperatorExpansion();
278 
282  virtual SymbolicExpr::Ptr immediateExpansion(const Token &name, const SymbolicExpr::Nodes &operands) = 0;
283  };
284 
286  typedef std::vector<OperatorExpansion::Ptr> OperatorTable;
287 
289 
295  public:
298 
299  private:
301 
302  protected:
304  : ops_(ops) {}
305 
306  public:
309 
310  // internal
312  };
313 
315 
323  public:
326 
327  // internal
329 
330  private:
331  RegisterDictionaryPtr regdict_;
332  RegToVarMap reg2var_;
334 
335  protected:
337  : regdict_(regdict) {}
338 
339  public:
341  static Ptr instance(const RegisterDictionaryPtr&);
342 
350  return ops_;
351  }
353  ops_ = ops;
354  }
357  // internal
360  };
361 
363 
368  public:
371 
372  // internal
373  typedef Sawyer::Container::Map<SymbolicExpr::Ptr /*placeholder*/, SymbolicExpr::Ptr /*address*/> ExprToMem;
374 
375  private:
376  ExprToMem exprToMem_;
378 
379  protected:
380  MemorySubstituter(const SmtSolver::Ptr &solver /*=NULL*/)
381  : OperatorExpansion(solver) {}
382 
383  public:
385  static Ptr instance(const SmtSolver::Ptr &solver /*=NULL*/);
386 
394  return ops_;
395  }
397  ops_ = ops;
398  }
401  // internal
402  virtual SymbolicExpr::Ptr immediateExpansion(const Token &name, const SymbolicExpr::Nodes &operands) override;
403  virtual SymbolicExpr::Ptr delayedExpansion(const SymbolicExpr::Ptr&, const SymbolicExprParser*) override;
404  };
405 
407 
413  public:
416 
419 
420  private:
421  NameToVarMap name2var_;
422 
423  protected:
424  TermPlaceholders() {}
425 
426  public:
428  static Ptr instance();
429 
431  const NameToVarMap& map() const { return name2var_; }
432 
433  // internal
435  };
436 
438 
443  protected:
446  : Sawyer::CommandLine::ValueParser(valueSaver) {}
447 
448  public:
451 
452  static Ptr instance() {
453  return Ptr(new SymbolicExprCmdlineParser);
454  }
455 
456  static Ptr instance(const Sawyer::CommandLine::ValueSaver::Ptr &valueSaver) {
457  return Ptr(new SymbolicExprCmdlineParser(valueSaver));
458  }
459 
460  static std::string docString();
461 
462  private:
463  virtual Sawyer::CommandLine::ParsedValue operator()(const char *input, const char **rest,
464  const Sawyer::CommandLine::Location &loc) override;
465  };
466 
467  static SymbolicExprCmdlineParser::Ptr symbolicExprParser(SymbolicExpr::Ptr &storage);
468  static SymbolicExprCmdlineParser::Ptr symbolicExprParser(std::vector<SymbolicExpr::Ptr> &storage);
469  static SymbolicExprCmdlineParser::Ptr symbolicExprParser();
470 
472 private:
473  AtomTable atomTable_;
474  OperatorTable operatorTable_;
475  SmtSolverPtr solver_; // optional solver for simplifications
476 
477 public:
478  static Sawyer::Message::Facility mlog;
479 
480 public:
483 
487  explicit SymbolicExprParser(const SmtSolverPtr &solver);
488 
490 
491  // used internally to initialize the diagnostics system
492  static void initDiagnostics();
493 
498  SymbolicExpr::Ptr parse(const std::string&, const std::string &inputName="string");
499 
503  SymbolicExpr::Ptr parse(std::istream &input, const std::string &filename,
504  unsigned lineNumber=1, unsigned columnNumber=0);
505 
509  SymbolicExpr::Ptr parse(TokenStream&);
510 
513 
516 
520  const AtomTable& atomTable() const { return atomTable_; }
521  AtomTable& atomTable() { return atomTable_; }
527  const OperatorTable& operatorTable() const { return operatorTable_; }
528  OperatorTable& operatorTable() { return operatorTable_; }
535  std::string docString() const;
536 
555 
556 private:
557  void init();
558 };
559 
560 std::ostream& operator<<(std::ostream&, const SymbolicExprParser::SyntaxError&);
561 std::ostream& operator<<(std::ostream&, const SymbolicExprParser::SubstitutionError&);
562 
563 } // namespace
564 } // namespace
565 
566 #endif
567 #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:45
const Token & operator[](size_t idx)
Returns the specified token without consuming it.
SymbolicExpr::Ptr immediateExpansion(const SymbolicExprParser::Token &) override
Expand a parsed atom into some other expression.
InstructionSemantics::BaseSemantics::RiscOperatorsPtr riscOperators() const
Property: Semantic state used during delayed expansion.
void defineRegisters(const InstructionSemantics::BaseSemantics::RiscOperatorsPtr &)
Add definitions for registers.
size_t nBits() const
Property: Total width of values.
Definition: SymbolicExpr.h:333
const ValueSaver::Ptr valueSaver() const
Property: functor responsible for saving a parsed value in user storage.
SymbolicExpr::Ptr delayedExpansion(const SymbolicExpr::Ptr &, const SymbolicExprParser *) override
Substitute one expression with another.
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.
boost::shared_ptr< RiscOperators > RiscOperatorsPtr
Shared-ownership pointer to a RISC operators object.
Collection of streams.
Definition: Message.h:1606
static Ptr instance(const RegisterDictionaryPtr &)
Allocating constructor.
SymbolicExpr::Ptr delayedExpansion(const SymbolicExpr::Ptr &) const
Perform delayed expansion.
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.
void riscOperators(const InstructionSemantics::BaseSemantics::RiscOperatorsPtr &ops)
Property: Semantic state used during delayed expansion.
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:223
Sawyer::SharedPointer< AtomExpansion > Ptr
Shared-ownership pointer to an AtomExpansion.
void consumeInlineComment()
Skip over angle-bracket comments.
SymbolicExpr::Ptr immediateExpansion(const SymbolicExprParser::Token &) override
Expand a parsed atom into some other expression.
Main namespace for the ROSE library.
Parses symbolic expressions from text.
SymbolicExpr::Type exprType() const
Type of expression.
static Ptr instance(const InstructionSemantics::BaseSemantics::RiscOperatorsPtr &)
Allocating constructor.
int consumeCharacter()
Consume the next character.
virtual SymbolicExpr::Ptr delayedExpansion(const SymbolicExpr::Ptr &, const SymbolicExprParser *) override
Substitute one expression with another.
virtual SymbolicExpr::Ptr immediateExpansion(const Token &name, const SymbolicExpr::Nodes &operands) override
Operator to expand a list into an expression tree.
Reference-counting intrusive smart pointer.
Definition: SharedPointer.h:68
const std::string & name() const
Name of this input stream.
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.
InstructionSemantics::BaseSemantics::RiscOperatorsPtr riscOperators() const
Property: Semantic state used during delayed expansion.
const std::string & lexeme() const
Lexeme from which token was parsed.
Sawyer::SharedPointer< OperatorExpansion > Ptr
Shared-ownership pointer.
Sawyer::SharedPointer< Node > Ptr
Reference counting pointer.
void consumeWhiteSpace()
Skip over characters until a non-white-space character is encountered.
SymbolicExpr::Ptr immediateExpansion(const SymbolicExprParser::Token &) override
Expand a parsed atom into some other expression.
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.
Binary analysis.
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.
std::string docString() const
Documentation string.
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.
int consumeEscapeSequence()
Skip over an escape sequence and return the escaped character.
std::vector< AtomExpansion::Ptr > AtomTable
Ordered atom table.
void riscOperators(const InstructionSemantics::BaseSemantics::RiscOperatorsPtr &ops)
Property: Semantic state used during delayed expansion.
Position within a command-line.
Sawyer::SharedPointer< Expansion > Ptr
Shared-ownership pointer to an Expansion.
Base class parsing a value from input.
const std::string & title() const
Property: Title to use for documentation.
const Sawyer::Container::BitVector & bits() const
Bit vector for numeric constants.
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 SmtSolver::Ptr &solver)
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.
void appendAtomExpansion(const AtomExpansion::Ptr &)
Append a new functor for expanding atoms into symbolic expressions.
const AtomTable & atomTable() const
Return all atom expansion functors.