| 1 | #!/usr/bin/env python2
|
| 2 | """
|
| 3 | typed_arith_parse.py: Parse shell-like and C-like arithmetic.
|
| 4 | """
|
| 5 | from __future__ import print_function
|
| 6 |
|
| 7 | import sys
|
| 8 |
|
| 9 | from _devbuild.gen.typed_arith_asdl import (
|
| 10 | arith_expr, arith_expr_t,
|
| 11 | )
|
| 12 |
|
| 13 | from typing import Dict, List, Optional
|
| 14 | #from typing import cast
|
| 15 |
|
| 16 | from asdl.examples import tdop
|
| 17 | from asdl.examples import tdop_lexer
|
| 18 |
|
| 19 |
|
| 20 | #
|
| 21 | # Null Denotation -- token that takes nothing on the left
|
| 22 | #
|
| 23 |
|
| 24 | def NullConstant(p, token, bp):
|
| 25 | # type: (tdop.Parser, tdop.Token, int) -> arith_expr_t
|
| 26 | if token.type == 'number':
|
| 27 | return arith_expr.Const(int(token.val))
|
| 28 | # We have to wrap a string in some kind of variant.
|
| 29 | if token.type == 'name':
|
| 30 | return arith_expr.Var(token.val)
|
| 31 |
|
| 32 | raise AssertionError(token.type)
|
| 33 |
|
| 34 |
|
| 35 | def NullParen(p, token, bp):
|
| 36 | # type: (tdop.Parser, tdop.Token, int) -> arith_expr_t
|
| 37 | """ Arithmetic grouping """
|
| 38 | r = p.ParseUntil(bp)
|
| 39 | p.Eat(')')
|
| 40 | return r
|
| 41 |
|
| 42 |
|
| 43 | def NullPrefixOp(p, token, bp):
|
| 44 | # type: (tdop.Parser, tdop.Token, int) -> arith_expr_t
|
| 45 | """Prefix operator.
|
| 46 |
|
| 47 | Low precedence: return, raise, etc.
|
| 48 | return x+y is return (x+y), not (return x) + y
|
| 49 |
|
| 50 | High precedence: logical negation, bitwise complement, etc.
|
| 51 | !x && y is (!x) && y, not !(x && y)
|
| 52 | """
|
| 53 | r = p.ParseUntil(bp)
|
| 54 | return arith_expr.Unary(token.val, r)
|
| 55 |
|
| 56 |
|
| 57 | def NullIncDec(p, token, bp):
|
| 58 | # type: (tdop.Parser, tdop.Token, int) -> arith_expr_t
|
| 59 | """ ++x or ++x[1] """
|
| 60 | right = p.ParseUntil(bp)
|
| 61 | if not isinstance(right, (arith_expr.Var, arith_expr.Index)):
|
| 62 | raise tdop.ParseError("Can't assign to %r" % right)
|
| 63 | return arith_expr.Unary(token.val, right)
|
| 64 |
|
| 65 |
|
| 66 | #
|
| 67 | # Left Denotation -- token that takes an expression on the left
|
| 68 | #
|
| 69 |
|
| 70 | def LeftIncDec(p, token, left, rbp):
|
| 71 | # type: (tdop.Parser, tdop.Token, arith_expr_t, int) -> arith_expr_t
|
| 72 | """ For i++ and i-- """
|
| 73 | if not isinstance(left, (arith_expr.Var, arith_expr.Index)):
|
| 74 | raise tdop.ParseError("Can't assign to %r" % left)
|
| 75 | token.type = 'post' + token.type
|
| 76 | return arith_expr.Unary(token.val, left)
|
| 77 |
|
| 78 |
|
| 79 | def LeftIndex(p, token, left, unused_bp):
|
| 80 | # type: (tdop.Parser, tdop.Token, arith_expr_t, int) -> arith_expr_t
|
| 81 | """ index f[x+1] """
|
| 82 | # f[x] or f[x][y]
|
| 83 | if not isinstance(left, arith_expr.Var):
|
| 84 | raise tdop.ParseError("%s can't be indexed" % left)
|
| 85 | index = p.ParseUntil(0)
|
| 86 | if p.AtToken(':'):
|
| 87 | p.Next()
|
| 88 | end = p.ParseUntil(0) # type: Optional[arith_expr_t]
|
| 89 | else:
|
| 90 | end = None
|
| 91 |
|
| 92 | p.Eat(']')
|
| 93 |
|
| 94 | # TODO: If you see ], then
|
| 95 | # 1:4
|
| 96 | # 1:4:2
|
| 97 | # Both end and step are optional
|
| 98 |
|
| 99 | if end:
|
| 100 | return arith_expr.Slice(left, index, end, None)
|
| 101 | else:
|
| 102 | return arith_expr.Index(left, index)
|
| 103 |
|
| 104 |
|
| 105 | def LeftTernary(p, token, left, bp):
|
| 106 | # type: (tdop.Parser, tdop.Token, arith_expr_t, int) -> arith_expr_t
|
| 107 | """ e.g. a > 1 ? x : y """
|
| 108 | true_expr = p.ParseUntil(bp)
|
| 109 | p.Eat(':')
|
| 110 | false_expr = p.ParseUntil(bp)
|
| 111 | return arith_expr.Ternary(left, true_expr, false_expr)
|
| 112 |
|
| 113 |
|
| 114 | def LeftBinaryOp(p, token, left, rbp):
|
| 115 | # type: (tdop.Parser, tdop.Token, arith_expr_t, int) -> arith_expr_t
|
| 116 | """ Normal binary operator like 1+2 or 2*3, etc. """
|
| 117 | return arith_expr.Binary(token.val, left, p.ParseUntil(rbp))
|
| 118 |
|
| 119 |
|
| 120 | def LeftAssign(p, token, left, rbp):
|
| 121 | # type: (tdop.Parser, tdop.Token, arith_expr_t, int) -> arith_expr_t
|
| 122 | """ Normal binary operator like 1+2 or 2*3, etc. """
|
| 123 | # x += 1, or a[i] += 1
|
| 124 | if not isinstance(left, (arith_expr.Var, arith_expr.Index)):
|
| 125 | raise tdop.ParseError("Can't assign to %r" % left)
|
| 126 | node = arith_expr.Binary(token.val, left, p.ParseUntil(rbp))
|
| 127 | return node
|
| 128 |
|
| 129 |
|
| 130 | # For overloading of , inside function calls
|
| 131 | COMMA_PREC = 1
|
| 132 |
|
| 133 | def LeftFuncCall(p, token, left, unused_bp):
|
| 134 | # type: (tdop.Parser, tdop.Token, arith_expr_t, int) -> arith_expr.FuncCall
|
| 135 | """ Function call f(a, b). """
|
| 136 | args = [] # type: List[arith_expr_t]
|
| 137 | # f(x) or f[i](x)
|
| 138 | if not isinstance(left, arith_expr.Var):
|
| 139 | raise tdop.ParseError("%s can't be called" % left)
|
| 140 | func_name = left.name # get a string
|
| 141 |
|
| 142 | while not p.AtToken(')'):
|
| 143 | # We don't want to grab the comma, e.g. it is NOT a sequence operator. So
|
| 144 | # set the precedence to 5.
|
| 145 | args.append(p.ParseUntil(COMMA_PREC))
|
| 146 | if p.AtToken(','):
|
| 147 | p.Next()
|
| 148 | p.Eat(")")
|
| 149 | return arith_expr.FuncCall(func_name, args)
|
| 150 |
|
| 151 |
|
| 152 | def MakeShellParserSpec():
|
| 153 | # type: () -> tdop.ParserSpec
|
| 154 | """
|
| 155 | Create a parser.
|
| 156 |
|
| 157 | Compare the code below with this table of C operator precedence:
|
| 158 | http://en.cppreference.com/w/c/language/operator_precedence
|
| 159 | """
|
| 160 | spec = tdop.ParserSpec()
|
| 161 |
|
| 162 | spec.Left(31, LeftIncDec, ['++', '--'])
|
| 163 | spec.Left(31, LeftFuncCall, ['('])
|
| 164 | spec.Left(31, LeftIndex, ['['])
|
| 165 |
|
| 166 | # 29 -- binds to everything except function call, indexing, postfix ops
|
| 167 | spec.Null(29, NullIncDec, ['++', '--'])
|
| 168 | spec.Null(29, NullPrefixOp, ['+', '!', '~', '-'])
|
| 169 |
|
| 170 | # Right associative: 2 ** 3 ** 2 == 2 ** (3 ** 2)
|
| 171 | spec.LeftRightAssoc(27, LeftBinaryOp, ['**'])
|
| 172 | spec.Left(25, LeftBinaryOp, ['*', '/', '%'])
|
| 173 |
|
| 174 | spec.Left(23, LeftBinaryOp, ['+', '-'])
|
| 175 | spec.Left(21, LeftBinaryOp, ['<<', '>>'])
|
| 176 | spec.Left(19, LeftBinaryOp, ['<', '>', '<=', '>='])
|
| 177 | spec.Left(17, LeftBinaryOp, ['!=', '=='])
|
| 178 |
|
| 179 | spec.Left(15, LeftBinaryOp, ['&'])
|
| 180 | spec.Left(13, LeftBinaryOp, ['^'])
|
| 181 | spec.Left(11, LeftBinaryOp, ['|'])
|
| 182 | spec.Left(9, LeftBinaryOp, ['&&'])
|
| 183 | spec.Left(7, LeftBinaryOp, ['||'])
|
| 184 |
|
| 185 | spec.LeftRightAssoc(5, LeftTernary, ['?'])
|
| 186 |
|
| 187 | # Right associative: a = b = 2 is a = (b = 2)
|
| 188 | spec.LeftRightAssoc(3, LeftAssign, [
|
| 189 | '=',
|
| 190 | '+=', '-=', '*=', '/=', '%=',
|
| 191 | '<<=', '>>=', '&=', '^=', '|='])
|
| 192 |
|
| 193 | spec.Left(COMMA_PREC, LeftBinaryOp, [','])
|
| 194 |
|
| 195 | # 0 precedence -- doesn't bind until )
|
| 196 | spec.Null(0, NullParen, ['(']) # for grouping
|
| 197 |
|
| 198 | # -1 precedence -- never used
|
| 199 | spec.Null(-1, NullConstant, ['name', 'number'])
|
| 200 | spec.Null(-1, tdop.NullError, [')', ']', ':', 'eof'])
|
| 201 |
|
| 202 | return spec
|
| 203 |
|
| 204 |
|
| 205 | def MakeParser(s):
|
| 206 | # type: (str) -> tdop.Parser
|
| 207 | """Used by tests."""
|
| 208 | spec = MakeShellParserSpec()
|
| 209 | lexer = tdop_lexer.Tokenize(s)
|
| 210 | p = tdop.Parser(spec, lexer)
|
| 211 | return p
|
| 212 |
|
| 213 |
|
| 214 | def ParseShell(s, expected=None):
|
| 215 | # type: (str, Optional[str]) -> arith_expr_t
|
| 216 | """Used by tests."""
|
| 217 | p = MakeParser(s)
|
| 218 | tree = p.Parse()
|
| 219 |
|
| 220 | sexpr = repr(tree)
|
| 221 | if expected is not None:
|
| 222 | assert sexpr == expected, '%r != %r' % (sexpr, expected)
|
| 223 |
|
| 224 | #print('%-40s %s' % (s, sexpr))
|
| 225 | return tree
|
| 226 |
|
| 227 |
|
| 228 | class Evaluator(object):
|
| 229 | def __init__(self):
|
| 230 | # type: () -> None
|
| 231 | self.mem = {} # type: Dict[str, int]
|
| 232 |
|
| 233 | def Eval(self, node):
|
| 234 | # type: (arith_expr_t) -> int
|
| 235 | """Use the isinstance() style for comparison."""
|
| 236 |
|
| 237 | if isinstance(node, arith_expr.Const):
|
| 238 | assert node.i is not None
|
| 239 | return node.i
|
| 240 |
|
| 241 | if isinstance(node, arith_expr.Binary):
|
| 242 | assert node.left is not None
|
| 243 | assert node.right is not None
|
| 244 |
|
| 245 | left = self.Eval(node.left)
|
| 246 | right = self.Eval(node.right)
|
| 247 | op = node.op
|
| 248 |
|
| 249 | if op == '+':
|
| 250 | return left + right
|
| 251 |
|
| 252 | return 3
|
| 253 |
|
| 254 | # NOTE: This doesn't translate yet because of cast().
|
| 255 | """
|
| 256 | def Eval2(self, node):
|
| 257 | # type: (arith_expr_t) -> int
|
| 258 |
|
| 259 | tag = node.tag
|
| 260 | if tag == arith_expr_e.Const:
|
| 261 | n = cast(arith_expr.Const, node)
|
| 262 |
|
| 263 | assert n.i is not None
|
| 264 | return n.i
|
| 265 |
|
| 266 | if tag == arith_expr_e.Binary:
|
| 267 | n2 = cast(arith_expr.Binary, node)
|
| 268 |
|
| 269 | assert n2.left is not None
|
| 270 | assert n2.right is not None
|
| 271 |
|
| 272 | left = self.Eval(n2.left)
|
| 273 | right = self.Eval(n2.right)
|
| 274 | op = n2.op
|
| 275 |
|
| 276 | if op == '+':
|
| 277 | return left + right
|
| 278 |
|
| 279 | return 3
|
| 280 | """
|
| 281 |
|
| 282 |
|
| 283 | def main(argv):
|
| 284 | # type: (List[str]) -> int
|
| 285 | try:
|
| 286 | action = argv[1]
|
| 287 | s = argv[2]
|
| 288 | except IndexError:
|
| 289 | print('Usage: ./arith_parse.py ACTION EXPRESSION')
|
| 290 | return 2
|
| 291 |
|
| 292 | try:
|
| 293 | node = ParseShell(s)
|
| 294 | except tdop.ParseError as e:
|
| 295 | print('Error parsing %r: %s' % (s, e), file=sys.stderr)
|
| 296 |
|
| 297 | if action == 'parse':
|
| 298 | print(node)
|
| 299 | elif action == 'eval':
|
| 300 | ev = Evaluator()
|
| 301 | result = ev.Eval(node)
|
| 302 | print(node)
|
| 303 | print(' => ')
|
| 304 | print(result)
|
| 305 | else:
|
| 306 | print('Invalid action %r' % action)
|
| 307 | return 2
|
| 308 |
|
| 309 | return 0
|
| 310 |
|
| 311 |
|
| 312 | if __name__ == '__main__':
|
| 313 | sys.exit(main(sys.argv))
|