Compiler Design Part-2

 Topic Covers

Grammar:

A phrase structure grammar is (N,T,P,S) where,

• N - Non terminal
• T - Terminal
• N intersection T = phi
• S - start symbol
• P- Production rules

Type 0: / unstricted grammar

Type 1: Length Increasing grammar- Context Sensitve Grammar
Type 2: CFG
Type 3: Regular Grammar

Derivation of CFG:

• Left Derivation
• Right Derivation
• Parse tree Derivation

Left Recursion-

• A production of grammar is said to have left recursion if the leftmost variable of its RHS is same as variable of its LHS.
• A grammar containing a production having left recursion is called as Left Recursive Grammar.

Example- 

S → Sa / ∈

(Left Recursive Grammar)

 

• Left recursion is considered to be a problematic situation for Top down parsers.
• Therefore, left recursion has to be eliminated from the grammar.

Ambiguity in CFG:

Possible questions to ask
Whether the grammar is predective parsing or not
Check Whether the grammar is ambiguos or not

Problem due to Ambiguity
Associativity Property Violation
Precedence property Violation
Determine Associativity and precedence of the operators

NOTE:

• For unambiguous grammars, Leftmost derivation and Rightmost derivation represents the same parse tree.
• For ambiguous grammars, Leftmost derivation and Rightmost derivation represents different parse trees.

Recursion in CFG

Left recursion
Right Recursion

Elimination of Left Recursion
Problems with Left Recursion
Conversion of left to right Recursion

Non-Deterministic CFG
Elimination of Non-determination