Grammar are set of rules of any language.
It is used for syntax checking.
Grammar is a program which stores set of rules. for example
if you write "ab=" this statement is not correct so compiler generate some syntax error. Actually its grammatical meaning is not correct here assignment operator is binary operator so it takes two operand one is on left side and other is on right side which is not there.
Syntax tree : Tree of an expression is called syntax tree and syntax tree are also called expression tree.
Example:
A syntax tree in which leaf node are operand and every initial node are operator.
Example: c = a + b
NOTE:
For solving expression we make a tree.
' = ' → Binary operator ( it take two node)
' + ' → Unary operator ( it take one node)
Ternary operator takes three nodes.
Parse Tree:
Parse mean checking syntax.
Parsing : It is the process of checking syntax.
Parser : It is a program which check syntax according to grammar.
FORMAL DEFINITION OF GRAMMAR:
Grammar is a set of four tuples.
G = ( V , T , P , S )
where:
V → is set of variables or non terminals ( It is in capital letters , like : A,B,C,D ....)
T → is a set of terminals like ( a,b,c,d,..... (, ), [ , ],...etc) expect capital letters or non terminals.
P → is a set of production of form A → α
A → Production α → Set of rules (it is string)
where :
( i ) A ∈ V
( ii ) α ∈ ( V U T )* or (V + T )*
Example : A → ab
S → Starting symbol ( i.e root node ). S is member of V.
Every tree has one root node so starting starting point is unique.
Notations :
1. All non terminals (NT) or variables are represented by capital alphabets.
2. All characters except capital letters are terminals.
Examples: There are 256 letters in which 26 are non terminal or capital letters.
here 256-26 = 230
230 terminal.
one more terminals is id → (identifiers)
So total terminals are 230 + 1= 231
EXAMPLE :
G = ( {E} , { id , ( , ) } , P , E )
G is a grammar where set of production are :
P = { E → E + E
E → E * E
E → ( E )
E → id
}
Solution:
since production function contain.
A → α ; where A ∈ V , α ∈ (V U T)
Left hand side contain only one variable and right hand side contain string.
V = { E }
T = { + , * , ( , ) , id }
S = E
Question 1: Find weather id + id * id is accepted by given grammar such as :
P = { E → E + E
E → E * E
E → ( E )
E → id
}
Solution: Replace L.H.S with R.H.S
E → E + E
→ id + E
→ id + E * E
→ id + id * E
→ id + id * id
Hence the given string is acceptable.
Trace:
Right hand side (L.H.S) is replaced by Left hand side (L.H.S) is called derivation.
1. Left most derivation (LD /LMD)
2. Right most derivation (RD/RMD)
Left Most Derivation (LD /LMD) :
In this derivation we replace or derive only left most non terminals.
Example : E → E + E → id + E → id + E * E → id + id * E → id + id * id
Right Most Derivation (RD/RMD) :
In this derivation we replace or derive only right most non terminals.
Example : E → E * E → E * id → E + E * id → E + id * id → id + id * id
Note :
→ Compiler use RD or LD but not use both at a time.
→ Derivation are always top-down , we start from root to leaf.
→ Reduction : Replace R.H.S string with L.H.S non terminal. It start from leaf to root , So it is bottom up approach.
Note: How we find grammar is ambiguous grammar ?
Suppose if have following production : P = { E → E + E / E * E / ( E ) / id }
" If we generate more than one parse tree of any string generated by a grammar than that grammar is called ambiguous Grammar."
By using LD we get two parse tree for given production.
By using RD we get two parse tree for given production.
So above grammar is ambiguous because in both the cases we get more than one parse tree.
Question :
S → aB / bA
A → bAA /aS / a
B → aBB / bS / b
For string : aaabbabbba
Find :
i. LD /Left Derivative.
ii. RD/ Right Derivation
ii. Parse tree
iv. Is grammar is ambiguous ?
Solution:
i . LD:
S → aB
→ aaBB
→ aaaBBB
→ aaabBB
→ aaabbB
→ aaabbaBB
→ aaabbabB
→ aaabbabbS
→ aaabbabbbA
→ aaabbabbba
ii . RD:
S → aB
→ aaBB
→ aaBbS
→ aaBbbA
→ aaBbba
→ aaaBBbba
→ aaaBbbba
→ aaabSbbba
→ aaabbAbbba
→ aaabbabbba
iii . Parse Tree:
Parse tree are called derivation tree in which every leaf node are terminals and internal node are variables.
Answer : Yes
Note :
If we generate more than one parse tree of any string generated by a grammar than that grammar is called ambiguous Grammar.
Practice Questions:
No comments:
Post a Comment