LL(1) grammars, looking for a good, clear resource.

Question

I am taking a principals of programming class right now.

We are learning about LL(1) grammars.

I found the book and lectures to be somewhat unclear and was hoping that someone could refer me to a good resource.

I found some good youtube tutorials for finate state automatons and determinate state automatons, but I cannot find anything similar for LL(1) grammars. It appears that there is a fair bit of info, it is just confusing. Looking for an "easy steps" approach.

Have a good weekend! Happy 4th of July to all you Americans!

---

Edit: I understand how the First works but I am not clear on the follow.

Answer 1

Basically, the follow set of a non-terminal A is just what it says on the tin; it's the set of non-terminals which can follow immediately after an A.

You might want to read the Wikipedia article about LL grammars and parsers, specifically the part about conflicts - that might help you understand it all a bit better.

Answer 2

LL basically means "top down".

A top down parser is something that starts with the proposition of wanting to parse the top level element in a grammar first, consumes the tokens necessary to start that element, and then proceeds to recurse "downwards" toward more detailed elements in the grammar.

The easiest way to understand top-down parsing is to implement a parser. A hypothetical example may look like:

void parseFile()
{
    while(classesContinue())
    {
        parseClass();
    }
}

void parseClass()
{
    consume(Tokens.Class);
    consume(Tokens.ID);
    consume(Tokens.LCurly);
    while(membersContinue())
    {
        parseMember();
    }
    consume(Tokens.RCurly);
}

The number in paranthesis next to LL (as in LL(1)), is the maximum number of look ahead necessary to implement any "choices" that have to be made by the parser. For example, "parseMember" may look like:

void parseMember()
{
    parseTypeName();
    parseID();
    switch (lookAhead())
    {
        case Tokens.Semi:
        case Token.Equals:
            parseVariableDecl();
            break;
        default:
            parseMethod();
            break;
    }
}

In which case the parser would be LL(1), because it requires one token of lookahead.

In any case, an LL (1) grammar is just a specification of an LL(1) parser in a formal notation, usually some variant of EBNF.

Does that help?