Re: Are there any good examples of FIRST () and FOLLOW ()?

I wrote:
|> cosc143u@rosie.uh.edu (91F9774) writes:
[...]
|> |> Example:
|> |> S->AB | epsilon
|> |> A->aA
|> |> | a
|> |> B->BS
|> |> | b
[...]
|> Your grammar is pretty hard to handle by ANY parsing
|> method. Yacc (bison, really) throws up its hands in horror no matter how
|> you transform the grammar. So, naturally enough, does an LL1 parser
|> generator. It seems to me to be inherently ambiguous.
|>


Mea maxima culpa! Max Hailperin has written to me pointing out that the
language described is in fact regular: (aa*b)*


It is true that eliminating left recursion and left-factoring the grammar
still leaves you with an ambiguous grammar. However, a regular grammar for
the language (for the augmented grammar) is:


S' -> S $ | $
S -> a R
R -> a R | b S | b


An LL1 grammar for it is:


S' -> S $
S -> a A b S | eps
A -> a A | eps


The rest of what I said is true, though :-)




BTW, this query was about predictive parsers, and was answered in that
vein. Follows play a somewhat different, although important role in LR
parser making. For information on this, see the excellent article by
DeREMER and PENELLO in ACM TOPLAS Vol 4. No 4. Oct 1982, pp 615-649


# Andrew Dunstan
# Department of Computer Science
# University of Adelaide
# South Australia
# net: andrewd@cs.adelaide.edu.au
--

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