Compiler Design and Construction - Old Questions

7.  Define a context free grammar. What are the component of context free grammar? Explain.

A Context Free Grammar (CFG) is defined by 4-tuples as G = (V, T, P, S) where

• V is a finite set of variable symbols (Non-terminals)
• T is a finite set of terminal symbols.
• P is a set of production rules.
• S is a start symbol, S ∈ V

For e.g.

    E → EAE | (E) | -E | id

    A → + | - | * | /

Here, E and A are non-terminals with E as start symbol and other symbols are terminals.

The components of CFG are:

• A set of terminal symbols which are the characters that appear in the language/strings generated by the grammar. Terminal symbols never appear on the left-hand side of the production rule and are always on the right-hand side.
• A set of non-terminal symbols (or variables) which are placeholders for patterns of terminal symbols that can be generated by the non-terminal symbols. These are the symbols that will always appear on the left-hand side of the production rules, though they can be included on the right-hand side. The strings that a CFG produces will contain only symbols from the set of non-terminal symbols.
• A set of production rules which are the rules for replacing non-terminal symbols. Production rules have the following form: variable → string of variables and terminals.
• A start symbol which is a special non-terminal symbol that appears in the initial string generated by the grammar.