Re: testing LR(0), SLR(1), etc., and item sets

You asked for:
> For some grammar design experiments, I need a tool that will:
> 1) test a grammar for LR(0), SLR(1), and LALR(1).
> 2) print the closed item sets.
> 3) print the lookahead sets for the varios constructions.


Not to be discouraging, but I don't know of any tool that helps you do
exactly, what you ask. Item 2 you are likely to find a tool for, as
many tools do print this as part of their debugging information.


However, most tools support only 1 of the 3 grammar classes, generally
either SLR(1) or LALR(1), although LR(0) would be possible. Thus,
items 1 and 3 are not likely to be implemented.


The reason behind that is simple. The step from writing an SLR(1)
generator, given an LR(0) generator is trivial. Thus, no one that I'm
aware of implements LR(0).


Next, once one has implemented the mechanism to do LALR(1) analysis.
There is no advantage to doing only SLR(1) analysis--from the tool
writers perspective, since every SLR grammar is LALR and their is no
run-time efficiency to be gained from writing out SLR tables rather
than LALR ones (and trivial to the point of generally unmeasurable)
gains from doing SLR table generation over LALR table generation in
terms of generator speed.


What you are likely to find, is tools which implement both LALR(1) and
some form of LR(1) (or LR(k) or GLR parsing). There are advantages of
LALR parsing over the more complicated LR and GLR forms, and
vice-versa.


----------------------------------------------------------------------


However, given that. I think your question is moderately interesting
and I've done some small amount of investigation on the topic. It
turns out that, the question can be asked on a state-by-state basis.
More importantly, the question can be merged with the question of
whether a grammar is LL or LR.


In particular, one can ask as one builds up the set-of-items
construction, whether a given "state" (that is sub-portion of a
grammar being parsed in context of the whole grammar) is LL(k)
parseable and if not, if the state has any reductions, whether the
state is LR(0), SLR, LALR, LR(1), LR(k), or GLR parseable.


I have been considering developing a verion of Yacc++ which does that,
because if the grammar is LL parseable, it is often worthwhile to
generate a recursive-descent parser for it. Moreover, with some work
the LR variants can be fit into an LL scheme so that the resulting
parser looks like a recursive descent parser for those parts of the
grammar which are LL, but shifts into a table driven mode for exactly
those parts of the grammar which are not (and where necessary invokes
the more general GLR mechanism for those parts which are not
deterministic).


----------------------------------------------------------------------


The next question becomes how interested you are in the question and
how much work you want to do. If you are seriously interested in the
question, and willing to implement a solution within an existing
framework (i.e. the one used by Yacc++), I would be willing to provide
you the sources and assistance, in return for the resulting completed
implementation. It is not a "trivial" task, but I believe that
significantly interesting parts of it could be done in about a month
or so, enough that you would have the answers to your grammar design
questions.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
19 Bronte Way #33M voice : (508) 435-5016
Marlboro, MA 01752 USA fax : (508) 251-2347 (24 hours)

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