fork download
copy 
  1. import copy
  2. import re
  3.  
  4. class Success(object):
  5.  
  6.     def __init__(self, val, rest):
  7.         self.val  = val
  8.         self.rest = rest
  9.  
  10.     def __str__(self):
  11.         return 'Success(' + repr(self.val) + ', ' + repr(self.rest) + ')'
  12.  
  13. class Failure(object):
  14.  
  15.     def __init__(self, rest):
  16.         self.rest = rest
  17.  
  18.     def __str__(self):
  19.         return 'Failure(' + repr(self.rest) + ')'
  20.  
  21. class Trampoline(object):
  22.  
  23.     def __init__(self):
  24.         self.stack = []
  25.         self.table = {}
  26.  
  27.     def hasNext(self):
  28.         return self.stack != []
  29.  
  30.     def step(self):
  31.         if self.hasNext():
  32.             (fn, argList) = self.stack.pop()
  33.             fn(*argList)
  34.  
  35.     def pushCall(self, fn, *argList):
  36.         self.stack.append((fn, argList))
  37.  
  38.     def push(self, fn, string, cont):
  39.  
  40.         def tableRef(fn, string):
  41.             if fn in self.table:
  42.                 fnMemo = self.table[fn]
  43.  
  44.                 if string not in fnMemo:
  45.                     fnMemo[string] = ([], {})
  46.  
  47.                 return fnMemo[string]
  48.             else:
  49.                 entry = ([], {})
  50.                 fnMemo = {string : entry}
  51.  
  52.                 self.table[fn] = fnMemo
  53.  
  54.                 return entry
  55.  
  56.         entry = tableRef(fn, string)
  57.  
  58.         if not entry[0] and not entry[1]:
  59.             entry[0].append(cont)
  60.  
  61.             def myCont(result):
  62.                 if str(result) not in entry[1]:
  63.                     entry[1][str(result)] = result
  64.  
  65.                     tempList = copy.deepcopy(entry[0])
  66.  
  67.                     for c in tempList:
  68.                         c(result)
  69.  
  70.             self.pushCall(fn, string, self, myCont)
  71.         else:
  72.             entry[0].append(cont)
  73.  
  74.             tempDict = copy.deepcopy(entry[1])
  75.  
  76.             for sr, r in tempDict.iteritems():
  77.                 cont(r)
  78.  
  79.     def run(self):
  80.         while self.hasNext():
  81.             self.step()
  82.  
  83. allCaches = []
  84.  
  85. def memo(fn):
  86.     cache = {}
  87.     allCaches.append(cache)
  88.  
  89.     def memo_wrapper(*args):
  90.         sargs = str(args)
  91.  
  92.         if sargs not in cache:
  93.             cache[sargs] = fn(*args)
  94.         return cache[sargs]
  95.  
  96.     return memo_wrapper
  97.  
  98. @memo
  99. def succeed(val):
  100.  
  101.     def f(string, tramp, cont):
  102.         cont(Success(val, string))
  103.  
  104.     return f
  105.  
  106. @memo
  107. def lit(match):
  108.  
  109.     def f(string, tramp, cont):
  110.         length = min(len(string), len(match))
  111.  
  112.         head = string[0:length]
  113.         tail = string[length:]
  114.  
  115.         if head == match:
  116.             cont(Success(head, tail))
  117.         else:
  118.             cont(Failure(string))
  119.  
  120.     return f
  121.  
  122. @memo
  123. def reg(pattern):
  124.  
  125.     def f(string, tramp, cont):
  126.         result = re.findall('^' + pattern, string)
  127.  
  128.         if not result:
  129.             cont(Failure(string))
  130.         else:
  131.             result = result[0]
  132.             length = len(result)
  133.  
  134.             head = string[0:length]
  135.             tail = string[length:]
  136.  
  137.             cont(Success(head, tail))
  138.  
  139.     return f
  140.  
  141. def bind(p, fn):
  142.  
  143.     def f(string, tramp, cont):
  144.  
  145.         def myCont(result):
  146.             if isinstance(result, Success):
  147.                 fn(result.val)(result.rest, tramp, cont)
  148.             else:
  149.                 cont(result)
  150.  
  151.         tramp.push(p, string, myCont)
  152.  
  153.     return f
  154.  
  155. @memo
  156. def seq(plist):
  157.  
  158.     def seq_(a, b):
  159.         def f1(x):
  160.             def f2(y):
  161.                 return succeed(x + [y])
  162.             return bind(b, f2)
  163.         return bind(a, f1)
  164.  
  165.     return reduce(seq_, plist, succeed([]))
  166.  
  167. @memo
  168. def alt(plist):
  169.  
  170.     def f(string, tramp, cont):
  171.         for p in plist:
  172.             tramp.push(p, string, cont)
  173.  
  174.     return f
  175.  
  176. @memo
  177. def rep1(p):
  178.  
  179.     def f(string, tramp, cont):
  180.         tramp.push(seq([p, rep1(p)]), string, cont)
  181.         tramp.push(p, string, cont)
  182.  
  183.     return f
  184.  
  185. @memo
  186. def rep0(p):
  187.  
  188.     def f(string, tramp, cont):
  189.         tramp.push(rep1(p), string, cont)
  190.         tramp.push(succeed([]), string, cont)
  191.  
  192.     return f
  193.  
  194. @memo
  195. def opt(p):
  196.  
  197.     def f(string, tramp, cont):
  198.         tramp.push(p, string, cont)
  199.         tramp.puch(succeed([]), string, cont)
  200.  
  201.     return f
  202.  
  203. @memo
  204. def ws(p):
  205.  
  206.     def f(string, tramp, cont):
  207.         tramp.push(seq([reg(r'[\s]*'), p, reg(r'[\s]*')]), string, cont)
  208.  
  209.     return f
  210.  
  211. @memo
  212. def red(p, fn):
  213.  
  214.     def f(val):
  215.         if type(val) == type([]):
  216.             return succeed(fn(*val))
  217.         else:
  218.             return succeed(fn(val))
  219.  
  220.     return bind(p, f)
  221.  
  222. def runParser(parser, string):
  223.     results = []
  224.     tramp = Trampoline()
  225.  
  226.     for cache in allCaches:
  227.         cache.clear()
  228.  
  229.     def myCont(result):
  230.         if isinstance(result, Success) and result.rest == '':
  231.             results.append(result)
  232.  
  233.     tramp.push(parser, string, myCont)
  234.     tramp.run()
  235.  
  236.     return results
  237.  
  238. # =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-= #
  239.  
  240. expr = (lambda *_:
  241.     alt([ red( seq([expr, lit('+'), term]),
  242.                lambda x, _, y: x + y),
  243.           red( seq([expr, lit('-'), term]),
  244.                lambda x, _, y: x - y),
  245.           term]) (*_))
  246.  
  247. term = (lambda *_:
  248.     alt([ red( seq([term, lit('*'), factor]),
  249.                lambda x, _, y: x * y),
  250.           red( seq([term, lit('/'), factor]),
  251.                lambda x, _, y: x / y),
  252.           factor]) (*_))
  253.  
  254. factor = (lambda *_:
  255.     alt ([ red( seq([ws(lit('(')), expr, ws(lit(')'))]),
  256.                 lambda _, e, __: e),
  257.            red( seq([ws(lit('-')), factor]),
  258.                 lambda _, f: -f),
  259.            number]) (*_))
  260.  
  261. number = red( ws(reg(r'[-+]?(?:0|[1-9][0-9]*)(?:\.[0-9]+)?')),
  262.               lambda _, n, __: float(n))
  263.  
  264. results = runParser(expr, '0.1*( \r1 + 2  *  5 \t+ -(15\n- 10) - - - 2*-1/0.5)')
  265. print '\n'.join([str(r) for r in results]), '\n', len(results), 'result(s)'
Success #stdin #stdout 0.14s 8888KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Success(1.0, '') 
1 result(s)
https://ideone.com/nEcJBD
language:
Python (cpython 2.7.16)
created:
12 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!