C Notes
HubApplications of C Programming LanguageFeatures of C Programming LanguageHistory of C Programming LanguageWhat is C Language?Why Learn C Programming in 2024?First C Program - Hello World in C with ExplanationGCC Compiler - Complete Guide to GNU C CompilerInstall C Compiler on Linux - GCC Setup Guide for All DistrosInstall C Compiler on macOS - Xcode Command Line Tools and Homebrew GCCInstall C Compiler on Windows - MinGW, MSYS2, and WSL GuideSetup VS Code for C Programming - Complete Configuration GuideC Syntax Rules — Complete GuideComments in C ProgrammingConstants in C ProgrammingData Types in CIdentifiers in C ProgrammingKeywords in C ProgrammingStructure of a C ProgramVariables in C ProgrammingArithmetic Operators in C ProgrammingAssignment Operators in C ProgrammingBitwise Operators in C ProgrammingIncrement and Decrement Operators in CLogical Operators in C ProgrammingRelational Operators in C ProgrammingTernary Operator in C ProgrammingBreak Statement in C ProgrammingContinue Statement in C ProgrammingDo-While Loop in C ProgrammingFor Loop in C ProgrammingGoto Statement in C Programmingif-else Statement in C Programmingif Statement in C ProgrammingNested if Statements in C ProgrammingSwitch Statement in C ProgrammingWhile Loop in C ProgrammingFunction Arguments in C - Pass by Value vs Pass by ReferenceFunction Call in C ProgrammingFunction Declaration (Prototype) in CFunction Definition in C ProgrammingIntroduction to Functions in C ProgrammingRecursion in C ProgrammingReturn Statement in C ProgrammingStorage Classes in C ProgrammingArray Operations in C - Searching, Sorting, Insert and DeleteArray Programs in C - Reverse, Rotate, Duplicates, MergeIntroduction to Arrays in C ProgrammingMultidimensional Arrays in C ProgrammingOne Dimensional Arrays in C ProgrammingPassing Arrays to Functions in CTwo Dimensional Arrays in C ProgrammingString Comparison in C - strcmp, strncmp, Case-InsensitiveString Functions in C - strlen, strcpy, strcat, strcmpC String Handling Library - Complete string.h ReferenceString Manipulation in C - Reverse, Uppercase, PalindromeString Programs in C - Anagram, Word Count, Vowels, FrequencyStrings in C Programming - Complete IntroductionDouble Pointers in C - Pointer to PointerPointer Arithmetic in C ProgrammingPointer Declaration and Initialization in CPointer Programs in C - Swap, String Reversal, Dynamic AllocationPointers and Arrays in C - The Relationship ExplainedPointers and Functions in C - Pass by ReferenceIntroduction to Pointers in C ProgrammingVoid Pointers in C - Generic Pointers Guidecalloc() in C – Contiguous Memory AllocationDynamic Arrays in C – Runtime-Sized Arraysfree() in C – Releasing Dynamic Memorymalloc() in C – Dynamic Memory AllocationMemory Management Best Practices in Crealloc() in C – Resizing Dynamic MemoryBinary Files in C – fread and fwriteFile Handling in C – IntroductionFile Handling Projects in C – Student Records & Phone BookFile Modes in C – Complete Guidefopen() and fclose() in C – Opening and Closing FilesReading Files in C – fgetc, fgets, fscanf, freadWriting Files in C – fputc, fputs, fprintf, fwriteConditional Compilation in C – #ifdef, #ifndef, #if#define Macros in C – Constants and Macro FunctionsHeader Files in C – Creating Custom Headers#include Directive in C – File InclusionMacro Functions in C – Parameterized MacrosC Preprocessor – Overview and DirectivesGraphs in C – Adjacency Matrix, Adjacency List, BFS, and DFSHash Tables in C – Implementation, Collision Handling, and ChainingLinked List in C – Singly, Doubly, and Circular with ImplementationQueue in C – Linear, Circular, and Priority Queue ImplementationStack in C – Array and Linked List Implementation with ApplicationsTrees in C – Binary Search Tree Implementation with TraversalsC Programming Best Practices – Coding Standards, Safety, and PerformanceBit Fields in C – Definition, Use Cases, and Protocol HeadersC Standard Library Overview – All Headers and Common FunctionsCommand Line Arguments in C – argc and argv ExplainedDebugging Techniques in C – GDB, Valgrind, and SanitizersFunction Pointers in C – Complete Guide with ExamplesMemory Layout of a C Program – Text, Data, BSS, Heap, StackBank Management System in C – Complete Project with File StorageFile Encryption Tool in C – XOR Cipher ImplementationLibrary Management System in C – Complete Project with Source CodeMini Compiler in C – Lexer and Parser for Simple ExpressionsSnake Game in C – Console-Based Game with Source CodeStudent Management System in C – Complete Project with Source CodeC Programming Cheatsheet – Complete Quick Reference GuideTop 50 C Programming Interview Questions with Answers (2025)Memory Management Interview Questions in C with AnswersOutput Prediction Questions in C – What Will This Program Print?Pointer Interview Questions in C – Tricky Problems with AnswersCommon C Programming Errors and Solutions – Debugging GuideImportant C Programs – 50+ Frequently Asked Programs with SolutionsQuick Revision Notes for C Programming – Complete C in 10 MinutesRecommended C Programming Books – From Beginner to ExpertFormat Specifiers in C - Complete Referencegetchar() and putchar() in C Programminggets() and puts() in C ProgrammingC Input Output Programs and Examplesprintf() Function in C Programmingscanf() Function in C ProgrammingArrays of Structures in C – Managing CollectionsEnums in C – Enumerated Data TypesNested Structures in C – Struct Within StructPointers to Structures in C – Arrow OperatorStructures in C – User-Defined Data Typestypedef in C – Creating Type AliasesUnions in C – Shared Memory Data Types
Build a mini compiler in C with lexical analyzer (lexer), parser, and expression evaluator. Learn compiler design basics with complete source code and explanation.
Building a mini compiler is one of the most educational projects in computer science. This project implements a simple expression compiler that can tokenize, parse, and evaluate mathematical expressions. You'll learn the fundamentals of compiler design: lexical analysis (tokenization), syntax analysis (parsing), and code execution (evaluation).
What Our Mini Compiler Does
Input: Mathematical expressions like 3 + 5 * (2 - 1) Output: Evaluated result with a breakdown of compilation phases
Supported features:
- Integer and floating-point numbers
- Operators:
+,-,*,/,% - Parentheses for grouping
- Variable assignment:
x = 5 - Multiple statements separated by semicolons
Phase 1: Lexical Analyzer (Lexer)
The lexer breaks input text into tokens – the smallest meaningful units.
Example
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
// Token types
typedef enum {
TOKEN_NUMBER,
TOKEN_PLUS,
TOKEN_MINUS,
TOKEN_MULTIPLY,
TOKEN_DIVIDE,
TOKEN_MODULO,
TOKEN_LPAREN,
TOKEN_RPAREN,
TOKEN_ASSIGN,
TOKEN_IDENTIFIER,
TOKEN_SEMICOLON,
TOKEN_EOF,
TOKEN_ERROR
} TokenType;
typedef struct {
TokenType type;
double numValue;
char identifier[64];
int line;
int column;
} Token;
typedef struct {
const char *source;
int pos;
int line;
int column;
} Lexer;
const char* tokenTypeName(TokenType type) {
switch (type) {
case TOKEN_NUMBER: return "NUMBER";
case TOKEN_PLUS: return "PLUS";
case TOKEN_MINUS: return "MINUS";
case TOKEN_MULTIPLY: return "MULTIPLY";
case TOKEN_DIVIDE: return "DIVIDE";
case TOKEN_MODULO: return "MODULO";
case TOKEN_LPAREN: return "LPAREN";
case TOKEN_RPAREN: return "RPAREN";
case TOKEN_ASSIGN: return "ASSIGN";
case TOKEN_IDENTIFIER: return "IDENTIFIER";
case TOKEN_SEMICOLON: return "SEMICOLON";
case TOKEN_EOF: return "EOF";
default: return "ERROR";
}
}
void initLexer(Lexer *lex, const char *source) {
lex->source = source;
lex->pos = 0;
lex->line = 1;
lex->column = 1;
}
char peek(Lexer *lex) {
return lex->source[lex->pos];
}
char advance(Lexer *lex) {
char c = lex->source[lex->pos++];
if (c == '\n') { lex->line++; lex->column = 1; }
else { lex->column++; }
return c;
}
void skipWhitespace(Lexer *lex) {
while (peek(lex) && isspace(peek(lex)))
advance(lex);
}
Token nextToken(Lexer *lex) {
skipWhitespace(lex);
Token token = {TOKEN_ERROR, 0, "", lex->line, lex->column};
char c = peek(lex);
if (c == '\0') { token.type = TOKEN_EOF; return token; }
// Numbers
if (isdigit(c) || (c == '.' && isdigit(lex->source[lex->pos + 1]))) {
token.type = TOKEN_NUMBER;
char numBuf[64];
int i = 0;
while (isdigit(peek(lex)) || peek(lex) == '.') {
numBuf[i++] = advance(lex);
}
numBuf[i] = '\0';
token.numValue = atof(numBuf);
return token;
}
// Identifiers (variable names)
if (isalpha(c) || c == '_') {
token.type = TOKEN_IDENTIFIER;
int i = 0;
while (isalnum(peek(lex)) || peek(lex) == '_') {
token.identifier[i++] = advance(lex);
}
token.identifier[i] = '\0';
return token;
}
// Single-character tokens
advance(lex);
switch (c) {
case '+': token.type = TOKEN_PLUS; break;
case '-': token.type = TOKEN_MINUS; break;
case '*': token.type = TOKEN_MULTIPLY; break;
case '/': token.type = TOKEN_DIVIDE; break;
case '%': token.type = TOKEN_MODULO; break;
case '(': token.type = TOKEN_LPAREN; break;
case ')': token.type = TOKEN_RPAREN; break;
case '=': token.type = TOKEN_ASSIGN; break;
case ';': token.type = TOKEN_SEMICOLON; break;
default:
fprintf(stderr, "Unknown character '%c' at %d:%d\n", c, token.line, token.column);
}
return token;
}
Phase 2: Parser (Recursive Descent)
The parser builds a tree structure from tokens using operator precedence rules.
Example
// AST Node types
typedef enum {
NODE_NUMBER,
NODE_BINARY_OP,
NODE_UNARY_OP,
NODE_VARIABLE,
NODE_ASSIGN
} NodeType;
typedef struct ASTNode {
NodeType type;
double numValue;
char varName[64];
char op;
struct ASTNode *left;
struct ASTNode *right;
} ASTNode;
// Parser state
typedef struct {
Lexer lexer;
Token current;
} Parser;
ASTNode* newNumberNode(double value) {
ASTNode *node = (ASTNode*)malloc(sizeof(ASTNode));
node->type = NODE_NUMBER;
node->numValue = value;
node->left = node->right = NULL;
return node;
}
ASTNode* newBinaryNode(char op, ASTNode *left, ASTNode *right) {
ASTNode *node = (ASTNode*)malloc(sizeof(ASTNode));
node->type = NODE_BINARY_OP;
node->op = op;
node->left = left;
node->right = right;
return node;
}
ASTNode* newVarNode(const char *name) {
ASTNode *node = (ASTNode*)malloc(sizeof(ASTNode));
node->type = NODE_VARIABLE;
strcpy(node->varName, name);
node->left = node->right = NULL;
return node;
}
void parserAdvance(Parser *p) {
p->current = nextToken(&p->lexer);
}
void initParser(Parser *p, const char *source) {
initLexer(&p->lexer, source);
parserAdvance(p);
}
// Forward declarations for recursive descent
ASTNode* parseExpression(Parser *p);
ASTNode* parseTerm(Parser *p);
ASTNode* parseFactor(Parser *p);
// Factor: number | variable | (expression) | -factor
ASTNode* parseFactor(Parser *p) {
Token tok = p->current;
if (tok.type == TOKEN_NUMBER) {
parserAdvance(p);
return newNumberNode(tok.numValue);
}
if (tok.type == TOKEN_IDENTIFIER) {
parserAdvance(p);
// Check for assignment
if (p->current.type == TOKEN_ASSIGN) {
parserAdvance(p);
ASTNode *node = (ASTNode*)malloc(sizeof(ASTNode));
node->type = NODE_ASSIGN;
strcpy(node->varName, tok.identifier);
node->right = parseExpression(p);
node->left = NULL;
return node;
}
return newVarNode(tok.identifier);
}
if (tok.type == TOKEN_LPAREN) {
parserAdvance(p);
ASTNode *node = parseExpression(p);
if (p->current.type != TOKEN_RPAREN) {
fprintf(stderr, "Error: Expected ')'\n");
return NULL;
}
parserAdvance(p);
return node;
}
if (tok.type == TOKEN_MINUS) {
parserAdvance(p);
ASTNode *node = (ASTNode*)malloc(sizeof(ASTNode));
node->type = NODE_UNARY_OP;
node->op = '-';
node->right = parseFactor(p);
node->left = NULL;
return node;
}
fprintf(stderr, "Unexpected token: %s\n", tokenTypeName(tok.type));
return NULL;
}
// Term: factor ((*|/|%) factor)*
ASTNode* parseTerm(Parser *p) {
ASTNode *left = parseFactor(p);
while (p->current.type == TOKEN_MULTIPLY ||
p->current.type == TOKEN_DIVIDE ||
p->current.type == TOKEN_MODULO) {
char op = (p->current.type == TOKEN_MULTIPLY) ? '*' :
(p->current.type == TOKEN_DIVIDE) ? '/' : '%';
parserAdvance(p);
ASTNode *right = parseFactor(p);
left = newBinaryNode(op, left, right);
}
return left;
}
// Expression: term ((+|-) term)*
ASTNode* parseExpression(Parser *p) {
ASTNode *left = parseTerm(p);
while (p->current.type == TOKEN_PLUS || p->current.type == TOKEN_MINUS) {
char op = (p->current.type == TOKEN_PLUS) ? '+' : '-';
parserAdvance(p);
ASTNode *right = parseTerm(p);
left = newBinaryNode(op, left, right);
}
return left;
}
Phase 3: Evaluator
Example
// Simple symbol table for variables
#define MAX_VARS 26
double variables[MAX_VARS] = {0};
double evaluate(ASTNode *node) {
if (!node) return 0;
switch (node->type) {
case NODE_NUMBER:
return node->numValue;
case NODE_VARIABLE:
return variables[node->varName[0] - 'a'];
case NODE_ASSIGN: {
double val = evaluate(node->right);
variables[node->varName[0] - 'a'] = val;
return val;
}
case NODE_UNARY_OP:
return -evaluate(node->right);
case NODE_BINARY_OP: {
double left = evaluate(node->left);
double right = evaluate(node->right);
switch (node->op) {
case '+': return left + right;
case '-': return left - right;
case '*': return left * right;
case '/':
if (right == 0) { fprintf(stderr, "Division by zero!\n"); return 0; }
return left / right;
case '%': return (int)left % (int)right;
}
}
default: return 0;
}
}
void freeAST(ASTNode *node) {
if (!node) return;
freeAST(node->left);
freeAST(node->right);
free(node);
}
Main Program: REPL (Read-Eval-Print Loop)
Example
int main() {
char input[256];
printf("Mini Expression Compiler v1.0\n");
printf("Supports: +, -, *, /, %%, (), variables (a-z)\n");
printf("Type 'quit' to exit\n\n");
while (1) {
printf(">>> ");
if (!fgets(input, sizeof(input), stdin)) break;
input[strcspn(input, "\n")] = '\0';
if (strcmp(input, "quit") == 0) break;
if (strlen(input) == 0) continue;
// Lexer phase - show tokens
printf("Tokens: ");
Lexer tempLex;
initLexer(&tempLex, input);
Token tok;
do {
tok = nextToken(&tempLex);
if (tok.type == TOKEN_NUMBER) printf("[NUM:%.2f] ", tok.numValue);
else if (tok.type == TOKEN_IDENTIFIER) printf("[ID:%s] ", tok.identifier);
else printf("[%s] ", tokenTypeName(tok.type));
} while (tok.type != TOKEN_EOF);
printf("\n");
// Parse and evaluate
Parser parser;
initParser(&parser, input);
ASTNode *ast = parseExpression(&parser);
if (ast) {
double result = evaluate(ast);
printf("Result: %g\n\n", result);
freeAST(ast);
}
}
printf("Goodbye!\n");
return 0;
}
Sample Output
Output
Mini Expression Compiler v1.0 Supports: +, -, *, /, %, (), variables (a-z) Type 'quit' to exit >>> 3 + 5 * 2 Tokens: [NUM:3.00] [PLUS] [NUM:5.00] [MULTIPLY] [NUM:2.00] [EOF] Result: 13 >>> (3 + 5) * 2 Tokens: [LPAREN] [NUM:3.00] [PLUS] [NUM:5.00] [RPAREN] [MULTIPLY] [NUM:2.00] [EOF] Result: 16 >>> x = 10 Tokens: [ID:x] [ASSIGN] [NUM:10.00] [EOF] Result: 10 >>> x * 2 + 3 Tokens: [ID:x] [MULTIPLY] [NUM:2.00] [PLUS] [NUM:3.00] [EOF] Result: 23
Compilation Phases Overview
| Phase | Input | Output | Purpose |
|---|---|---|---|
| Lexer | Source text | Token stream | Break text into meaningful units |
| Parser | Token stream | AST (tree) | Build structure, check syntax |
| Evaluator | AST | Result value | Compute the final answer |
Interview Questions
Q: What is operator precedence and how is it handled? Precedence determines which operations execute first. In recursive descent parsing, lower-precedence operators are parsed at higher levels. parseTerm handles *// (higher precedence), while parseExpression handles +/-.
Q: What's the difference between a lexer and a parser? The lexer handles character-level patterns (numbers, identifiers, operators) and produces tokens. The parser handles structural rules (expressions, statements) and produces a syntax tree.
Q: How would you add support for functions like sin(x)? In the lexer, recognize function names as identifiers. In the parser, when you see identifier(, parse the argument expression, close with ), and create a function call node.
Summary
This mini compiler project demonstrates the three fundamental phases of compilation: lexical analysis, parsing, and evaluation. The recursive descent parser naturally handles operator precedence through its call hierarchy. While simple, this architecture is the same foundation used by production compilers – just scaled up with more token types, grammar rules, and code generation phases.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Mini Compiler in C – Lexer and Parser for Simple Expressions.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this C Programming topic.
Search Terms
c-programming, c programming, programming, projects, mini, compiler, project, mini compiler in c – lexer and parser for simple expressions
Related C Programming Topics
Continue learning this concept
ProjectsBank Management System in C – Complete Project with File StorageBuild a Bank Management System in C with account creation, deposit, withdrawal, balance inquiry, and file-based storage. Complete source code with explanation.ProjectsFile Encryption Tool in C – XOR Cipher ImplementationBuild a File Encryption Tool in C using XOR cipher with key-based encryption, file processing, command-line interface, and multiple cipher modes explained.ProjectsLibrary Management System in C – Complete Project with Source CodeBuild a Library Management System in C with book management, member registration, book issue/return, fine calculation, and file storage. Full source code included.ProjectsSnake Game in C – Console-Based Game with Source CodeBuild a classic Snake Game in C for the console using arrays, game loops, keyboard input handling, and collision detection. Complete source code with explanation.ProjectsStudent Management System in C – Complete Project with Source CodeBuild a complete Student Management System in C with file handling, CRUD operations, searching, sorting, and menu-driven interface. Full source code included.File HandlingFile Handling Projects in C – Student Records & Phone BookComplete file handling project examples in C — student record management system, phone book application with add/search/delete/display operations, menu-driven programs with binary files.