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: aibi can exist, while context free languages are implemented using pushdown automata, having a stack memory in addition.