Syntax Analysis and LR Parsing

1. Working of Parser 14 Marks

Position of Parser

Main Functions

• Accept tokens from lexical analyzer.
• Check grammatical correctness.
• Construct parse tree or syntax tree.
• Report syntax errors.
• Recover from errors where possible.
• Support semantic-action execution.

Parser Components

• Input buffer: contains token sequence.
• Parsing stack: stores grammar symbols or states.
• Parsing table: determines parsing action.
• Driver program: controls stack, input and actions.

Types of Parsers

2. Top-Down Parsing 14 Marks

Basic Idea

The parser attempts to find a leftmost derivation of the input string. It chooses productions and predicts which production can generate the current input.

Types

• Backtracking parser
• Recursive-descent parser
• Predictive parser
• LL(1) parser

Problems

Left Recursion

A grammar such as E → E + T | T causes infinite recursion in top-down parsing.

Left Factoring

Left factoring is needed when alternatives have a common prefix.

Advantages

• Easy to understand and implement.
• Parse tree is constructed naturally.
• Suitable for hand-written parsers.

Limitations

• Cannot directly handle left-recursive grammar.
• May require left factoring.
• Less powerful than LR methods.

3. Recursive-Descent Parsing 14 Marks

Example Grammar

Procedure Outline

Working

1. Call the procedure for the start symbol.
2. Each procedure checks the current lookahead token.
3. Terminals are matched directly.
4. Non-terminals invoke other procedures.
5. Success occurs when complete input is matched.

Backtracking

If the parser tries one production and later fails, it may return to the earlier input position and try another alternative. Predictive parsing avoids this costly backtracking.

Advantages

• Simple program structure
• Easy semantic-action integration
• Readable and maintainable

Limitations

• Backtracking may be inefficient.
• Grammar transformation may be required.
• Not suitable for left-recursive grammar.

4. Predictive Parsing 14 Marks

LL(1) Meaning

• First L: scans input from Left to right.
• Second L: produces a Leftmost derivation.
• 1: uses one lookahead token.

Architecture

Algorithm

1. Push $ and start symbol onto stack.
2. Compare stack top X with input symbol a.
3. If X is a terminal and X = a, pop and advance input.
4. If X is a non-terminal, use M[X,a].
5. Replace X by the right side of selected production.
6. If both stack and input contain $, accept.
7. If table entry is empty, report error.

Conditions for LL(1)

• No left recursion
• Grammar should be left factored
• FIRST sets of alternatives must be disjoint
• If ε is possible, FIRST and FOLLOW conditions must hold

5. FIRST and FOLLOW Sets 14 Marks

Rules for FIRST

1. If X is terminal, FIRST(X) = {X}.
2. If X → ε, include ε.
3. For X → Y1Y2..., include FIRST(Y1) except ε; continue if Yi can derive ε.

Rules for FOLLOW

1. Place $ in FOLLOW(S), where S is start symbol.
2. For A → αBβ, add FIRST(β) except ε to FOLLOW(B).
3. If β derives ε or B is at end, add FOLLOW(A) to FOLLOW(B).

Example

Uses

• LL(1) parsing table construction
• Grammar analysis
• Error recovery
• Production selection

6. Construction of Predictive Parsing Table 14 Marks

Construction Rules

1. For each production A → α, place it in M[A,a] for every a in FIRST(α).
2. If ε belongs to FIRST(α), place A → α in M[A,b] for every b in FOLLOW(A).
3. All remaining entries are errors.

Example Grammar

Parsing id + id

7. Bottom-Up Parsing 14 Marks

Basic Idea

It performs the reverse of a rightmost derivation. Such a reverse derivation is called a rightmost derivation in reverse.

Handle

A handle is a substring that matches the right side of a production and whose reduction represents one step in the reverse rightmost derivation.

Types

• Shift-reduce parsing
• Operator precedence parsing
• LR parsing

Advantages

• Handles a larger class of grammars.
• Can handle left recursion.
• Detects errors as soon as possible in viable-prefix sense.

Limitations

• More complex construction.
• Parsing tables may be large.
• Manual design is difficult.

8. Shift-Reduce Parsing 14 Marks

Actions

• Shift: move next input symbol onto stack.
• Reduce: replace a handle by the left-side non-terminal.
• Accept: successful parsing.
• Error: invalid input.

Example

Conflicts

• Shift-reduce conflict: parser cannot decide whether to shift or reduce.
• Reduce-reduce conflict: parser cannot decide which production to reduce.

9. Operator Precedence Parsing 14 Marks

Operator Grammar Conditions

• No ε-production.
• No two adjacent non-terminals on the right side.

Precedence Relations

• a ⋖ b: a yields precedence to b
• a ≐ b: a has equal precedence with b
• a ⋗ b: a takes precedence over b

Basic Working

1. Compare topmost terminal on stack with current input symbol.
2. If stack terminal yields or equals precedence, shift.
3. If stack terminal takes precedence, reduce.
4. Accept when stack contains $S and input contains $.

Example Precedence

Advantages

• Simple for expression grammars.
• Efficient table-driven method.
• Directly handles precedence and associativity.

Limitations

• Works only for operator grammars.
• Cannot parse all context-free grammars.
• Error detection is weaker than LR parsers.

10. LR Parser 14 Marks

LR Parser Structure

ACTION Table

• Shift sj
• Reduce A → β
• Accept
• Error

GOTO Table

GOTO[state, non-terminal] specifies the next state after a reduction.

LR Item

An LR item is a production with a dot showing how much of the production has been recognized.

Advantages

• Very powerful deterministic parsing method.
• Handles left-recursive grammar.
• Detects syntax errors early.
• No grammar transformation is generally required.

Types

• SLR(1)
• Canonical LR(1)
• LALR(1)

11. SLR Parser and Table Construction 14 Marks

Construction Steps

1. Augment grammar using S' → S.
2. Construct LR(0) items using closure and goto.
3. Create canonical collection of item sets.
4. For A → α•aβ, enter shift action to goto state.
5. For A → α•, enter reduction for terminals in FOLLOW(A).
6. For S' → S•, enter accept on $.
7. Fill GOTO entries for non-terminals.

Closure Operation

Goto Operation

Advantages

• Smaller tables than CLR.
• Easy to construct compared with CLR.
• More powerful than LL(1) for many grammars.

Limitation

Some LR grammars are not SLR because FOLLOW sets may create conflicts.

12. Canonical LR Parser and Table Construction 14 Marks

LR(1) Item

Construction Steps

1. Augment the grammar.
2. Construct closure of LR(1) item sets.
3. Compute goto transitions.
4. Create canonical LR(1) collection.
5. Add shifts for terminal transitions.
6. Add reductions only on the item's specific lookahead.
7. Add accept for [S' → S•, $].

Why CLR Is More Powerful

SLR uses all terminals in FOLLOW(A), while CLR uses exact lookahead information attached to each item. Therefore unnecessary reductions and conflicts are avoided.

Advantages

• Most powerful standard LR method.
• Very precise lookahead handling.
• Accepts the largest grammar class among SLR, LALR and CLR.

Limitations

• Very large number of states.
• Large parsing table.
• Construction is complex.

13. LALR Parser and Table Construction 14 Marks

Construction Steps

1. Construct Canonical LR(1) item sets.
2. Identify states having identical LR(0) cores.
3. Merge these states.
4. Combine lookahead symbols of corresponding items.
5. Construct ACTION and GOTO tables from merged states.

Advantages

• Table size close to SLR.
• Power close to CLR.
• Widely used by parser generators such as YACC.

Limitation

Merging states can introduce reduce-reduce conflicts that were absent in the CLR parser.

14. Comparison of SLR, CLR and LALR 14 Marks

15. Using Ambiguous Grammars 14 Marks

Expression Grammar

The input id + id * id has two parse trees because the grammar does not define precedence.

Resolution Methods

• Rewrite grammar to encode precedence.
• Rewrite grammar to encode associativity.
• Use precedence declarations in parser generators.
• Resolve dangling-else conflict using a rule such as matching else with nearest unmatched if.

Why Ambiguous Grammar May Still Be Used

An ambiguous grammar can be shorter and more natural. Parser generators may permit it when conflicts are resolved using explicit precedence and associativity declarations.

Advantages

• Compact grammar
• Readable expression rules
• Convenient with parser-generator directives

Risk

Unresolved ambiguity creates shift-reduce or reduce-reduce conflicts and may generate unintended parse trees.

16. Automatic Parser Generator 14 Marks

General Architecture

YACC Workflow

1. Declare tokens and precedence.
2. Write grammar productions.
3. Attach semantic actions.
4. Run YACC to generate parser source.
5. Compile generated parser with lexical analyzer.

Benefits

• Reduces development time.
• Automatically creates complex tables.
• Reports grammar conflicts.
• Supports semantic actions and error handling.
• Easy grammar modification.

Limitations

• Generated code may be difficult to debug.
• Grammar conflicts require expert understanding.
• Tool-specific declarations reduce portability.

Unit 2 Quick Revision

• The parser checks syntax and constructs a parse tree.
• Top-down parsing produces a leftmost derivation.
• Bottom-up parsing produces a rightmost derivation in reverse.
• Predictive parsers use FIRST and FOLLOW sets.
• Shift-reduce parsing uses shift, reduce, accept and error actions.
• Operator precedence parsing is suitable for expression grammars.
• SLR uses LR(0) items and FOLLOW sets.
• CLR uses LR(1) items with exact lookahead.
• LALR merges CLR states having the same core.
• Parser generators automate table and parser construction.

Important RGPV Exam Questions

Long Answer Questions

1. Explain the working and role of a parser.
2. Explain top-down parsing and problems of left recursion and left factoring.
3. Explain recursive-descent parsing with an example.
4. Explain predictive parsing and the LL(1) algorithm.
5. Compute FIRST and FOLLOW sets for a grammar.
6. Construct a predictive parsing table and parse an input string.
7. Explain bottom-up and shift-reduce parsing.
8. Explain operator precedence parsing.
9. Explain LR parser architecture and actions.
10. Construct SLR parsing table for a grammar.
11. Explain Canonical LR parser construction.
12. Explain LALR table construction.
13. Compare SLR, CLR and LALR parsers.
14. Explain ambiguous grammars and conflict resolution.
15. Explain automatic parser generators.

Short Answer Questions

1. Define parser.
2. What is left recursion?
3. What is left factoring?
4. Define FIRST and FOLLOW.
5. What is a handle?
6. Define viable prefix.
7. What is an LR item?
8. What is a shift-reduce conflict?
9. Expand SLR, CLR and LALR.
10. What is an ambiguous grammar?

Download Study Resources

Frequently Asked Questions

Related Study Pages