First and Follow method..?Pls help

[Alex_]

Hello, i am supposed to solve a problem using this Method. Can anyone pls tell me what this exactly is, and how does it work?Or maybe a link to a source ...? i'd be very thankfuly!
Pls this is urgent.It's for my thesis!

the perl calculus problem sounds like this:
we have 3 ordinary perls(1,2,3), and 3 magic perls(A,B,C).
Each magic perl can transform itself in the following way:
A-> 1| 2| 3|
B-> 2B| 1A3AC
C-> 2| 3BC | 12A
; and i have to make a program that will say if it is possible to reach a certain array of simple perls given from the key-board,by selecting just one magic perl(ex:21132123;B->2B->21A3AC->21A3A12A->21132123).

[Jishnu]

Try Google.

[Alex_]

Try Google.

Like yeah...

[Abzero]

ok, well not that nice a problem;

firstly the gramma as a whole grammar is not LL(1). But taken as three grammar's it's ok.

Anyway not sure what your asking; do you not know how to construct a parser? or you don't unstand First & Follow?

[Jishnu]

Like yeah...

Which means?

[Alex_]

I gues i don't understand both! You see, at the university i'll study this next year. But i bumped in a problem that needed to be solved by the first and follow method..or parsing,anyway(for me both of them are greek still).
However i found a way to solve the problem... no more needs to understand the parsing method that urgent,but if you would like to give it a hand, i'll appreciate it :).
Hope you'll have the nerve to finish because i know it's a lot of theory.

Nevermind the "Like yeah"... i thought you just wanted to sweep me off the question. But now i see that your intention to help was real,thx. Btw, yes i have searched the web, found some documentations but still not that helpful.

[Abzero]

Ok, well First & Follow is pretty easy; the algorithm to do it is a little complicated; but for simple grammars you can do it by hand.

for example:

S -> AB$
S -> B$

A -> 2 | 3
B -> 1

If you were to construct a parser for this language, you need to know which production A/B you want to choose. You do this using the First set; which is the set of all token's which begin a production. So for example A is {2,3} and B {1}.

In S, if the first character is 2 or 3 you choose A, else choose 1.

The complication comes when you have null productions; etc.

S -> AB$
A -> C1
B -> 2 | 3
C -> 5

The first of C is {5}, the first of A must be the first of C, but as C is nullable it must also be the next character as well. ie. A {1,5}. (this could also be the first of another production.)

The follow set is used to select a null production.

For example

S -> AB$
A -> 1A
A -> null
B -> 2

The first of A is {1}, the follow of A is {2} (since B follows A, and the first of B is {2})

In A once you have processed the 1, you look at the lookahead and determine if it is in the follow set of A. If so then you choose the null production instead.

Follow also has complications with nullable, etc

S->AB$
A -> 1 | 0
B -> 2
B -> e

The follow of B is {$}, but since B can be nullable the follow of A is {2,$}.

Ok? (it's a very quick introduction.)

The second part of the question is how you build a parser which it.

This is very simple. You have a token stream which you can do two options with, peek (lookahead) and consume.

you can then construct a parse as follows:

create a function for each production:

(e.g S-> AB$ A=1,2,e B=3,4 )

proc S ( )
{
    if ( peek in first(A) ) {
        A
        B
    } else {
        B
    }
}

proc A ( ) {
    if( peek == 1 ) consume 1
    else consume 2
}

proc B () {
    if (peek == 3 ) consume 3
    else consume 4
}

This is very simplified; but easy with a bit of reading. Hope that helped.