1. What is an ambiguous grammar?
Explain the procedure for eliminating ambiguity from a grammar
with examples.
An ambiguous grammar is a context-free grammar for which there exists a string that can have more
than one leftmost or rightmost derivation, or more than one parse tree. This ambiguity leads to
confusion in syntax analysis.
Example:
E E + E | E * E | id
For input `id + id * id`, two parse trees are possible:
- (id + id) * id
- id + (id * id)
To eliminate ambiguity:
Step 1: Remove left recursion
Step 2: Left factor the grammar
Refactored grammar:
E T E'
E' + T E' |
T F T'
T' * F T' |
F ( E ) | id
Now the grammar is unambiguous and suitable for LL(1) parsing.
2. What is left recursion? Describe the algorithm used for eliminating left recursion.
Eliminate left recursion from:
E E+T|T
T T*F|F
F ( E ) | id
Left recursion occurs when a non-terminal refers to itself as the leftmost symbol in a production. It
causes infinite recursion in top-down parsers.
Algorithm to remove immediate left recursion:
For A A | :
Transform to:
A A'
A' A' |
Apply to grammar:
E T E'
E' + T E' |
T F T'
T' * F T' |
F ( E ) | id
Now left recursion is eliminated.
3. What is left factoring? Describe the algorithm for left factoring a grammar with an example.
Left factoring is a grammar transformation used to eliminate common prefixes to enable predictive
parsing.
Example:
A 1|2
Factored:
A A'
A' 1 | 2
Algorithm:
- Identify productions with a common prefix
- Factor out the common prefix into a new production
Example:
Stmt if expr then stmt else stmt | if expr then stmt
Factored:
Stmt if expr then stmt Stmt'
Stmt' else stmt |
4. Construct predictive parsing table and verify whether the grammar is LL(1):
E E+T|T
T T*F|F
F ( E ) | id
First eliminate left recursion:
E T E'
E' + T E' |
T F T'
T' * F T' |
F ( E ) | id
Compute FIRST and FOLLOW sets (see Question 6), and then build the parsing table.
If no entry in the table has multiple productions, then the grammar is LL(1).
5. Write the algorithm for recursive descent parsing. Explain with an example.
Recursive descent parsing uses mutually recursive functions to implement the grammar.
Algorithm:
For each non-terminal, write a function:
- Match input tokens with FIRST set
- Recursively call functions for the RHS symbols
- Use lookahead and match terminals
Example grammar:
E T E'
E' + T E' |
T F T'
T' * F T' |
F ( E ) | id
Function E():
T()
E'()
Function E'():
if next token is '+':
match('+')
T()
E'()
6. Write the rules and compute FIRST and FOLLOW for:
E E+T|T
T T*F|F
F ( E ) | id
First, eliminate left recursion (already done above):
E T E'
E' + T E' |
T F T'
T' * F T' |
F ( E ) | id
FIRST sets:
FIRST(E) = FIRST(T) = FIRST(F) = {(, id}
FIRST(E') = {+, }
FIRST(T') = {*, }
FOLLOW sets:
FOLLOW(E) = {$, )}
FOLLOW(E') = {$, )}
FOLLOW(T) = {+, $, )}
FOLLOW(T') = {+, $, )}
FOLLOW(F) = {*, +, $, )}
7. Construct SLR parsing table for:
E E+T|T
T T*F|F
F ( E ) | id
Steps:
- Augment the grammar: E' E
- Construct LR(0) items and DFA
- Compute FOLLOW sets
- Construct Action and Goto tables using shift, reduce, and accept rules
Due to complexity, this is usually handled using parser generator tools like YACC or Bison.
8. Construct CLR parsing table for the grammar:
Same as SLR, but use LR(1) items with lookaheads.
Gives more accurate parsing but larger tables.
9. Construct LALR parsing table for the grammar:
Merge similar LR(1) states to form a compact table.
LALR parsing table = reduced size of CLR with similar power.
10. What is YACC? Explain the different sections of a YACC program with examples.
YACC (Yet Another Compiler Compiler) is a parser generator that works with LEX.
Structure:
%{
C declarations
%}
%token declarations
%%
Grammar rules and associated C actions
%%
Main function (calls yyparse())
Example:
%{
#include <stdio.h>
%}
%token NUM
%%
expr: expr '+' term { printf("add\n"); }
| term;
term: NUM;
%%
int main() {
return yyparse();
11. Explain different LR parsers:
a. SLR (Simple LR):
- Uses LR(0) items and FOLLOW sets
- Simpler but may cause conflicts
b. CLR (Canonical LR):
- Uses LR(1) items (item + lookahead)
- More powerful, fewer conflicts
- Larger parsing tables
c. LALR (Lookahead LR):
- Merges LR(1) states with same LR(0) core
- Smaller tables like SLR but more powerful
These parsers are used in bottom-up parsing and support a wider range of grammars than LL
parsers.