CD Notes

Expression Parser Project

Build an advanced mathematical expression parser with tree visualization

Introduction and Goals

An expression parser takes mathematical expressions like 2 + 3 * 4 or sin(pi/2) + sqrt(16) and understands their structure — respecting operator precedence, associativity, and function application. This project goes beyond a simple calculator by building and visualizing the parse tree, demonstrating how the hierarchical structure of an expression determines its meaning.

This is an ideal second project after the basic calculator because it introduces several new concepts: right-associative operators (exponentiation), unary operators (negation), function calls as expressions, variables, and tree visualization. By the end, you will have a tool that can display the parse tree for any mathematical expression, making abstract parsing concepts concrete and visual.

Language Specification

Our expression parser handles a rich set of mathematical constructs:

- Integer and floating-point literals	42, 3.14, .5, 1e10
- Arithmetic operators	+, -, *, /, % (modulo)
- Exponentiation	^ (right-associative: 2^3^2 = 2^9 = 512)
- Unary negation	-5, -(3+4)
- Parentheses	(2+3) * 4
- Functions	sin, cos, tan, sqrt, abs, log, exp
- Constants	pi, e
- Variables	x, y, z (with assignment)

Operator Precedence Table

Precedence determines evaluation order. Higher precedence binds tighter:

Level 1 (lowest)	+, - Binary addition/subtraction (left-associative)
Level 2	*, /, % Multiplication/division (left-associative)
Level 3	^ Exponentiation (RIGHT-associative)
Level 4	- (unary) Negation (prefix, right-to-left)
Level 5 (highest)	func() Function application (prefix)

The grammar naturally encodes this hierarchy — each precedence level gets its own grammar rule:

expression	term (('+' \| '-') term)*
term	power (('' \| '/' \| '%') power)
power	unary ('^' power)? // Right-recursive for right-assoc
unary	'-' unary \| postfix
postfix	primary \| FUNC_NAME '(' expression ')'
primary	NUMBER \| VARIABLE \| '(' expression ')'

Notice the critical difference: power uses '^' power (recursive call to itself) rather than '^' unary. This makes exponentiation right-associative. For 2^3^2, the parser first processes 3^2 = 9, then 2^9 = 512.

Implementation: Recursive Descent Parser

Each grammar rule becomes a C function. The code directly mirrors the grammar structure:

Example

// Parse expression: handles + and - (lowest precedence) double parse_expression(Parser *p) { double result = parse_term(p); while (p->token.type == TOK_PLUS || p->token.type == TOK_MINUS) { TokenType op = p->token.type; advance(p); double right = parse_term(p); result = (op == TOK_PLUS) ? result + right : result - right; } return result; } // Parse term: handles *, /, % (medium precedence) double parse_term(Parser *p) { double result = parse_power(p); while (p->token.type == TOK_STAR || p->token.type == TOK_SLASH || p->token.type == TOK_PERCENT) { TokenType op = p->token.type; advance(p); double right = parse_power(p); if (op == TOK_STAR) result *= right; else if (op == TOK_SLASH) { if (right == 0) { error(p, "Division by zero"); return 0; } result /= right; } else result = fmod(result, right); } return result; } // Parse power: handles ^ (right-associative, high precedence) double parse_power(Parser *p) { double base = parse_unary(p); if (p->token.type == TOK_CARET) { advance(p); double exponent = parse_power(p); // RIGHT-recursive! return pow(base, exponent); } return base; } // Parse unary: handles negation (prefix -) double parse_unary(Parser *p) { if (p->token.type == TOK_MINUS) { advance(p); return -parse_unary(p); // Recursive: handles --x, ---x } return parse_postfix(p); } // Parse postfix: handles function calls double parse_postfix(Parser *p) { if (p->token.type == TOK_FUNC) { char func_name[32]; strcpy(func_name, p->token.text); advance(p); expect(p, TOK_LPAREN); double arg = parse_expression(p); expect(p, TOK_RPAREN); return apply_function(func_name, arg); } return parse_primary(p); } // Parse primary: numbers, variables, parenthesized expressions double parse_primary(Parser *p) { if (p->token.type == TOK_NUMBER) { double val = p->token.value; advance(p); return val; } if (p->token.type == TOK_VARIABLE) { double val = get_variable(p->token.text); advance(p); return val; } if (p->token.type == TOK_LPAREN) { advance(p); double result = parse_expression(p); expect(p, TOK_RPAREN); return result; } error(p, "Expected number, variable, or '('"); return 0; }

Building a Parse Tree (AST Version)

Instead of evaluating directly, build a tree structure for visualization:

Example

typedef struct TreeNode { char label[32]; // "+", "*", "sin", "3.14", "x" struct TreeNode *left; struct TreeNode *right; } TreeNode; TreeNode* build_expression(Parser *p) { TreeNode *left = build_term(p); while (p->token.type == TOK_PLUS || p->token.type == TOK_MINUS) { TreeNode *node = make_node(p->token.text); advance(p); node->left = left; node->right = build_term(p); left = node; } return left; }

Tracing Through Examples

Example 1: 2 + 3 * 4

parse_power	parse_unary → parse_primary → returns 2
No * or /	term returns 2
Token is '+'	advance, call parse_term again
parse_power	parse_primary → returns 3
Token is '*'	advance, call parse_power
parse_primary	returns 4

Example 2: 2^3^2 (right-associative)

parse_unary	returns 2
Token is '^'	advance, call parse_power RECURSIVELY
parse_unary	returns 3
Token is '^'	advance, call parse_power RECURSIVELY
parse_unary	returns 2
No '^'	returns 2

Example 3: sin(pi/2) + 1

parse_term	parse_power → parse_unary → parse_postfix
Token is FUNC "sin"	advance, expect '('
Token is '/'	advance
No *	term returns 1.0
Token is '+'	advance
parse_term	parse_primary → returns 1

Tree Visualization

Print the parse tree in a readable format:

Example

void print_tree(TreeNode *node, int depth, char *prefix) { if (!node) return; printf("%s%s%s\n", prefix, depth > 0 ? "├── " : "", node->label); char new_prefix[256]; sprintf(new_prefix, "%s│ ", prefix); print_tree(node->left, depth + 1, new_prefix); sprintf(new_prefix, "%s ", prefix); print_tree(node->right, depth + 1, new_prefix); }

Output for (a + b) * (c - d):

* ├── + │ ├── a │ └── b └── - ├── c └── d

Variable Support

Add a simple environment for variable storage:

Example

typedef struct { char name[32]; double value; } Variable; Variable variables[100]; int var_count = 0; // Support assignment: x = 5 // Modify parser to check for "IDENT = expression" at top level double parse_statement(Parser *p) { if (p->token.type == TOK_VARIABLE && peek_next(p) == TOK_ASSIGN) { char name[32]; strcpy(name, p->token.text); advance(p); advance(p); // Skip variable and '=' double value = parse_expression(p); set_variable(name, value); return value; } return parse_expression(p); }

Error Handling

Provide clear, specific error messages:

c example

void error(Parser *p, const char *expected) {
    fprintf(stderr, "Error at position %d: %s\n", p->position, expected);
    fprintf(stderr, "  Input: %s\n", p->input);
    fprintf(stderr, "  %*s^\n", p->position + 9, "");  // Point to error
}

Key Takeaways

This project demonstrates that operator precedence and associativity are naturally encoded in the grammar hierarchy. Each precedence level corresponds to a grammar rule and a parser function. Right-associativity is achieved through right-recursion (the function calls itself for the right operand), while left-associativity uses iteration (a while loop consuming operators of equal precedence). Building and visualizing parse trees makes these abstract concepts tangible, showing exactly how the parser's structure determines the mathematical meaning of every expression.

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Expression Parser Project.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.

Search Terms

compiler-design, compiler design, compiler, design, projects, expression, parser, project

Continue learning this concept

ProjectsLexical Analyzer ProjectPractical project for building a lexical analyzer with token recognition ProjectsSyntax Checker ProjectBuild a comprehensive syntax and semantic analyzer with error reporting ProjectsToy Compiler Project: Minimal Complete CompilerStep-by-step guide to building a complete toy compiler from scratch ProjectsCalculator Compiler ProjectDetailed project guide for building a mathematical expression evaluator ProjectsMini Programming Language ProjectComplete project building an interpreter for a small procedural language Parser GeneratorsPractical Parser ProjectsReal-world parser implementation guide with AST construction, symbol tables, and code generation

PreviousCalculator Compiler Project NextLexical Analyzer Project

CD Notes

Expression Parser Project

Build an advanced mathematical expression parser with tree visualization

Introduction and Goals

Language Specification

Our expression parser handles a rich set of mathematical constructs:

- Integer and floating-point literals	42, 3.14, .5, 1e10
- Arithmetic operators	+, -, *, /, % (modulo)
- Exponentiation	^ (right-associative: 2^3^2 = 2^9 = 512)
- Unary negation	-5, -(3+4)
- Parentheses	(2+3) * 4
- Functions	sin, cos, tan, sqrt, abs, log, exp
- Constants	pi, e
- Variables	x, y, z (with assignment)

Operator Precedence Table

Precedence determines evaluation order. Higher precedence binds tighter:

Level 1 (lowest)	+, - Binary addition/subtraction (left-associative)
Level 2	*, /, % Multiplication/division (left-associative)
Level 3	^ Exponentiation (RIGHT-associative)
Level 4	- (unary) Negation (prefix, right-to-left)
Level 5 (highest)	func() Function application (prefix)

The grammar naturally encodes this hierarchy — each precedence level gets its own grammar rule:

expression	term (('+' \| '-') term)*
term	power (('' \| '/' \| '%') power)
power	unary ('^' power)? // Right-recursive for right-assoc
unary	'-' unary \| postfix
postfix	primary \| FUNC_NAME '(' expression ')'
primary	NUMBER \| VARIABLE \| '(' expression ')'

Implementation: Recursive Descent Parser

Each grammar rule becomes a C function. The code directly mirrors the grammar structure:

Example

Building a Parse Tree (AST Version)

Instead of evaluating directly, build a tree structure for visualization:

Example

Tracing Through Examples

Example 1: 2 + 3 * 4

parse_power	parse_unary → parse_primary → returns 2
No * or /	term returns 2
Token is '+'	advance, call parse_term again
parse_power	parse_primary → returns 3
Token is '*'	advance, call parse_power
parse_primary	returns 4

Example 2: 2^3^2 (right-associative)

parse_unary	returns 2
Token is '^'	advance, call parse_power RECURSIVELY
parse_unary	returns 3
Token is '^'	advance, call parse_power RECURSIVELY
parse_unary	returns 2
No '^'	returns 2

Example 3: sin(pi/2) + 1

parse_term	parse_power → parse_unary → parse_postfix
Token is FUNC "sin"	advance, expect '('
Token is '/'	advance
No *	term returns 1.0
Token is '+'	advance
parse_term	parse_primary → returns 1

Tree Visualization

Print the parse tree in a readable format:

Example

Output for (a + b) * (c - d):

* ├── + │ ├── a │ └── b └── - ├── c └── d

Variable Support

Add a simple environment for variable storage:

Example

Error Handling

Provide clear, specific error messages:

c example

void error(Parser *p, const char *expected) {
    fprintf(stderr, "Error at position %d: %s\n", p->position, expected);
    fprintf(stderr, "  Input: %s\n", p->input);
    fprintf(stderr, "  %*s^\n", p->position + 9, "");  // Point to error
}

Key Takeaways

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Expression Parser Project.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.

Search Terms

compiler-design, compiler design, compiler, design, projects, expression, parser, project

Continue learning this concept

PreviousCalculator Compiler Project NextLexical Analyzer Project