Re: SQL autocomplete project

George Neuner <>
Thu, 08 Oct 2009 03:46:38 -0400

          From comp.compilers

Related articles
SQL autocomplete project (console kid) (2009-10-06)
Re: SQL autocomplete project (Hans-Peter Diettrich) (2009-10-08)
Re: SQL autocomplete project (George Neuner) (2009-10-08)
Re: SQL autocomplete project (John Millaway) (2009-10-08)
Re: SQL autocomplete project (Chris F Clark) (2009-10-10)
| List of all articles for this month |

From: George Neuner <>
Newsgroups: comp.compilers
Date: Thu, 08 Oct 2009 03:46:38 -0400
Organization: A noiseless patient Spider
References: 09-10-005
Keywords: SQL, parse
Posted-Date: 09 Oct 2009 17:43:48 EDT

On Tue, 6 Oct 2009 17:32:02 -0700 (PDT), console kid
<> wrote:

>Hi I am doing my final year project , that is a SQL autocomplete
>library ( a dll that can used by any other win32 application ).

>I have a list of SQL grammar, so according to the rules in that
>grammar file the program will read that file and build internal NFA

I think you will need PDA for this recognition task. SQL is a pretty
simple language, but I don't believe NDFA is powerful enough to parse

>I am confused on this entirely , please give me a suggestion.
>This project is different from writing a parser tree. because
>parser is parsing the fully completed SQL syntax and this will
>not do that.

You're definitely confused. What you want *is* a predictive parser
which has partial match rule actions which display the syntax
alternatives going forward.

The main difference is that you want it to be (or at least appear)
interactive, matching as the user types rather than waiting for a line
or full SQL clause to be entered.

Because SQL queries tend to be short, you can simulate interactive
parsing by running the parser (from the beginning) on unfinished input
whenever the user types white space. The display actions should end
by failing the parse if the parser isn't in an accepting state.

For example:

    SELECT * FROM => displays "<table name>" and fails
    SELECT * FROM foo => displays "WHERE <expr>" and accepts because
                                                the where clause is optional

If the user keeps typing, you go on to parse the where clause.

>The algorithm should guess the possibilities using a graph traveling
>like a thing.

I assume you have to write this thing yourself because otherwise I
would say just use a parser generator and tie the parser to your input

If you are dead set on using graphs then I would take a look at the
LALR algorithm which should be more than sufficient for SQL. Think
about how your implementation could generate and navigate a state
graph rather than using the traditional tables and stack.


Post a followup to this message

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