Learn Compiler Design: From B. K.

Sharma

Unit II

Syntax Analysis and CFG

Learn Compiler Design: From B. K. Sharma

Unit II: Syllabus

• Syntax Analysis and Syntax Directed
Translation
• Syntax Analysis:
– CFGs
– Top Down Parsing
– Brute Force Approach
– Recursive Descent Parsing
– Transformation on the grammars
Learn Compiler Design: From B. K. Sharma

Unit II: Syllabus

– Predictive Parsing
– Bottom Up Parsing
– Operator Precedence Parsing
– LR Parsers
• SLR,
• LALR
• LR
• Parser Generator
Learn Compiler Design: From B. K. Sharma

Unit II: Syllabus

• Syntax Directed Definitions
– Construction of syntax trees
– Bottom Up Evaluation of S-attributed
definition
– L-attribute Definition
– Top Town translation
– Bottom Up Evaluation of inherited attributes
– Recursive Evaluation
– Analysis of Syntax Directed Definition
Learn Compiler Design: From B. K. Sharma
Summary of Lesson 13: Introduction Parsing or
Syntax Analysis
1: Parsing is the process of deriving a given input string
according to the productions of the grammar.

2: Parser determines if the tokens given by scanner is

syntactically valid according to the productions of CFG.

3: The output of parsing is syntax tree which is condensed

version of parse tree after removing the Non-terminals of
the grammar; containing operators as internal nodes and
operands as external nodes (leaves).
Learn Compiler Design: From B. K. Sharma

Mapping of Lesson with Course Outcome

(CO)
Lesson CO3
Lesson 13: Parsing or Understand LL, LR,
Syntax Analysis and SLR parsing
techniques.
Learn Compiler Design: From B. K. Sharma
Lesson 14: Syntax Analysis and CFG:
Learning Outcomes
At the end of this lesson, students will be able to

1: Define CFG and derivation.

2: Given a CFG and an input string, derive the

input string in leftmost and rightmost derivations.
Learn Compiler Design: From B K Sharma

Regular Expressions and CFGs

Regular Expressions : Basis of Lexical Analysis

Context Free Grammars: Basis of Parsing

Reg. Lang. CFLs

Context-free grammars (CFGs) are used to

describe context-free languages.
Learn Compiler Design: From B K Sharma

Context Free Grammars(CFGs)

Context free grammar G can be defined by four
tuples as:

Grammar G  (V , T , S , P)

Variables or NT Terminal Start Productions

symbols variable
Learn Compiler Design: From B K Sharma

Context Free Grammars(CFGs)

Grammar G  (V , T , S , P)
CFG for the language {0k1k | k≥0}
G = ({S}, {0, 1}, S, {S → 0S1, S → ε})

The production rule symbol is →

The arrow is read as "can have the form".
The production rule or simply production :
S 0 S 1

is read as “S can have the form 0 S 1”

Learn Compiler Design: From B K Sharma

Context Free Grammars(CFGs)

Alternatives of production rules:

E E + E E E + E
E ( E ) | ( E )
E -E | -E
E id | id

E E + E
E E + E| ( E ) | -E | id
( E )
-E
id
Learn Compiler Design: From B K Sharma

What is derivation?
Derivation: is a process that transform a starting non-
terminal into a collection of terminals / tokens by
applying a sequence of grammar rule applications and
substitutions of Non-terminals with terminals or
tokens.
A derivation uses the productions of a grammar to
replace non-terminals until there are only tokens left.
In CFG, the start symbol is used to derive the string.
We can derive the string by repeatedly replacing a
non-terminal by the right hand side of the production,
until all non-terminal have been replaced by terminal
symbols.
Learn Compiler Design: From B K Sharma

CFG and Derivations

 derives in one step

+
 derives in  one step

* derives in  zero steps



EXAMPLE: E  -E (the  means “derives” in

one step) using the production rule: E  -E
Learn Compiler Design: From B K Sharma

CFG and Derivations

Example

A context-free grammar : G S  aSa

S  bSb
S 
A derivation:

α ⇒ β means that string α can be rewritten into β.

The arrow, →, used in productions

Learn Compiler Design: From B K Sharma

CFG and Derivations

Example

A context-free grammar : G S  aSa

S  bSb
S 
Another derivation:
Learn Compiler Design: From B K Sharma

Two types of Derivations

Leftmost Derivations:

Replace the leftmost non-terminal symbol

Rightmost Derivations:

Replace the rightmost non-terminal symbol

Learn Compiler Design: From B K Sharma

Types of Derivations: G S  aAB

Example A  bBb
B  A| 
Leftmost derivation:

Rightmost derivation:
Learn Compiler Design: From B. K. Sharma

Active Learning Activity

One- Minute Paper
Consider the following CFG:
G:

Derive the input string (id*id) +id using

leftmost derivations
Learn Compiler Design: From B K Sharma

Types of Derivations:
Example
G: Leftmost Derivations:
Learn Compiler Design: From B. K. Sharma

Active Learning Activity

One- Minute Paper
Consider the following CFG:
G:

Derive the input string (id*id) +id using right

most derivations
Learn Compiler Design: From B K Sharma

Types of Derivations:
Example
Rightmost Derivations:
Learn Compiler Design: From B K Sharma

Sentential form

Every string of symbols in the derivation is

a sentential form.

S  aSb  aaSbb  aabb

Sentential Form Sentence

A sentence is a sentential form that has only

terminal symbols.
Learn Compiler Design: From B K Sharma
Derivation Tree / Parse Tree
G:
Leftmost Derivations:

Given a leftmost derivation, we

can build a parse tree
Learn Compiler Design: From B K Sharma
Derivation Tree / Parse Tree
G: Rightmost Derivations:

Given a rightmost derivation, we

can build a parse tree
Learn Compiler Design: From B K Sharma
Derivation Tree / Parse Tree
Leftmost Derivations: Rightmost Derivations:
Learn Compiler Design: From B K Sharma
Derivation Tree / Parse Tree

G:
Learn Compiler Design: From B K Sharma
Derivation Tree / Parse Tree

Every parse tree corresponds to:

A single, unique leftmost derivation
A single, unique right most derivation
Ambiguity:
However, one input string may have several
parse tree!!!!
Therefore:
Several leftmost derivations
Several rightmost derivations
Learn Compiler Design: From B K Sharma

Grammar Problems
- ambiguity
- ε-moves
Grammar
- cycles
Problems
- left recursion
- left factoring

Read PPT named Ambiguity in CFG and Removal

Learn Compiler Design: From B. K. Sharma
Summary of Lesson 14: Syntax Analysis and CFG
1: Basis of Parsing is context-free grammar (CFG) which
describes context free languages.
2: Context free grammar G can be defined by four tuples
as: G=(V,T,S,P)
3: Two types of derivations are left-most derivations and
right-most derivations.
4: Every parse tree corresponds to:
A single, unique leftmost derivation
A single, unique right most derivation
6:However, one input string may have several parse tree!!!!
Learn Compiler Design: From B K Sharma

Read PPT named Ambiguity in CFG and Removal

Learn Compiler Design: From B K Sharma

Extra Slide
Learn Compiler Design: From B K Sharma

Chomsky Hierarchy of Grammar

Grammar Type Language Automaton Production
Rules
Type 0 Recursively Turing α→β
Unrestricted Enumerable Machine

Type 1 Context Linear αAβ → αγβ

Context - Sensitive Bounded
Sensitive Automaton
Type 2 Context- Push-Down A→γ
Context - Free Automaton
Free

Type 3 Regular Finite-State A →a and

Regular Automaton A →aB