Compiler Design - Assignment 2 Answers
Q1. Operator Precedence Grammar with Relations and Parsing
Example
Operator Precedence Grammar is a type of grammar used in bottom-up parsing where precedence
relations are defined between operators to determine the correct order of evaluation.
Three precedence relations are used: less than (<), greater than (>), and equal (=). These relations
help the parser decide whether to shift or reduce.
Given Grammar: E → E+T | T , T → T*F | F , F → (E) | id
Input string: (id+(id*id)). The parsing proceeds using operator precedence where '*' has higher
precedence than '+', and parentheses control evaluation order. The string is successfully parsed.
Q2. LR Parser and LR(0) Check
LR parser is a bottom-up parser that reads input from Left to right and produces Rightmost
derivation in reverse. It uses stack, input buffer, and parsing tables (ACTION and GOTO).
Algorithm: Initialize stack with $, read input symbols, consult ACTION table to perform shift, reduce,
accept or error operations.
Given Grammar: S → AA , A → aA | b.
The grammar produces conflicts in LR(0) items therefore it is not LR(0).
Q4. CLR(1) and LALR Parser
CLR (Canonical LR) parser uses LR(1) items with lookahead symbols. It is very powerful but
produces large parsing tables.
LALR parser merges states with the same LR(0) core to reduce table size while keeping most of the
power of CLR.
Given Grammar: E → BB , B → cB | d. This grammar can be parsed by CLR(1) and also by LALR
parser.
Q5. Top Down Parsing and Bottom Up Parsing
Top Down Parsing constructs the parse tree from root to leaves. Examples include Recursive
Descent Parser and Predictive (LL(1)) Parser.
Bottom Up Parsing constructs the parse tree from leaves to root. Examples include Shift Reduce
Parser, LR Parser, SLR, CLR and LALR parsers.
Top down parsing is easier to implement but cannot handle left recursion while bottom up parsing is
more powerful.
Q6. Non■Recursive Descent Parsing (Predictive Parsing) and
LL(1) Check
Predictive parsing is a top-down parsing technique that uses a parsing table and stack. It does not
use backtracking and selects production rules based on the next input symbol.
Grammar 1: S → AaAb | BbBa , A → ε , B → ε. This grammar satisfies LL(1) conditions.
Grammar 2: S → iEtSS' | a , S' → eS | ε , E → b. This grammar produces FIRST/FOLLOW conflict
and therefore it is not LL(1).
Q7. LL(1) Parser Functions and Data Structures
Important functions used in LL(1) parser are FIRST(), FOLLOW(), and construction of parsing table.
The LL(1) parser mainly uses a stack, input buffer, and parsing table for parsing operations.
Q8. Short Notes
Left Recursion: When a nonterminal appears as the first symbol on the right side of its own
production. Example: E → E + T.
Left Factoring: A grammar transformation used to remove common prefixes. Example: A → ab |
ac becomes A → aA', A' → b | c.
Conflicts: Occur when a parser cannot decide between shift or reduce operations.
Backtracking: Technique where parser tries alternative productions if the current one fails.
Predictive parsers avoid backtracking.
Q9. LALR Parser Construction
LALR parser is obtained by merging similar CLR states that have identical LR(0) cores. This
reduces table size while preserving parsing capability.
Given Grammar: S → CC , C → aC | d. The grammar can be parsed using LALR parser after
constructing LR items and merging compatible states.
Q10. SLR Parsing Technique
SLR parser is a bottom-up parser based on LR(0) items and FOLLOW sets.
Steps: Construct LR(0) items, compute FOLLOW sets, build ACTION and GOTO tables, then
perform parsing.
Grammar examples: S → AS | b , A → SA | a and E → E+E | E*E | (E) | id. These grammars
produce conflicts therefore they are not SLR.