RE: yacc for Pascal, was Why LL(1) Parsers do not support left recursion?

Quinn Tyler Jackson <qtj-query@shaw.ca>
6 Aug 2006 12:40:14 -0400

          From comp.compilers

Related articles
RE: yacc for Pascal, was Why LL(1) Parsers do not support left recursi qtj-query@shaw.ca (Quinn Tyler Jackson) (2006-07-31)
Re: yacc for Pascal, was Why LL(1) Parsers do not support left recursi DrDiettrich1@aol.com (Hans-Peter Diettrich) (2006-08-03)
RE: yacc for Pascal, was Why LL(1) Parsers do not support left recursi qtj-query@shaw.ca (Quinn Tyler Jackson) (2006-08-06)
| List of all articles for this month |

From: Quinn Tyler Jackson <qtj-query@shaw.ca>
Newsgroups: comp.compilers
Date: 6 Aug 2006 12:40:14 -0400
Organization: Compilers Central
References: 06-08-010
Keywords: parse, C++

I said:


> > I consider a grammar
> > broken (until proven otherwise) the moment it *must* call code in a
> > reduction to know whether or not it should accept something as legal.




DoDi asked:


> I'm just curious: could you make the C++ grammar work, so that it works
> without an external disambiguation between typenames and other
> identifiers?


The addition of named-index trie scoping provided a means to do
that. There were some new constructions also that allow for delayed
and controlled reparsing of substrings when a scope is left, that are
described in Adapting to Babel, that also make some of that more
possible.


The grammar-only-C++ project was a proof-of-concept more than anything
else: it showed that ad hockery could be avoided while still correctly
parsing C++ at the grammar level within near linear time in the
average case. While ideologically possible to do, and possible to do
without becoming *too* opaque, with a language such as C++, there is a
point where the exercise has proven itself and practicalities override
ideology. (Anyone *need* a new C++ parser?)


That said, the two grammars I find most graceful* are for the languages:


L = {a^n b^C(n) | C(n) is the Catalan number of n}
L = {a^n b^phi(n) | phi(n) is Euler's totient of n}


That these parse in less than O(n^2) and that the $-grammar for the Euler's
totient $-grammar has only 4 productions have stolen my attention from the
C++ $-grammar. ;-)


--
Quinn Tyler Jackson


http://www.thothic.com


* Well, these two and the linear-time p-knot-finding $-grammar.


Post a followup to this message

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