PLC Laboratory 4

LL1 Grammars

On the input, there is a context free grammar. For this grammar compute sets FIRST and FOLLOW and based on these sets decide if the grammar is LL1.

To simplify the solution, you can use your solution from the previous laboratory: Laboratory 3

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 either "It it LL1 grammar" or "It is not LL1 grammar".

Example

• Input

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

• Output

It is not LL1 grammar