Kay Röpke wrote:
hi!
On Mar 4, 2009, at 3:42 AM, Baron Schwartz wrote:
I'm just curious....
You seem to imply that parsing involves building the parse tree.
Logically, parsing and building the parse tree could be separated
(event based parser, where the parser signals parse events and a
listener does something interesting such as building the parse tree)
I'm just curious if there is some rule ofthe tumb that determines
whether it'd be better to integrate building the parse tree rather
than abstract it using an event-based parser design.
I think Jim kind of said this already, but I'll say it a different
way. You're probably confusing parsing with tokenizing and lexing and
all kinds of other stuff.
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.
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.
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).
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).
Fifth, are some easy tricks for taking constant expressions and type
conversions out of inner loops. Call me when you get there.
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.
--
Jim Starkey
President, NimbusDB, Inc.
978 526-1376
_______________________________________________
Mailing list: https://launchpad.net/~drizzle-discuss
Post to : [email protected]
Unsubscribe : https://launchpad.net/~drizzle-discuss
More help : https://help.launchpad.net/ListHelp
