Operator Precedence Parser

• Built for operator precedence grammar.

• Used to parse expressions based on operator priorities (like +, *, etc.).

Operator Precedence Grammar

• A special type of grammar with no epsilon (ε) productions.
• Does not have two non-terminals side by side on the right-hand side of any rule.
• Comes with precedence rules (decides which operator to process first).
• Can be ambiguous or unambiguous depending on how rules are defined.

Operator Precedence Parser Algorithm :

1. If the front of input $ and top of stack both have $, it's done
else
2. compare front of input b with ⋗
if b! = '⋗'
then push b
scan the next input symbol
3. if b == '⋗'
then pop till ⋖ and store it in a string S
pop ⋖ also
reduce the popped string
if (top of stack) ⋖ (front of input)
then push ⋖ S
if (top of stack) ⋗ (front of input)
then push S and goto 3
LR parsers
LR parsers is an efficient bottom-up syntax analysis technique that can be used to parse large classes
of context-free grammar is called LR(k) parsing.
L stands for left-to-right scanning
R stands for rightmost derivation in reverse
k is several input symbols. when k is omitted k is assumed to be 1.
Advantages of LR parsing

• LR parsers handle context-free grammars. These grammars describe the structure of

programming languages-how statements, expressions, and other language constructs fit
together.

• LR parsers ensure that your code adheres to these rules.

• It is able to detect syntactic errors

• It is an efficient non-backtracking shift shift-reducing parsing method.

Types of LR Parsing Methods

• SLR parser

• LALR parser

• Canonical LR parser

SLR Parser
• LR parser is also called as SLR parser

• it is weakest of the three methods but easier to implement

• a grammar for which SLR parser can be constructed is called SLR grammar

Steps for constructing the SLR parsing table

1. Calculate first and follow of each variable

2. Do numbering of all the production rule.

3. Writing augmented grammar

2. LR(0) collection of items to be found

3. Construct parsing table

4. Parse the string.

CLR (1) Parsing
• CLR refers to canonical lookahead.
• CLR parsing use the canonical collection of LR (1) items to build the CLR (1) parsing table.
• CLR (1) parsing table produces the more number of states as compare to the SLR (1) parsing.
• In the CLR (1), we place the reduce node only in the lookahead symbols.

Various steps involved in the CLR (1) Parsing:

o Give number to each production rule.

o Add Augment production in the given grammar

o Create Canonical collection of LR (1) items

o Construct a CLR (1) parsing table

o Parse the string.

LALR Parser
• LALR Parser is lookahead LR parser.
• It is the most powerful parser which can handle large classes of grammar.
• The size of CLR parsing table is quite large as compared to other parsing table.
• LALR reduces the size of this table.
• LALR works similar to CLR.
• The only difference is , it combines the similar states of CLR parsing table into one single
state.
Predictive Parser

• A type of recursive descent parser.

• It is a top-down parser (starts from the start symbol and goes down
to terminals).
• No backtracking is required — decisions are made in one pass.
• At each step, it looks at the next input symbol to decide which
grammar rule to apply.
• Works only with LL(1) grammars, where one lookahead symbol is
enough to make a decision.
•
difference between Top-Down Parsing and Bottom-Up Parsing
Top-Down Parsing Bottom-Up Parsing

Starts from the start symbol Starts from the input symbols

Works from top to bottom of the tree Works from bottom to top of the tree

Tries to build the parse tree Tries to reduce input to start symbol

Follows leftmost derivation Follows rightmost derivation in reverse

Selects which rule to apply next Decides when to reduce a string

Needs no backtracking in predictive type May use backtracking in some types

Easier to implement manually More suitable for automatic tools

Used in recursive descent parsers Used in shift-reduce parsers

Works best with LL grammars Works best with LR grammars

May struggle with left recursion Can handle left recursion well

Recursive Descent Parser

• It’s a top-down parser that reads the input left to right.

• Each grammar rule has its own function in the code.

• It builds a parse tree by matching the input to grammar rules.

• It works best with LL(1) grammars (one lookahead symbol).

• Backtracking is used when there are multiple choices, and the first one fails.

Recursive Descent Parser With Backtracking

• Normal Recursive Descent Parser may backtrack if the first choice fails.

• Predictive Parser (a special case) does NOT backtrack.

• To avoid backtracking, we rewrite the grammar using techniques like:

o Removing Left Recursion

o Left Factoring

Example:
Original Grammar (has left recursion):

E→E+T|T

T→T*F|F

F → ( E ) | id
 After Removing Left Recursion:

E → T E'

E' → + T E' | ε

T → F T'

T' → * F T' | ε

F → ( E ) | id

Between S-attributed and L-attributed

S-attributed Definitions L-attributed Definitions

Uses only synthesized attributes Uses both synthesized and inherited attributes

Evaluated bottom-up Evaluated top-down

From leaves to root From root to leaves

No restrictions on attribute dependencies Some restrictions on inherited attributes

Bottom-up parsers like LR Top-down parsers like LL

Based on child nodes only Based on parent or left siblings

Easier to implement in bottom-up parsing More complex due to dependency restrictions

Evaluating expressions Type checking, parameter passing

Less flexible for complex semantic needs More flexible in many semantic designs

Used in S-attributed grammar tools Used in L-attributed grammar tools

Context free grammar and their properties.

Context-Free Language (CFL)
• A CFL is a language made using Context-Free Grammar (CFG).

• It is accepted by a special machine called a Pushdown Automaton (PDA) that uses a stack to
keep track of things.

• CFLs are great at handling nested structures like brackets: (( )), { { } }, etc.

• CFLs are more powerful than regular languages but not as powerful as all computer
languages.

Properties :
1. Closure Properties

CFLs are closed under (stay CFL):

• Union, Concatenation, Kleene Star

• Reversal, Homomorphism, Inverse Homomorphism

 • Substitution, Prefix, Cycle

• Intersection/Difference with Regular Language

Not closed under (may not stay CFL):

• Intersection & Difference between two CFLs

• Complement, Subset, Superset, Infinite Union

2. Decision Properties

Can decide:

• Emptiness – Is the language empty?

• Finiteness – Has limited strings?

• Membership – Is a string in the language?

Cannot always decide:

• Equivalence – Are two CFLs the same?

• Universality – Does it include all strings?

• Inclusion – Is one inside another?

3. Deterministic property

• Accepted by Deterministic PDA (DPDA).

• Not all CFLs are deterministic.

What is a Syntax Tree

A syntax tree is a type of tree diagram that shows the structure of a program or expression in a
hierarchical form.

• Leaf nodes represent operands (like variables or constants).

• Internal nodes represent operators (like +, -, *, /).

A syntax tree is a simplified form of a parse tree, focusing only on the meaningful parts of an
expression.

Rules for Constructing a Syntax Tree:

1. mknode(op, left, right)

o Creates an operator node with the given operator op

o left and right are pointers to the child nodes (operands).

2. mkleaf(id, entry)

o Creates a leaf node for an identifier like a variable a, b, etc.

 o entry is a pointer to the variable’s entry in the symbol table.

3. mkleaf(num, val)

o Creates a leaf node for a number (constant value).

o val holds the actual numeric value.

Example 1: Syntax Tree for the string a - b ∗ c + d is:

Example 2: Syntax Tree for the string a * (b + c) – d /2 is: