[antlr-interest] most efficient grammar pasing

Tom Liu TomL at avokia.com
Wed Dec 6 14:16:09 PST 2006


Hi Ter,

I didn't learn much about the pasing theory and algorithms
But in the recent several months, I have finshed two full
Grammar T-SQL parsers, one is for sql server, the other is for sybase.

I think the most efficient algorithm of parsing
will finally become the analyzing of grammar itself,
and Never do any analysis of what is to be parsed - the script
which is written according to the grammar.
No predication will be involved. 
It should have an expected parsing time performance of near O(n).

The result of grammar analyzing should be some kind of tree or graph
grammar structures. The parsing procedure is like a cut or narrowing
down
the posibilities of mattached grammar rules and then every
token is recognized and belongs to one of the grammar rules.
Finally, the script itself which is being parsed is prsented as a path 
in the grammar structure graph.


I initially got this idea from BMH String Pattern-matching Algorithm,
By studying it more deeply, I cognized that, dig and use more knowledge
of the pattern to be matched or the grammar to be used for parsing,
we can do more efficient processing, no matter what the materials to be
processed is.

Have fun

Tom



Date: Wed, 6 Dec 2006 10:44:33 -0800
From: Terence Parr <parrt at cs.usfca.edu>
Subject: [antlr-interest] quick description of LL(*) algorithm
To: Antlr Interest <antlr-interest at antlr.org>
Cc: PEG <peg at lists.csail.mit.edu>
Message-ID: <4936F5EF-9A35-438E-BA45-4DC7F59B29ED at cs.usfca.edu>
Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed

Hi,

I started putting this LL(*) description in the upcoming ANTLR v3  
book, but decided it was beyond the scope of the reference guide so  
here it is in the lookahead blog:

http://www.antlr.org/blog/antlr3/lookahead.tml

Not sure that it is useful to industry or academia because it is  
neither practical, nor complete, nor rigorous. ;)  Anyway, there you go.

Ter



More information about the antlr-interest mailing list