On Mar 5, 2009, at 5:01 PM, Jim Starkey wrote:
my 2¢:
1) retain the current lexer if you care for charset support
(drizzle can probably skip this)
2) retain the current lexer if you care for all the edge cases it
handles (hard to fully recreate with a tool, trust me)
3) build a grammar for the MySQL/drizzle language, start small,
without joins and subselects feeding of the token stream from the
existing lexer (this is one function and one token struct, should
be relatively easy to adapt to other lexers)
4) let the generated (or handwritten if you have too much time)
parser build an AST(!) _not_ a parse tree (reason: parse trees
change as you change the parser, ASTs are not supposed to change
simply because you split a recognition step. an AST needs design,
obviously)
5) _only_ build an AST, do no binding or anything else (except you
need it to successfully parse, like names of functions added by
plugins or something like that - note: you probably do not need the
function's prototypes, treat that part as a name binding problem)
6) traverse the AST, do name binding (if there are more things you
need to do to verify the semantics of the sentence, either do
multiple passes or if you know beforehand that this will be too
slow, try to do it in one pass)
7) optimize the tree (probably a peephole optimizer, like constant
folding etc)
8) restructure the rest of the code that it can deal with the tree
you've built (this should probably not be the last step
chronologically, because i'm sure there will be problems where you
cannot easily change code to the nice new reality you've created
with the AST ;))
A couple of thoughts and quibbles.
First, drizzle should be all Unicode/UTF-8. Translations between
local character sets and UTF-8 are client, not server, issues.
yeah, that's why i noted that drizzle might want to skip this step.
other's are not this fortunate :( although i fully agree that some
unicode encoding ought to be enough support in a server.
luckily this is a lexer issue, the parser couldn't care less :)
Second, AST (abstract syntax tree -- I had to look it up myself) is
differs from a "parse" tree in that a parse tree represents
syntactic irrelevancies like parenthesis. In all fairly, I think
that parse trees are primarily generated by undergraduates before
they change their majors to marketing.
sorry, i should've spelled AST out at least once.
parse trees have merit outside undergrad classes, though ;) syntax-
aware editors are one prime example for the need of every little
semantically useless information about the input. servers naturally
need only know what the meaning of the sentence was and can build the
abstract view of things.
Third, I applaud your definition of parser. To make it short and
simple: *Parsers parse*. Having a parse do *anything* else is
*always* a mistake (I've written dozens of parsers and made lots of
mistakes).
oh yeah, it's really easy to mess it up badly, i agree. however,
depending on the language you need to parse, you can't produce a
"pure" parser (see the C++ parser mess…). i'm not yet certain where
the mysql dialect falls into in this respect.
most likely you need information about the added UDFs, because
otherwise using one in a query would be a syntax error, because you
couldn't descend into the function call rule. the same thing probably
applies to user defined types, if they ever materialize.
otoh, maybe we can fake UDF recognition by blindly accepting anything
that remotely looks like a function call and then resolve it in a
later stage. i will certainly find out, though. moving it into the
parser is nice because you can error out much earlier and skip a
postprocessing step that needs to find all the potential function
calls in the tree. this is not a major design decision, because it's
rather localized.
Fourth, trying to augment a syntax tree during semantic analysis
will prove short sighted. Stuff like view processing, virtual field
substitution, validation expression incorporation, and filterset
integration all happen during semantic analysis. Trying to stick
with the original tree only leads to grief (see Rdb/ELN for a good
example).
i honestly think there are a few operations that can be done with
rewriting/augmenting the existing tree. others are more natural and
maintainable if done on separate trees (i.e. one pass takes an input
tree and builds a second tree from it). most of the trees for sql
should not be large anyway, unlike those used in compilers.
i'm not experienced enough to comment on the specific examples you
mention, so i won't :)
Fifth, are some easy tricks for taking constant expressions and type
conversions out of inner loops. Call me when you get there.
i'll track you down ;)
And last, an execution structure is a sublime alternative to the
horrible MySQL execution spaghetti. It makes so much for sense to
simplify and accelerate the code by making decisions at compile/
optimize time rather than looking at dozens of flags and switches at
runtime to figure out what's supposed to happen. And, might I add,
it's also maintainable.
+1
cheers,
-k
--
Kay Roepke
Software Engineer, MySQL Enterprise Tools
Sun Microsystems GmbH Sonnenallee 1, DE-85551 Kirchheim-Heimstetten
Geschaeftsfuehrer: Thomas Schroeder, Wolfang Engels, Dr. Roland Boemer
Vorsitz d. Aufs.rat.: Martin Haering HRB MUC 161028
_______________________________________________
Mailing list: https://launchpad.net/~drizzle-discuss
Post to : [email protected]
Unsubscribe : https://launchpad.net/~drizzle-discuss
More help : https://help.launchpad.net/ListHelp
