LAparser.py 19 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462
  1. """
  2. Purpose: Linear Algebra Parser
  3. Based on: SimpleCalc.py example (author Paul McGuire) in pyparsing-1.3.3
  4. Author: Mike Ellis
  5. Copyright: Ellis & Grant, Inc. 2005
  6. License: You may freely use, modify, and distribute this software.
  7. Warranty: THIS SOFTWARE HAS NO WARRANTY WHATSOEVER. USE AT YOUR OWN RISK.
  8. Notes: Parses infix linear algebra (LA) notation for vectors, matrices, and scalars.
  9. Output is C code function calls. The parser can be run as an interactive
  10. interpreter or included as module to use for in-place substitution into C files
  11. containing LA equations.
  12. Supported operations are:
  13. OPERATION: INPUT OUTPUT
  14. Scalar addition: "a = b+c" "a=(b+c)"
  15. Scalar subtraction: "a = b-c" "a=(b-c)"
  16. Scalar multiplication: "a = b*c" "a=b*c"
  17. Scalar division: "a = b/c" "a=b/c"
  18. Scalar exponentiation: "a = b^c" "a=pow(b,c)"
  19. Vector scaling: "V3_a = V3_b * c" "vCopy(a,vScale(b,c))"
  20. Vector addition: "V3_a = V3_b + V3_c" "vCopy(a,vAdd(b,c))"
  21. Vector subtraction: "V3_a = V3_b - V3_c" "vCopy(a,vSubtract(b,c))"
  22. Vector dot product: "a = V3_b * V3_c" "a=vDot(b,c)"
  23. Vector outer product: "M3_a = V3_b @ V3_c" "a=vOuterProduct(b,c)"
  24. Vector magn. squared: "a = V3_b^Mag2" "a=vMagnitude2(b)"
  25. Vector magnitude: "a = V3_b^Mag" "a=sqrt(vMagnitude2(b))"
  26. Matrix scaling: "M3_a = M3_b * c" "mCopy(a,mScale(b,c))"
  27. Matrix addition: "M3_a = M3_b + M3_c" "mCopy(a,mAdd(b,c))"
  28. Matrix subtraction: "M3_a = M3_b - M3_c" "mCopy(a,mSubtract(b,c))"
  29. Matrix multiplication: "M3_a = M3_b * M3_c" "mCopy(a,mMultiply(b,c))"
  30. Matrix by vector mult.: "V3_a = M3_b * V3_c" "vCopy(a,mvMultiply(b,c))"
  31. Matrix inversion: "M3_a = M3_b^-1" "mCopy(a,mInverse(b))"
  32. Matrix transpose: "M3_a = M3_b^T" "mCopy(a,mTranspose(b))"
  33. Matrix determinant: "a = M3_b^Det" "a=mDeterminant(b)"
  34. The parser requires the expression to be an equation. Each non-scalar variable
  35. must be prefixed with a type tag, 'M3_' for 3x3 matrices and 'V3_' for 3-vectors.
  36. For proper compilation of the C code, the variables need to be declared without
  37. the prefix as float[3] for vectors and float[3][3] for matrices. The operations do
  38. not modify any variables on the right-hand side of the equation.
  39. Equations may include nested expressions within parentheses. The allowed binary
  40. operators are '+-*/^' for scalars, and '+-*^@' for vectors and matrices with the
  41. meanings defined in the table above.
  42. Specifying an improper combination of operands, e.g. adding a vector to a matrix,
  43. is detected by the parser and results in a Python TypeError Exception. The usual cause
  44. of this is omitting one or more tag prefixes. The parser knows nothing about a
  45. a variable's C declaration and relies entirely on the type tags. Errors in C
  46. declarations are not caught until compile time.
  47. Usage: To process LA equations embedded in source files, import this module and
  48. pass input and output file objects to the fprocess() function. You can
  49. can also invoke the parser from the command line, e.g. 'python LAparser.py',
  50. to run a small test suite and enter an interactive loop where you can enter
  51. LA equations and see the resulting C code.
  52. """
  53. import re,sys
  54. from pyparsing import Word, alphas, ParseException, Literal, CaselessLiteral \
  55. , Combine, Optional, nums, Forward, ZeroOrMore, \
  56. StringEnd, alphanums
  57. # Debugging flag can be set to either "debug_flag=True" or "debug_flag=False"
  58. debug_flag=False
  59. #----------------------------------------------------------------------------
  60. # Variables that hold intermediate parsing results and a couple of
  61. # helper functions.
  62. exprStack = [] # Holds operators and operands parsed from input.
  63. targetvar = None # Holds variable name to left of '=' sign in LA equation.
  64. def _pushFirst( str, loc, toks ):
  65. if debug_flag: print("pushing ", toks[0], "str is ", str)
  66. exprStack.append( toks[0] )
  67. def _assignVar( str, loc, toks ):
  68. global targetvar
  69. targetvar = toks[0]
  70. #-----------------------------------------------------------------------------
  71. # The following statements define the grammar for the parser.
  72. point = Literal('.')
  73. e = CaselessLiteral('E')
  74. plusorminus = Literal('+') | Literal('-')
  75. number = Word(nums)
  76. integer = Combine( Optional(plusorminus) + number )
  77. floatnumber = Combine( integer +
  78. Optional( point + Optional(number) ) +
  79. Optional( e + integer )
  80. )
  81. lbracket = Literal("[")
  82. rbracket = Literal("]")
  83. ident = Forward()
  84. ## The definition below treats array accesses as identifiers. This means your expressions
  85. ## can include references to array elements, rows and columns, e.g., a = b[i] + 5.
  86. ## Expressions within []'s are not presently supported, so a = b[i+1] will raise
  87. ## a ParseException.
  88. ident = Combine(Word(alphas + '-',alphanums + '_') + \
  89. ZeroOrMore(lbracket + (Word(alphas + '-',alphanums + '_')|integer) + rbracket) \
  90. )
  91. plus = Literal( "+" )
  92. minus = Literal( "-" )
  93. mult = Literal( "*" )
  94. div = Literal( "/" )
  95. outer = Literal( "@" )
  96. lpar = Literal( "(" ).suppress()
  97. rpar = Literal( ")" ).suppress()
  98. addop = plus | minus
  99. multop = mult | div | outer
  100. expop = Literal( "^" )
  101. assignop = Literal( "=" )
  102. expr = Forward()
  103. atom = ( ( e | floatnumber | integer | ident ).setParseAction(_pushFirst) |
  104. ( lpar + expr.suppress() + rpar )
  105. )
  106. factor = Forward()
  107. factor << atom + ZeroOrMore( ( expop + factor ).setParseAction( _pushFirst ) )
  108. term = factor + ZeroOrMore( ( multop + factor ).setParseAction( _pushFirst ) )
  109. expr << term + ZeroOrMore( ( addop + term ).setParseAction( _pushFirst ) )
  110. equation = (ident + assignop).setParseAction(_assignVar) + expr + StringEnd()
  111. # End of grammar definition
  112. #-----------------------------------------------------------------------------
  113. ## The following are helper variables and functions used by the Binary Infix Operator
  114. ## Functions described below.
  115. vprefix = 'V3_'
  116. vplen = len(vprefix)
  117. mprefix = 'M3_'
  118. mplen = len(mprefix)
  119. ## We don't support unary negation for vectors and matrices
  120. class UnaryUnsupportedError(Exception): pass
  121. def _isvec(ident):
  122. if ident[0] == '-' and ident[1:vplen+1] == vprefix:
  123. raise UnaryUnsupportedError
  124. else: return ident[0:vplen] == vprefix
  125. def _ismat(ident):
  126. if ident[0] == '-' and ident[1:mplen+1] == mprefix:
  127. raise UnaryUnsupportedError
  128. else: return ident[0:mplen] == mprefix
  129. def _isscalar(ident): return not (_isvec(ident) or _ismat(ident))
  130. ## Binary infix operator (BIO) functions. These are called when the stack evaluator
  131. ## pops a binary operator like '+' or '*". The stack evaluator pops the two operand, a and b,
  132. ## and calls the function that is mapped to the operator with a and b as arguments. Thus,
  133. ## 'x + y' yields a call to addfunc(x,y). Each of the BIO functions checks the prefixes of its
  134. ## arguments to determine whether the operand is scalar, vector, or matrix. This information
  135. ## is used to generate appropriate C code. For scalars, this is essentially the input string, e.g.
  136. ## 'a + b*5' as input yields 'a + b*5' as output. For vectors and matrices, the input is translated to
  137. ## nested function calls, e.g. "V3_a + V3_b*5" yields "V3_vAdd(a,vScale(b,5)". Note that prefixes are
  138. ## stripped from operands and function names within the argument list to the outer function and
  139. ## the appropriate prefix is placed on the outer function for removal later as the stack evaluation
  140. ## recurses toward the final assignment statement.
  141. def _addfunc(a,b):
  142. if _isscalar(a) and _isscalar(b): return "(%s+%s)"%(a,b)
  143. if _isvec(a) and _isvec(b): return "%svAdd(%s,%s)"%(vprefix,a[vplen:],b[vplen:])
  144. if _ismat(a) and _ismat(b): return "%smAdd(%s,%s)"%(mprefix,a[mplen:],b[mplen:])
  145. else: raise TypeError
  146. def _subfunc(a,b):
  147. if _isscalar(a) and _isscalar(b): return "(%s-%s)"%(a,b)
  148. if _isvec(a) and _isvec(b): return "%svSubtract(%s,%s)"%(vprefix,a[vplen:],b[vplen:])
  149. if _ismat(a) and _ismat(b): return "%smSubtract(%s,%s)"%(mprefix,a[mplen:],b[mplen:])
  150. else: raise TypeError
  151. def _mulfunc(a,b):
  152. if _isscalar(a) and _isscalar(b): return "%s*%s"%(a,b)
  153. if _isvec(a) and _isvec(b): return "vDot(%s,%s)"%(a[vplen:],b[vplen:])
  154. if _ismat(a) and _ismat(b): return "%smMultiply(%s,%s)"%(mprefix,a[mplen:],b[mplen:])
  155. if _ismat(a) and _isvec(b): return "%smvMultiply(%s,%s)"%(vprefix,a[mplen:],b[vplen:])
  156. if _ismat(a) and _isscalar(b): return "%smScale(%s,%s)"%(mprefix,a[mplen:],b)
  157. if _isvec(a) and _isscalar(b): return "%svScale(%s,%s)"%(vprefix,a[mplen:],b)
  158. else: raise TypeError
  159. def _outermulfunc(a,b):
  160. ## The '@' operator is used for the vector outer product.
  161. if _isvec(a) and _isvec(b):
  162. return "%svOuterProduct(%s,%s)"%(mprefix,a[vplen:],b[vplen:])
  163. else: raise TypeError
  164. def _divfunc(a,b):
  165. ## The '/' operator is used only for scalar division
  166. if _isscalar(a) and _isscalar(b): return "%s/%s"%(a,b)
  167. else: raise TypeError
  168. def _expfunc(a,b):
  169. ## The '^' operator is used for exponentiation on scalars and
  170. ## as a marker for unary operations on vectors and matrices.
  171. if _isscalar(a) and _isscalar(b): return "pow(%s,%s)"%(str(a),str(b))
  172. if _ismat(a) and b=='-1': return "%smInverse(%s)"%(mprefix,a[mplen:])
  173. if _ismat(a) and b=='T': return "%smTranspose(%s)"%(mprefix,a[mplen:])
  174. if _ismat(a) and b=='Det': return "mDeterminant(%s)"%(a[mplen:])
  175. if _isvec(a) and b=='Mag': return "sqrt(vMagnitude2(%s))"%(a[vplen:])
  176. if _isvec(a) and b=='Mag2': return "vMagnitude2(%s)"%(a[vplen:])
  177. else: raise TypeError
  178. def _assignfunc(a,b):
  179. ## The '=' operator is used for assignment
  180. if _isscalar(a) and _isscalar(b): return "%s=%s"%(a,b)
  181. if _isvec(a) and _isvec(b): return "vCopy(%s,%s)"%(a[vplen:],b[vplen:])
  182. if _ismat(a) and _ismat(b): return "mCopy(%s,%s)"%(a[mplen:],b[mplen:])
  183. else: raise TypeError
  184. ## End of BIO func definitions
  185. ##----------------------------------------------------------------------------
  186. # Map operator symbols to corresponding BIO funcs
  187. opn = { "+" : ( _addfunc ),
  188. "-" : ( _subfunc ),
  189. "*" : ( _mulfunc ),
  190. "@" : ( _outermulfunc ),
  191. "/" : ( _divfunc),
  192. "^" : ( _expfunc ), }
  193. ##----------------------------------------------------------------------------
  194. # Recursive function that evaluates the expression stack
  195. def _evaluateStack( s ):
  196. op = s.pop()
  197. if op in "+-*/@^":
  198. op2 = _evaluateStack( s )
  199. op1 = _evaluateStack( s )
  200. result = opn[op]( op1, op2 )
  201. if debug_flag: print(result)
  202. return result
  203. else:
  204. return op
  205. ##----------------------------------------------------------------------------
  206. # The parse function that invokes all of the above.
  207. def parse(input_string):
  208. """
  209. Accepts an input string containing an LA equation, e.g.,
  210. "M3_mymatrix = M3_anothermatrix^-1" returns C code function
  211. calls that implement the expression.
  212. """
  213. global exprStack
  214. global targetvar
  215. # Start with a blank exprStack and a blank targetvar
  216. exprStack = []
  217. targetvar=None
  218. if input_string != '':
  219. # try parsing the input string
  220. try:
  221. L=equation.parseString( input_string )
  222. except ParseException as err:
  223. print('Parse Failure', file=sys.stderr)
  224. print(err.line, file=sys.stderr)
  225. print(" "*(err.column-1) + "^", file=sys.stderr)
  226. print(err, file=sys.stderr)
  227. raise
  228. # show result of parsing the input string
  229. if debug_flag:
  230. print(input_string, "->", L)
  231. print("exprStack=", exprStack)
  232. # Evaluate the stack of parsed operands, emitting C code.
  233. try:
  234. result=_evaluateStack(exprStack)
  235. except TypeError:
  236. print("Unsupported operation on right side of '%s'.\nCheck for missing or incorrect tags on non-scalar operands."%input_string, file=sys.stderr)
  237. raise
  238. except UnaryUnsupportedError:
  239. print("Unary negation is not supported for vectors and matrices: '%s'"%input_string, file=sys.stderr)
  240. raise
  241. # Create final assignment and print it.
  242. if debug_flag: print("var=",targetvar)
  243. if targetvar != None:
  244. try:
  245. result = _assignfunc(targetvar,result)
  246. except TypeError:
  247. print("Left side tag does not match right side of '%s'"%input_string, file=sys.stderr)
  248. raise
  249. except UnaryUnsupportedError:
  250. print("Unary negation is not supported for vectors and matrices: '%s'"%input_string, file=sys.stderr)
  251. raise
  252. return result
  253. else:
  254. print("Empty left side in '%s'"%input_string, file=sys.stderr)
  255. raise TypeError
  256. ##-----------------------------------------------------------------------------------
  257. def fprocess(infilep,outfilep):
  258. """
  259. Scans an input file for LA equations between double square brackets,
  260. e.g. [[ M3_mymatrix = M3_anothermatrix^-1 ]], and replaces the expression
  261. with a comment containing the equation followed by nested function calls
  262. that implement the equation as C code. A trailing semi-colon is appended.
  263. The equation within [[ ]] should NOT end with a semicolon as that will raise
  264. a ParseException. However, it is ok to have a semicolon after the right brackets.
  265. Other text in the file is unaltered.
  266. The arguments are file objects (NOT file names) opened for reading and
  267. writing, respectively.
  268. """
  269. pattern = r'\[\[\s*(.*?)\s*\]\]'
  270. eqn = re.compile(pattern,re.DOTALL)
  271. s = infilep.read()
  272. def parser(mo):
  273. ccode = parse(mo.group(1))
  274. return "/* %s */\n%s;\nLAParserBufferReset();\n"%(mo.group(1),ccode)
  275. content = eqn.sub(parser,s)
  276. outfilep.write(content)
  277. ##-----------------------------------------------------------------------------------
  278. def test():
  279. """
  280. Tests the parsing of various supported expressions. Raises
  281. an AssertError if the output is not what is expected. Prints the
  282. input, expected output, and actual output for all tests.
  283. """
  284. print("Testing LAParser")
  285. testcases = [
  286. ("Scalar addition","a = b+c","a=(b+c)"),
  287. ("Vector addition","V3_a = V3_b + V3_c","vCopy(a,vAdd(b,c))"),
  288. ("Vector addition","V3_a=V3_b+V3_c","vCopy(a,vAdd(b,c))"),
  289. ("Matrix addition","M3_a = M3_b + M3_c","mCopy(a,mAdd(b,c))"),
  290. ("Matrix addition","M3_a=M3_b+M3_c","mCopy(a,mAdd(b,c))"),
  291. ("Scalar subtraction","a = b-c","a=(b-c)"),
  292. ("Vector subtraction","V3_a = V3_b - V3_c","vCopy(a,vSubtract(b,c))"),
  293. ("Matrix subtraction","M3_a = M3_b - M3_c","mCopy(a,mSubtract(b,c))"),
  294. ("Scalar multiplication","a = b*c","a=b*c"),
  295. ("Scalar division","a = b/c","a=b/c"),
  296. ("Vector multiplication (dot product)","a = V3_b * V3_c","a=vDot(b,c)"),
  297. ("Vector multiplication (outer product)","M3_a = V3_b @ V3_c","mCopy(a,vOuterProduct(b,c))"),
  298. ("Matrix multiplication","M3_a = M3_b * M3_c","mCopy(a,mMultiply(b,c))"),
  299. ("Vector scaling","V3_a = V3_b * c","vCopy(a,vScale(b,c))"),
  300. ("Matrix scaling","M3_a = M3_b * c","mCopy(a,mScale(b,c))"),
  301. ("Matrix by vector multiplication","V3_a = M3_b * V3_c","vCopy(a,mvMultiply(b,c))"),
  302. ("Scalar exponentiation","a = b^c","a=pow(b,c)"),
  303. ("Matrix inversion","M3_a = M3_b^-1","mCopy(a,mInverse(b))"),
  304. ("Matrix transpose","M3_a = M3_b^T","mCopy(a,mTranspose(b))"),
  305. ("Matrix determinant","a = M3_b^Det","a=mDeterminant(b)"),
  306. ("Vector magnitude squared","a = V3_b^Mag2","a=vMagnitude2(b)"),
  307. ("Vector magnitude","a = V3_b^Mag","a=sqrt(vMagnitude2(b))"),
  308. ("Complicated expression", "myscalar = (M3_amatrix * V3_bvector)^Mag + 5*(-xyz[i] + 2.03^2)","myscalar=(sqrt(vMagnitude2(mvMultiply(amatrix,bvector)))+5*(-xyz[i]+pow(2.03,2)))"),
  309. ("Complicated Multiline", "myscalar = \n(M3_amatrix * V3_bvector)^Mag +\n 5*(xyz + 2.03^2)","myscalar=(sqrt(vMagnitude2(mvMultiply(amatrix,bvector)))+5*(xyz+pow(2.03,2)))")
  310. ]
  311. all_passed = [True]
  312. def post_test(test, parsed):
  313. # copy exprStack to evaluate and clear before running next test
  314. parsed_stack = exprStack[:]
  315. exprStack.clear()
  316. name, testcase, expected = next(tc for tc in testcases if tc[1] == test)
  317. this_test_passed = False
  318. try:
  319. try:
  320. result=_evaluateStack(parsed_stack)
  321. except TypeError:
  322. print("Unsupported operation on right side of '%s'.\nCheck for missing or incorrect tags on non-scalar operands."%input_string, file=sys.stderr)
  323. raise
  324. except UnaryUnsupportedError:
  325. print("Unary negation is not supported for vectors and matrices: '%s'"%input_string, file=sys.stderr)
  326. raise
  327. # Create final assignment and print it.
  328. if debug_flag: print("var=",targetvar)
  329. if targetvar != None:
  330. try:
  331. result = _assignfunc(targetvar,result)
  332. except TypeError:
  333. print("Left side tag does not match right side of '%s'"%input_string, file=sys.stderr)
  334. raise
  335. except UnaryUnsupportedError:
  336. print("Unary negation is not supported for vectors and matrices: '%s'"%input_string, file=sys.stderr)
  337. raise
  338. else:
  339. print("Empty left side in '%s'"%input_string, file=sys.stderr)
  340. raise TypeError
  341. parsed['result'] = result
  342. parsed['passed'] = this_test_passed = result == expected
  343. finally:
  344. all_passed[0] = all_passed[0] and this_test_passed
  345. print('\n' + name)
  346. equation.runTests((t[1] for t in testcases), postParse=post_test)
  347. ##TODO: Write testcases with invalid expressions and test that the expected
  348. ## exceptions are raised.
  349. print("Tests completed!")
  350. print("PASSED" if all_passed[0] else "FAILED")
  351. assert all_passed[0]
  352. ##----------------------------------------------------------------------------
  353. ## The following is executed only when this module is executed as
  354. ## command line script. It runs a small test suite (see above)
  355. ## and then enters an interactive loop where you
  356. ## can enter expressions and see the resulting C code as output.
  357. if __name__ == '__main__':
  358. import sys
  359. if not sys.flags.interactive:
  360. # run testcases
  361. test()
  362. sys.exit(0)
  363. # input_string
  364. input_string=''
  365. # Display instructions on how to use the program interactively
  366. interactiveusage = """
  367. Entering interactive mode:
  368. Type in an equation to be parsed or 'quit' to exit the program.
  369. Type 'debug on' to print parsing details as each string is processed.
  370. Type 'debug off' to stop printing parsing details
  371. """
  372. print(interactiveusage)
  373. input_string = input("> ")
  374. while input_string != 'quit':
  375. if input_string == "debug on":
  376. debug_flag = True
  377. elif input_string == "debug off":
  378. debug_flag = False
  379. else:
  380. try:
  381. print(parse(input_string))
  382. except Exception:
  383. pass
  384. # obtain new input string
  385. input_string = input("> ")
  386. # if user types 'quit' then say goodbye
  387. print("Good bye!")
  388. import os
  389. os._exit(0)