use LL(1) or LALR(1) for JavaScript SQL interpreter?

Hi,


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
appreciated.


My goal is to write an database management system (DBMS) in JavaScript
so that other JavaScript in a browser can manipulate a lot of data
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
data.


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
KB of JavaScript. I can make it so the tokenizer produces an array of
JavaScript objects: one for each token.


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
would have to rewrite Lemon to produce a JavaScript parser. The parser
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?


Thank you,
Peter

Return to the comp.compilers page.
Search the comp.compilers archives again.