Context Free Grammar in Top Down Parsing

Context Free Grammar/Grammar consists of terminals, non-terminals, a start symbol and productions

A Context Free Grammar(CFG) is used to generate patterns of strings

A Context Free Grammar G is a quadruple (V,T,P,S) where

                V is set of non-terminals

                T is set of Terminals (V ∩∑= Ø)

                P is Production rules (P: V→(V∪∑)*)

                S is A start symbol

It is a set of recursive rewriting rules (or Productions)

A CFG is defined by a set of productions, each production is of the form

                                X → β

Where

                X is a single non-terminal symbol, representing a set of phrases in the language

                β  is a sequence of terminal and non-terminal symbols

A CFG Consists of the following components

• A set of terminal symbols. They are the characters of alphabet which appear in the strings that are generated by the grammar
• A set of non-terminal symbols: They are the place holders for patterns of terminal symbols which can be generated by the non-terminal symbols
• A set of productions: They are the rules for replacing or rewriting, the non-terminal symbols that are present on the left side of the production in a string, with other non-terminal or terminal symbols present on the right side of the production
• A Start symbol: It is a special non-terminal symbol that appears in the initial string which is generated by the grammar

Example of CFG

Notations

Strings of Terminals	Lower case letters, digits, punctuation
Non Terminals	Upper Case Letters
Arbitary Terminasls / Non-Terminasls	X,Y,Z
Strings of Terminals	u,v,w
Strings of Terminasls/non-terminals	µ,β,Ƴ
Start Symbol	S

To generate a string of terminal symbols from a CFG,

• Start with a string that consists the start symbol;
• Apply one of the productions with the start symbol on the left hand side, replacing the start symbol with the right hand side of the production;
• The process of selecting non-terminal symbols in the string has to be repeated, and they have to be replaced with the right hand side of some corresponding production. The process has to be repeated until all non-terminals are replaced by terminal symbols

Share on Google Plus

About Data Sciences by Venu

Hi, My name is Venugopala Chary and I'm Currently working as Associate Professor in Reputed Engineerng College, Hyderabad. I have B.Tech and M.tech in regular from JNTU Hyderabad. I have 11 Years of Teaching Experience for both B.Tech and M.Tech Courses.