|From:||"Peter Michaux" <firstname.lastname@example.org>|
|Date:||11 Nov 2006 15:45:21 -0500|
|Keywords:||parse, SQL, question|
|Posted-Date:||11 Nov 2006 15:45:21 EST|
I have been reading "Modern Compiler Implemenation in Java" by Andrew
W. Appel. I'm getting a bit familiar with the different kinds of
parsers and roughly how they work. It is all very interesting! Any
experienced advice on how to proceed with my project would be greatly
easily using a small subset of SQL. For me, this is quite a big
objective but a client of mine wants to load up the browser with a
whole bunch of data and SQL would be a very nice way to play with the
I have been looking at the SQLite implementation as a reference. I
think I can clone the hand-written C tokenizer from SQLite into about 4
The parser is next and there are at least a couple options.
My first thought was to handwrite a recursive decent interpreter that
parses the SQL on the decent and evaluates it on the way back up.
Looking around on Google is seems like there must exist an LL(1)
grammar for SQL that would guide me though this process. Does anyone
know of a really good LL(1) SQL grammar I could use?
SQLite uses an LALR(1) parser generator called Lemon that generates a C
parser. Lemon is about 4000 lines of code. If I want to use a LALR(1) I
for SQLite that Lemon generates is about 70 KB which is way too big for
browser use in my application given today's bandwidths. Of course
SQLite implements a much larger subset of SQL than I am considering and
those LALR(1) state tables look like they might grow exponentially by
the number of options. However is it generally true that LALR(1)
parsers are much bigger than recusive decent parsers?
Any suggestions about which type of parser I should pursue?
Return to the
Search the comp.compilers archives again.