ROSE  0.11.2.0
BinarySymbolicExprParser.h
1 #ifndef ROSE_BinaryAnalysis_SymbolicExprParser_H
2 #define ROSE_BinaryAnalysis_SymbolicExprParser_H
3 #include <rosePublicConfig.h>
4 #ifdef ROSE_BUILD_BINARY_ANALYSIS_SUPPORT
5 
6 #include <BaseSemantics2.h>
7 #include <BinarySymbolicExpr.h>
8 #include <Sawyer/BiMap.h>
9 #include <Sawyer/CommandLine.h>
10 #include <Sawyer/Message.h>
11 #include <Sawyer/SharedPointer.h>
12 
13 namespace Rose {
14 namespace BinaryAnalysis {
15 
30 public:
32 
33  class SyntaxError: public std::runtime_error {
34  public:
35  std::string inputName;
36  unsigned lineNumber;
37  unsigned columnNumber;
38  SyntaxError(const std::string &mesg, const std::string &inputName, unsigned lineNumber, unsigned columnNumber);
39  ~SyntaxError() throw () {}
40  void print(std::ostream&) const;
41  };
42 
44  class SubstitutionError: public std::runtime_error {
45  public:
46  SubstitutionError(const std::string &mesg)
47  : std::runtime_error(mesg) {}
48  ~SubstitutionError() throw () {}
49  void print(std::ostream&) const;
50  };
51 
53 
54  class Token {
55  public:
57  enum Type {
58  NONE = 0,
64  };
65 
66  private:
67  Type tokenType_;
68  std::string lexeme_; // lexeme
69  SymbolicExpr::Type exprType_; // type for expression
70  Sawyer::Container::BitVector bits_; // bits representing constant terms
71  unsigned lineNumber_, columnNumber_; // for start of token
72 
73  public:
76  : tokenType_(NONE), lineNumber_(0), columnNumber_(0) {}
77 
79  Token(Type tokenType, const SymbolicExpr::Type &exprType, const std::string &lexeme,
80  unsigned lineNumber, unsigned columnNumber)
81  : tokenType_(tokenType), lexeme_(lexeme), exprType_(exprType),
82  lineNumber_(lineNumber), columnNumber_(columnNumber) {
83  ASSERT_forbid(BITVECTOR == tokenType);
84  }
85 
87  Token(const Sawyer::Container::BitVector &bv, const SymbolicExpr::Type &exprType, const std::string &lexeme,
88  unsigned lineNumber, unsigned columnNumber)
89  : tokenType_(BITVECTOR), lexeme_(lexeme), exprType_(exprType), bits_(bv),
90  lineNumber_(lineNumber), columnNumber_(columnNumber) {
91  ASSERT_require(exprType.nBits() == bv.size());
92  }
93 
95  SymbolicExprParser::SyntaxError syntaxError(const std::string &mesg, const std::string &name="input") const {
96  return SymbolicExprParser::SyntaxError(mesg, name, lineNumber_, columnNumber_);
97  }
98 
100  Type tokenType() const { return tokenType_; }
101 
103  const std::string &lexeme() const { return lexeme_; }
104 
106  SymbolicExpr::Type exprType() const { return exprType_; }
107 
109  const Sawyer::Container::BitVector& bits() const { return bits_; }
110 
112  unsigned lineNumber() const { return lineNumber_; }
113 
115  unsigned columnNumber() const { return columnNumber_; }
116  };
117 
119 
123  class TokenStream {
124  std::istream &input_;
125  std::string name_;
126  unsigned lineNumber_, columnNumber_;
127  const Token endToken_;
128  std::vector<Token> tokens_;
129  int readAhead_;
130 
131  public:
136  explicit TokenStream(std::istream &input, const std::string &name="input",
137  unsigned lineNumber=1, unsigned columnNumber=0)
138  : input_(input), name_(name), lineNumber_(lineNumber), columnNumber_(columnNumber), readAhead_(EOF) {
139  init();
140  }
141 
143  const std::string& name() const { return name_; }
144 
146  unsigned lineNumber() const { return lineNumber_; }
147 
149  unsigned columnNumber() const { return columnNumber_; }
150 
152  const Token& operator[](size_t idx);
153 
155  void shift(size_t n=1);
156 
158  int nextCharacter();
159 
162  int consumeCharacter();
163 
165  void consumeWhiteSpace();
166 
168  int consumeEscapeSequence();
169 
172  void consumeInlineComment();
173 
176 
183  std::string consumeTerm();
184 
190 
193  Token scan();
194 
195  private:
196  void init();
197 
198  // Try to fill the token vector so it contains tokens up through at least [idx]
199  void fillTokenList(size_t idx);
200  };
201 
203 
205  std::string title_;
206  std::string docString_;
207  public:
208  virtual ~Expansion() {}
209 
212 
216  const std::string& title() const { return title_; }
217  void title(const std::string &s) { title_ = s; }
225  const std::string& docString() const { return docString_; }
226  void docString(const std::string &s) { docString_ = s; }
239  return src;
240  }
241  };
242 
244 
245  class AtomExpansion: public Expansion {
246  public:
249 
256  virtual SymbolicExpr::Ptr immediateExpansion(const Token &name) = 0;
257  };
258 
260  typedef std::vector<AtomExpansion::Ptr> AtomTable;
261 
263 
264  class OperatorExpansion: public Expansion {
265  public:
268 
269  protected:
270  SmtSolverPtr solver; // may be null
271 
272  explicit OperatorExpansion(const SmtSolverPtr &solver);
273 
274  public:
275  virtual ~OperatorExpansion();
276 
280  virtual SymbolicExpr::Ptr immediateExpansion(const Token &name, const SymbolicExpr::Nodes &operands) = 0;
281  };
282 
284  typedef std::vector<OperatorExpansion::Ptr> OperatorTable;
285 
287 
293  public:
296 
297  private:
299 
300  protected:
302  : ops_(ops) {}
303 
304  public:
307 
308  // internal
310  };
311 
313 
321  public:
324 
325  // internal
327 
328  private:
329  const RegisterDictionary *regdict_;
330  RegToVarMap reg2var_;
332 
333  protected:
335  : regdict_(regdict) {}
336 
337  public:
339  static Ptr instance(const RegisterDictionary*);
340 
348  return ops_;
349  }
351  ops_ = ops;
352  }
355  // internal
357  SymbolicExpr::Ptr delayedExpansion(const SymbolicExpr::Ptr&, const SymbolicExprParser*) ROSE_OVERRIDE;
358  };
359 
361 
366  public:
369 
370  // internal
371  typedef Sawyer::Container::Map<SymbolicExpr::Ptr /*placeholder*/, SymbolicExpr::Ptr /*address*/> ExprToMem;
372 
373  private:
374  ExprToMem exprToMem_;
376 
377  protected:
378  MemorySubstituter(const SmtSolver::Ptr &solver /*=NULL*/)
379  : OperatorExpansion(solver) {}
380 
381  public:
383  static Ptr instance(const SmtSolver::Ptr &solver /*=NULL*/);
384 
392  return ops_;
393  }
395  ops_ = ops;
396  }
399  // internal
400  virtual SymbolicExpr::Ptr immediateExpansion(const Token &name, const SymbolicExpr::Nodes &operands) ROSE_OVERRIDE;
401  virtual SymbolicExpr::Ptr delayedExpansion(const SymbolicExpr::Ptr&, const SymbolicExprParser*) ROSE_OVERRIDE;
402  };
403 
405 
410  class TermPlaceholders: public AtomExpansion {
411  public:
414 
417 
418  private:
419  NameToVarMap name2var_;
420 
421  protected:
422  TermPlaceholders() {}
423 
424  public:
426  static Ptr instance();
427 
429  const NameToVarMap& map() const { return name2var_; }
430 
431  // internal
432  SymbolicExpr::Ptr immediateExpansion(const SymbolicExprParser::Token&) ROSE_OVERRIDE;
433  };
434 
436 
440  class SymbolicExprCmdlineParser: public Sawyer::CommandLine::ValueParser {
441  protected:
444  : Sawyer::CommandLine::ValueParser(valueSaver) {}
445 
446  public:
449 
450  static Ptr instance() {
451  return Ptr(new SymbolicExprCmdlineParser);
452  }
453 
454  static Ptr instance(const Sawyer::CommandLine::ValueSaver::Ptr &valueSaver) {
455  return Ptr(new SymbolicExprCmdlineParser(valueSaver));
456  }
457 
458  static std::string docString();
459 
460  private:
461  virtual Sawyer::CommandLine::ParsedValue operator()(const char *input, const char **rest,
462  const Sawyer::CommandLine::Location &loc) ROSE_OVERRIDE;
463  };
464 
465  static SymbolicExprCmdlineParser::Ptr symbolicExprParser(SymbolicExpr::Ptr &storage);
466  static SymbolicExprCmdlineParser::Ptr symbolicExprParser(std::vector<SymbolicExpr::Ptr> &storage);
467  static SymbolicExprCmdlineParser::Ptr symbolicExprParser();
468 
470 private:
471  AtomTable atomTable_;
472  OperatorTable operatorTable_;
473  SmtSolverPtr solver_; // optional solver for simplifications
474 
475 public:
476  static Sawyer::Message::Facility mlog;
477 
478 public:
481 
485  explicit SymbolicExprParser(const SmtSolverPtr &solver);
486 
488 
489  // used internally to initialize the diagnostics system
490  static void initDiagnostics();
491 
496  SymbolicExpr::Ptr parse(const std::string&, const std::string &inputName="string");
497 
501  SymbolicExpr::Ptr parse(std::istream &input, const std::string &filename,
502  unsigned lineNumber=1, unsigned columnNumber=0);
503 
507  SymbolicExpr::Ptr parse(TokenStream&);
508 
511 
514 
518  const AtomTable& atomTable() const { return atomTable_; }
519  AtomTable& atomTable() { return atomTable_; }
525  const OperatorTable& operatorTable() const { return operatorTable_; }
526  OperatorTable& operatorTable() { return operatorTable_; }
533  std::string docString() const;
534 
552  SymbolicExpr::Ptr delayedExpansion(const SymbolicExpr::Ptr&) const;
553 
554 private:
555  void init();
556 };
557 
558 std::ostream& operator<<(std::ostream&, const SymbolicExprParser::SyntaxError&);
559 std::ostream& operator<<(std::ostream&, const SymbolicExprParser::SubstitutionError&);
560 
561 } // namespace
562 } // namespace
563 
564 #endif
565 #endif
const OperatorTable & operatorTable() const
Return all operator expansion functors.
Virtual base class for atom and operator expansion.
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.
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.
Collection of streams.
Definition: Message.h:1599
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.
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.
Sawyer::SharedPointer< class SmtSolver > SmtSolverPtr
Reference-counting pointer for SMT solvers.
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.
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.
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.
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:38
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.
static Ptr instance(const InstructionSemantics2::BaseSemantics::RiscOperatorsPtr &)
Allocating constructor.
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.