Context Free Grammer



Context-free Grammars

A context-free grammar for a language specifies the syntactic structure of programs in that language.

  • Components of a grammar:
    • a finite set of tokens (obtained from the scanner);
    • a set of variables representing “related” sets of strings, e.g., declarations, statements, expressions.
    • a set of rules that show the structure of these strings.
    • an indication of the “top-level” set of strings we care about


    • Context-free Grammars:   Definition
      • Formally, a context-free grammar G is a 4-tuple G = (V, T, P, S), where:
        • V is a finite set of variables (or nonterminals).  These describe sets of “related” strings.
        • T is a finite set of terminals (i.e., tokens).
        • P is a finite set of productions, each of the form
    • A     α 
      • ε  V is the start symbol.
      • where A ε V is a variable, and  α ε (V  ∪ T)* is a sequence of terminals and nonterminals.


    Example of CFG :

    E ==>E A E | (E) | -E | id

         A==>  + | - | * | / |

                            Where E,A are the non-terminals while id, +, *, -, /,(, ) are the terminals.