Re: Parsing C++, was Is YACC / PCCTS used in commercial compilers?

Frank Barrus wrote:


> Yes, using recursive descent and
> backtracking makes the implementation of the parser easier, but ...
> Backtracking incurs a high execution overhead...
> unless the "common" non-backtracked path is carefully
> chosen to be the most frequent case ... LALR(1) has a more or
> less linear execution time.


I think that you are right that an LALR approach with modifications
for the ambiguous cases will be faster. But it's not a given that it
will be significantly faster. Is it better to reprocess a stack of
productions once the ambiguity has been resolved, than to back up and
reparse it? They sound like comparable processing to me. That being
said, I think that the LALR approach should be able rescan stuff less
often than an LL aproach becuase of it's increased power. However,
one may be able to take the time saved with a simpler grammar, and
optimize other parts of the system (like symbol tables), or come up
with some clever precompiled header or incremental compilation scheme,
or optimize the template expansion database across modules, or
whatever.


PS: Frank contacted me directly and noted that his technique is quite
efficient with respect to the post-processing of the ambiguous
productions. He agreees that it adds complexity to the grammar, which
may take time away from other optimizatins; however it would be best
to both use an efficient parser *and* optimize the rest of the system.


john lilley
==========================================================================
|| John Lilley GUIs phone: 303-543-9115 ||
|| Nerds for Hire, Inc. Parsers fax: 303-543-6069 ||
|| http://www.empathy.com jlilley@empathy.com ||
--

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