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

andrewd@cs.adelaide.edu.au (Andrew Dunstan)
Mon, 29 Jun 1992 00:21:11 GMT

          From comp.compilers

Related articles
Are there any good examples of FIRST () and FOLLOW ()? cosc143u@rosie.uh.edu (1992-06-20)
Re: Are there any good examples of FIRST () and FOLLOW ()? jos@and.nl (1992-06-22)
Re: Are there any good examples of FIRST () and FOLLOW ()? andrewd@cs.adelaide.edu.au (1992-06-25)
Re: Are there any good examples of FIRST () and FOLLOW ()? andrewd@cs.adelaide.edu.au (1992-06-29)
| List of all articles for this month |

Newsgroups: comp.compilers
From: andrewd@cs.adelaide.edu.au (Andrew Dunstan)
Organization: Compilers Central
Date: Mon, 29 Jun 1992 00:21:11 GMT
References: 92-06-100 92-06-125
Keywords: LL(1)

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
--


Post a followup to this message

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