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.

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 each expression write one line containing the result – the computed value of the expression. If there is any error in the input, write text ERROR instead.

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.

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 $