Re: computing LOOKAHEAD sets

"J.H.Jongejan" <>
2 Sep 2005 14:18:36 -0400

          From comp.compilers

Related articles
computing LOOKAHEAD sets (Vangelis Katsikaros) (2005-08-31)
Re: computing LOOKAHEAD sets (J.H.Jongejan) (2005-09-02)
| List of all articles for this month |

From: "J.H.Jongejan" <>
Newsgroups: comp.compilers
Date: 2 Sep 2005 14:18:36 -0400
Organization: RuG
References: 05-08-114
Keywords: parse
Posted-Date: 02 Sep 2005 14:18:36 EDT

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.


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,

Post a followup to this message

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