ROSE  0.9.10.91
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/SharedPointer.h>
9 
10 namespace Rose {
11 namespace BinaryAnalysis {
12 
27 public:
29  class SyntaxError: public std::runtime_error {
30  public:
31  std::string inputName;
32  unsigned lineNumber;
33  unsigned columnNumber;
34  void print(std::ostream&) const;
35  SyntaxError(const std::string &mesg, const std::string &inputName, unsigned lineNumber, unsigned columnNumber);
36  ~SyntaxError() throw () {}
37  };
38 
40  class Token {
41  public:
43  enum Type {
44  NONE = 0,
50  };
51 
52  private:
53  Type type_;
54  std::string lexeme_; // lexeme
55  size_t width_; // width of value in bits, as in "[N]"
56  size_t width2_; // second width, as M in "[N->M]"
57  Sawyer::Container::BitVector bits_; // bits representing constant terms
58  unsigned lineNumber_, columnNumber_; // for start of token
59 
60  public:
63  : type_(NONE), width_(0), width2_(0), lineNumber_(0), columnNumber_(0) {}
64 
66  Token(Type type, size_t width, const std::string &lexeme, unsigned lineNumber, unsigned columnNumber)
67  : type_(type), lexeme_(lexeme), width_(width), width2_(0),
68  lineNumber_(lineNumber), columnNumber_(columnNumber) {
69  ASSERT_forbid(BITVECTOR==type);
70  }
71 
73  Token(Type type, size_t width, size_t width2, const std::string &lexeme, unsigned lineNumber, unsigned columnNumber)
74  : type_(type), lexeme_(lexeme), width_(width), width2_(width2),
75  lineNumber_(lineNumber), columnNumber_(columnNumber) {
76  ASSERT_forbid(BITVECTOR==type);
77  }
78 
80  Token(const Sawyer::Container::BitVector &bv, const std::string &lexeme, unsigned lineNumber, unsigned columnNumber)
81  : type_(BITVECTOR), lexeme_(lexeme), width_(bv.size()), width2_(0), bits_(bv),
82  lineNumber_(lineNumber), columnNumber_(columnNumber) {}
83 
85  SymbolicExprParser::SyntaxError syntaxError(const std::string &mesg, const std::string &name="input") const {
86  return SymbolicExprParser::SyntaxError(mesg, name, lineNumber_, columnNumber_);
87  }
88 
90  Type type() const { return type_; }
91 
93  const std::string &lexeme() const { return lexeme_; }
94 
96  size_t width() const { return width_; }
97 
99  size_t width2() const { return width2_; }
100 
102  const Sawyer::Container::BitVector& bits() const { return bits_; }
103 
105  unsigned lineNumber() const { return lineNumber_; }
106 
108  unsigned columnNumber() const { return columnNumber_; }
109  };
110 
115  class TokenStream {
116  std::istream &input_;
117  std::string name_;
118  unsigned lineNumber_, columnNumber_;
119  const Token endToken_;
120  std::vector<Token> tokens_;
121  int readAhead_;
122 
123  public:
128  explicit TokenStream(std::istream &input, const std::string &name="input",
129  unsigned lineNumber=1, unsigned columnNumber=0)
130  : input_(input), name_(name), lineNumber_(lineNumber), columnNumber_(columnNumber), readAhead_(EOF) {
131  init();
132  }
133 
135  const std::string& name() const { return name_; }
136 
138  unsigned lineNumber() const { return lineNumber_; }
139 
141  unsigned columnNumber() const { return columnNumber_; }
142 
144  const Token& operator[](size_t idx);
145 
147  void shift(size_t n=1);
148 
150  int nextCharacter();
151 
154  int consumeCharacter();
155 
157  void consumeWhiteSpace();
158 
160  int consumeEscapeSequence();
161 
164  void consumeInlineComment();
165 
168 
175  std::string consumeTerm();
176 
178  size_t consumeWidth();
179 
182  size_t consumeWidth(size_t &width2 /*out*/);
183 
186  Token scan();
187 
188  private:
189  void init();
190 
191  // Try to fill the token vector so it contains tokens up through at least [idx]
192  void fillTokenList(size_t idx);
193  };
194 
197  std::string title_;
198  std::string docString_;
199  public:
200  virtual ~Expansion() {}
201 
204 
208  const std::string& title() const { return title_; }
209  void title(const std::string &s) { title_ = s; }
217  const std::string& docString() const { return docString_; }
218  void docString(const std::string &s) { docString_ = s; }
220  };
221 
223  class AtomExpansion: public Expansion {
224  public:
227 
231  virtual SymbolicExpr::Ptr operator()(const Token &name) = 0;
232  };
233 
235  class OperatorExpansion: public Expansion {
236  public:
239 
240  protected:
241  SmtSolverPtr solver; // may be null
242 
243  explicit OperatorExpansion(const SmtSolverPtr &solver);
244 
245  public:
246  virtual ~OperatorExpansion();
247 
251  virtual SymbolicExpr::Ptr operator()(const Token &name, const SymbolicExpr::Nodes &operands) = 0;
252  };
253 
260  public:
263 
264  private:
266 
267  protected:
269  : ops_(ops) {}
270 
271  public:
274 
275  // internal
277  };
278 
287  public:
290 
291  // internal
293 
294  private:
295  const RegisterDictionary *regdict_;
296  RegToVarMap reg2var_;
297 
298  protected:
300  : regdict_(regdict) {}
301 
302  public:
304  static Ptr instance(const RegisterDictionary*);
305 
311  SymbolicExpr::Ptr substitute(const SymbolicExpr::Ptr&,
313 
314  // internal
316  };
317 
323  class TermPlaceholders: public AtomExpansion {
324  public:
327 
330 
331  private:
332  NameToVarMap name2var_;
333 
334  protected:
335  TermPlaceholders() {}
336 
337  public:
339  static Ptr instance();
340 
342  const NameToVarMap& map() const { return name2var_; }
343 
344  // internal
346  };
347 
349  typedef std::vector<AtomExpansion::Ptr> AtomTable;
350 
352  typedef std::vector<OperatorExpansion::Ptr> OperatorTable;
353 
358  class SymbolicExprCmdlineParser: public Sawyer::CommandLine::ValueParser {
359  protected:
362  : Sawyer::CommandLine::ValueParser(valueSaver) {}
363 
364  public:
367 
368  static Ptr instance() {
369  return Ptr(new SymbolicExprCmdlineParser);
370  }
371 
372  static Ptr instance(const Sawyer::CommandLine::ValueSaver::Ptr &valueSaver) {
373  return Ptr(new SymbolicExprCmdlineParser(valueSaver));
374  }
375 
376  static std::string docString();
377 
378  private:
379  virtual Sawyer::CommandLine::ParsedValue operator()(const char *input, const char **rest,
380  const Sawyer::CommandLine::Location &loc) ROSE_OVERRIDE;
381  };
382 
383  static SymbolicExprCmdlineParser::Ptr symbolicExprParser(SymbolicExpr::Ptr &storage);
384  static SymbolicExprCmdlineParser::Ptr symbolicExprParser(std::vector<SymbolicExpr::Ptr> &storage);
385  static SymbolicExprCmdlineParser::Ptr symbolicExprParser();
386 
387 private:
388  AtomTable atomTable_;
389  OperatorTable operatorTable_;
390  SmtSolverPtr solver_; // optional solver for simplifications
391 
392 public:
395 
399  explicit SymbolicExprParser(const SmtSolverPtr &solver);
400 
402 
407  SymbolicExpr::Ptr parse(const std::string&, const std::string &inputName="string");
408 
412  SymbolicExpr::Ptr parse(std::istream &input, const std::string &filename,
413  unsigned lineNumber=1, unsigned columnNumber=0);
414 
418  SymbolicExpr::Ptr parse(TokenStream&);
419 
422 
425 
429  const AtomTable& atomTable() const { return atomTable_; }
430  AtomTable& atomTable() { return atomTable_; }
436  const OperatorTable& operatorTable() const { return operatorTable_; }
437  OperatorTable& operatorTable() { return operatorTable_; }
444  std::string docString() const;
445 
460 private:
461  void init();
462 };
463 
464 std::ostream& operator<<(std::ostream&, const SymbolicExprParser::SyntaxError&);
465 
466 } // namespace
467 } // namespace
468 
469 #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.
Sawyer::SharedPointer< Node > Ptr
Shared-ownership pointer to an expression Node.
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.
SymbolicExpr::Ptr operator()(const SymbolicExprParser::Token &) ROSE_OVERRIDE
Operator to expand the symbol into an expression tree.
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.
STL namespace.
unsigned columnNumber() const
Current column number.
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:34
const std::string & name() const
Name of this input stream.
Name space for the entire library.
Definition: Access.h:13
virtual SymbolicExpr::Ptr operator()(const Token &name, const SymbolicExpr::Nodes &operands)=0
Operator to expand a list into an expression tree.
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.
virtual SymbolicExpr::Ptr operator()(const Token &name)=0
Operator to expand the symbol into an expression tree.
void docString(const std::string &s)
Property: Documentation string.
Information about a parsed switch value.
AtomTable & atomTable()
Return all atom expansion functors.
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:22
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.
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.
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.
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.
static Ptr instance(const InstructionSemantics2::BaseSemantics::RiscOperatorsPtr &)
Allocating constructor.
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.
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.