Re: computing LOOKAHEAD sets

"J.H.Jongejan" <jjan@cs.rug.nl>
2 Sep 2005 14:18:36 -0400

          From comp.compilers

Related articles
computing LOOKAHEAD sets vkatsikaros@yahoo.gr (Vangelis Katsikaros) (2005-08-31)
Re: computing LOOKAHEAD sets jjan@cs.rug.nl (J.H.Jongejan) (2005-09-02)
| List of all articles for this month |

From: "J.H.Jongejan" <jjan@cs.rug.nl>
Newsgroups: comp.compilers
Date: 2 Sep 2005 14:18:36 -0400
Organization: RuG
References: 05-08-114
Keywords: parse

Vangelis Katsikaros wrote:
> I am a computer science student and I would like to ask something. I
> cant fully understand how I compute the LOOKAHEAD set for a grammar.
>
> For my exams we use LOOKAHEAD to identify a LL(1) grammar. The procces
> includes computing firstly FIRST and FOLLOW sets. Then using them we can
> compute the LOOKAHEAD. But I cant fully understand this second process.
>
> I know how to compute FIRST and FOLLOW set and I would like a
> description or algorithm for computing the LOOKAHEAD from these.


Vangelis,


Always start with a reduced grammar, i.e. the grammar with all
useless symbols/rules removed (full definition of this below).
Then LA(A -> x) = if nullable(x) then first(x) union follow(A)
                                      else first(x)


Here, of course A is a nonterminal, x a string of (non-)terminals.


To make a grammar reduced do the following two steps:
1. remove all nonterminating symbols
2. remove all unreachable symbols (and their rules)


With regards,


Jan Jongejan
Dept. Comp.Sci.,
Univ. of Groningen,
Netherlands.


Post a followup to this message

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