| Context
Free Grammar
Contributed by
Rimincha Ammu
Introduction
A Context Free Grammar (CFG) is
a set of recursive rewriting rules
(or productions) used to generate
patterns of strings.
A CFG consists of the following
components:
· A set of terminal
symbols, which are the characters
of the alphabet that appear in
the strings generated by the grammar.
· A set of non-terminal
symbols, which are placeholders
for patterns of terminal symbols
that can be generated by the non-terminal
symbols.
· A set of productions,
which are rules for replacing
(or rewriting) non-terminal symbols
(on the left side of the production)
in a string with other non-terminal
or terminal symbols (on the right
side of the production).
· A start symbol,
which is a special non-terminal
symbol that appears in the initial
string generated by the grammar.
To generate a string of terminal
symbols from a CFG, we:
· Begin with a string
consisting of 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;
· Repeat the process of
selecting non-terminal symbols
in the string, and replacing them
with the right hand side of some
corresponding production, until
all non-terminals have been replaced
by terminal symbols.
A) Context Free Grammar
for if……..else………if
statement
<start> ---à if (
<expr> ) <stmt> else
<stmt> if ( <expr>
) <stmt>
<stmt> = Statement
<expr> = Expression
Non-terminal symbols are <stmt>
and <expr>
Terminal symbols are if
and else
<start>
is the Start symbol
B) Context Free Grammar
for Switch statement
<start> ---à
switch ( <expr> ) <stmt>
<stmt> ---à case
<expr> : <stmt>
<stmt> = Statement
<expr> = Expression
Non-terminal symbols are <stmt>
and <expr>
Terminal symbols are switch
and case
The symbol <stmt>
at the end of the first line is
the production
<start> is
the Start symbol
C) Context Free Grammar
for Do……….while
statement
<start> ---à do <stmt>
while ( <expr> ) ;
<stmt> = Statement
<expr> = Expression
Non-terminal symbols are <stmt>
and <expr>
Terminal symbols are do
and while
<start>
is the Start symbol
--------------------------------------------------------------------------------
ANSWER 2 B
|
