PLC Laboratory 3

Computing sets FIRST and FOLLOW

On the input, there is a context free grammar. For this grammar compute sets FIRST (for each right side of given rules) and FOLLOW (for each nonterminal).

To simplify the solution, you can use prepared grammar readers (they are prepared for Java and C#). They both read a context grammar from the input and represents it as an object.

Informal description, how to compute FIRST and FOLLOW in implementation friendly way is Guide (only in czech)

Input specification

The input contains a context free grammar definition. Non-terminals are upper-case letters, terminals are lower-case letters. It composes from several lines; each line ends with the semicolon, and it contains rules for one nonterminal. The line starts with this nonterminal, then there is a colon and it is followed by right hand sides of its rules separated by '|'.

There may be also notes in the input, they are written in compose brackets. They have no meaning for the grammar definition.

For more detail see the example.

Output specification

For the context free grammar from the input write FIRST sets for the right-hand side of all its rules. Next write computed FOLLOW sets for all grammar non-terminals.

Output’s formatting is not strict, your output should be similar to the output from the example.

Example

• Input

{Input grammar}
A : b C | B d;
B : C C | b A;
C : c C | {e};

• Output

Your output can be different, based on your representation of epsilon and the end of input character. Also a formatting depends on you.

first[A:bC] = b
first[A:Bd] = b c d
first[B:CC] = c {e}
first[B:bA] = b
first[C:cC] = c
first[C:{e}] = {e}
follow[A] = d $
follow[B] = d
follow[C] = c d $