Re: How to check if grammar is LR(k)

Hossein Saffar asked:
> Is it possible to find out if a grammar is LR(k) or not without making
> the parsing table?


1) There are some sets of grammars which are known to be LR(k). For
      example, if all the recursion in the grammar is either left or
      right (but not a mixture of some left and some right)--the grammar
      is linear and all linear grammars are LR(k). Similarly, if the
      grammar is known to be LL(k), the grammar is known to be LR(k), but
      not necessarily SLR(k) or LALR(k).


2) Likewise, there are some things know to make a grammar inherently
      not LR(k), ambiguity is one of them. Thus, the inclusion of a rule
      like "A: A A ; /* A being a non-terminal */" is ambiguous and means
      any grammar with the rule used in it is not LR(k).


3) There is an algebra promoted by Mark William Hopkins (sp?) that
      purports to solve the LR problem, but produces results that have
      always struck me as supiciously contradictory of other facts I know
      of grammar theory. However, perhaps I just don't understand.


4) Making a parser table is easy (well, perhaps not by hand for a
      non-trivial grammar, but quite easy once mechanized).


Why do you ask?
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)

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