lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


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