fork download
copy 
  1. from re          import compile
  2. from ast         import literal_eval
  3. from functools   import reduce
  4. from collections import Iterator, deque, namedtuple
  5.  
  6. Location = namedtuple('Location', 'start, end, filename, first_line')
  7.  
  8.  
  9. class StructMixIn:
  10.  
  11.     infix       = False
  12.     closed      = False
  13.     indented    = False
  14.  
  15.     def after(self, other):
  16.  
  17.         self.location = Location(
  18.             other.location.end,
  19.             other.location.end,
  20.             other.location.filename,
  21.             other.location.first_line
  22.         )
  23.         return self
  24.  
  25.     def at(self, stream, start):
  26.  
  27.         self.location = Location(
  28.             stream.position(start),
  29.             stream.position(stream.offset),
  30.             stream.filename,
  31.             stream.line(start)
  32.         )
  33.         return self
  34.  
  35.  
  36. class Expression (list, StructMixIn):
  37.  
  38.     def __repr__(self):
  39.  
  40.         return ('({})' if self.closed else '{}').format(
  41.             ' '.join(map(repr, self[1:])) if self[0] == '' else
  42.             '{1}{0}{2}'  .format(*self) if len(self) == 3 and self[0] == '.' else
  43.             '{1} {0} {2}'.format(*self) if len(self) == 3 else
  44.             '{1} {0}'    .format(*self) if len(self) == 2 else
  45.             '({}) {}'.format(self[0], ' '.join(map(repr, self[1:])))
  46.         )
  47.  
  48.  
  49. class Link (str, StructMixIn):
  50.  
  51.     def __new__(cls, data, infix=False):
  52.  
  53.         obj = str.__new__(cls, data)
  54.         obj.infix = bool(infix)
  55.         return obj
  56.  
  57.     def __repr__(self):
  58.  
  59.         return self
  60.  
  61.  
  62. class Constant (StructMixIn):
  63.  
  64.     def __init__(self, value):
  65.  
  66.         super().__init__()
  67.         self.value = value
  68.  
  69.     def __repr__(self):
  70.  
  71.         return repr(self.value)
  72.  
  73.  
  74. class Internal (Constant):
  75.  
  76.     pass
  77.  
  78. # In all comments below, `R` and `Q` are infix links, while lowercase letters
  79. # are arbitrary expressions.
  80. has_priority = (lambda f: lambda a, b: f(a)[0] > f(b)[1])(lambda m, g={
  81.     # `a R b Q c` <=> `a R (b Q c)` if left binding strength of `Q`
  82.     # is higher than right binding strength of `R`.
  83.     '':      (-2,  -2),   # call with an argument
  84.     '^':     (-3,  -4),   # exponentiation
  85.     '*':     (-5,  -5),   # multiplication
  86.     '/':     (-5,  -5),   # fp division
  87.     '//':    (-5,  -5),   # int division
  88.     '%':     (-5,  -5),   # modulus
  89.     '+':     (-6,  -6),   # addition
  90.     '-':     (-6,  -6),   # subtraction
  91. }.get: g(m, (-7, -7)))  # Default
  92.  
  93.  
  94. # If `unassoc(R)`: `a R b R c` <=> `Expression [ Link R, Link a, Link b, Link c]`
  95. # Otherwise:       `a R b R c` <=> `Expression [ Link R, Expression [...], Link c]`
  96. # (This doesn't apply to right-fixed links.)
  97. unassoc = {',', '..', '::', '', '\n'}.__contains__
  98.  
  99. # These operators have no right-hand statement part in any case.
  100. unary = {'!'}.__contains__
  101.  
  102.  
  103. # infixl :: (State, StructMixIn, Link, StructMixIn) -> StructMixIn
  104. #
  105. # Handle an infix expression given its all three parts.
  106. #
  107. # If that particular expression has no right-hand statement part,
  108. # `rhs` will be pushed to the object queue.
  109. #
  110. def infixl(stream, lhs, op, rhs):
  111.  
  112.     break_   = False
  113.     postfixl = lambda: (lhs if op in '\n ' else infixl_insert_rhs(lhs, op, None))
  114.  
  115.     while rhs == '\n' and not unary(op):
  116.  
  117.         break_, rhs = rhs, next(stream)
  118.  
  119.     if isinstance(rhs, Internal) or unary(op):  # `(a R)`
  120.  
  121.         stream.appendleft(rhs)
  122.         return postfixl()
  123.  
  124.     if break_ and op == '' and rhs.indented:
  125.  
  126.         # a
  127.         #   b         <=>  a b (c d)
  128.         #   c d
  129.         return reduce(
  130.             lambda lhs, rhs: infixl_insert_rhs(lhs, op, rhs),
  131.             rhs[1:] if isinstance(rhs, Expression) and rhs[0] == '\n' else [rhs], lhs
  132.         )
  133.  
  134.     if break_ and op != '\n' and not rhs.indented:  # `a R`
  135.  
  136.         return infixl(stream, postfixl(), break_, rhs)
  137.  
  138.     if not rhs.closed and rhs.infix and (op == '' or has_priority(op, rhs)):
  139.  
  140.         # `a R Q b` <=> `(a R) Q b` if R is prioritized over Q or R is empty.
  141.         return infixl(stream, postfixl(), rhs, next(stream))
  142.  
  143.     return infixl_insert_rhs(lhs, op, rhs)
  144.  
  145.  
  146. # infixl_insert_rhs :: (StructMixIn, Link, StructMixIn) -> StructMixIn
  147. #
  148. # Recursively descends into `root` if infix precedence rules allow it to,
  149. # otherwise simply creates and returns a new infix expression AST node.
  150. #
  151. def infixl_insert_rhs(root, op, rhs):
  152.  
  153.     if isinstance(root, Expression) and not root.closed:
  154.  
  155.         if has_priority(op, root[0]):
  156.  
  157.             # `a R b Q c` <=> `a R (b Q c)` if Q is prioritized over R
  158.             root.append(infixl_insert_rhs(root.pop(), op, rhs))
  159.             return root
  160.  
  161.         elif op == root[0] and unassoc(op) and rhs is not None:
  162.  
  163.             root.append(rhs)  # `a R b R c` <=> `R a b c`
  164.             return root
  165.  
  166.     # `R`         <=> `Link R`
  167.     # `R rhs`     <=> `Expression [ Link '', Link R, Link rhs ]`
  168.     # `lhs R`     <=> `Expression [ Link R, Link lhs ]`
  169.     # `lhs R rhs` <=> `Expression [ Link R, Link lhs, Link rhs ]`
  170.     e = Expression([op, root] if rhs is None else [op, root, rhs])
  171.     e.closed = rhs is None
  172.     e.location = Location(
  173.         root.location.start,
  174.         e[-(not e.closed)].location.end,
  175.         root.location.filename,
  176.         root.location.first_line
  177.     )
  178.     return e
  179.  
  180.  
  181. def indent(stream, token):
  182.  
  183.     indent = len(token.group())
  184.  
  185.     if indent > stream.indent[-1]:
  186.  
  187.         stream.indent.append(indent)
  188.         block = do(stream, token, {''}, preserve_close_state=True)
  189.         block.indented = True
  190.         return block
  191.  
  192.     while indent != stream.indent[-1]:
  193.  
  194.         stream.indent.pop() < 0 and stream.error('no matching indentation level', token.start())
  195.         stream.appendleft(Link('\n', True).at(stream, token.end()))
  196.         stream.appendleft(Internal('').at(stream, token.end()))
  197.  
  198.  
  199. def whitespace(stream, token): pass
  200.  
  201.  
  202. def number(stream, token):
  203.  
  204.     return Constant(literal_eval(token.group()))
  205.  
  206.  
  207. def string(stream, token):
  208.  
  209.     g = token.group(2) * (4 - len(token.group(2)))
  210.     q = ''.join(sorted(set(token.group(1))))
  211.     return Constant(literal_eval(''.join([q, g, token.group(3), g])))
  212.  
  213.  
  214. def link(stream, token, infixn={'if', 'else', 'or', 'and', 'in', 'is', 'where'}):
  215.  
  216.     infix = token.group(2) or token.group(3) or token.group(4)
  217.     return Link(infix or token.group(), infix or (token.group() in infixn))
  218.  
  219.  
  220. def do(stream, token, ends={')'}, preserve_close_state=False):
  221.  
  222.     object   = Constant(None).at(stream, token.end())
  223.     can_join = False
  224.  
  225.     for item in stream:
  226.  
  227.         if isinstance(item, Internal):
  228.  
  229.             item.value in ends or stream.error(
  230.               'unexpected block delimiter' if item.value else
  231.               'unexpected EOF'             if stream.offset >= len(stream.buffer) else
  232.               'unexpected dedent', item.location.start[0]
  233.             )
  234.  
  235.             break
  236.  
  237.         elif can_join:
  238.  
  239.             # Two objects in a row should be joined with an empty infix link.
  240.             object = infixl(stream, object, Link('', True).after(object), item)
  241.  
  242.         # Ignore line feeds directly following an opening parentheses.
  243.         elif item != '\n':
  244.  
  245.             object, can_join = item, True
  246.  
  247.     object.closed |= not preserve_close_state
  248.     return object
  249.  
  250.  
  251. def end(stream, token):
  252.  
  253.     return Internal(token.group())
  254.  
  255.  
  256. def string_err(stream, token):
  257.  
  258.     stream.error('unexpected EOF while reading a string literal', token.start())
  259.  
  260.  
  261. def error(stream, token):
  262.  
  263.     stream.error('invalid input', token.start())
  264.  
  265.  
  266. def R(func, expr):
  267.  
  268.     return func, compile(expr).match
  269.  
  270.  
  271. class it (Iterator, deque):
  272.  
  273.     tokens = [R(indent, r' *')], [
  274.         R(whitespace, r'[^\S\n]+|\s*#.*')
  275.       , R(number,     r'(?i)[+-]?(?:0b[0-1]+|0o[0-7]+|0x[0-9a-f]+|\d+(?:\.\d+)?(?:e[+-]?\d+)?j?)')
  276.       , R(string,     r'(?s)([br]*)(\'\'\'|"""|"|\')((?:\\?.)*?)\2')
  277.       , R(link,       r"(\w+'*|\*+(?=:)|([!$%&*+\--/:<-@\\^|~;]+|,+))|\s*(\n)|`(\w+'*)`")
  278.       , R(do,         r'\(')
  279.       , R(end,        r'\)|$')
  280.       , R(string_err, r'''['"]''')
  281.       , R(error,      r'.')
  282.     ]
  283.  
  284.     def __new__(cls, data, filename='<string>'):
  285.  
  286.         self = super(it, cls).__new__(cls)
  287.         self.filename = filename
  288.         self.buffer   = data
  289.         self.offset   = 0
  290.         self.indent   = deque([-1])
  291.         self.nextset  = self.tokens[0]
  292.         return next(self)
  293.  
  294.     def __next__(self):
  295.  
  296.         while not self:
  297.  
  298.             f, match = next((f, match)
  299.                 for f, re in self.nextset
  300.                 for match in [re(self.buffer, self.offset)] if match
  301.             )
  302.             self.offset  = match.end()
  303.             self.nextset = self.tokens[not match.group().endswith('\n')]
  304.             q = f(self, match)
  305.  
  306.             if q is not None:
  307.  
  308.                 return q.at(self, match.start())
  309.  
  310.         return self.popleft()
  311.  
  312.     # position :: int -> (int, int, int)
  313.     #
  314.     # Given a character offset, get an (offset, lineno, charno) triple.
  315.     #
  316.     def position(self, offset):
  317.  
  318.         return (offset,
  319.             1      + self.buffer.count('\n', 0, offset),
  320.             offset - self.buffer.rfind('\n', 0, offset))
  321.  
  322.     # error :: (str, int) -> _|_
  323.     #
  324.     # Raise a `SyntaxError` at a given offset.
  325.     #
  326.     def error(self, description, at):
  327.  
  328.         _, lineno, charno = self.position(at)
  329.         raise SyntaxError(description, (self.filename, lineno, charno, self.line(at)))
  330.  
  331.     # line :: int -> str
  332.     #
  333.     # Get a line which contains the character at a given offset.
  334.     #
  335.     def line(self, offset):
  336.  
  337.         return self.buffer[
  338.             self.buffer.rfind('\n', 0, offset) + 1 or None:
  339.             self.buffer. find('\n',    offset) + 1 or None
  340.         ]
  341.  
  342. ##########################
  343.  
  344. import fractions as fr
  345. import operator  as op
  346.  
  347. ns = {'': lambda f, *xs: f(*xs), '^': op.pow, '*': op.mul, '/': fr.Fraction, '//': op.truediv, '%': op.mod, '+': op.add, '-': op.sub}
  348.  
  349.  
  350. def eval(x):
  351.     if isinstance(x, Link):       return ns[x]
  352.     if isinstance(x, Constant):   return x.value
  353.     if isinstance(x, Expression): return call(*x)
  354.     raise TypeError('invalid AST node', x)
  355.  
  356.  
  357. def call(f, *args, rightbind=False):
  358.     return f if not args else call(*args, rightbind=True) if f.infix and f == '' \
  359.       else (lambda x: eval(f)(x, *map(eval, args))) if f.infix and not f.closed and rightbind      \
  360.       else (lambda x: eval(f)(eval(args[0]), x)   ) if f.infix and not f.closed and len(args) == 1 \
  361.       else eval(f)(*map(eval, args))
  362.  
  363.  
  364. ############################
  365.  
  366. import sys
  367.  
  368. while True:
  369.     try: print(eval(it(input('> '))))
  370.     except EOFError:   raise SystemExit
  371.     except SystemExit: raise
  372.     except BaseException as e: sys.excepthook(type(e), e, e.__traceback__)
Success #stdin #stdout #stderr 0.26s 14936KB
comments ()
stdin
copy 
2 + 3             #  5
4 - 3             #  1
2 + (-3)          # -1
4 * 5             # 20
6/4               # 3/2
1.2 + 1/2         # 1.7
1/(-3)            # -1/3
0.5 + 0.2         # 0.7
3 ^ 2 ^ 2         # 81
17654/342         # 8827/171
2/3 ^ 2           # 2/9
(2/3) ^ 2         # 4/9
(2 + 3) / (2 - 2) # Ошибка: делить на ноль (5/0) нельзя
2 + 345 + + + + 6 # Ошибка: выражение записано неправильно
stdout
copy 
> 5
> 1
> -1
> 20
> 3/2
> 1.7
> -1/3
> 0.7
> 81
> 8827/171
> 2/9
> 4/9
> > >
stderr
copy 
Traceback (most recent call last):
  File "prog.py", line 369, in <module>
    try: print(eval(it(input('> '))))
  File "prog.py", line 353, in eval
    if isinstance(x, Expression): return call(*x)
  File "prog.py", line 361, in call
    else eval(f)(*map(eval, args))
  File "/usr/lib/python3.2/fractions.py", line 167, in __new__
    raise ZeroDivisionError('Fraction(%s, 0)' % numerator)
ZeroDivisionError: Fraction(5, 0)
Traceback (most recent call last):
  File "prog.py", line 369, in <module>
    try: print(eval(it(input('> '))))
  File "prog.py", line 353, in eval
    if isinstance(x, Expression): return call(*x)
  File "prog.py", line 361, in call
    else eval(f)(*map(eval, args))
TypeError: add() argument after * must be a sequence, not map
https://ideone.com/58awxP
language:
Python 3 (python  3.12)
created:
11 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!