Re: Parsing techniques

John Lilley (jlilley@empathy.com) wrote:
: Yes. I'm working with a public-domain C++ grammar that uses PCCTS, an
: LL(k) generator. Although LL(k) is weaker than LALR(k), PCCTS augments
: it with predicates and backtracking. PCCTS also performs intelligent
: analysis when k>1 to avoid exponential explosion of the leading sets. I
: have heard but cannot confirm that LALR(k>1) is almost impossible for
: complex grammars. Does anyone else have experience regarding LALR(k>1)?
: I'd like to know for sure...


It is possible to extend LALR parsing the same way as does PCCTS for
LL parsing. I have added predicates, backtracking, intelligent
analysis for LALR(k>1), and full analysis for LALR(k>1) to the LALR
parser generator LARK of the Cocktail Toolbox. It works pretty well
for complex grammars such as for example COBOL, PL/I, and C++. My
COBOL grammar is really huge: It has around 2000 rules. It produces
200 states with LR conflicts. Around 50% of the conflicts can be
resolved automatically using LALR(2) analysis. For PL/I and C++ the
LALR(k>1) analysis is of no help because unlimited lookahead is needed
for conflict resolution. This can be achieved with the backtracking
facility.


Best regards


Josef Grosch


CoCoLab
Hagsfelder Allee 16
D-76131 Karlsruhe
Germany


Tel.: +49-721-697061
Fax : +49-721-661966
Mail: grosch@cocolab.sub.com
--

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