Recursive Descent Parser in C - Assignment Report
Objective
The primary objective of this assignment is to design and implement a Recursive Descent Parser in C
capable of parsing and validating simple control structures (if, else, and while) and arithmetic expressions
with support for nested parentheses. A unique feature includes the recognition of a special token LTD, which
stands for the "Last Three Digits" of the student ID and is substituted during evaluation. This parser aims to
simulate compiler front-end syntax analysis using recursive procedures, token streams, and error detection
mechanisms.
Grammar Summary
<program> -> <block>
<block> -> "{" { <statement> } "}"
<statement> -> <if-statement> | <while-statement> | <expression> ";"
<if-statement> -> "if" "(" <condition> ")" <block> [ "else" <block> ]
<while-statement> -> "while" "(" <condition> ")" <block>
<condition> -> <expression> <relational-operator> <expression>
<relational-operator> -> "==" | "!=" | "<" | ">" | "<=" | ">="
<expression> -> <term> { ("+" | "-") <term> }
<term> -> <factor> { ("*" | "/") <factor> }
<factor> -> <number> | <identifier> | "LTD" | "(" <expression> ")"
Design and Implementation
Lexer (Tokenizer):
- Keywords: if, else, while
- Symbols: {, }, (, ), ;, +, -, *, /, relational operators
Recursive Descent Parser in C - Assignment Report
- Identifiers: variable names starting with letters
- Numbers: sequences of digits
- Special Token: LTD, substituted during evaluation
Parser Structure:
- Each grammar rule corresponds to a parsing function.
- Recursive function calls support nested structures.
- match() ensures token correctness.
Error Handling:
- Detects mismatched brackets, missing semicolons, unexpected tokens, invalid identifiers, misplaced
relational operators.
LTD Handling:
- Treated as a special identifier, replaced with the last 3 digits of the student ID.
Sample Test Cases
Valid Case:
if (a == LTD) {
while (b < 100) {
(a + b) * (b - LTD);
} else {
Recursive Descent Parser in C - Assignment Report
(x + y) * (a - b);
Invalid Case 1 - Missing Semicolon:
a+b
Output: Syntax Error: Expected token type 20 (semicolon) but found }
Invalid Case 2 - Mismatched Brackets:
if (a == b) {
a + b;
Output: Syntax Error: Unexpected token after program end: (null)
Invalid Case 3 - Invalid Identifier:
3a + 5;
Output: Syntax Error: Invalid factor: 3a
Compilation & Execution Instructions
File: parser.c
Recursive Descent Parser in C - Assignment Report
To compile:
gcc parser.c -o parser
To run:
./parser
Input Method:
Copy-paste the input code block or read from a file using redirection.
Conclusion
This assignment simulates a basic front-end compiler parser using recursive descent. It helps develop a deep
understanding of parsing control structures and expressions. Through modular design, error handling, and
careful matching of grammar rules, this parser successfully validates simple source code fragments and
forms the foundation for more advanced compiler features in the future.
