CREATE OWN LIBRARY

Simple Grammar

Simple grammar:

Simple grammar is another form of Context Free Grammar (CFG) and its production rule is the same as Greibach Normal Form (GNF) (For details see previous chapter Greibach Normal Form) with one extra condition.

As we know the production of GNF is V → TV*  or    V → T | TV*

Simple Grammar or S-grammar:

A CFG is said to be a simple grammar if all the production in the form of  V → TV* (Same as GNF) and any pair of Variable and Terminal (V, T) occurs at most once in Production.

Let take an example to clear the S-grammar:

The grammar G is Greibach Normal Form (GNF) because it holds V → TV*  or   V → T | TV*. 

But it is not simple grammar because as per S-grammar second condition variable and terminal should occurs at most once in production but here (S, a) appears twice in this production which is:

S → aAB

S → a

Now another example to see which one is S-grammar:

This given grammar is GNF as well as S-grammar because it follow production rule V → TV* and all variable and terminal appear only one in the production.

Q. Consider the given grammar:

G:        S → aAB | bCD | cD | d

            A → aAC | aB

Is it a Simple grammar or S-grammar?

Solution:

This given grammar is GNF because it follows production rule V→ TV* but it is not S-grammar because (A, a) appears twice in this production.

Parsing Time of S-grammar:

S-grammar can parse any string at linear time i.e. O(n) time.

Example:

Let ω = aabb so,  S → aAB → aaBB → aabB → aabb

So, we require n time to process any strings. 

There is no algorithm for CFL / NCFL which parse any string at linear time O(n) time.

But for DCFL, there is S-grammar which can parse any strings at linear time O(n).

Application of Simple grammar:

Many features of common programming language can be described by Simple grammar or S-grammar.