xipd

commit

f450786ac49b69fbdef78068e8b090c8121857f9

parent

d52b25c12086e64f3ecc0ad2550a4fc35844f0a4

Author

Tobias Bengfort <tobias.bengfort@posteo.de>

Date

2022-09-02 06:47

fix operator parsing

the previous algorithm did not execute left-to-right

https://en.wikipedia.org/wiki/Shunting_yard_algorithm

Diffstat

1 files changed, 59 insertions, 24 deletions

diff --git a/xipd/parser.py b/xipd/parser.py

@@ -1,5 +1,17 @@
    1     1 import re
    2     2 
   -1     3 # https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Operator_Precedence#table
   -1     4 OPERATORS = [
   -1     5 	('*~', 12),
   -1     6 	('*', 12),
   -1     7 	('/~', 12),
   -1     8 	('/', 12),
   -1     9 	('+~', 11),
   -1    10 	('+', 11),
   -1    11 	('-~', 11),
   -1    12 	('-', 11),
   -1    13 ]
   -1    14 
    3    15 
    4    16 class SyntaxError(TypeError):
    5    17 	pass
@@ -87,36 +99,59 @@ class Parser:
   87    99 			self.parse_raw,
   88   100 		])
   89   101 
   90    -1 	def parse_expr(self, s):
   91    -1 		return self.parse_any(s, [
   92    -1 			self.parse_op_add,
   93    -1 			self.parse_op_mult,
   94    -1 			self.parse_expr_no_op,
   95    -1 		])
   96    -1 
   97   102 	def parse_parens(self, s):
   98   103 		_, s = self.parse_re(s, r'\(')
   99   104 		expr, s = self.parse_expr(s)
  100   105 		_, s = self.parse_re(s, r'\)')
  101   106 		return expr, s
  102   107 
  103    -1 	def parse_op_add(self, s):
  104    -1 		left, s = self.parse_any(s, [
  105    -1 			self.parse_op_mult,
  106    -1 			self.parse_expr_no_op,
  107    -1 		])
  108    -1 		op, s = self.parse_re(s, r' *(\+|-)~? *')
  109    -1 		right, s = self.parse_expr(s)
  110    -1 		return ('op', op.strip(), left, right), s
  111    -1 
  112    -1 	def parse_op_mult(self, s):
  113    -1 		left, s = self.parse_expr_no_op(s)
  114    -1 		op, s = self.parse_re(s, r' *(\*|/)~? *')
  115    -1 		right, s = self.parse_any(s, [
  116    -1 			self.parse_op_mult,
  117    -1 			self.parse_expr_no_op,
  118    -1 		])
  119    -1 		return ('op', op.strip(), left, right), s
   -1   108 	def parse_op(self, s):
   -1   109 		s = s.lstrip()
   -1   110 		for op, precedence in OPERATORS:
   -1   111 			if s.startswith(op):
   -1   112 				s = s[len(op):].lstrip()
   -1   113 				return (op, precedence), s
   -1   114 		else:
   -1   115 			raise SyntaxError
   -1   116 
   -1   117 	def _apply_operator_precedence(self, ops, exprs):
   -1   118 		expr_stack = [exprs[0]]
   -1   119 		op_stack = []
   -1   120 
   -1   121 		def pop():
   -1   122 			op, _ = op_stack.pop()
   -1   123 			rhs = expr_stack.pop()
   -1   124 			lhs = expr_stack.pop()
   -1   125 			expr_stack.append(('op', op, lhs, rhs))
   -1   126 
   -1   127 		for i, op in enumerate(ops):
   -1   128 			while op_stack and op_stack[-1][1] >= op[1]:
   -1   129 				pop()
   -1   130 			op_stack.append(op)
   -1   131 			expr_stack.append(exprs[i + 1])
   -1   132 
   -1   133 		while op_stack:
   -1   134 			pop()
   -1   135 
   -1   136 		assert len(expr_stack) == 1
   -1   137 		return expr_stack[0]
   -1   138 
   -1   139 	def parse_expr(self, s):
   -1   140 		expr, s = self.parse_expr_no_op(s)
   -1   141 		exprs = [expr]
   -1   142 		ops = []
   -1   143 
   -1   144 		while True:
   -1   145 			try:
   -1   146 				op, s_tmp = self.parse_op(s)
   -1   147 				expr, s_tmp = self.parse_expr_no_op(s_tmp)
   -1   148 				ops.append(op)
   -1   149 				exprs.append(expr)
   -1   150 				s = s_tmp
   -1   151 			except SyntaxError:
   -1   152 				break
   -1   153 
   -1   154 		return self._apply_operator_precedence(ops, exprs), s
  120   155 
  121   156 	def parse_assign(self, s):
  122   157 		name, s = self.parse_name(s)