Algorithm for computing first-k follow-k sets

#1 08-23-2008, 01:52 PM

Hello,

This is probably pretty elementary but I havent been able to locate a
method to compute first-k follow-k sets (i.e. the k terminals derived
from a symbol or following that symbol) efficiently for a grammar.
Most textbooks only seem to cover the k = 1 case. Are there references
out there which contain how to compute the generalization to k > 1?

Thanks in advance,

Carter.

#2 08-23-2008, 07:18 PM

Carter Cheng schrieb:

> This is probably pretty elementary but I havent been able to locate a
> method to compute first-k follow-k sets (i.e. the k terminals derived
> from a symbol or following that symbol) efficiently for a grammar.
> Most textbooks only seem to cover the k = 1 case. Are there references
> out there which contain how to compute the generalization to k > 1?

With k>1 you'll have sets of k-tuples, which make the tables explode.
References to procedures have just been mentioned in this group (see
ANTLR...).

DoDi

#3 08-24-2008, 04:08 PM

Carter, i think I've asked that question a while ago, but found no
satisfactory results.

Kwang-Moo Choe, outlines an algorithm for computing First(k) Sets and
Follow(k) Sets here:

http://plus.kaist.ac.kr/~choe/cs522/...par-SLL(k).pdf

but I THINK that the algorithm does not work on left-recursive
grammars (note: i haven't tried it)

The web site where i found the link is:
http://plus.kaist.ac.kr/~choe/

Regards,

On Sat, Aug 23, 2008 at 2:52 PM, Carter Cheng <cartercheng@gmail.com> wrote:

> This is probably pretty elementary but I havent been able to locate a
> method to compute first-k follow-k sets (i.e. the k terminals derived
> from a symbol or following that symbol) efficiently for a grammar.
> Most textbooks only seem to cover the k = 1 case. Are there references
> out there which contain how to compute the generalization to k > 1?

#4 08-25-2008, 07:14 AM

On 08/24/08 15:08, Felipe Angriman wrote:
[snip]
> Kwang-Moo Choe, outlines an algorithm for computing First(k) Sets and
> Follow(k) Sets here:
>
> http://plus.kaist.ac.kr/~choe/cs522/...par-SLL(k).pdf

Page 1 of that pdf uses notation:

k:alpha beta

without defining what : means. My first guess is that it
takes the first k elements of an A^* if they exist; however,
that's not clear. Mr. Choe probably defines : in his
class room and say no need to repeat it on the .pdf.

>
> but I THINK that the algorithm does not work on left-recursive
> grammars (note: i haven't tried it)

Page 5 of that pdf says G (I guess a grammar)
is not LL(k) if G is left-recursive. so, I guess the
algorithm does not work on left-recursive grammars.

[snip]

#5 08-25-2008, 08:33 AM

On 08/25/08 06:14, Larry Evans wrote:
> On 08/24/08 15:08, Felipe Angriman wrote:
> [snip]
>> Kwang-Moo Choe, outlines an algorithm for computing First(k) Sets and
>> Follow(k) Sets here:
>>
>> http://plus.kaist.ac.kr/~choe/cs522/...par-SLL(k).pdf
>
> Page 1 of that pdf uses notation:
>
> k:alpha beta
>
> without defining what : means.
[snip]
It's defined on page 18 of:

http://plus.kaist.ac.kr/~choe/cs522/cs522/pdf/1elt.pdf

#6 08-25-2008, 01:55 PM

Thanks for the help everyone. For what I am doing I doubt I will need
to goto higher k values but I was just curious if methods for
computing these properties of a symbol in a grammar were readily
available.

Thanks again,

Carter.

#7 08-26-2008, 10:40 AM

> Page 1 of that pdf uses notation:
>
> k:alpha beta
>
> without defining what : means. My first guess is that it
> takes the first k elements of an A^* if they exist; however,
> that's not clear. Mr. Choe probably defines : in his
> class room and say no need to repeat it on the .pdf.

This notation is defined in Terrence Parr PhD Thesis Page 5 that why
it isn't defined here
http://plus.kaist.ac.kr/~choe/cs522/...par-SLL(k).pdf

>>
>> but I THINK that the algorithm does not work on left-recursive
>> grammars (note: i haven't tried it)

>Page 5 of that pdf says G (I guess a grammar)
>is not LL(k) if G is left-recursive. so, I guess the
>algorithm does not work on left-recursive grammars.

My comment regarding the applicability of the algorithm to Left
Recursive Grammars is because Carter never said he wanted to compute
tables for LL(k) Grammars (which might be the most fitting supposition
since this is a compiler discussion list). However, if i consider the
request made by carter as is, i was compelled to answer in the manner
i did before.

Regards,

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode