OILS / opy / _regtest / src / asdl / arith_parse.py View on Github | oilshell.org

246 lines, 134 significant
1#!/usr/bin/env python
2from __future__ import print_function
3"""
4arith_parse.py: Parse shell-like and C-like arithmetic.
5"""
6
7import sys
8
9from asdl import tdop
10from asdl.tdop import CompositeNode
11from asdl import arith_ast
12
13op_id = arith_ast.op_id_e # TODO: Rename this back.
14
15
16#
17# Null Denotation -- token that takes nothing on the left
18#
19
20def NullConstant(p, token, bp):
21 if token.type == 'number':
22 return arith_ast.Const(token.val)
23 # We have to wrap a string in some kind of variant.
24 if token.type == 'name':
25 return arith_ast.ArithVar(token.val)
26
27 raise AssertionError(token.type)
28
29
30def NullParen(p, token, bp):
31 """ Arithmetic grouping """
32 r = p.ParseUntil(bp)
33 p.Eat(')')
34 return r
35
36
37def NullPrefixOp(p, token, bp):
38 """Prefix operator.
39
40 Low precedence: return, raise, etc.
41 return x+y is return (x+y), not (return x) + y
42
43 High precedence: logical negation, bitwise complement, etc.
44 !x && y is (!x) && y, not !(x && y)
45 """
46 r = p.ParseUntil(bp)
47 return CompositeNode(token, [r])
48
49
50def NullIncDec(p, token, bp):
51 """ ++x or ++x[1] """
52 right = p.ParseUntil(bp)
53 if right.token.type not in ('name', 'get'):
54 raise tdop.ParseError("Can't assign to %r (%s)" % (right, right.token))
55 return CompositeNode(token, [right])
56
57
58#
59# Left Denotation -- token that takes an expression on the left
60#
61
62def LeftIncDec(p, token, left, rbp):
63 """ For i++ and i--
64 """
65 if left.token.type not in ('name', 'get'):
66 raise tdop.ParseError("Can't assign to %r (%s)" % (left, left.token))
67 token.type = 'post' + token.type
68 return CompositeNode(token, [left])
69
70
71def LeftIndex(p, token, left, unused_bp):
72 """ index f[x+1] """
73 # f[x] or f[x][y]
74 if not isinstance(left, arith_ast.ArithVar):
75 raise tdop.ParseError("%s can't be indexed" % left)
76 index = p.ParseUntil(0)
77 if p.AtToken(':'):
78 p.Next()
79 end = p.ParseUntil(0)
80 else:
81 end = None
82
83 p.Eat(']')
84
85 # TODO: If you see ], then
86 # 1:4
87 # 1:4:2
88 # Both end and step are optional
89
90 if end:
91 return arith_ast.Slice(left, index, end, None)
92 else:
93 return arith_ast.Index(left, index)
94
95
96def LeftTernary(p, token, left, bp):
97 """ e.g. a > 1 ? x : y """
98 true_expr = p.ParseUntil(bp)
99 p.Eat(':')
100 false_expr = p.ParseUntil(bp)
101 children = [left, true_expr, false_expr]
102 return CompositeNode(token, children)
103
104
105def LeftBinaryOp(p, token, left, rbp):
106 """ Normal binary operator like 1+2 or 2*3, etc. """
107 if token.val == '+':
108 op_id_ = op_id.Plus
109 elif token.val == '-':
110 op_id_ = op_id.Minus
111 elif token.val == '*':
112 op_id_ = op_id.Star
113 else:
114 raise AssertionError(token.val)
115 return arith_ast.ArithBinary(op_id_, left, p.ParseUntil(rbp))
116
117
118def LeftAssign(p, token, left, rbp):
119 """ Normal binary operator like 1+2 or 2*3, etc. """
120 # x += 1, or a[i] += 1
121 if left.token.type not in ('name', 'get'):
122 raise tdop.ParseError("Can't assign to %r (%s)" % (left, left.token))
123 return CompositeNode(token, [left, p.ParseUntil(rbp)])
124
125
126def LeftComma(p, token, left, rbp):
127 """ foo, bar, baz
128
129 Could be sequencing operator, or tuple without parens
130 """
131 r = p.ParseUntil(rbp)
132 if left.token.type == ',': # Keep adding more children
133 left.children.append(r)
134 return left
135 children = [left, r]
136 return CompositeNode(token, children)
137
138
139# For overloading of , inside function calls
140COMMA_PREC = 1
141
142def LeftFuncCall(p, token, left, unused_bp):
143 """ Function call f(a, b). """
144 args = []
145 # f(x) or f[i](x)
146 if not isinstance(left, arith_ast.ArithVar):
147 raise tdop.ParseError("%s can't be called" % left)
148 func_name = left.name # get a string
149
150 while not p.AtToken(')'):
151 # We don't want to grab the comma, e.g. it is NOT a sequence operator. So
152 # set the precedence to 5.
153 args.append(p.ParseUntil(COMMA_PREC))
154 if p.AtToken(','):
155 p.Next()
156 p.Eat(")")
157 return arith_ast.FuncCall(func_name, args)
158
159
160def MakeShellParserSpec():
161 """
162 Create a parser.
163
164 Compare the code below with this table of C operator precedence:
165 http://en.cppreference.com/w/c/language/operator_precedence
166 """
167 spec = tdop.ParserSpec()
168
169 spec.Left(31, LeftIncDec, ['++', '--'])
170 spec.Left(31, LeftFuncCall, ['('])
171 spec.Left(31, LeftIndex, ['['])
172
173 # 29 -- binds to everything except function call, indexing, postfix ops
174 spec.Null(29, NullIncDec, ['++', '--'])
175 spec.Null(29, NullPrefixOp, ['+', '!', '~', '-'])
176
177 # Right associative: 2 ** 3 ** 2 == 2 ** (3 ** 2)
178 spec.LeftRightAssoc(27, LeftBinaryOp, ['**'])
179 spec.Left(25, LeftBinaryOp, ['*', '/', '%'])
180
181 spec.Left(23, LeftBinaryOp, ['+', '-'])
182 spec.Left(21, LeftBinaryOp, ['<<', '>>'])
183 spec.Left(19, LeftBinaryOp, ['<', '>', '<=', '>='])
184 spec.Left(17, LeftBinaryOp, ['!=', '=='])
185
186 spec.Left(15, LeftBinaryOp, ['&'])
187 spec.Left(13, LeftBinaryOp, ['^'])
188 spec.Left(11, LeftBinaryOp, ['|'])
189 spec.Left(9, LeftBinaryOp, ['&&'])
190 spec.Left(7, LeftBinaryOp, ['||'])
191
192 spec.LeftRightAssoc(5, LeftTernary, ['?'])
193
194 # Right associative: a = b = 2 is a = (b = 2)
195 spec.LeftRightAssoc(3, LeftAssign, [
196 '=',
197 '+=', '-=', '*=', '/=', '%=',
198 '<<=', '>>=', '&=', '^=', '|='])
199
200 spec.Left(COMMA_PREC, LeftComma, [','])
201
202 # 0 precedence -- doesn't bind until )
203 spec.Null(0, NullParen, ['(']) # for grouping
204
205 # -1 precedence -- never used
206 spec.Null(-1, NullConstant, ['name', 'number'])
207 spec.Null(-1, tdop.NullError, [')', ']', ':', 'eof'])
208
209 return spec
210
211
212def MakeParser(s):
213 """Used by tests."""
214 spec = MakeShellParserSpec()
215 lexer = tdop.Tokenize(s)
216 p = tdop.Parser(spec, lexer)
217 return p
218
219
220def ParseShell(s, expected=None):
221 """Used by tests."""
222 p = MakeParser(s)
223 tree = p.Parse()
224
225 sexpr = repr(tree)
226 if expected is not None:
227 assert sexpr == expected, '%r != %r' % (sexpr, expected)
228
229 #print('%-40s %s' % (s, sexpr))
230 return tree
231
232
233def main(argv):
234 try:
235 s = argv[1]
236 except IndexError:
237 print('Usage: ./arith_parse.py EXPRESSION')
238 else:
239 try:
240 tree = ParseShell(s)
241 except tdop.ParseError as e:
242 print('Error parsing %r: %s' % (s, e), file=sys.stderr)
243
244
245if __name__ == '__main__':
246 main(sys.argv)