SYNTAX ANALYSIS(PARSING)
PRESENTED BY GROUP II
COMPLIER CONSTRUCTION II
27TH MAY, 2025.
What is Syntax Analysis?
Syntax analysis is the second phase of a compiler. It is also called
parsing.
After breaking the code into tokens (done by lexical analysis), it
checks if the tokens follows the grammar rules.
It creates a parse tree or shows a syntax error.
Why Lexical Analysis is Not Enough
Limitations:
•Lexical analysis only identifies tokens like if, +, (
•It cannot detect structure errors, such as missing brackets or
wrong nesting.
Solution:
•Use Context-Free Grammar (CFG) in syntax analysis to handle
nested and structured code
Context-Free Grammar (CFG)
A Context-Free Grammar (CFG) is a set of rules used to define valid sentence
structures in a language.
G = (V,T,P,S).
Components are:
•Non-terminals(V): Variables (like sentences or expressions)
•Terminals(T): Actual symbols or tokens (like if, +, a, b)
•Productions(P): Rules showing how non-terminals can become terminals
•Start symbol(S): Where parsing begins
DERIVATION
What is a Derivation?
A sequence of production rules used to produce an input string from the
start symbol.
Types:
•Left-most derivation: Replace the left-most non-terminal first
•Right-most derivation: Replace the right-most non-terminal first
•Parse Tree derivation: A parse tree is a graphical depiction of a derivation.
It starts with a root symbol, breaks down using production rules, and ends
with terminal symbols (actual words or tokens).
EXAMPLE
Input: id + id * id
Production rules:
E→E+E
E→E*E
E → id
Left-most derivation is: Right-most derivation:
E→E+E E→E+E
E→ id+ E E→E+E*E
E→ id+ E * E E → E + E * id
E → id+ id * E E → E + id * id
E → id+ id * id E → id + id * id
AMBIGUITY
What is Ambiguity?
A grammar G is said to be ambiguous if it has more than one parse tree
(left or right derivation) for at least one string.
Example
E→E+E
E→E*E
E → id
For the string id + id * id, the above grammar generates two parse trees.
Ambiguity in grammar is not good for a compiler construction. It can be
removed by either re-writing the whole grammar without ambiguity, or by
setting and following associativity and precedence constraints.
ASSOCIATIVITY
Associativity If an operand has operators on both sides, the side on which the
operator takes this operand is decided by the associativity of those operators.
There are two main types:
•Left-associative: evaluated left to right(Operations such as Addition,
Multiplication, Subtraction, and Division.). To satisfy left associativity we use,
left-recursive production rules.
e.g., a + b + c → (a + b) + c
•Right-associative: evaluated right to left(Operations like Exponentiation)
e.g., a ^ b ^ c → a ^ (b ^ c). To satisfy right-associativity we use, right-recursive
production rules.
When there’s a sequence of the same operator, associativity tells the compiler
which operation to evaluate first if no parentheses are used.
PRECEDENCE
If two different operators share a common operand, the precedence of operators decides
which will take the operand.
Example: id + id * id
This can have two different parse trees, one corresponding to (id+id)*id and another
corresponding to id+(id*id).
Mathematically, * (multiplication) has precedence over + (addition), so the expression
id+id*id will always be interpreted as:
id + (id * id).
TYPES OF PARSERs
The way the production rules are implemented (derivation) divides parsing into two
types: top-down parsing and bottom-up parsing.
Top-Down Parsing: Start from the start symbol and work downward to match the
input. Then, builds the parse tree from root to leaves.
Example:
Recursive Descent Parser – uses recursive procedures to process the input. Recursive
descent parsing suffers from backtracking. Backtracking means, if one derivation of a
production fails, the syntax analyzer restarts the process using different rules of same
production.
Bottom-Up Parsing: bottom-up parsing starts with the input symbols and
tries to construct the parse tree up to the start symbol.
SUMMARY
Syntax analysis validates the structure of code.
Uses Context-Free Grammar (CFG).
Builds parse trees for correct syntax.
Handles ambiguity, associativity, and precedence.
Uses top-down or bottom-up parsing techniques.
THANK YOU!
