parser.go

Documentation: github.com/chenzhuoyu/iasm/expr

     1  package expr
     2  
     3  import (
     4      `strconv`
     5      `unicode`
     6      `unsafe`
     7  )
     8  
     9  type _TokenKind uint8
    10  
    11  const (
    12      _T_end _TokenKind = iota + 1
    13      _T_int
    14      _T_punc
    15      _T_name
    16  )
    17  
    18  const (
    19      _OP2 = 0x80
    20      _POW = _OP2 | '*'
    21      _SHL = _OP2 | '<'
    22      _SHR = _OP2 | '>'
    23  )
    24  
    25  type _Slice struct {
    26      p unsafe.Pointer
    27      n int
    28      c int
    29  }
    30  
    31  type _Token struct {
    32      pos int
    33      ptr *rune
    34      u64 uint64
    35      tag _TokenKind
    36  }
    37  
    38  func (self _Token) str() (v string) {
    39      return string(self.rbuf())
    40  }
    41  
    42  func (self _Token) rbuf() (v []rune) {
    43      (*_Slice)(unsafe.Pointer(&v)).c = int(self.u64)
    44      (*_Slice)(unsafe.Pointer(&v)).n = int(self.u64)
    45      (*_Slice)(unsafe.Pointer(&v)).p = unsafe.Pointer(self.ptr)
    46      return
    47  }
    48  
    49  func tokenEnd(p int) _Token {
    50      return _Token {
    51          pos: p,
    52          tag: _T_end,
    53      }
    54  }
    55  
    56  func tokenInt(p int, v uint64) _Token {
    57      return _Token {
    58          pos: p,
    59          u64: v,
    60          tag: _T_int,
    61      }
    62  }
    63  
    64  func tokenPunc(p int, v rune) _Token {
    65      return _Token {
    66          pos: p,
    67          tag: _T_punc,
    68          u64: uint64(v),
    69      }
    70  }
    71  
    72  func tokenName(p int, v []rune) _Token {
    73      return _Token {
    74          pos: p,
    75          ptr: &v[0],
    76          tag: _T_name,
    77          u64: uint64(len(v)),
    78      }
    79  }
    80  
    81  // Repository represents a repository of Term's.
    82  type Repository interface {
    83      Get(name string) (Term, error)
    84  }
    85  
    86  // Parser parses an expression string to it's AST representation.
    87  type Parser struct {
    88      pos int
    89      src []rune
    90  }
    91  
    92  var binaryOps = [...]func(*Expr, *Expr) *Expr {
    93      '+'  : (*Expr).Add,
    94      '-'  : (*Expr).Sub,
    95      '*'  : (*Expr).Mul,
    96      '/'  : (*Expr).Div,
    97      '%'  : (*Expr).Mod,
    98      '&'  : (*Expr).And,
    99      '^'  : (*Expr).Xor,
   100      '|'  : (*Expr).Or,
   101      _SHL : (*Expr).Shl,
   102      _SHR : (*Expr).Shr,
   103      _POW : (*Expr).Pow,
   104  }
   105  
   106  var precedence = [...]map[int]bool {
   107      {_SHL: true, _SHR: true},
   108      {'|' : true},
   109      {'^' : true},
   110      {'&' : true},
   111      {'+' : true, '-': true},
   112      {'*' : true, '/': true, '%': true},
   113      {_POW: true},
   114  }
   115  
   116  func (self *Parser) ch() rune {
   117      return self.src[self.pos]
   118  }
   119  
   120  func (self *Parser) eof() bool {
   121      return self.pos >= len(self.src)
   122  }
   123  
   124  func (self *Parser) rch() (v rune) {
   125      v, self.pos = self.src[self.pos], self.pos + 1
   126      return
   127  }
   128  
   129  func (self *Parser) hex(ss []rune) bool {
   130      if len(ss) == 1 && ss[0] == '0' {
   131          return unicode.ToLower(self.ch()) == 'x'
   132      } else if len(ss) <= 1 || unicode.ToLower(ss[1]) != 'x' {
   133          return unicode.IsDigit(self.ch())
   134      } else {
   135          return ishexdigit(self.ch())
   136      }
   137  }
   138  
   139  func (self *Parser) int(p int, ss []rune) (_Token, error) {
   140      var err error
   141      var val uint64
   142  
   143      /* find all the digits */
   144      for !self.eof() && self.hex(ss) {
   145          ss = append(ss, self.rch())
   146      }
   147  
   148      /* parse the value */
   149      if val, err = strconv.ParseUint(string(ss), 0, 64); err != nil {
   150          return _Token{}, err
   151      } else {
   152          return tokenInt(p, val), nil
   153      }
   154  }
   155  
   156  func (self *Parser) name(p int, ss []rune) _Token {
   157      for !self.eof() && isident(self.ch()) { ss = append(ss, self.rch()) }
   158      return tokenName(p, ss)
   159  }
   160  
   161  func (self *Parser) read(p int, ch rune) (_Token, error) {
   162      if isdigit(ch) {
   163          return self.int(p, []rune { ch })
   164      } else if isident0(ch) {
   165          return self.name(p, []rune { ch }), nil
   166      } else if isop2ch(ch) && !self.eof() && self.ch() == ch {
   167          return tokenPunc(p, _OP2 | self.rch()), nil
   168      } else if isop1ch(ch) {
   169          return tokenPunc(p, ch), nil
   170      } else {
   171          return _Token{}, newSyntaxError(self.pos, "invalid character " + strconv.QuoteRuneToASCII(ch))
   172      }
   173  }
   174  
   175  func (self *Parser) next() (_Token, error) {
   176      for {
   177          var p int
   178          var c rune
   179  
   180          /* check for EOF */
   181          if self.eof() {
   182              return tokenEnd(self.pos), nil
   183          }
   184  
   185          /* read the next char */
   186          p = self.pos
   187          c = self.rch()
   188  
   189          /* parse the token if not a space */
   190          if !unicode.IsSpace(c) {
   191              return self.read(p, c)
   192          }
   193      }
   194  }
   195  
   196  func (self *Parser) grab(tk _Token, repo Repository) (*Expr, error) {
   197      if repo == nil {
   198          return nil, newSyntaxError(tk.pos, "unresolved symbol: " + tk.str())
   199      } else if term, err := repo.Get(tk.str()); err != nil {
   200          return nil, err
   201      } else {
   202          return Ref(term), nil
   203      }
   204  }
   205  
   206  func (self *Parser) nest(nest int, repo Repository) (*Expr, error) {
   207      var err error
   208      var ret *Expr
   209      var ntk _Token
   210  
   211      /* evaluate the nested expression */
   212      if ret, err = self.expr(0, nest + 1, repo); err != nil {
   213          return nil, err
   214      }
   215  
   216      /* must follows with a ')' */
   217      if ntk, err = self.next(); err != nil {
   218          return nil, err
   219      } else if ntk.tag != _T_punc || ntk.u64 != ')' {
   220          return nil, newSyntaxError(ntk.pos, "')' expected")
   221      } else {
   222          return ret, nil
   223      }
   224  }
   225  
   226  func (self *Parser) unit(nest int, repo Repository) (*Expr, error) {
   227      if tk, err := self.next(); err != nil {
   228          return nil, err
   229      } else if tk.tag == _T_int {
   230          return Int(int64(tk.u64)), nil
   231      } else if tk.tag == _T_name {
   232          return self.grab(tk, repo)
   233      } else if tk.tag == _T_punc && tk.u64 == '(' {
   234          return self.nest(nest, repo)
   235      } else if tk.tag == _T_punc && tk.u64 == '+' {
   236          return self.unit(nest, repo)
   237      } else if tk.tag == _T_punc && tk.u64 == '-' {
   238          return neg2(self.unit(nest, repo))
   239      } else if tk.tag == _T_punc && tk.u64 == '~' {
   240          return not2(self.unit(nest, repo))
   241      } else {
   242          return nil, newSyntaxError(tk.pos, "integer, unary operator or nested expression expected")
   243      }
   244  }
   245  
   246  func (self *Parser) term(prec int, nest int, repo Repository) (*Expr, error) {
   247      var err error
   248      var val *Expr
   249  
   250      /* parse the LHS operand */
   251      if val, err = self.expr(prec + 1, nest, repo); err != nil {
   252          return nil, err
   253      }
   254  
   255      /* parse all the operators of the same precedence */
   256      for {
   257          var op int
   258          var rv *Expr
   259          var tk _Token
   260  
   261          /* peek the next token */
   262          pp := self.pos
   263          tk, err = self.next()
   264  
   265          /* check for errors */
   266          if err != nil {
   267              return nil, err
   268          }
   269  
   270          /* encountered EOF */
   271          if tk.tag == _T_end {
   272              return val, nil
   273          }
   274  
   275          /* must be an operator */
   276          if tk.tag != _T_punc {
   277              return nil, newSyntaxError(tk.pos, "operators expected")
   278          }
   279  
   280          /* check for the operator precedence */
   281          if op = int(tk.u64); !precedence[prec][op] {
   282              self.pos = pp
   283              return val, nil
   284          }
   285  
   286          /* evaluate the RHS operand, and combine the value */
   287          if rv, err = self.expr(prec + 1, nest, repo); err != nil {
   288              return nil, err
   289          } else {
   290              val = binaryOps[op](val, rv)
   291          }
   292      }
   293  }
   294  
   295  func (self *Parser) expr(prec int, nest int, repo Repository) (*Expr, error) {
   296      if prec >= len(precedence) {
   297          return self.unit(nest, repo)
   298      } else {
   299          return self.term(prec, nest, repo)
   300      }
   301  }
   302  
   303  // Parse parses the expression, and returns it's AST tree.
   304  func (self *Parser) Parse(repo Repository) (*Expr, error) {
   305      return self.expr(0, 0, repo)
   306  }
   307  
   308  // SetSource resets the expression parser and sets the expression source.
   309  func (self *Parser) SetSource(src string) *Parser {
   310      self.pos = 0
   311      self.src = []rune(src)
   312      return self
   313  }
   314
View as plain text