OT(slightly): parser generator for expression with custom operators

[Lorenzo Donati <lorenzodonatibz@...>]

Hi All!

Warning - long post ahead!

Some recent threads have pushed me to post this. It is an idea which has 
been buzzing in my head for a long time (well I should say it is a 
problem since I don't have a solution for it :-)

Recently many posts have revolved around the idea of custom operators 
for Lua, in a way or another. I also have had several times the problem 
of parsing DSLs which would have had benefits if it were possible to 
define arbitrary custom operators in Lua *(wait, wait I'm not proposing 
an enhancement to Lua in this sense - please put away those menacing 
sticks :-)*.

I know that, if one has the ability to write down an appropriate grammar 
in BNF form, he could use parsers generators to build a parser for that 
purpose. Since I haven't got that ability (I never had a formal course 
in compiler theory or such) I've often wondered if there were a simple 
solution for parsing a very simple language, i.e. one made up only of 
math-like expressions, with prefix, infix and suffix operators.

So my question is rather theoretical (and maybe plainly silly, since my 
CS-fu is not very strong).

As an end user of a programming language like Lua, in which I often 
write simple DSLs, I'd like to be able to define such a parser by only 
defining the operators and their characteristics, not to write down a 
grammar. Some Lua pseudo-code to explain better what I mean:

-- this would generate an interpreter for
-- that expression language I mentioned;
-- its argument is a table describing which
-- operators must be supported and the action
-- to take when evaluating them
interpreter = parselib.NewInterpreter {

  {
    name = "assign",token = ":=",
    precedence_level = 5, type = "binary,infix",
    associate = "right",
    handler = function( x, y )
      x:assign(y)
    end
  }
  {
    name = "add",token = "+",
    precedence_level = 4, type = "binary,infix",
    associate = "left",
    handler = function( x, y )
     return x + y
    end
  }
  {
    name = "mogrify",token = "~!~",
    precedence_level = 3, type = "binary,infix",
    associate = "left",
    handler = function( x, y )
      return x:mogrify(y)
    end
  }
  {
    name = "pre_inc",token = "++",
    precedence_level = 2, type = "unary,prefix",
    associate = "right",
    handler = function( x )
      return x:increment()
    end
  }

}


this "magic" library will build an interpreter (at runtime) that will 
operate for example this way:

-- sets symbolic names for objects to be used
-- in the expressions to be evaluated
interpreter:SetEnvironment { a = a_obj, b = b_obj, c = c_obj }

interpreter:Evaluate "a = b ~!~ c"

the previous call would translate that expression into an equivalent 
evaluation of this expression:

a_obj:assign( b_obj:mogrify(c_obj) )


This is more or less what I'd like to be available.

My question for CS people out there is: is it possible to automatically 
generate a parser for such an expression language automatically, given 
only a "tabular" description of the operators characteristics, under 
some reasonable constraints (e.g., only unary and binary ops supported; 
binary are only infix, etc.)?

Or is there some underspecification in what I envision, i.e. a classic 
grammar description MUST be used because that tabular description is not 
powerful enough to let an automatic parser generator to do its work?
Or maybe this is possible, but the tabular description should contain 
much more information than that, and so it will spoil the semplicity of 
the envisioned approach.

Ok, I hope I haven't bothered the list too much with this.

If I'm lucky maybe some smart guy will start itching on this and will 
someday create this DSL dream-lib for CS-impaired people like me :-)


TIA and cheers
-- Lorenzo