A lost art? LL(k) parsing

[honey the codewitch]

I've been hunting for an algorithm for computing FOLLOWS(k) sets for LL(k) grammars. It's a parsing thing. The only thing google is returning me on it is a dead link referred to on a newsgroup. I try to use google to get to a cached copy of the link but google is taking me back to the newsgroup page that links to the link I want. I found another reference to it on like stack overflow or something, and they referred me to Dick Grune's book which I already have, and doesn't cover it very well if at all (my memory is hazy but if it was in there I would have known, as I am the mad captain and LL(k) is my white whale) I think I might have to figure it out myself, and that worries me. To say it's non-trivial is a bit of an understatement. There are several ways to do it, and most require permutation and exponential growth of parse tables. I don't know how to properly permutate follows sets. It's confusing.

Real programmers use butterflies

[Lost User]

honey the codewitch wrote:

FOLLOWS(k) sets

Do you mean "first and follow sets"?

[honey the codewitch]

FOLLOWS(k) sets particularly for where k>1 FOLLOWS(k=1) I can do, but there's a monumental difference in implementing k=1 and k>1, unfortunately. k is a convention used to indicate the number of lookahead symbols.

Real programmers use butterflies

[Lost User]

Hmmmm, Found a paper from Oxford that describes how to construct first and follow sets for arbitrary k. He gives an example for LL(5). The LL(f inite) strategy for optimal LL(k) parsing[^] by Peter Belcak I can comprehend alot of very complicated things, but this paper is very hard to understand. :wtf:

[honey the codewitch]

I was hoping for something with less math, but thanks. I never went to uni, so my exposure to math formalisms is limited Edit: Actually, that paper is very good. I don't understand all of it yet, but the author seems to be explaining the formalisms used so that I can potentially understand them. Thanks for the link!

Real programmers use butterflies

[Lost User]

You are welcome. :) For what it's worth... I e-mail postdoc and researchers all the time. I've e-mailed two universities this weekend asking to obtain their text corpus for my NLP project. It doesn't hurt to e-mail the guy and ask if he has an implementation you can take a look at. Also... if you look in the bibliography at the bottom of the paper some of those links go to other parser projects. Best Wishes, -David Delaune

[Daniel Pfeffer]

You might try the Computer Science library of your local University. The librarian is likely to be able to refer you to appropriate books.

Freedom is the freedom to say that two plus two make four. If that is granted, all else follows. -- 6079 Smith W.

[honey the codewitch]

Yeah, and a lot of those assume a background in mathematics that I lack. I've gotten only so far with things like the dragon book.

Real programmers use butterflies

[Lost User]

Well, I am not even kidding, the codeproject Lounge is probably the worse place to get help on science/technical issues. The lounge lizards will poke fun at anything they don't understand, gripe about everything under the sun and give you a list of every pseudo-celebrity that died this week. You already know the C/C++ and C# languages (probably more) and I think you are selling yourself short if you think that you will be unable to understand logic notation[^]. Most of what is in that paper falls under tautology[^]. It might take a while but it's really just another language to learn. If all these teenagers on Reddit can read/write formal logic[^] then I am sure you can too. Best Wishes, -David Delaune

[megaadam]

I do not think the Codewitch was exactly asking for help. Just describing a technical situation, as they have done before...

"If we don't change direction, we'll end up where we're going"

[Fueled By Decaff]

Is it saved in the wayback machine archive?

[obermd]

Out of curiosity, why are you doing LL(k) parsing and not LR(k) parsing in this project? I vaguely remember doing LL(1) and LL(2) parsing in college as an exercise and it was a royal nightmare to get right. I think I still have my copy of the Dragon book.

[honey the codewitch]

LR(k) isn't realistic for k>1. The parse tables are too big, which is why nobody does it. There is GLR parsing which overcomes that at the cost of non-determinism. It's a monster to use. Furthermore, LL(k) is far easier for the end user to code against, since it's top down and not bottom up. I'm actually attempting to use my LR(1) table gen code to help me make LL(k) for k>1 because my LR(1) code already generates a state machine for all the symbols in a grammar. I think I can use that state machine to resolve ambiguities I encounter at k=1.

Real programmers use butterflies