### Introduction To Parsing and Context Free Language

- The sequence of tokens generated by scanner are given to parser as input, which produces parse tree.
- In a parse tree, leaves are terminals or epsilon and internal nodes are non-terminals and root is the start symbol.
- Context-free language plays an important role while creating a parse tree.
- The degree of expression of formal languages:
- Recursively enumerable language
**(Strongest)**
- Context Sensitive language
*Context Free language*
*Regular* *language* **(Weakest)**

- A CFG is a 4-tuple grammar: G=(V, ∑, R, S)
- V: a finite set containing non-terminal symbols.
- ∑: a finite set disjoint from V and defined by G.
- R: rules of production defined by G.
- S: Element of V, usually the left symbol of the first production rule.

- For example, these are some production rules of some CFL

S –> AB; S –> ASB; A –> a; B –> b

here a, b are terminals; A, B and S are non-terminals and S is the start symbol.

- Regular languages are implemented using FA, having no memory element. no rule like: a
^{i}b^{i} can exist, while context free languages are implemented using pushdown automata, having a stack memory in addition.