[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