Re: Parsing techniques

miano@worldnet.att.net (John M. Miano)
1 Dec 1996 22:54:27 -0500

          From comp.compilers
Related articles
Parsing techniques lex@prl.philips.nl (1993-05-04)
Re: Parsing techniques ipser@solomon.technet.sg (1993-05-07)
Re: Parsing techniques simonh@swidev.demon.co.uk (1993-05-08)
Parsing techniques kentr@rollinssoft.com (Kent Rollins) (1996-11-26)
Re: Parsing techniques scotts@metaware.com (Scott Stanchfield) (1996-12-01)
Re: Parsing techniques jon@mauney.com (1996-12-01)
Re: Parsing techniques miano@worldnet.att.net (1996-12-01)
Re: Parsing techniques jlilley@empathy.com (1996-12-01)
Re: Parsing techniques icedancer@ibm.net (1996-12-03)
Re: Parsing techniques house@usq.edu.au (Ron House) (1996-12-07)
Re: Parsing techniques grosch@cocolab.sub.com (1996-12-09)
Re: Parsing techniques parrt@MageLang.com (Terence Parr) (1996-12-09)
Re: Parsing techniques parrt@MageLang.com (Terence Parr) (1996-12-09)
[1 later articles]
| List of all articles for this month |
From: miano@worldnet.att.net (John M. Miano)
Newsgroups: comp.compilers
Date: 1 Dec 1996 22:54:27 -0500
Organization: John Miano Software
References: 96-11-157
Keywords: parse, LL(1), LALR, C++

Kent Rollins <kentr@rollinssoft.com> wrote:
>I am just getting into parsing and have some general questions about
>the subject. Most of the literature I have read seems to imply that
>LL(k) grammars are only for small/simple languages and that LR
>grammars must be used for thicker languages like C++. Am I misreading
>this info? Can C++ successfully be parsed with an LL(k) grammar? If
>so, would the resulting parser be easier to debug? Would it be easier
>to explain and recover from the errors it detects during parsing?


Many years ago I saw an LL grammar for C and it was easy to see why
this is rarely done. LL grammars do not allow left recursion which
makes creating the grammar much more difficult than with an LR
grammar.


>I have noticed numerous examples of ambiguous C/C++ statements posted
>in this newsgroup that cause problems for such parsers. Assuming the
>use of a lexer/parser combo, can all ambiguity be overcome or will we
>always be able to create a contrived code example that will break even
>the best C++ parser?


There are many C and C++ compilers that use LR parsers. Take a look at
the GNU C/C++ compiler source.


>Where do hand-coded, recursive decent parsers fall into the mix? I
>haven't read too much about them, but it seems that error recovery
>would be terribly difficult. I am looking for the Wirth book on this
>subject of which I have heard good reviews.


I suspect that more PeeCee compilers use this type of parsing just
from the error messages that they produce. The drawback of table
driven parsers is that they take up a lot of space. With 16bit systems
this can be quite a problem. For such a compiler take a look at the
LCC source.


>I have several books on parsing and compiler construction
>([Aho,Sethi,Ullman], [Hollub], [Wilhelm,Maurer]). All of these are
>excellent technical works, but none of them discuss the high-level
>aspects of parsing such as which techniques are best for a given
>language and a desired result. Any comments?


It seems that most newer languages are designed so that they are easy
to parse using YACC.


John


--

Post a followup to this message

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