[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
- Subject: OT(slightly): parser generator for expression with custom operators
- From: Lorenzo Donati <lorenzodonatibz@...>
- Date: Wed, 29 Jun 2011 17:13:29 +0200
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