Forem: Sarun Tapee

Garbage Collector Implementation in C

Sarun Tapee — Wed, 24 Sep 2025 16:41:18 +0000

In C, there is no garbage collector. This article will guide you on how to implement a garbage collector for C. You will learn how data is stored in memory and the challenge that C has. By the end, you will be able to make your own garbage collector. The complete code could be found on GitHub

Algorithm

Let's begin with the algorithm for detecting a memory leak. A memory leak occurs when the program keeps allocating heap memory and never frees it when it is no longer used. If your program will finally terminate, it is fine since the operating system will reclaim the memory for other processes to use. But if your program needs to run continuously, your computer will finally run out of memory and crash. So the purpose of the garbage collector is to somehow free the unused memory during runtime.

The first question is how to detect which memory area needs to be freed. The simplest idea is that we can target those memory areas that are not reachable by the program anymore. So there is no need to keep it.

This problem can be modeled as a graph. As you can see in the following picture.

The blue node represents the root of the graph, which is the memory that is located in the stack and the global scope. The green node is a memory in the heap that is reachable from the root. And the red node is a memory that is located in the heap and not reachable.

In conclusion, the algorithm to detect unreachable nodes is to traverse all the nodes in the graph starting from the root and mark the reachable nodes. Then we can identify which node is reachable and which is not.

Challenge

Since C is not a strongly typed language. The challenge is as follows.

There is no metadata at the runtime. So that we do not know the meaning of each byte stored in the memory.
We can cast a type in C to any type, so the pointer value could be stored in a variable of type int.
A programmer can store a pointer value in any form they want. e.g., a Singly Linked List that can traverse in both directions by storing the previous node's address together with the next node's address using the XOR operator.

We will not handle challenge no.3, But we need to solve the first two challenges since we need to traverse the graph. There are two possible solutions.

Register metadata (struct name, struct size, number of fields, field name, field type, field size, offset of each field) of every structure in our program to our garbage collector library so that it knows how to deserialize the data.
Scan every byte in the stack and the global area and assume that it is a pointer value. If it points to a valid area address in the heap, follow it.

Comparing the solutions

The first solution will be faster when you traverse the graph, since you know which field is a pointer. But the drawback is that it is more verbose to use since we need to register every struct type in the library. The usage would be like this

typedef struct student_ {
  int id;
  char name[32];
  student_t *friend;
} student_t;

register_struct("student_t", (fields_t *) {
  {"id", "int", sizeof(int)}, 
  {"name", "char", sizeof(char) * 32}, 
  {"friend", "student_t", sizeof(student_t *)}
});

student_t *student = my_calloc("student_t", 1);

This will work, but there are some problems that after calling my_calloc we should now cast the pointer student to another type and store another value than student_t. Another problem is that some struct might contain a void * pointer, then we cannot traverse the graph further because we do not know what type that pointer holds.

With those drawbacks of the first solution, I decided to go with solution no.2, which is scanning every byte on the stack and the global memory area. But we do not need to check every possibility of a byte combination (the sliding window of 8 bytes, the size of the pointer is 8 bytes) because in normal compilation of a C program, the struct field gets padded to contain in word size (the size of the pointer) to make a reading operation faster. Let's look at the example code below.

#include <stdio.h>
#include <stdint.h>

#define sizeof_field(struct_name, field_name) \
  (sizeof(((struct_name *) 0)->field_name))

#define offsetof(struct_name, field_name) \
  ((unsigned int) (intptr_t) &((struct_name *) 0)->field_name)

#define show_field(struct_name, field) \
  (printf("%-16s size=%-8lu offset=%u\n", #struct_name "." #field , sizeof_field(struct_name, field), offsetof(struct_name, field)))

typedef struct emp_ {
    char emp_name[30];
    unsigned int emp_id;
    unsigned int age;
    struct emp_ *mgr;
    float salary;
} emp_t;

int main (void) {
  show_field(emp_t, emp_name);
  show_field(emp_t, emp_id);
  show_field(emp_t, age);
  show_field(emp_t, mgr);
  show_field(emp_t, salary);
}

Output

emp_t.emp_name   size=30       offset=0
emp_t.emp_id     size=4        offset=32
emp_t.age        size=4        offset=36
emp_t.mgr        size=8        offset=40
emp_t.salary     size=4        offset=48

As you can see from the output emp_id field does not start from position 30 but 32 because the field emp_name is padded to 32, and the extra 2 bytes are unused. This may seem like an inefficient use of memory, but this makes the read operation faster. Because the CPU reads memory one word at a time. Imagine that if the emp_name is not padded, the field emp_id data will live in 2 different words, so when you access the field emp_id, the CPU needs to read 2 times and combine the results to get the value.

With this memory padding assumption, we can scan 8 bytes and jump to the next 8 bytes.

As can be seen from the picture above, instead of scanning bytes as read color, we can scan as green color. Of course, we might have misunderstood that some heap memory is still being used because some word might contain data that has a meaning that it is a pointer to the heap area, but the possibility is very low, and there is no harm in keeping that memory area. It is better than freeing the memory that we are still using.

Implementation

Now we have almost all the knowledge to implement a garbage collector. The missing part is how we get the boundary of the stack and the global variable area. Their is providing macro __builtin_frame_address(0) to get the address of the current frame function. and etex to get the ending of the code section (the beginning of the global variable section), end to get the ending of the global variable section.

So in the beginning, we can call __builtin_frame_address(0) at the top of the main function and save the address to stack_base, but for ease of use, let's make a macro.

uintptr_t stack_base = 0;

#define gc_init() \
  stack_base = (uintptr_t) __builtin_frame_address(0)

Next, we will make a function to wrap a calloc function, let's name it gc_calloc. This function will store the address of every memory that is allocated on the heap and delegate work to calloc.

Now, thinking of the information that we need to keep for our gc_calloc, we probably need to store the address of allocated memory and its size. Since we need to find the address when traversing the tree quite often. I think a sorted array would be a good data structure to hold this information because we can use the binary search algorithm to find the address. The implementation is as follows.

#define ALLOC_CAP 5000
static chunk_t alloced_chunks[ALLOC_CAP] = {0};
static size_t alloced_size = 0;

Then implement the gc_calloc

void *gc_calloc(size_t n, size_t size) {
  void *p;
  chunk_t c;
  int i;

  if (n*size == 0) return NULL;
  assert(alloced_size < ALLOC_CAP);
  p = calloc(n, size);
  c = (chunk_t) {.size=n*size, .addr=p};
  for (i = alloced_size - 1; i >= 0 && alloced_chunks[i].addr > p; i--) {
    alloced_chunks[i + 1] = alloced_chunks[i];
  }
  alloced_chunks[i+1] = c;
  alloced_size++;
  return p;
}

Next, we need to implement the tree traversal. Let's name it gc_mark. For marking, we need a data structure to store the state of traversing, which is an array of int mark. We assumed that the pointer is stored in one word, so when we scan the byte, we need to make sure that our starting point is aligned to the word by checking start % sizeof(void *) == 0. Since the memory allocation is specified in bytes, if the size has a fragment of a word, we should not scan the remainder to avoid buffer overflow. And the leftover cannot hold a pointer anyway because it is smaller than a pointer size.

static char mark[ALLOC_CAP] = {0};

void gc_mark() {
  uintptr_t stack_start;
  size_t i;

  stack_start = (uintptr_t) __builtin_frame_address(0);
  assert(stack_base != 0 && "gc_init() is not called");
  for (i = 0; i < alloced_size; i++) {
    mark[i] = 0;
  }

  // scanning stack area
  do_mark(stack_start, stack_base + sizeof(void *));

  // scanning global variable area
  _mark_from_global_var();
}

static void do_mark(uintptr_t start, uintptr_t end) {
  int i;
  void **p;
  chunk_t *c;
  uintptr_t bound;

  assert(start % sizeof(void *) == 0);
  bound = start + ((end - start) / sizeof(void *) * sizeof(void*));
  for (p = (void *) start; (uintptr_t) p < bound; p++) {
    i = bs_lte(*p);
    if (i == -1) continue;
    assert(i < (int) alloced_size);
    c = &alloced_chunks[i];
    assert((uintptr_t) c->addr <= (uintptr_t) *p);
    if (!mark[i] && (uintptr_t) *p < (uintptr_t) c->addr + c->size) {
      mark[i] = 1;
      do_mark( (uintptr_t) c->addr, (uintptr_t) c->addr + c->size);
    }
  }
}

There is a little gatcha for global variable scanning. Notice that our allocation information is stored in the variable alloced_chunks, which is also located in the global scope. So we need to ignore this area. Otherwise, our gc_mark will always say that every memory in the heap is in use.

static void _mark_from_global_var() {
  uintptr_t _start;
  uintptr_t _end;

  _start = align_up((uintptr_t) &etext);
  _end = (uintptr_t) &end + sizeof(void *);
  assert(_start % sizeof(void *) == 0);
  assert(end % sizeof(void *) == 0);
  do_mark(_start, (uintptr_t) &alloced_chunks[0]);
  do_mark((uintptr_t) &alloced_chunks[ALLOC_CAP], _end);
}

The last piece is to clean the leaked memory gc_sweep.

void gc_sweep() {
  size_t i;
  size_t j;

  for (i = 0; i < alloced_size; i++) {
    if (!mark[i]) {
      free(alloced_chunks[i].addr);
    }
  }
  j = 0;
  for (i = 0; i < alloced_size; i++) {
    if (mark[i]) {
      alloced_chunks[j++] = alloced_chunks[i];
    }
  }
  alloced_size = j;
}

To debug our garbage collector, let's implement a function to print the state of the allocation gc_dump_alloced.

void gc_dump_alloced() {
  int i;

  printf("alloc (%zu)\n", alloced_size);
  for (i = 0; i < (int) alloced_size; i++) {
    printf("addr: %p, size: %zu, mark: %s\n", alloced_chunks[i].addr, alloced_chunks[i].size, mark[i] ? "true": "false");
  }
}

Test the implementation

Now, Let's test the implementaion.

#include "garbage_collect.h"
#include <stdio.h>

void *global_var;

typedef struct node_ node_t;

typedef struct node_ {
  node_t *left;
  node_t *right;
} node_t;

typedef struct student_ {
  int id;
  node_t node;
} student_t;

int main(void) {
  gc_init();
  node_t *stud_lst;

  global_var = gc_calloc(3, sizeof(int));

  stud_lst = &((student_t *) gc_calloc(1, sizeof(student_t)))->node;
  stud_lst->right = &((student_t *) gc_calloc(1, sizeof(student_t)))->node;
  stud_lst->right->right = &((student_t *) gc_calloc(1, sizeof(student_t)))->node;

  printf("global_var hold: %p\n", global_var);
  gc_mark();
  gc_dump_alloced();

  printf("---\nset stud_lst = NULL\n");
  stud_lst = NULL;
  gc_mark();
  printf("mark\n");
  gc_dump_alloced();
  gc_sweep();
  printf("sweep\n");
  gc_dump_alloced();

  return 0;
}

It's work!!

./exe
global_var hold: 0x55a6ef582310
alloc (4)
addr: 0x55a6ef582310, size: 12, mark: true
addr: 0x55a6ef582330, size: 24, mark: true
addr: 0x55a6ef582350, size: 24, mark: true
addr: 0x55a6ef582370, size: 24, mark: true
---
set stud_lst = NULL
mark
alloc (4)
addr: 0x55a6ef582310, size: 12, mark: true
addr: 0x55a6ef582330, size: 24, mark: false
addr: 0x55a6ef582350, size: 24, mark: false
addr: 0x55a6ef582370, size: 24, mark: false
sweep
alloc (1)
addr: 0x55a6ef582310, size: 12, mark: true

Usage

Instead of calling gc_mark and followed by gc_sweep, let's make a wrapper function for convenience.

void gc_clean() {
  gc_mark();
  gc_sweep();
}

Then the usage will simplify to.

int main(void) {
  gc_init();
  node_t *stud_lst;

  global_var = gc_calloc(3, sizeof(int));

  stud_lst = &((student_t *) gc_calloc(1, sizeof(student_t)))->node;
  stud_lst->right = &((student_t *) gc_calloc(1, sizeof(student_t)))->node;
  stud_lst->right->right = &((student_t *) gc_calloc(1, sizeof(student_t)))->node;

  stud_lst = NULL;
  gc_clean();
  return 0;
}

Congratulations. You now get your own garbage collector working. The complete code could be found on GitHub

Event Loop - the need and how to implement

Sarun Tapee — Mon, 22 Sep 2025 01:46:40 +0000

TL;DR

The event loop is a thread that runs in an infinite loop, pulling the tasks, which are callback functions, from the queue and executing them one by one. If the queue is empty, it goes into an idle state waiting for a task to be added to the queue to be processed again. The implementation of the task can achieve concurrency by dividing the task into sub-tasks. When a sub-task is finished, put the next sub-task in the queue to let other tasks have a chance to execute. There is no need for thread synchronization like mutex and condition variable since there is only one thread (the event loop thread) that accesses the resource, and the context switching is in the programmer's control, unlike a multi-threaded that each thread gets CPU time depending on the implementation logic of the operating system. The implementation code can be found in GitHub.

Process vs Thread

Before discussing processes and threads, let's understand the operating system. As shown in the picture below, the operating system is divided into three layers. Hardware, Operating System, and Application Programs. When we write a program. For example, "Hello world", it lives in the Application Programs layer. When the program gets executed, it runs on an operating system as a process. There are many processes running on your computer, and it is the job of the operating system to give each process access to the hardware, like the CPU, concurrently by switching processes to run on the CPU.

Each process has its own virtual memory, which is managed by the operating system, as shown in the following picture.

As can be seen, each process has its own virtual memory, so the communication between them can be done by transferring the data (a socket can be used). whereas threads share the same code and heap memory area, so each thread can access all the memory area except the other thread's stack memory area. When a process creates a new thread, it goes and runs on its own, and the operating system treats it like a process. The difference is that each thread that was created by the same process shares the same virtual memory

Concurrency and Parallelism

Parallelism means that your thread gets executed at the same time. While concurrency means that your thread gets executed one after the other by switching the execution between the threads, in the eyes of humans, the two threads seem like happening at the same time because both threads have progress. The illustration is shown as follows.

When you program a multi-threaded program, it doesn't mean that your program will run in parallel. Your program will run in parallel only if there is no overlap, and you have more than one CPU. Overlap means each thread has to operate on the same data structure, and the operation cannot happen in parallel. For example, one thread wants to read the data structure, but another thread wants to write to it, which will make the data structure inconsistent, so we need to prevent this not happening at the same time by using a mutex and a condition variable to ensure that only one thread can access the data structure at a time. Note that if two threads want to read the same data structure, this can happen at the same time.

Multi-thread Programming

To demonstrate multi-thread programming. I will use the C programming language, but the concept applies to any programming language of your choice. The classic problem of multi-thread programming is the consumer-producer problem. The consumer thread pulls data from the data structure, and the producer thread puts data into that data structure. To synchronize between two threads, we need a mutex to lock the access to the data structure and a condition variable to send a signal between threads. The pseudo code is as follows. Let's say that the shared data structure is a queue.

queue

// consumer
lock(queue) (1)
while (queue is empty) { (2)
 wait(until queue have data) (3)
}
pull data from queue (4)
unlock(queue) (5)

// producer
lock(queue) (6)
if (queue not full) { (7)
 put data into queue (8)
 signal(queue have data) (9)
}
unlock(queue) (10)

Let's see how each step works.

Consumer

Step 1: We lock the queue so that other threads cannot access the queue.
Step 2: We check the condition with a while loop instead of an if clause to prevent Spurious Wakeup. For example, after getting the signal from Step 3, some other thread might have already pulled the data from the queue, so we need to check the condition again after getting the signal.
Step 3: If the condition from Step 2 is met, block the thread until it gets the signal to wake up. Behind the scenes, the operating system will unlock the queue to let other threads access the queue. After getting a signal from the producer on step 9, the consumer thread will move to the ready state, meaning that it will not get executed until the producer calls unlock on Step 10. Then, the operating system, behind the scenes, will lock the queue and hand the key to this consumer thread, allowing it to access the queue.
Step 4: The consumer thread pulls data from the queue.
Step 5: unlock the queue to let other threads access the queue.

Producer

Step 6: The producer locks the queue to prevent other threads from accessing the queue.
Step 7: Check the condition.
Step 8: Put data into the queue.
Step 9: Signal to the waiting thread that the queue has data. The signal is not queued, which means if there is no waiting thread, the signal is lost. So there is no need to check if there is a waiting thread.
Step 10: Unlock the queue to let other threads access the queue.

Now let's see an implementation in C.

#include <stdio.h>
#include <assert.h>
#include <pthread.h>
#include <string.h>

#define QUEUE_SIZE 5

typedef struct queue_ {
  int data[QUEUE_SIZE];
  int front;
  int rear;
  int len;
} queue_t;

void queue_init(queue_t *q) {
  memset(q, 0, sizeof(*q));
}

void queue_add(queue_t *q, int n) {
  assert(q->len < QUEUE_SIZE);
  q->data[q->rear] = n;
  q->len++;
  q->rear++;
  if (q->rear >= QUEUE_SIZE) q->rear = 0;
}

int queue_remove(queue_t *q) {
  int r;

  assert(q->len > 0);
  r = q->data[q->front];
  q->front++;
  q->len--;
  if (q->front >= QUEUE_SIZE) q->front = 0;
  return r;
}

int queue_is_full(queue_t *q) {
  return q->len == QUEUE_SIZE;
}

int queue_is_empty(queue_t *q) {
  return q->len == 0;
}

int gen_num() {
  static int n = 0;
  return n++;
}

queue_t q;
pthread_mutex_t mu;
pthread_cond_t not_empty;
pthread_cond_t not_full;

void *consumer(void *arg) {
  char *name;
  int n;

  name = (char *) arg;
  printf("%s: locking mu\n", name);
  pthread_mutex_lock(&mu);
  printf("%s: locked mu\n", name);
  while (queue_is_empty(&q)) {
    printf("%s: wait for queue not_empty signal\n", name);
    pthread_cond_wait(&not_empty, &mu);
    printf("%s: awake\n", name);
  }
  while (!queue_is_empty(&q)) {
    n = queue_remove(&q);
    printf("%s: remove num %d from queue\n", name, n);
  }
  printf("%s: drain all queue and send not_full signal\n", name);
  pthread_cond_signal(&not_full);
  printf("%s: unlocking mu\n", name);
  pthread_mutex_unlock(&mu);
  printf("%s: unlocked mu\n", name);
  printf("%s: done\n", name);
  return NULL;
}

void *producer(void *arg) {
  char *name;
  int n;

  name = (char *) arg;
  printf("%s: locking mu\n", name);
  pthread_mutex_lock(&mu);
  printf("%s: locked mu\n", name);
  while (queue_is_full(&q)) {
    printf("%s: wait for queue not_full signal\n", name);
    pthread_cond_wait(&not_full, &mu);
    printf("%s: awake\n", name);
  }
  while (!queue_is_full(&q)) {
    n = gen_num();
    queue_add(&q, n);
    printf("%s: put number %d to queue\n", name, n);
  }
  printf("%s: filled all slot in queue and sending not_empty signal\n", name);
  pthread_cond_signal(&not_empty);
  printf("%s: unlocking mu\n", name);
  pthread_mutex_unlock(&mu);
  printf("%s: unlocked mu\n", name);
  printf("%s: done\n", name);
  return NULL;
}

int main(void) {
  pthread_t c1, c2;
  pthread_t p1, p2;
  pthread_attr_t attr;

  queue_init(&q);
  pthread_mutex_init(&mu, NULL);
  pthread_cond_init(&not_empty, NULL);
  pthread_cond_init(&not_full, NULL);
  pthread_attr_init(&attr);
  pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);

  pthread_create(&c1, &attr, consumer, "c1");
  pthread_create(&c2, &attr, consumer, "c2");
  pthread_create(&p1, &attr, producer, "p1");
  pthread_create(&p2, &attr, producer, "p2");

  pthread_join(c1, NULL);
  pthread_join(c2, NULL);
  pthread_join(p1, NULL);
  pthread_join(p2, NULL);
  printf("done\n");
  return 0;
}

Serialize multi-thread to single-thread

Multithread programming is hard to get right. It might encounter a deadlock or livelock. And another reason is that creating a new thread consumes memory, so you cannot keep creating threads.

Example use case

Let's say that you have an application that has to listen to the network, accept input from the command line, and a timer that has a task to run in an interval.

As above picture, on the left side, each thread executes the function in its own context. If there is an overlap, it requires a mutex and a condition variable to synchronize between each thread. But on the right side, each thread pushes tasks to the event loop thread, which does not require thread synchronization because every task is executed on the event loop thread context.

The implementation of the event loop is shown as follows. glthread is just a doubly linked list data structure.

// event_loop.h
#ifndef __EVENT_LOOP__
#define __EVENT_LOOP__

#include <pthread.h>
#include "glthread.h"

typedef void (*fn_cb)(void *);

typedef struct task_ {
  fn_cb cb;
  void *arg;
  glthread_node_t node;
} task_t;

typedef struct event_loop_ {
  pthread_t thread;
  pthread_mutex_t mu;
  pthread_cond_t have_task;
  glthread_t glthread;
  task_t *current_task;
} event_loop_t;

void event_loop_init(event_loop_t *el);
void event_loop_run(event_loop_t *el);
task_t *event_loop_add_task(event_loop_t *el, fn_cb cb, void *arg);
void event_loop_cancel_task(event_loop_t *el, task_t *t);

#endif

// event_loop.c
#include "event_loop.h"
#include "glthread.h"
#include <assert.h>
#include <pthread.h>
#include <stdlib.h>

static void *event_loop_fn(void *arg) {
  event_loop_t *el;
  task_t *task;

  el = (event_loop_t *) arg;
  for (;;) {
    pthread_mutex_lock(&el->mu);
    el->current_task = NULL;
    while (el->glthread.size == 0) {
      pthread_cond_wait(&el->have_task, &el->mu);
    }
    task = tostruct(task_t, (&el->glthread), glthread_remove(&el->glthread, NULL));
    el->current_task = task;
    pthread_mutex_unlock(&el->mu);
    task->cb(task->arg);
    free(task);
    task = NULL;
  }
  return NULL;
}


void event_loop_init(event_loop_t *el) {
  el->thread = 0;
  pthread_mutex_init(&el->mu, NULL);
  pthread_cond_init(&el->have_task, NULL);
  glthread_init(&el->glthread, offsetof(task_t, node));
}

void event_loop_run(event_loop_t *el) {
  pthread_attr_t attr;

  pthread_attr_init(&attr);
  pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED);
  pthread_create(&el->thread, &attr, event_loop_fn, el);
}

task_t *event_loop_add_task(event_loop_t *el, fn_cb cb, void *arg) {
  task_t *t;

  t = malloc(sizeof(*t));
  t->cb = cb;
  t->arg = arg;
  pthread_mutex_lock(&el->mu);
  glthread_add(&el->glthread, &t->node);
  pthread_cond_signal(&el->have_task);
  pthread_mutex_unlock(&el->mu);
  return t;
}

void event_loop_cancel_task(event_loop_t *el, task_t *t) {
  pthread_mutex_lock(&el->mu);
  if (el->current_task == t) return;
  glthread_remove(&el->glthread, &t->node);
  pthread_mutex_unlock(&el->mu);
  free(t);
}

Usage

The following is an example usage of an event loop.

// main.c
#include <stdio.h>
#include <unistd.h>
#include "event_loop.h"

event_loop_t el;

int sum(int *nums, int size) {
  int res;
  int i;

  res = 0;
  for (i = 0; i < size; i++) {
    res += nums[i];
  }
  return res;
}

int mul(int *nums, int size) {
  int res;
  int i;

  res = 1;
  for (i = 0; i < size; i++) {
    res += nums[i];
  }
  return res;
}

typedef struct arg_obj_ {
  int *nums;
  int size;
} arg_obj_t;

void sum_fn(void *arg) {
  arg_obj_t *arg_obj;

  arg_obj = (arg_obj_t *) arg;
  printf("sum=%d\n", sum(arg_obj->nums, arg_obj->size));
}

void mul_fn(void *arg) {
  arg_obj_t *arg_obj;

  arg_obj = (arg_obj_t *) arg;
  printf("mul=%d\n", mul(arg_obj->nums, arg_obj->size));

}

int download = 0;
int upload = 0;

void download_fn(void *arg) {
  (void) arg;

  while (download < 100) {
    download += 2;
    printf("download: %d\n", download);
    if (download % 10 == 0) {
      event_loop_add_task(&el, download_fn, NULL);
      return;
    }
  }
  printf("download success\n");
}

void upload_fn(void *arg) {
  (void) arg;

  while (upload < 100) {
    upload += 2;
    printf("upload: %d\n", download);
    if (upload % 10 == 0) {
      event_loop_add_task(&el, upload_fn, NULL);
      return;
    }
  }
  printf("upload success\n");
}
arg_obj_t arg;
int nums[] = {1, 2, 3, 4, 5};

int main(void) {
  arg.nums = nums;
  arg.size = sizeof(nums) / sizeof(nums[0]);
  event_loop_init(&el);
  event_loop_run(&el);
  sleep(1);
  event_loop_add_task(&el, sum_fn, &arg);
  event_loop_add_task(&el, mul_fn, &arg);
  sleep(1);
  event_loop_add_task(&el, download_fn, NULL);
  event_loop_add_task(&el, upload_fn, NULL);
  printf("main done\n");
  pthread_exit(0);
}

Pitfall

As you can see the event loop approch is not require data syncronization between thread. But are there any pitfalls for the above implementation. There is a premature delete problem. Let's say there are two tasks, one is to print each field of the struct another is to delete that struct.

Let's say that the struct has 3 fields. The printing task was implemented to print one field, then push the rest sub-tasks to the event loop to allow other tasks to execute. And there is a delete struct task after the printing task. The tasks in the queue are as follows.

queue
| Print 1st field | Delete struct | Print 2nd field | Print 3rd field |

When the Delete struct was executed, the Print 2nd field will access the invalid memory area.

To solve this problem, you can modify the implementation of the event loop. Instead of having one queue of tasks, you can have multiple queues e.g., HIGH_PRIORITY, MEDIUM_PRIORITY, and LOW_PRIORITY. Your event loop will take a task from HIGH_PRIORITY first, and if that queue is empty, move on to the lower priority queue. Then push the Delete struct to the lower priority queue.

MEDIUM_PRIORITY
| Print 1st field | Print 2nd field | Print 3rd field |

LOW_PRIORITY
| Delete struct |

Variable Operand and Logical Operator

Sarun Tapee — Wed, 23 Jul 2025 01:41:20 +0000

The last two things that we will do are a method to resolve variable value, and support logical expressions by adding a production rule to parse an input string, and operators and, or.

Resolve variable value

To resolve a variable value, we can do so by passing a pointer to a function to a variable-operator node.

// dtype.h
...
class DTypeVar: public DType {
private:
    std::string name;
public:
    DTypeVar(const char *name, DType *(*get_val)(const char *name)=nullptr);
    DType* (*get_val)(const char *name);
    virtual void set_get_val(DType *(*get_val)(const char *name));
    ...
};

// dtype.cpp
void DTypeVar::set_get_val(DType *(*get_val)(const char *name)) {
    this->get_val = get_val;
}

void DTypeVar::setValue(void *v) {
    // empty
}

void DTypeVar::setValue(DType *v) {
    // empty
}

math_exp_type DTypeVar::resultType() {
    if (!this->get_val) return MATH_WILDCARD_VALUE;
    DType *t = this->get_val(this->name.c_str());
    if (!t) return MATH_WILDCARD_VALUE;
    return t->id;
}

DType *DTypeVar::eval() {
    if (!this->get_val) return nullptr;
    return this->get_val(this->name.c_str());
}

DType *DTypeVar::clone() {
    DTypeVar *c = new DTypeVar(this->name.c_str());
    *c = *this;
    c->left = nullptr;
    c->right = nullptr;
    c->parent = nullptr;
    return c;
}
...

For convenience, add a method in MathExprTree class to set get_val function. When the MathExprTree::setGetVal is called, instead of traversing every node in the tree, we will store variable nodes as a linked list in a tree for faster iteration.

// math_expr_tree.h
class MathExprTree {
private:
    ...
    std::list<DTypeVar *> vars;
public:
    ...
    MathExprTree(lex_data **postfix, int size, DType *(get_val)(const char *name)=nullptr); // add defult argument to the last parameter of constructor
    void setGetVal(DType *(*get_val)(const char *name));
    ...
};

// math_expr_tree.cpp
MathExprTree::MathExprTree(lex_data **postfix, int size, DType *(*get_val)(const char *name)) {
    lex_data *l;
    std::stack<MathExprNode *> s;

    for (int i = 0; i < size; i++) {
        l = postfix[i];
        if (l->token_code == MATH_SPACE) continue;
        assert(is_operator(l->token_code) || is_operand(l->token_code));
        if (is_operand(l->token_code)) {
            ...
            DTypeVar *var = dynamic_cast<DTypeVar *>(o);
            if (var) {
                this->vars.push_back(var);
            }
        } else if (is_unary_op(l->token_code)) {
            ...
}

void MathExprTree::setGetVal(DType *(*get_val)(const char *name)){
    for (std::list<DTypeVar *>::iterator it = this->vars.begin(); it != this->vars.end(); it++) {
        (*it)->set_get_val(get_val);
    }
}

Production rule for logical expression

Begin with the math production rule. To support unary (sqr, sqrt, sin, cos) and binary operators (max, min, pow), we need to modify our production rule to be like this.

E -> F + E | F - E | F
F -> T * F | T / F | T
T -> (E) | <var> | <int> | <double> | G(E) | P(E, E)
G -> sqr | sqrt | sin | cos
P -> min | max | pow

Then we can use the math production rule to construct the inequality production rule.

Q -> E INEQ E
INEQ -> == | != | < | <= | > | >=

After that, we can use the inequality production rule to construct the logical production rule

S -> S or J | J
J -> J and K | K 
K -> (S) | D | K LOP Q | Q LOP K
D -> Q LOP Q
LOP -> and | or

As you can see, our logical production rule suffers from left recursion. After removing left recursion, the production rule becomes.

S -> J S'
S' -> or J S' | $

J -> K J'
J' -> and K J' | $

K -> (S) K' | D K' | Q LOP K K'
K' -> LOP Q K' | $

D -> Q LOP Q
LOP -> and | or

Implement a calculator program

At this point, we can test our expression implementation by creating a calculator program as follows.

// calculator.cpp
extern parse_status E(); // math expression parser
extern parse_status Q(); // inequality expression parser
extern parse_status S(); // logical expression parser
extern lex_data **infix_to_postfix(lex_data *infix, int size_in, int *size_out);

// hard code the value of variable a, and b
DType *get_val(const char *name) {
    if (strcmp(name, "a") == 0) {
        return new DTypeInt(2);
    }
    if (strcmp(name, "b") == 0) {
        return new DTypeDouble(1.5);
    }
    return nullptr;
}

int main(void) {
    parse_status s;
    lex_data **postfix;
    int postfix_len;
    MathExprTree *tree;
    DType *res;
    lex_data d;

    while (1) {
        printf("input -> ");
        fgets(lex_buffer, sizeof(lex_buffer), stdin);
        stack_reset();
        s = S();
        if (s == PARSE_ERROR) {
            s = Q();
            if (s == PARSE_ERROR) {
                s = E();
            }
        }
        d = cyylex(); yyrewind(1);
        if (s == PARSE_ERROR || d.token_code != PARSER_EOL) {
            printf("invalid math expression\n");
            continue;
        }
        postfix = infix_to_postfix(lex_stack.data, lex_stack.top + 1, &postfix_len);
        tree = new MathExprTree(postfix, postfix_len, get_val);
        // tree = new MathExprTree(postfix, postfix_len);
        // tree->setGetVal(get_val);
        do {
            if (!tree->valid()) {
                printf("invalid math operation\n");
                break;
            }
            res = tree->eval();
            if (!res) {
                printf("cannot slove equation\n");
                break;
            }
            switch (res->id) {
            case MATH_INTEGER_VALUE: printf("%d", ((DTypeInt *) res)->val); break; 
            case MATH_DOUBLE_VALUE: printf("%f", ((DTypeDouble *) res)->val); break; 
            case MATH_BOOL: printf("%s", ((DTypeBool *) res)->val ? "True" : "False"); break;
            default: assert(0);
            }
            printf("\n");
        } while (0);
        delete tree;
        free(postfix);
        tree = nullptr;
        postfix = nullptr;
    }
    return 0;
}

That's it for the mathematical expression parser series. Thank you for reading my article. Hope you have learned something 🥳.

Construction of Expression Tree

Sarun Tapee — Wed, 23 Jul 2025 00:26:16 +0000

After getting the postfix form of the mathematical expression, we can construct an expression tree and evaluate the result of the expression.

prefix form:
a + sqr(max(b,c)) * d

postfix form:
a b c max sqr d * + 

expression tree:

    +
   / \
  a   *
     / \
   sqr  d
   /
  max
 /  \
b    c

postfix to expression tree algorithm

The algorithm to construct expression treee is as follows.

For each element in postfix
    if operand
        push to stack
    if unary operator
        left_child = stack.pop
        elem->left = left_child
        push elem to stack
    if binary operator
        right_child = stack.pop
        left_child = stack.pop
        elem->left = left_child
        elem->right = right_child
        push elem to stack
root = stack.pop

Evaluate the result of the expression tree

To evaluate the result of the expression tree, all we need to do is postorder traversal of the tree and return the result.

Define tree data type

As we can see from the tree structure, we can observe that all the leaf nodes are operands, and the internal nodes are operators. We will implement the tree class as follows class diagram.

MathExprTree and MathExprNode

// math_expr_tree.h
class MathExprNode {
protected:
    MathExprNode(); // protected constructor to prevent creating an object of this class
public:
    virtual ~MathExprNode(); // make destructor virtual to not only call the destructor of the base class on a pointer of MathExprNode
    MathExprNode *parent;
    MathExprNode *left;
    MathExprNode *right;
    virtual math_exp_type resultType() = 0;
    virtual DType *eval() = 0;
};

class MathExprTree {
private:
    void clear(MathExprNode *node);
public:
    MathExprNode *root;
    MathExprTree(lex_data **postfix, int size);
    virtual ~MathExprTree();
    void inorderPrint(); // just to check the tree after construct
    bool valid(); // check if the data type and operator are compatible
    DType *eval(); // evaluate the result of the expression tree

};

// math_expr_tree.cpp
static void _inorderPrint(MathExprNode *node); 

MathExprNode::MathExprNode() {
    this->parent = NULL;
    this->left = NULL;
    this->right = NULL;
}

MathExprNode::~MathExprNode() {}

MathExprTree::MathExprTree(lex_data **postfix, int size) {
    lex_data *l;

    for (int i = 0; i < size; i++) {
        l = postfix[i];
        if (l->token_code == MATH_SPACE) continue;
        assert(is_operator(l->token_code) || is_operand(l->token_code));
        if (is_operand(l->token_code)) {
            DType *o = DType::factory(l->token_code, l->text, get_val);
            s.push(o);
        } else if (is_unary_op(l->token_code)) {
            MathExprNode *node = Operator::factory(l->token_code);
            MathExprNode *left = s.top(); s.pop();
            left->parent = node;
            node->left = left;
            s.push(node);
        } else {
            MathExprNode *node = Operator::factory(l->token_code);
            MathExprNode *right = s.top(); s.pop();
            MathExprNode *left = s.top(); s.pop();
            node->left = left;
            node->right = right;
            left->parent = node;
            right->parent = node;
            s.push(node);
        }
    }
    this->root = s.top(); s.pop();
    assert(s.empty());
    assert(!this->root->parent);
}

void MathExprTree::clear(MathExprNode *node) {
    if (!node) return;
    clear(node->left);
    clear(node->right);
    delete node;
}

MathExprTree::~MathExprTree() {
    clear(this->root);
    this->root = nullptr;
}

void MathExprTree::inorderPrint() {
    _inorderPrint(this->root);
}

bool MathExprTree::valid() {
    return this->root && this->root->resultType() != MATH_INVALID;
}


DType *MathExprTree::eval() {
    if (!this->root) return nullptr;
    return this->root->eval();
}

static void _inorderPrint(MathExprNode *node) {
    if (!node) return;
    _inorderPrint(node->left);
    Operator *o = dynamic_cast<Operator *>(node);
    if (o) {
        printf("%s ", o->symbol.c_str());
    } else {
        DType *t = dynamic_cast<DType *>(node);
        assert(t);
        switch (t->id) {
        case MATH_INTEGER_VALUE: printf("%d ", ((DTypeInt *) t)->val); break;
        case MATH_DOUBLE_VALUE: printf("%f ", ((DTypeDouble *) t)->val); break;
        default: assert(0);
        }
    }
    _inorderPrint(node->right);
}

Operator

// operator.h
class Operator: public MathExprNode {
protected:
    Operator();
public:
    virtual ~Operator();
    math_exp_type id;
    std::string symbol;
    bool is_unary;
    static Operator *factory(math_exp_type id);
    virtual math_exp_type resultType() = 0;
    virtual DType *eval() = 0;
};

class OperatorPlus: public Operator {
private:
    math_exp_type resultType(math_exp_type a, math_exp_type b); 
public:
    OperatorPlus();
    ~OperatorPlus();
    virtual math_exp_type resultType() override;
    virtual DType *eval() override;
};

class OperatorMinus: public Operator {
private:
    math_exp_type resultType(math_exp_type a, math_exp_type b); 
public:
    OperatorMinus();
    ~OperatorMinus();
    virtual math_exp_type resultType() override;
    virtual DType *eval() override;
};

// operator.cpp
Operator::Operator(){
    this->id = MATH_INVALID;
    this->symbol = "";
    this->is_unary = false;
};
Operator::~Operator(){};

Operator *Operator::factory(math_exp_type id) {
    switch (id) {
    case MATH_PLUS: return new OperatorPlus();
    case MATH_MINUS: return new OperatorMinus();
    default: assert(0);
    }
}

OperatorPlus::OperatorPlus() {
    this->id = MATH_PLUS;
    this->symbol = "+";
    this->is_unary = false;
};
OperatorPlus::~OperatorPlus() {};

math_exp_type OperatorPlus::resultType(math_exp_type a, math_exp_type b) {
    switch (comb(a, b)) {
    case comb(MATH_INTEGER_VALUE, MATH_INTEGER_VALUE): return MATH_INTEGER_VALUE;
    case comb(MATH_DOUBLE_VALUE, MATH_DOUBLE_VALUE): return MATH_DOUBLE_VALUE;
    case comb(MATH_WILDCARD_VALUE, MATH_WILDCARD_VALUE): return MATH_WILDCARD_VALUE;
    case comb(MATH_INTEGER_VALUE, MATH_DOUBLE_VALUE): return MATH_DOUBLE_VALUE;
    case comb(MATH_WILDCARD_VALUE, MATH_DOUBLE_VALUE): return MATH_DOUBLE_VALUE;
    case comb(MATH_INTEGER_VALUE, MATH_WILDCARD_VALUE): return MATH_INTEGER_VALUE;
    default: return MATH_INVALID;
    }
}

math_exp_type OperatorPlus::resultType() {
    if (!this->left || !this->right) return MATH_INVALID;
    return resultType(this->left->resultType(), this->right->resultType());
}

DType *OperatorPlus::eval() {
    if (!this->left || !this->right) {
        return nullptr;
    }
    DType *res;
    DType *left = this->left->eval();
    DType *right = this->right->eval();

    res = nullptr;
    do {
        if (!left || !right) break;
        switch (left->id) {
        case MATH_INTEGER_VALUE:
            switch (right->id) {
            case MATH_INTEGER_VALUE:
                    res = new DTypeInt();
                    ((DTypeInt *) res)->val = ((DTypeInt *) left)->val + ((DTypeInt *) right)->val;
                    break;
            case MATH_DOUBLE_VALUE:
                    res = new DTypeDouble();
                    ((DTypeDouble *) res)->val = (double) ((DTypeInt *) left)->val + ((DTypeDouble *) right)->val;
                    break;
            }
            break;
        case MATH_DOUBLE_VALUE:
            switch (right->id) {
            case MATH_INTEGER_VALUE:
                    res = new DTypeDouble();
                    ((DTypeDouble *) res)->val = ((DTypeDouble *) left)->val + (double) ((DTypeInt *) right)->val ;
                    break;
            case MATH_DOUBLE_VALUE:
                    res = new DTypeDouble();
                    ((DTypeDouble *) res)->val = ((DTypeDouble *) left)->val + ((DTypeDouble *) right)->val ;
                    break;
            }
            break;
        }
    } while(0);

    delete left;
    delete right;
    return res;
}

OperatorMinus::OperatorMinus() {
    this->id = MATH_MINUS;
    this->symbol = "-";
    this->is_unary = false;
};
OperatorMinus::~OperatorMinus() {};

math_exp_type OperatorMinus::resultType(math_exp_type a, math_exp_type b) {
    switch (comb(a, b)) {
    case comb(MATH_INTEGER_VALUE, MATH_INTEGER_VALUE): return MATH_INTEGER_VALUE;
    case comb(MATH_DOUBLE_VALUE, MATH_DOUBLE_VALUE): return MATH_DOUBLE_VALUE;
    case comb(MATH_WILDCARD_VALUE, MATH_WILDCARD_VALUE): return MATH_WILDCARD_VALUE;
    case comb(MATH_INTEGER_VALUE, MATH_DOUBLE_VALUE): return MATH_DOUBLE_VALUE;
    case comb(MATH_WILDCARD_VALUE, MATH_DOUBLE_VALUE): return MATH_DOUBLE_VALUE;
    case comb(MATH_INTEGER_VALUE, MATH_WILDCARD_VALUE): return MATH_INTEGER_VALUE;
    default: return MATH_INVALID;
    }
}

math_exp_type OperatorMinus::resultType() {
    if (!this->left || !this->right) return MATH_INVALID;
    return resultType(this->left->resultType(), this->right->resultType());
}

DType *OperatorMinus::eval() {
    if (!this->left || !this->right) {
        return nullptr;
    }
    DType *res;
    DType *left = this->left->eval();
    DType *right = this->right->eval();

    res = nullptr;
    do {
        if (!left || !right) break;
        switch (left->id) {
        case MATH_INTEGER_VALUE:
            switch (right->id) {
            case MATH_INTEGER_VALUE:
                    res = new DTypeInt();
                    ((DTypeInt *) res)->val = ((DTypeInt *) left)->val - ((DTypeInt *) right)->val;
                    break;
            case MATH_DOUBLE_VALUE:
                    res = new DTypeDouble();
                    ((DTypeDouble *) res)->val = (double) ((DTypeInt *) left)->val - ((DTypeDouble *) right)->val;
                    break;
            }
            break;
        case MATH_DOUBLE_VALUE:
            switch (right->id) {
            case MATH_INTEGER_VALUE:
                    res = new DTypeDouble();
                    ((DTypeDouble *) res)->val = ((DTypeDouble *) left)->val - (double) ((DTypeInt *) right)->val ;
                    break;
            case MATH_DOUBLE_VALUE:
                    res = new DTypeDouble();
                    ((DTypeDouble *) res)->val = ((DTypeDouble *) left)->val - ((DTypeDouble *) right)->val ;
                    break;
            }
            break;
        }
    } while(0);

    delete left;
    delete right;
    return res;
}

Operand

// dtype.h
class DType: public MathExprNode {
protected:
    DType();
public:
    virtual ~DType();
    math_exp_type id;
    virtual void setValue(void *v) = 0;
    virtual void setValue(DType *v) = 0;
    virtual math_exp_type resultType() = 0;
    virtual DType *eval() = 0;
    virtual DType *clone() = 0;
    static DType *factory(math_exp_type id, const char *v, DType *(*get_val)(const char *name)=nullptr);
};

class DTypeInt: public DType {
public:
    int val;
    DTypeInt(int v=0);
    DTypeInt(const char *v);
    virtual void setValue(void *v) override;
    virtual void setValue(DType *v) override;
    virtual math_exp_type resultType() override;
    virtual DType *eval() override;
    virtual DType *clone() override;
};

class DTypeDouble: public DType {
public:
    double val;
    DTypeDouble(double v=0.0);
    DTypeDouble(const char *v);
    virtual void setValue(void *v) override;
    virtual void setValue(DType *v) override;
    virtual math_exp_type resultType() override;
    virtual DType *eval() override;
    virtual DType *clone() override;
};

// dtype.cpp
DType::DType() {
    this->id = MATH_INVALID;
}
DType::~DType() {}

DType *DType::factory(math_exp_type id, const char *v, DType *(*get_val)(const char *name)) {
    switch (id) {
    case MATH_INTEGER_VALUE: return new DTypeInt(v);
    case MATH_DOUBLE_VALUE: return new DTypeDouble(v);
    case MATH_IDENTIFIER: return new DTypeVar(v, get_val);
    default: assert(0);
    }
}

DTypeInt::DTypeInt(int v) {
    this->id = MATH_INTEGER_VALUE;
    this->val = v;
}

DTypeInt::DTypeInt(const char *v): DTypeInt() {
    setValue((void *) v);
}

void DTypeInt::setValue(void *v) {
    this->val = atoi((char*) v);
}

void DTypeInt::setValue(DType *v) {
    this->val = dynamic_cast<DTypeInt *>(v)->val;
}

math_exp_type DTypeInt::resultType() {
    return MATH_INTEGER_VALUE;
}

DType *DTypeInt::eval() {
    return clone();
}

DType *DTypeInt::clone() {
    return new DTypeInt(this->val);
}

DTypeDouble::DTypeDouble(double v) {
    this->id = MATH_DOUBLE_VALUE;
    this->val = v;
}

DTypeDouble::DTypeDouble(const char* v): DTypeDouble() {
    setValue((void *) v);
}

void DTypeDouble::setValue(void *v) {
    this->val = atof((char*) v);
}

void DTypeDouble::setValue(DType *v) {
    this->val = dynamic_cast<DTypeDouble *>(v)->val;
}

math_exp_type DTypeDouble::resultType() {
    return MATH_DOUBLE_VALUE;
}

DType *DTypeDouble::eval() {
    return clone();
}

DType *DTypeDouble::clone() {
    return new DTypeDouble(this->val);
}

Testing the Tree implementation

In the infix_to_postfix_test.c, you can add code to test the tree as follows.

// infix_to_postfix_test.c
#define DO_TEST(infix_array, test_tree) { \
    ...
    if (test_tree) { \
        MathExprTree *tree = new MathExprTree(postfix, len); \
        tree->inorderPrint(); \
        printf("\n"); \
        bool ok = tree->valid(); \
        printf("tree %s\n", ok ? "valid" : "in-valid"); \
        if (ok) { \
            printf("res: "); \
            DType *res = tree->eval(); \
            switch (res->id) { \
            case MATH_INTEGER_VALUE: printf("%d", ((DTypeInt *) res)->val); break; \
            case MATH_DOUBLE_VALUE: printf("%f", ((DTypeDouble *) res)->val); break; \
            case MATH_BOOL: printf("%s", ((DTypeBool *) res)->val ? "True" : "False"); break; \
            default: assert(0); \
            } \
            printf("\n"); \
            delete res; \
        } \
        delete tree; \
    } \
}

int main(void) {

    ...

    // 10 + 12 * 42.3 / (2 - 0.5)
    lex_data infix_array5[] = {
        {MATH_INTEGER_VALUE, 2, "10" },
        {MATH_SPACE, 1, " " },
        {MATH_PLUS, 1, "+" },
        {MATH_SPACE, 1, " " },
        {MATH_INTEGER_VALUE, 2, "12" },
        {MATH_SPACE, 1, " " },
        {MATH_MUL, 1, "*" },
        {MATH_SPACE, 1, " " },
        {MATH_DOUBLE_VALUE, 4, "42.3" },
        {MATH_DIV, 1, "/" },
        {MATH_BRACKET_START, 1, "(" },
        {MATH_INTEGER_VALUE, 1, "2" },
        {MATH_MINUS, 1, "-" },
        {MATH_DOUBLE_VALUE, 3, "0.5" },
        {MATH_BRACKET_END, 1, ")" },
    };

    // 1 + 2 * 3 
    lex_data infix_array6[] = {
        {MATH_INTEGER_VALUE, 1, "1" },
        {MATH_PLUS, 1, "+" },
        {MATH_INTEGER_VALUE, 1, "2" },
        {MATH_MUL, 1, "*" },
        {MATH_INTEGER_VALUE, 1, "3" },
    };

    // 1 + 2 * 3.0 
    lex_data infix_array7[] = {
        {MATH_INTEGER_VALUE, 1, "1" },
        {MATH_PLUS, 1, "+" },
        {MATH_INTEGER_VALUE, 1, "2" },
        {MATH_MUL, 1, "*" },
        {MATH_DOUBLE_VALUE, 3, "3.0" },
    };

    ...
     DO_TEST(infix_array5, 1);
     DO_TEST(infix_array6, 1);
     DO_TEST(infix_array7, 1);
}

The rest operators like *, /, max, min, sqr, sqrt, pow, =, !=, <, <=, >, >= are for your exercise.

Infix to Postfix conversion

Sarun Tapee — Tue, 22 Jul 2025 19:50:25 +0000

When we have the expression a + b, we know the meaning that we should add a and b together. This form is called infix. Another form is postfix, which will look like a b +. So why do we need a postfix form? Postfix forms do not have ambiguity. For example,a + b * c we do not know which operation should evaluate first. To remove the ambiguity, we use parentheses (a + b) * c, but there is no problem in the postfix form a b + c *.

How to convert infix to postfix

The algorithm for converting infix to postfix is as follows. which can handle mathematical expressions like this (a + b) * c / sqr(c) + pow(2, 3) - max(d, e).

1. Loop through the sequence of infix strings
2. for each token
  - if toke is operand, append token to postfix string
  - if token == '(' push token in stack
  - if token == ')' pop token from the stack and append to postfix string until find ')' token. Token ')' is removed from the stack.
  - if token == ',' pop token from the stack and append to postfix string until find '(' token. Token ')' still in the stack.
  - if token is a unary operator, append the token to the postfix string.
  - else compare token with top of the stack and pop a token from stack, then append to the postfix string until the precedence of operator of top of the stack is greater than the token. Then push the token to the stack.
3. Pop an operator from the stack and append to the postfix string until the stack is empty.

Implementation

You can either use the built-in stack from C++ or implement it yourself.

// infix_to_postfix.c
typedef struct _stack {
    int top;
    int cap;
    void **data;
} _stack;

static _stack make_stack(int cap);
static void free_stack(_stack *s);
static void stack_push(_stack *s, void *v);
static void *stack_pop(_stack *s);
static void *stack_peek(_stack *s);
static bool stack_is_empty(_stack *s);


lex_data **infix_to_postfix(lex_data *infix, int size_in, int *size_out) {
    lex_data **postfix;
    _stack s = make_stack(size_in);
    int len = 0;
    lex_data *l;
    lex_data *o;

    postfix = (lex_data**) malloc(size_in * sizeof(lex_data**));

    for (int i = 0; i < size_in; i++) {
        l = &infix[i];
        if (l->token_code == MATH_SPACE) continue;
        if (is_operand(l->token_code)) {
            postfix[len++] = l;
        } else if (l->token_code == MATH_BRACKET_START) {
            stack_push(&s, (void *) l);
        } else if (l->token_code == MATH_BRACKET_END) {
            while (1) {
                o = (lex_data*) stack_pop(&s);
                if (o->token_code == MATH_BRACKET_START) {
                    break;
                }
                postfix[len++] = o;
            }
        } else if (l->token_code == MATH_COMMA) {
            while (!stack_is_empty(&s) && ((lex_data*) stack_peek(&s))->token_code != MATH_BRACKET_START) {
                postfix[len++] = (lex_data*) stack_pop(&s);
            }
        }else {
            if (!is_unary_op(l->token_code)) {
                while (!stack_is_empty(&s) && precedent(l->token_code) <= precedent(((lex_data*) stack_peek(&s))->token_code)) {
                    postfix[len++] = (lex_data*) stack_pop(&s);
                }
            }
            stack_push(&s, l);
        }
    }

    while (!stack_is_empty(&s)) {
        postfix[len++] = (lex_data*) stack_pop(&s);
    }

    free_stack(&s);
    *size_out = len;
    return postfix;
}


_stack make_stack(int cap) {
    _stack s = {.top = -1, .cap = cap}; 
    s.data = (void**) malloc(cap * sizeof(void*));
    return s;
}

void free_stack(_stack *s) {
    assert(s);
    free(s->data);
    s->data = NULL;
}

void stack_push(_stack *s, void *v) {
    assert(s && s->top + 1 < s->cap);
    s->data[++s->top] = v;
}

void *stack_pop(_stack *s) {
    assert(s && s->top > -1);
    return s->data[s->top--];
}

void *stack_peek(_stack *s) {
    assert(s && s->top > -1);
    return s->data[s->top];
}

bool stack_is_empty(_stack *s) {
    assert(s);
    return s->top == -1;
}

Testing the infix_to_postfix implementation

You can test your implementation as follows

// infix_to_postfix_test.c
#include <stdio.h>
#include "parser_export.h"
#include "math_expr_tree.h"
#include "dtype.h"
#include <assert.h>

extern lex_data **infix_to_postfix(lex_data *infix, int size_in, int *size_out);

#define DO_TEST(infix_array) { \
    int n; \
    int len; \
    lex_data **postfix; \
    n = sizeof(infix_array)/sizeof(infix_array[0]); \
    printf("---\n"); \
    for (int i = 0; i < n; i++) { \
        printf("%s", infix_array[i].text); \
    } \
    printf("\n"); \
    postfix = infix_to_postfix(infix_array, n, &len);  \
    for (int i = 0; i < len; i++) { \
        printf("%s ", postfix[i]->text); \
    } \
    printf("\n"); \
    } \
}

int main(void) {
    // a + b * c
    lex_data infix_array1[] = {
        {MATH_IDENTIFIER, 1, "a" },
        {MATH_SPACE, 1, " " },
        {MATH_PLUS, 1, "+" },
        {MATH_SPACE, 1, " " },
        {MATH_IDENTIFIER, 1, "b" },
        {MATH_SPACE, 1, " " },
        {MATH_MUL, 1, "*" },
        {MATH_SPACE, 1, " " },
        {MATH_IDENTIFIER, 1, "c" },
    };


    // max(a, b)
    lex_data infix_array2[] = {
        {MATH_MAX, 3, "max" },
        {MATH_BRACKET_START, 1, "(" },
        {MATH_IDENTIFIER, 1, "a" },
        {MATH_COMMA, 1, "," },
        {MATH_SPACE, 1, " " },
        {MATH_IDENTIFIER, 1, "b" },
        {MATH_BRACKET_END, 1, ")" },
    };

    // a + sqr(b) * sqrt(c) + pow(d,e) 
    lex_data infix_array3[] = {
        {MATH_IDENTIFIER, 1, "a" },
        {MATH_PLUS, 1, "+" },
        {MATH_SQR, 3, "sqr" },
        {MATH_BRACKET_START, 1, "(" },
        {MATH_IDENTIFIER, 1, "b" },
        {MATH_BRACKET_END, 1, ")" },
        {MATH_MUL, 1, "*" },
        {MATH_SQRT, 4, "sqrt" },
        {MATH_BRACKET_START, 1, "(" },
        {MATH_IDENTIFIER, 1, "c" },
        {MATH_BRACKET_END, 1, ")" },
        {MATH_PLUS, 1, "+" },
        {MATH_POW, 3, "pow" },
        {MATH_BRACKET_START, 1, "(" },
        {MATH_IDENTIFIER, 1, "d" },
        {MATH_COMMA, 1, "," },
        {MATH_IDENTIFIER, 1, "e" },
        {MATH_BRACKET_END, 1, ")" },
    };    

    // a + sqr(max(b,c,d)) - e
    lex_data infix_array4[] = {
        {MATH_IDENTIFIER, 1, "a" },
        {MATH_PLUS, 1, "+" },
        {MATH_SQR, 3, "sqr" },
        {MATH_BRACKET_START, 1, "(" },
        {MATH_MAX, 3, "max"},
        {MATH_BRACKET_START, 1, "(" },
        {MATH_IDENTIFIER, 1, "b" },
        {MATH_COMMA, 1, "," },
        {MATH_IDENTIFIER, 1, "c" },
        {MATH_COMMA, 1, "," },
        {MATH_IDENTIFIER, 1, "d" },
        {MATH_BRACKET_END, 1, ")" },
        {MATH_BRACKET_END, 1, ")" },
        {MATH_MINUS, 1, "-"},
        {MATH_IDENTIFIER, 1, "e" },
    };    
    DO_TEST(infix_array1);
    DO_TEST(infix_array2);
    DO_TEST(infix_array3);
    DO_TEST(infix_array4);
}

Context Free Gramma (CFG)

Sarun Tapee — Tue, 22 Jul 2025 19:03:18 +0000

A grammar is represented by a production rule which looks like this X -> Y, it means that we can convert X to Y, where X is a non-terminal symbol, and Y could be a terminal symbol, non-terminal symbol, or the combination of both. For example, let's look at the following grammar.

A -> aB
B -> bA | b | ba

Let's label the rule for ease of explanation.

     (1)
A -> aB

     (2)  (3)  (4)
B -> bA | b  | ba

We can try to expand this production rule by starting from the first rule as follwing table.

apply rule No.	result string
	A
1	aB
2	abA
1	abaB
4	ababa

After applying rule number 4, we can not expand the string anymore because it is terminated. And we can say that the string ababa complies with our grammar. If you look at the above grammar, you will notice that it is nothing but the grammar of alternate characters a and b

Implement alternate a b grammar

Let's convert the above grammar to code. Begin with A -> aB

// alternate_a_b.c
parse_status A() {
    PARSE_INIT;
    d = cyylex();
    if (d.token_code != MATH_IDENTIFIER || strcmp(d.text, "a") != 0) RETURN_PARSE_ERROR;
    parse_status s = B();
    if (s == PARSE_ERROR) RETURN_PARSE_ERROR;
    return PARSE_SUCCESS;
}

Now let's implement B -> bA | b | ba. Since there are 3 production rules. We need to try each production rule one by one, and if the testing fails, then move to the next production rule. The order of testing matters. If we test rule number 3 before rule number 2, it will match character b and return success without checking rule number 2. So we should order the rule that covers a bigger domain before the rule that is a subdomain. In this case, we should order as such: (2), (4), (3).

Since we need to parse the string according to the rule one by one. If the parsing fails in the middle, we want to jump to the next rule. The do {...} while(0) control structure can make our code more elegant since if the checking fails in the middle, we can break out of the loop and check the next rule.

// rule 1
do {
  // check1
  // check2
  if (fail) break; // move to next rule
  // check3
} while(0);

// rule 2
do {
} while (0);

// rule 3
do {
} while (0);

...

The production rule B -> bA | b | ba will look like the following.

// alternate_a_b.c
...

parse_status B() {
    PARSE_INIT;
    parse_status s;

    do {
        d = cyylex();
        if (d.token_code != MATH_IDENTIFIER || strcmp(d.text, "b") != 0)
            break;
        s = A();
        if (s == PARSE_ERROR) 
            break;
        return PARSE_SUCCESS;
    } while(0);

    RESTORE_CHECK_POINT;

    do {
        d = cyylex();
        if (d.token_code != MATH_IDENTIFIER || strcmp(d.text, "b") != 0) 
            break;
        d = cyylex();
        if (d.token_code != MATH_IDENTIFIER || strcmp(d.text, "a") != 0)
            break;
        return PARSE_SUCCESS;
    } while(0);

    RESTORE_CHECK_POINT;

    do {
        d = cyylex();
        if (d.token_code != MATH_IDENTIFIER || strcmp(d.text, "b") != 0)
            break;
        return PARSE_SUCCESS;
    } while(0);

    RETURN_PARSE_ERROR;
}

We can test our grammar by implementing the main function as follows.

// alternate_a_b.c
...

void parse_alternate_a_b() {
    if (A() == PARSE_ERROR) {
        printf("invalid ab\n");
    } else {
        lex_data d = cyylex();
        yyrewind(1);
        if ((int) d.token_code == (int) PARSER_EOL)
            printf("valid ab\n");
        else 
            printf("valid ab partial\n");
    }
    for (int i = 0; i <= lex_stack.top; i++) {
        lex_data *p = &lex_stack.data[i];
        printf("%s ", p->text);
    }
    printf("\n");
}

// parser.l
...

extern void parse_alternate_a_b();

int main(void) {
    int token_code;

    while (1) {
        printf("input -> ");
        fgets(lex_buffer, sizeof(lex_buffer), stdin);
        stack_reset();
        parse_alternate_a_b();
    }
    return 0;
}

Mathematical Expression

Now we know how to convert a production rule to code. Let's try to convert a mathematical expression to code. The mathematical expression can be written as follows. which can match a simple mathematical expression like a + b * c / (d + f) + 3 - 1.5

E -> E + F | E - F | F
F -> F * T | F / T | T
T -> (E) | <var> | <int> | <double>

If you try to convert the above production rule to code, you will end up with an infinite recursion. For example, E -> E + F the code will look like.

parse_status E() {
  ...
  do {
    s = E(); // this will cause infinite recursion
    if (s == PARSE_ERROR) break;
    d = cyylex();
    if (d.token_code != MATH_PLUS) break;
    s = F();
    if (s == PARSE_ERROR) break;
    return PARSE_SUCCESS;
  } while (0);
  ...
}

There are two ways to solve this issue.

Swap the order
Apply the algorithm to remove left recursion.

After swapping the order, the production rule will become.

E -> F + E | F - E | F
F -> T * F | T / F | T
T -> (E) | <var> | <int> | <double>

Then you can implement the code without suffering from left recursion.

Another approach is to apply an algorithm. The algorithm is as follows.

1. Remove all the rules that have left recursion.
2. Add a new rule and append to the remaining rules.
3. Add the removed rule to the new rule, but delete the first non-terminal symbol that causes left recursion and append the non-terminal symbol of the new rule.
2. Add an empty symbol as a terminal symbol ($) to the new rules.

Example

E -> E + F | E - F | F

Remove all the rules that have left recursion.

E -> F

Add a new rule and append to the remaining rules.

E -> FE'

E'

Add the removed rule to the new rule, but delete the first non-terminal symbol that causes left recursion and append the non-terminal symbol of the new rule.

E -> FE'

E' -> + FE' | - FE'

Add an empty symbol as a terminal symbol ($) to the new rules.

E -> FE'

E' -> + FE' | - FE' | $

After applying the algorithm to remove left recursion, the production rule will become.

E -> FE'
E' -> +FE' | -FE' | $

F -> TF'
F' -> *TF' | /TF' | $

T -> (E) | <var> | <int> | <double>

Example of E' -> +FE' | -FE' | $ implementation is as follows.

// E' -> +FE' | -FE' | $
parse_status E_dash() {
    PARSE_INIT;
    parse_status s;

    do {
        d = cyylex();
        if (d.token_code != MATH_PLUS) break;
        s = F();
        if (s == PARSE_ERROR) break;
        s = E_dash();
        if (s == PARSE_ERROR) break;
        return PARSE_SUCCESS;
    } while(0);
    RESTORE_CHECK_POINT;

    do {
        d = cyylex();
        if (d.token_code != MATH_MINUS) break;
        s = F();
        if (s == PARSE_ERROR) break;
        s = E_dash();
        if (s == PARSE_ERROR) break;
        return PARSE_SUCCESS;
    } while(0);
    RESTORE_CHECK_POINT;

    return PARSE_SUCCESS; // match empty rule
}

Enhance lexical parser functionality

Sarun Tapee — Tue, 22 Jul 2025 16:17:49 +0000

Now we have a lexical parser working, but we need the ability to undo the parsing by moving back in lex_buffer. Imagine that we want to check if the expression is a SQL select syntax or a mathematical expression. First, we need to check the input string with SQL select syntax. If we find out that the input string is not compiled with SQL select syntax, we need to undo all the previous parsing and then check the input string against the mathematical expression syntax. This algorithm is called backtracking.

Using Stack

One solution to implement a backtrack algorithm is to use a stack by pushing data into the stack while parsing the input string. When we cannot go further, we pop the data out of the stack and then process it against a new syntax. We will keep doing this until we find a matching syntax.

Let's begin by defining data to push into the stack

// parser_export.h
typedef struct lex_data {
    math_exp_type token_code;
    int len;
    char *text;
} lex_data;

// math_exp_enum.h
typedef enum math_exp_type {
    MATH_BRACKET_START,
    MATH_BRACKET_END,

    MATH_OPERATOR_START,
    MATH_LESS_THAN_EQ,
    MATH_LESS_THAN,
    MATH_GREATER_THAN,
    MATH_GREATER_THAN_EQ,
    MATH_EQ,
    MATH_NOT_EQ,
    MATH_AND,
    MATH_OR,
    MATH_MUL,
    MATH_PLUS,
    MATH_MINUS,
    MATH_DIV,
    MATH_SQRT,
    MATH_SQR,
    MATH_MAX,
    MATH_MIN,
    MATH_SIN,
    MATH_COS,
    MATH_POW,
    MATH_OPERATOR_END,

    MATH_COMMA,

    MATH_OPERAND_START,
    MATH_INTEGER_VALUE,
    MATH_DOUBLE_VALUE,
    MATH_IDENTIFIER,
    MATH_IDENTIFIER_IDENTIFIER,
    MATH_BOOL,
    MATH_OPERAND_END,

    MATH_WILDCARD_VALUE,
    MATH_STRING_VALUE,
    MATH_SPACE,

    MATH_INVALID,

    PARSER_EOL,
    PARSER_QUIT,

    MATH_EXP_TYPE_MAX,
} math_exp_type;

For stack implementation

// parser_export.h
...
#define STACK_CAP 512

typedef struct stack {
    int top;
    lex_data data[STACK_CAP];
} stack;

...

// parser.l
%{
#include "parser_export.h"
char lex_buffer[MAX_STR_SIZE];
char *curr_ptr = lex_buffer;
stack lex_stack = {.top = -1};


static void stack_push(lex_data v) {
    assert(lex_stack.top+1 < STACK_CAP);
    lex_stack.data[++lex_stack.top] = v;
}

static lex_data stack_pop() {
    assert(lex_stack.top > -1);
    return lex_stack.data[lex_stack.top--];
}

static int stack_size() {
    return lex_stack.top + 1;
}

static lex_data stack_peek() {
    assert(lex_stack.top > -1);
    return lex_stack.data[lex_stack.top];
}

void stack_reset() {
    lex_data d;

    while (stack_size() > 0) {
        d = stack_pop();
        free(d.text);
    }
    yy_scan_string(lex_buffer);
    curr_ptr = lex_buffer;
}

lex_data cyylex() {
    int token_code = yylex();
    lex_data d = {.token_code = (math_exp_type) token_code, .len = yyleng};
    d.text = (char*) malloc(yyleng+1);
    strncpy(d.text, yytext, yyleng+1);
    stack_push(d);
    curr_ptr += yyleng;
    return d;
}

void yyrewind(int n) {
    int i;

    while (n > 0 && lex_stack.top != -1) {
        i = lex_stack.top;
        free(lex_stack.data[i].text);
        lex_stack.data[i].text = NULL;
        if (lex_stack.data[i].token_code != MATH_SPACE) {
            n--;
        }
        curr_ptr -= lex_stack.data[lex_stack.top--].len;
    }
    yy_scan_string(curr_ptr);
}

void restore(int _chkp) {
    assert(_chkp <= lex_stack.top);
    lex_data *p;
    while (lex_stack.top > _chkp) {
        p = &lex_stack.data[lex_stack.top--];
        free(p->text);
        p->text = NULL;
        curr_ptr -= p->len;
    }
    yy_scan_string(curr_ptr);
}

static void process_white_space(int n) {
    lex_data d = {.token_code = MATH_SPACE, .len = n};
    stack_push(d);
    curr_ptr += n;
}

%}

Since we need to undo the parsing, we need to keep track of the head of the string so that when we undo, we can reset the lex by calling yy_scan_string and passing the beginning of the string to the function. That's why we need char *curr_ptr to keep track of the current position of the string.

The method of the stack is straightforward.

cyylex function is a wrapper of yylex.

yyrewind function is used to undo the parsing by providing the number of times to undo the cyylex call.

restore function is used to undo the parsing to the desired point (checkpoint).

process_white_space is used to push white space to the stack. Since we know what white space looks like, we do not need to store a space string.

Then we need to define a regular expression in parser.l file. Note that for white space, we want to ignore it, but we need to push it to the stack to use in the undo process, so that we know the length of the string we need to move backward.

...
%%
"(" {
    return MATH_BRACKET_START;
}

")" {
    return MATH_BRACKET_END;
}

...

[ ] {
    /* Ignore */
    process_white_space(1);
}

...

0|-?[1-9][0-9]* {
    return MATH_INTEGER_VALUE;
}

-?[0-9]*\.[0-9]+ {
    return MATH_DOUBLE_VALUE;
}

[a-zA-Z0-9_]+ {
    return MATH_IDENTIFIER;
}

...
%%

Usage of enhanced lexical parser

Let's test our lexical parser implementation by checking if the input string is in the format of a circular equation (pow(x,2) + pow(y,2) = c).

// parser_export.h
...
typedef enum parse_status {
    PARSE_ERROR,
    PARSE_SUCCESS,
} parse_status;
...

// equation.c
static parse_status circle_eql() {
    lex_data d;

    d = cyylex();
    if (d.token_code != MATH_POW) {
        yyrewind(1);
        return PARSE_ERROR;
    }
    d = cyylex();
    if (d.token_code != MATH_BRACKET_START) {
        yyrewind(2);
        return PARSE_ERROR;
    }
    d = cyylex();
    if (d.token_code != MATH_IDENTIFIER) {
        yyrewind(3);
        return PARSE_ERROR;
    }
    d = cyylex();
    if (d.token_code != MATH_COMMA) {
        yyrewind(4);
        return PARSE_ERROR;
    }
    d = cyylex();
    if (d.token_code != MATH_INTEGER_VALUE || strcmp("2", d.text) != 0) {
        yyrewind(5);
        return PARSE_ERROR;
    }
    d = cyylex();
    if (d.token_code != MATH_BRACKET_END) {
        yyrewind(6);
        return PARSE_ERROR;
    }
    d = cyylex();
    if (d.token_code != MATH_PLUS) {
        yyrewind(7);
        return PARSE_ERROR;
    }
    d = cyylex();
    if (d.token_code != MATH_POW) {
        yyrewind(8);
        return PARSE_ERROR;
    }
    d = cyylex();
    if (d.token_code != MATH_BRACKET_START) {
        yyrewind(9);
        return PARSE_ERROR;
    }
    d = cyylex();
    if (d.token_code != MATH_IDENTIFIER) {
        yyrewind(10);
        return PARSE_ERROR;
    }
    d = cyylex();
    if (d.token_code != MATH_COMMA) {
        yyrewind(11);
        return PARSE_ERROR;
    }
    d = cyylex();
    if (d.token_code != MATH_INTEGER_VALUE || strcmp("2", d.text) != 0) {
        yyrewind(12);
        return PARSE_ERROR;
    }
    d = cyylex();
    if (d.token_code != MATH_BRACKET_END)  {
        yyrewind(13);
        return PARSE_ERROR;
    }
    d = cyylex();
    if (d.token_code != MATH_EQ) {
        yyrewind(14);
        return PARSE_ERROR;
    }
    d = cyylex();
    if (d.token_code != MATH_INTEGER_VALUE) {
        yyrewind(15);
        return PARSE_ERROR;
    }
    return PARSE_SUCCESS;
}

As you can see, the usage of our lex parser is not convenient since we need to keep track of how many times we call cyylex and when the parsing fails, we need to undo by calling yyrewind before returning PARSE_ERROR. Let's make use of a macro.

// parser_export.h
...
#define PARSE_INIT \
    lex_data d; \
    int _chkp = lex_stack.top;

#define RETURN_PARSE_ERROR { \
    restore(_chkp); \
    return PARSE_ERROR; \
}

#define RESTORE_CHECK_POINT { \
    restore(_chkp); \
}

Now the usage can be simplified as follows

// equation.c
static parse_status circle_eql() {
    PARSE_INIT
    d = cyylex();
    if (d.token_code != MATH_POW)
        RETURN_PARSE_ERROR
    d = cyylex();
    if (d.token_code != MATH_BRACKET_START)
        RETURN_PARSE_ERROR
    d = cyylex();
    if (d.token_code != MATH_IDENTIFIER)
        RETURN_PARSE_ERROR
    d = cyylex();
    if (d.token_code != MATH_COMMA)
        RETURN_PARSE_ERROR
    d = cyylex();
    if (d.token_code != MATH_INTEGER_VALUE || strcmp("2", d.text) != 0)
        RETURN_PARSE_ERROR
    d = cyylex();
    if (d.token_code != MATH_BRACKET_END)
        RETURN_PARSE_ERROR
    d = cyylex();
    if (d.token_code != MATH_PLUS)
        RETURN_PARSE_ERROR
    d = cyylex();
    if (d.token_code != MATH_POW)
        RETURN_PARSE_ERROR
    d = cyylex();
    if (d.token_code != MATH_BRACKET_START)
        RETURN_PARSE_ERROR
    d = cyylex();
    if (d.token_code != MATH_IDENTIFIER)
        RETURN_PARSE_ERROR
    d = cyylex();
    if (d.token_code != MATH_COMMA)
        RETURN_PARSE_ERROR
    d = cyylex();
    if (d.token_code != MATH_INTEGER_VALUE || strcmp("2", d.text) != 0)
        RETURN_PARSE_ERROR
    d = cyylex();
    if (d.token_code != MATH_BRACKET_END)
        RETURN_PARSE_ERROR
    d = cyylex();
    if (d.token_code != MATH_EQ)
        RETURN_PARSE_ERROR
    d = cyylex();
    if (d.token_code != MATH_INTEGER_VALUE)
        RETURN_PARSE_ERROR
    return PARSE_SUCCESS;
}

Then you can test the implementation by writing a main function. ellips_eql is left for your exercise.

// equation.c
void parse_equation() {
    if (circle_eql() == PARSE_SUCCESS)
        printf("equation of circle\n");
    if (ellipse_eql() == PARSE_SUCCESS)
        printf("equation fo ellipse\n");
}

// parser.l
extern void parse_equation();

int main(void) {
    int token_code;

    while (1) {
        printf("input -> ");
        fgets(lex_buffer, sizeof(lex_buffer), stdin);
        stack_reset();
        parse_equation();
    }
    return 0;
}

The complete code can be found on my GitHub.

Implement a lexical parser

Sarun Tapee — Tue, 22 Jul 2025 02:23:26 +0000

To implement a lexical parser, we will use a tool called Fast Lexical Analyzer Generator (flex or lex) to perform pattern-matching on text.

You can install the tool using the following command

sudo apt update
sudo apt upgrade
sudo apt install flex

First, we need to create a file to feed to the lex program, and then it will generate a C language file. You can name the file any name you like. I will go with parser.l. The syntax of the file is as follows.

%{
  // section 1
%}

%%
  // section 2
%%

  // section 3 (optional)

Section 1 begins with %{ and ends with %}. In this section, you can write any C code.

Section 2 begins with %% and ends with %%. In this section, you will write a regular expression to match the string input.

Section 3 is optional. You can write a main function here if you want to create a program.

Example

Let's make our parser file to parse the input string and identify if the input is a string, integer, or double format.

%{

extern "C" int yylex();
#include <stdio.h>
#define MAX_STR_SIZE 512

char lex_buffer[MAX_STR_SIZE];

%}

%%

\n {
    return 0;
}

0|-?[1-9][0-9]* {
    return 1;
}

-?[0-9]*\.[0-9]+ {
    return 2;
}

[a-zA-Z0-9_]+ {
    return 3;
}

[ ] {
    // ignore space
}

. {
   // catch any character
   printf("ignore special character: %s\n", yytext);
}

%%

int main(void) {
    int code;

    while (1) {
        printf("input -> ");
        fgets(lex_buffer, sizeof(lex_buffer), stdin);
        yy_scan_string(lex_buffer);
        code = yylex();
        while (code != 0) {
            printf("code: %d, text: %s, len: %d\n", code, yytext, yyleng);
            code = yylex();
        }
    }
}

The API of the Lex tool is shown in the following table.

API	desc
Function
void yy_scan_string(char *buffer)	feed input string to lex
int yylex()	match a pattern that is defined as a regular expression in section 2 and return an integer value
Global Variable
yytext	points to the string that is just being processed by yylex()
yyleng	hold length of yytext

Code Explanation

In section 1, we have to declare the yylex() function due to an issue with the lex tool. Then define lex_buffer to hold a string input.

In section 2, we define a regular expression to tokenize the string input. The return type should be an integer or void if you want to ignore the matching string. In our code, we define 6 rules for the string matching since the body of code will be run when we call yylex function, we can put any logic in here (e.g., output the message in the last rule).

The rule that we define is very simple. Starting from a new line \n, which will identify the end of input if there are more characters following a new line, we just ignore it. The second rule is to match an integer. The third rule is to match doubles. The fourth rule is to match an identifier (e.g., "this_is_variable_1", "anotherVariable2"). The fifth rule is to ignore space so that we leave the body empty. And the last rule is to catch all the sequences that do not match the rules above it.

Lastly, in section 3, we implement the main function to loop forever to take an input from stdin and store it in the global variable lex_buffer. Then we call yy_scan_string to set the input string to lex parser. Finally, we keep calling yylex to process the lex_buffer until we find the new line character.

Compliation

Generate C source code by using the lex tool as follows.

lex parser.l

You will get a lex.yy.c file, then compile the source file to an executable.

g++ -o exe lex.yy.c -lfl

-lfl flag is used to link the lex library. If there is a compilation error, go fix your parser.l not lex.yy.c file

Then you can test our program.

./exe
input -> hello42 12 4.2&@ >_<
code: 3, text: hello42, len: 7
code: 1, text: 12, len: 2
code: 2, text: 4.2, len: 3
ignore special character: &
ignore special character: @
ignore special character: >
code: 3, text: _, len: 1
ignore special character: <
input ->

Matching Algorithm

It is good to know how the lex tool matches the input string. It will try to match as long as possible for each rule. If the string matches with more than one rule, the rule listed first will win.

Introduction

Sarun Tapee — Tue, 22 Jul 2025 02:22:53 +0000

In this series, I will walk through the implementation of a mathematical parser in C/C++ that I learned from Udemy course with an instructor, Abhishek. My completed code is in my GitHub. I do not get sponsorship from him, but I think his courses are very good for learning C/C++. I recommend checking out his courses, there are a lot of interesting projects.

Let's begin with the expectation of this project. By the end of this series, you will have your mathematical expression parser that parses an input string and evaluates the result, including inequality and logical expressions as demonstrated in the following picture.

How does it work

Try parsing the input string expression in the following order: logical, inequality, and math expression. If the parsing fails, try the next expression.
During parsing, create a lexical stack using a backtracking algorithm.
Convert a mathematical expression from infix form to postfix form, which does not need parentheses to reduce ambiguity of operator precedence.
Create a lexical tree from the postfix form.
Evaluate the result by traversing the tree in postorder.