ROSE  0.9.10.200
BinarySymbolicExprParser.h
1 #ifndef ROSE_BinaryAnalysis_SymbolicExprParser_H
2 #define ROSE_BinaryAnalysis_SymbolicExprParser_H
3 
4 #include <BaseSemantics2.h>
5 #include <BinarySymbolicExpr.h>
6 #include <Sawyer/BiMap.h>
7 #include <Sawyer/CommandLine.h>
8 #include <Sawyer/Message.h>
9 #include <Sawyer/SharedPointer.h>
10 
11 namespace Rose {
12 namespace BinaryAnalysis {
13 
28 public:
30 
31  class SyntaxError: public std::runtime_error {
32  public:
33  std::string inputName;
34  unsigned lineNumber;
35  unsigned columnNumber;
36  SyntaxError(const std::string &mesg, const std::string &inputName, unsigned lineNumber, unsigned columnNumber);
37  ~SyntaxError() throw () {}
38  void print(std::ostream&) const;
39  };
40 
42  class SubstitutionError: public std::runtime_error {
43  public:
44  SubstitutionError(const std::string &mesg)
45  : std::runtime_error(mesg) {}
46  ~SubstitutionError() throw () {}
47  void print(std::ostream&) const;
48  };
49 
51 
52  class Token {
53  public:
55  enum Type {
56  NONE = 0,
62  };
63 
64  private:
65  Type type_;
66  std::string lexeme_; // lexeme
67  size_t width_; // width of value in bits, as in "[N]"
68  size_t width2_; // second width, as M in "[N->M]"
69  Sawyer::Container::BitVector bits_; // bits representing constant terms
70  unsigned lineNumber_, columnNumber_; // for start of token
71 
72  public:
75  : type_(NONE), width_(0), width2_(0), lineNumber_(0), columnNumber_(0) {}
76 
78  Token(Type type, size_t width, const std::string &lexeme, unsigned lineNumber, unsigned columnNumber)
79  : type_(type), lexeme_(lexeme), width_(width), width2_(0),
80  lineNumber_(lineNumber), columnNumber_(columnNumber) {
81  ASSERT_forbid(BITVECTOR==type);
82  }
83 
85  Token(Type type, size_t width, size_t width2, const std::string &lexeme, unsigned lineNumber, unsigned columnNumber)
86  : type_(type), lexeme_(lexeme), width_(width), width2_(width2),
87  lineNumber_(lineNumber), columnNumber_(columnNumber) {
88  ASSERT_forbid(BITVECTOR==type);
89  }
90 
92  Token(const Sawyer::Container::BitVector &bv, const std::string &lexeme, unsigned lineNumber, unsigned columnNumber)
93  : type_(BITVECTOR), lexeme_(lexeme), width_(bv.size()), width2_(0), bits_(bv),
94  lineNumber_(lineNumber), columnNumber_(columnNumber) {}
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 type() const { return type_; }
103 
105  const std::string &lexeme() const { return lexeme_; }
106 
108  size_t width() const { return width_; }
109 
111  size_t width2() const { return width2_; }
112 
114  const Sawyer::Container::BitVector& bits() const { return bits_; }
115 
117  unsigned lineNumber() const { return lineNumber_; }
118 
120  unsigned columnNumber() const { return columnNumber_; }
121  };
122 
124 
128  class TokenStream {
129  std::istream &input_;
130  std::string name_;
131  unsigned lineNumber_, columnNumber_;
132  const Token endToken_;
133  std::vector<Token> tokens_;
134  int readAhead_;
135 
136  public:
141  explicit TokenStream(std::istream &input, const std::string &name="input",
142  unsigned lineNumber=1, unsigned columnNumber=0)
143  : input_(input), name_(name), lineNumber_(lineNumber), columnNumber_(columnNumber), readAhead_(EOF) {
144  init();
145  }
146 
148  const std::string& name() const { return name_; }
149 
151  unsigned lineNumber() const { return lineNumber_; }
152 
154  unsigned columnNumber() const { return columnNumber_; }
155 
157  const Token& operator[](size_t idx);
158 
160  void shift(size_t n=1);
161 
163  int nextCharacter();
164 
167  int consumeCharacter();
168 
170  void consumeWhiteSpace();
171 
173  int consumeEscapeSequence();
174 
177  void consumeInlineComment();
178 
181 
188  std::string consumeTerm();
189 
191  size_t consumeWidth();
192 
195  size_t consumeWidth(size_t &width2 /*out*/);
196 
199  Token scan();
200 
201  private:
202  void init();
203 
204  // Try to fill the token vector so it contains tokens up through at least [idx]
205  void fillTokenList(size_t idx);
206  };
207 
209 
211  std::string title_;
212  std::string docString_;
213  public:
214  virtual ~Expansion() {}
215 
218 
222  const std::string& title() const { return title_; }
223  void title(const std::string &s) { title_ = s; }
231  const std::string& docString() const { return docString_; }
232  void docString(const std::string &s) { docString_ = s; }
245  return src;
246  }
247  };
248 
250 
251  class AtomExpansion: public Expansion {
252  public:
255 
262  virtual SymbolicExpr::Ptr immediateExpansion(const Token &name) = 0;
263  };
264 
266  typedef std::vector<AtomExpansion::Ptr> AtomTable;
267 
269 
270  class OperatorExpansion: public Expansion {
271  public:
274 
275  protected:
276  SmtSolverPtr solver; // may be null
277 
278  explicit OperatorExpansion(const SmtSolverPtr &solver);
279 
280  public:
281  virtual ~OperatorExpansion();
282 
286  virtual SymbolicExpr::Ptr immediateExpansion(const Token &name, const SymbolicExpr::Nodes &operands) = 0;
287  };
288 
290  typedef std::vector<OperatorExpansion::Ptr> OperatorTable;
291 
293 
299  public:
302 
303  private:
305 
306  protected:
308  : ops_(ops) {}
309 
310  public:
313 
314  // internal
316  };
317 
319 
327  public:
330 
331  // internal
333 
334  private:
335  const RegisterDictionary *regdict_;
336  RegToVarMap reg2var_;
338 
339  protected:
341  : regdict_(regdict) {}
342 
343  public:
345  static Ptr instance(const RegisterDictionary*);
346 
354  return ops_;
355  }
357  ops_ = ops;
358  }
361  // internal
363  SymbolicExpr::Ptr delayedExpansion(const SymbolicExpr::Ptr&, const SymbolicExprParser*) ROSE_OVERRIDE;
364  };
365 
367 
372  public:
375 
376  // internal
377  typedef Sawyer::Container::Map<SymbolicExpr::Ptr /*placeholder*/, SymbolicExpr::Ptr /*address*/> ExprToMem;
378 
379  private:
380  ExprToMem exprToMem_;
382 
383  protected:
384  MemorySubstituter(const SmtSolver::Ptr &solver /*=NULL*/)
385  : OperatorExpansion(solver) {}
386 
387  public:
389  static Ptr instance(const SmtSolver::Ptr &solver /*=NULL*/);
390 
398  return ops_;
399  }
401  ops_ = ops;
402  }
405  // internal
406  virtual SymbolicExpr::Ptr immediateExpansion(const Token &name, const SymbolicExpr::Nodes &operands);
407  virtual SymbolicExpr::Ptr delayedExpansion(const SymbolicExpr::Ptr&, const SymbolicExprParser*) ROSE_OVERRIDE;
408  };
409 
411 
416  class TermPlaceholders: public AtomExpansion {
417  public:
420 
423 
424  private:
425  NameToVarMap name2var_;
426 
427  protected:
428  TermPlaceholders() {}
429 
430  public:
432  static Ptr instance();
433 
435  const NameToVarMap& map() const { return name2var_; }
436 
437  // internal
438  SymbolicExpr::Ptr immediateExpansion(const SymbolicExprParser::Token&) ROSE_OVERRIDE;
439  };
440 
442 
446  class SymbolicExprCmdlineParser: public Sawyer::CommandLine::ValueParser {
447  protected:
450  : Sawyer::CommandLine::ValueParser(valueSaver) {}
451 
452  public:
455 
456  static Ptr instance() {
457  return Ptr(new SymbolicExprCmdlineParser);
458  }
459 
460  static Ptr instance(const Sawyer::CommandLine::ValueSaver::Ptr &valueSaver) {
461  return Ptr(new SymbolicExprCmdlineParser(valueSaver));
462  }
463 
464  static std::string docString();
465 
466  private:
467  virtual Sawyer::CommandLine::ParsedValue operator()(const char *input, const char **rest,
468  const Sawyer::CommandLine::Location &loc) ROSE_OVERRIDE;
469  };
470 
471  static SymbolicExprCmdlineParser::Ptr symbolicExprParser(SymbolicExpr::Ptr &storage);
472  static SymbolicExprCmdlineParser::Ptr symbolicExprParser(std::vector<SymbolicExpr::Ptr> &storage);
473  static SymbolicExprCmdlineParser::Ptr symbolicExprParser();
474 
476 private:
477  AtomTable atomTable_;
478  OperatorTable operatorTable_;
479  SmtSolverPtr solver_; // optional solver for simplifications
480 
481 public:
482  static Sawyer::Message::Facility mlog;
483 
484 public:
487 
491  explicit SymbolicExprParser(const SmtSolverPtr &solver);
492 
494 
495  // used internally to initialize the diagnostics system
496  static void initDiagnostics();
497 
502  SymbolicExpr::Ptr parse(const std::string&, const std::string &inputName="string");
503 
507  SymbolicExpr::Ptr parse(std::istream &input, const std::string &filename,
508  unsigned lineNumber=1, unsigned columnNumber=0);
509 
513  SymbolicExpr::Ptr parse(TokenStream&);
514 
517 
520 
524  const AtomTable& atomTable() const { return atomTable_; }
525  AtomTable& atomTable() { return atomTable_; }
531  const OperatorTable& operatorTable() const { return operatorTable_; }
532  OperatorTable& operatorTable() { return operatorTable_; }
539  std::string docString() const;
540 
558  SymbolicExpr::Ptr delayedExpansion(const SymbolicExpr::Ptr&) const;
559 
560 private:
561  void init();
562 };
563 
564 std::ostream& operator<<(std::ostream&, const SymbolicExprParser::SyntaxError&);
565 std::ostream& operator<<(std::ostream&, const SymbolicExprParser::SubstitutionError&);
566 
567 } // namespace
568 } // namespace
569 
570 #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.
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.
Token(Type type, size_t width, const std::string &lexeme, unsigned lineNumber, unsigned columnNumber)
Constructs a specific token from a string.
Collection of streams.
Definition: Message.h:1579
int nextCharacter()
Returns the next character.
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.
size_t consumeWidth()
Parse and consume a width specification.
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.
int consumeCharacter()
Consume the next character.
Reference-counting smart pointer.
Definition: SharedPointer.h:67
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()
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.
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.
boost::shared_ptr< class RiscOperators > RiscOperatorsPtr
Shared-ownership pointer to a RISC operators object.
std::string consumeTerm()
Parse and consume a term.
size_t width() const
Width of expression in bits.
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.
Token(const Sawyer::Container::BitVector &bv, const std::string &lexeme, unsigned lineNumber, unsigned columnNumber)
Construct a token for a numeric constant.
void defineRegisters(const InstructionSemantics2::BaseSemantics::RiscOperatorsPtr &)
Add definitions for registers.
Defines registers available for a particular architecture.
Definition: Registers.h:32
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.
Token(Type type, size_t width, size_t width2, const std::string &lexeme, unsigned lineNumber, unsigned columnNumber)
Constructs a specific token from a string.
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.
size_t width2() const
Width of domain (address) in bits for memory states.
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.
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.