LAB MANUAL
TOP-DOWN PARSING
Title
Implementation of Top-Down Parsing Techniques
Objective of the Lab
- To understand and implement top-down parsing techniques using C programming.
- To practise writing small programs for detecting grammar properties (left/right recursion, balanced
parentheses).
- To implement actual parsers (recursive descent and predictive parsers).
1. Introduction
Parsing is the process of analysing a string of symbols (source code) according to the rules of a
formal grammar. Top-down parsing builds the parse tree from the root down to the leaves. It starts
from the start symbol and tries to derive the input string.
2. Types of Top-Down Parsing
1. Recursive Descent Parsing – a set of mutually recursive procedures for each non-terminal.
2. Predictive Parsing – uses lookahead and a stack to decide which production to use.
3. Process of Top-Down Parsing
1. Start with the start symbol of the grammar.
2. Expand non-terminals using productions.
3. Match input tokens with terminals.
4. Backtrack if a mismatch occurs (recursive descent) or consult parsing table (predictive parser).
5. Accept the string if the input is consumed and stack is empty.
4. Tools Used
We can write and compile C programs on any C IDE such as Code::Blocks, Dev-C++, GCC/G++ or
online IDEs. Workflow in Code::Blocks:
- Open Code::Blocks → New File → Empty C file.
- Type the C code (use algorithms given below).
- Save as .c.
- Click “Build and Run”.
- Provide input when prompted.
5. Shorter Programs (Grammar Analysis)
These exercises strengthen your understanding of grammar analysis and small parsing tasks.
Program 3: Check for Left Recursion
Objective: Detect whether a grammar production contains left recursion.
Algorithm/Flow:
1. Start the program.
2. Read the non-terminal symbol and its production.
3. Check whether the first symbol in the production is the same as the non-terminal.
4. If yes, display “Left recursion detected”, else “No left recursion”.
5. Stop.
Program 4: Check for Right Recursion
Objective: Detect whether a grammar production contains right recursion.
Algorithm/Flow:
1. Start the program.
2. Read the non-terminal symbol and its production.
3. Check whether the last symbol in the production is the same as the non-terminal.
4. If yes, display “Right recursion detected”, else “No right recursion”.
5. Stop.
Program 5: Check for Balanced Parentheses
Objective: Check whether parentheses in the input string are balanced.
Algorithm/Flow:
1. Start the program.
2. Read the input string.
3. Traverse each character: increment counter for '(' and decrement for ')'.
4. If counter becomes negative at any point, break.
5. After traversal, if counter is zero → “Balanced”, else “Not balanced”.
6. Stop.
6. Main Assignment Programs
Program 1: Recursive Descent Parser
Objective: Implement a recursive descent parser for a simple expression grammar.
Algorithm/Flow:
1. Start the program.
2. Read the input string.
3. Implement one function for each non-terminal: E, E', T.
4. E() calls T() then E'().
5. E'() checks for a + sign and recursively calls itself.
6. T() checks for id.
7. If the entire string is successfully traversed → “Successfully parsed” else “Error”.
8. Stop.
Program 2: Predictive Parser Using Stack
Objective: Implement a non-recursive predictive parser for the grammar S → a S b | ε.
Algorithm/Flow:
1. Start the program.
2. Read the input string.
3. Push '$' and start symbol S on the stack.
4. While stack not empty:
- If top of stack equals current input symbol → pop and move to next input.
- If top of stack is S and current input is a → expand S to a S b by pushing b, S, a.
- Else → error.
5. If input is finished and stack is empty → accept string else error.
6. Stop.
7. Workflow of the Tool (Code::Blocks / GCC)
Open Code::Blocks → New C Project → add new .c file.
Type one of the programs above using the algorithm.
Save.
Click Build and Run.
Give input when asked.
See output (whether grammar property detected or string parsed).
8. Conclusion
This lab introduced top-down parsing theory, types of top-down parsers (recursive descent,
predictive), writing small helper programs to detect grammar properties, and implementation of two
real parsers in C. By completing these exercises, students can understand how compilers parse
source code before translation.
