OpenEuphoria

RE: Inner loop compiler

• Posted by Pete E <xseal at harborside.com> Sep 05, 2002
• 652 views

Matthew Lewis wrote:
> This is exactly the approach I took for matheval (the most current code 
> out
> there is actually contained in EuSQL, which uses matheval).  You could 
> look
> at parseval.e.  It may not be the *best* way to implement this, but it 
> is
> easily extendible.  It would need some adjustment to work for this, 
> however,
> since it assumes that everything should be one giant expression, so it 
> ends
> up multiplying everything together when there is nothing else to 
> do--which
> is just what you'd expect for math:
> 
> (x+y)(x+y) => (x+y) * (x+y)
> 
> All you'd really have to do is take that part out.  Basically, it scans 
> the
> input, and turns things into tokens.  Each token has a precedence, which
> establishes the order in which things should be done (i.e., multiply 
> before
> you add).  Based on the precedence, tokens are 'collapsed':
> 
> "(x + 1)^2" =>
> { '(', {var,"x",{1}}, {add,{},{}}, {constant,{1},{}}, ')', 
> {exponent,{},{}},
> {constant,{2},{}} =>
> { '(',  {add,{var,"x",{1}},{constant,{1},{}}},  ')', {exponent,{},{}},
> {constant,{2},{}} =>
> {exponent,{add,{var,"x",{1}},{constant,{1},{}}}, {constant,{2},{}} } =>
> 
> {exponent,
>   {add,
>     {var,"x",{1}},
>     {constant,{1},{}}}, 
>   {constant,{2},{}} }


This collapse technique looks useful for an optimization phase.  The 
parsers I've written already handle operator precedence for arithmetic 
expressions.
 
> Parseval.e basically shows you what you need to do to set up your 
> tokens.
> resolve_math_func() is a way for files to get the proper id for math
> functions in the library.  reg_parse_func() tells parseval.e what to do
> about a new token, and supplies the routine id for the function that 
> will
> actually 'collapse' the token.  This is where error checking is done.  
> If
> you're interested, I'd be happy to answer any questions you have.
> 
> BTW, you can d/l EuSQL at
> http://www14.brinkster.com/matthewlewis/projects.html
> 
> Matt Lewis

The thing I haven't figured out how to do yet is convert the nested 
expression into a flat instruction sequence.  Some temporary storage 
will always be required.

Say you have the expression: a * b + x * y

The intermediate form is:
  {add, 
    {mul, {var, "a"}, {var, "b"},
    {mul, {var, "x"}, {var, "y"}
  }

The simpleton compiler might try to do this:
  mov eax, [@a]
  mul eax, [@b]

  mov eax, [@x]
  mul eax, [@y]

  add eax, eax

A smarter compiler might try to use a second register, but what happens 
when you run out of registers for a complex expression...  the stack 
will have to used somehow.  Maybe some temporary variables can be 
inserted by the parser when it sees a complicated expression... and let 
the optimizer substitute registers for the temp variables.

I also found some other examples of run-time assemblers and mathematical 
compilers here:

http://www.flipcode.com/cgi-bin/msg.cgi?showThread=COTD-ExpressionCompiler&forum=cotd&id=-1


http://www.flipcode.com/cgi-bin/msg.cgi?showThread=COTD-SoftWire&forum=cotd&id=-1


Pete