Re: O(n) Good Enough

Glen Austin <>
17 Jan 1999 20:50:04 -0500

          From comp.compilers

Related articles
O(n) Good Enough (Quinn Tyler Jackson) (1999-01-15)
Re: O(n) Good Enough (1999-01-17)
Re: O(n) Good Enough (James Jones) (1999-01-17)
Re: O(n) Good Enough (Glen Austin) (1999-01-17)
Re: O(n) Good Enough (Dennis Ritchie) (1999-01-19)
Re: O(n) Good Enough (David R Tribble) (1999-01-22)
Re: O(n) Good Enough (Dennis Ritchie) (1999-01-23)
| List of all articles for this month |

From: Glen Austin <>
Newsgroups: comp.compilers
Date: 17 Jan 1999 20:50:04 -0500
Organization: BEA Systems, Inc.
References: 99-01-052
Keywords: parse, comment

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?

Glen Austin
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.

Post a followup to this message

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