|O(n) Good Enough email@example.com (Quinn Tyler Jackson) (1999-01-15)|
|Re: O(n) Good Enough J.Scheerder@cwi.nl (1999-01-17)|
|Re: O(n) Good Enough firstname.lastname@example.org (James Jones) (1999-01-17)|
|Re: O(n) Good Enough email@example.com (Glen Austin) (1999-01-17)|
|Re: O(n) Good Enough firstname.lastname@example.org (Dennis Ritchie) (1999-01-19)|
|Re: O(n) Good Enough email@example.com (David R Tribble) (1999-01-22)|
|Re: O(n) Good Enough firstname.lastname@example.org (Dennis Ritchie) (1999-01-23)|
|From:||Glen Austin <email@example.com>|
|Date:||17 Jan 1999 20:50:04 -0500|
|Organization:||BEA Systems, Inc.|
From my limited experience in looking into a C language grammar, it
appears that the efficiencies in compiler design appear to be
"gleaned" in more efficient symbol table lookup than in making the
"parse" more efficient.
Assuming you meant to try to optimize something like yacc, my words
would be please go ahead. Just getting grammars to work properly is
difficult enough for me, without having to try to rewrite the code
generating the code. (It's my understanding that the folks at AT&T
used to design the yystate, yyreduce, yygoto, yyrule, etc. tables by
hand, before yacc was designed, imagine that.)
Another approach, if the language being developed for was wide open,
would be to optimize the grammar of the language, but you might end up
with something more intelligible to a machine than a human. You might
get an O(n) parse, but a human might not be able to read the code.
Since I'm about to design a symbol table, I've been looking into
designs from books like "Compiler Design in C" and the Aho book
(Compilers Principles, Techniques, and Tools). Any other suggestions?
BEA Systems, Inc.
Quinn Tyler Jackson wrote:
> Two simple questions:
> Is a O(n) parser good enough?
> Although there is plenty of literature discussing the efficiency of
> low level (read character based) pattern matching algorithms, I
> haven't found much O(x) [where x is anything from n log m to n^r] type
> literature on the efficiency of parsers. Any pointers to literature
> in this area?
[Parsers are usually pretty fast, but lexers can be a performance issue.
Return to the
Search the comp.compilers archives again.