Re: O(n) Good Enough

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.
-John]

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