Ever wondered how a interpreter works ? I wondered too.
The basic concept for a computer/how it translates basic human logic to machine level logic goes to Automata Theory of Computer Science by an well renowned English mathematician, computer scientist, logician, cryptanalyst, philosopher and theoretical biologist Alan Turing .
Learn more about Automata Theory here :
Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science with close connections to mathematical logic. The word automata comes from the Greek word αὐτόματος, which means "self-acting, self-willed, self-moving". An automaton is an abstract self-propelled computing device which follows a predetermined sequence of operations automatically. An automaton with a finite number of states is called a Finite Automaton (FA) or Finite-State Machine (FSM). The figure on the right illustrates a finite-state machine, which is a well-known type of automaton. This automaton consists of states and transitions. As the automaton sees a symbol of input, it makes a transition to another state, according to its transition function, which takes the previous state and current input symbol as its arguments.
What we are implementing toady ?
A stack based simple interpreter for beginners in C
Prerequisite :
- Well versed with C language.
- Implementation and working of Stack .
Let's start with implementing simple Addition interpreter in C
let's start with implementing :
What we need ? A set of predefined words which are reserved for the program to follow instructions given by the user.
What are these instructions? If you've ever written assembly code, you're likely familiar with them. Instructions are commands provided to a computer at a high level. Essentially, an instruction is a directive given to a computer's processor by a computer program. In this context, even though we're not directly interfacing with the computer's processor, we're achieving a similar effect through an interpreter implemented in C.
An enum in the C language is a keyword used to define a data type that consists of a set of named integral constants. These constants are typically used to represent related values or options in a more readable and expressive manner within a program.
Why use enums? To simply reserve specific words or values for use as keywords.
These are the keywords we will be reserving :
typedef enum {
LOAD_CONSTANT, //Tell machine to load value
ADD, //Instruct machine to add
PRINT, //Print the Stack-Top
HALT, //Exit the program
} OpCode;
And a stack too, we limited static stack to 100 but can dynamic using stack using linked list.
#define STACK_SIZE 100
double stack[STACK_SIZE];
int stackTop = 0;
We will be predefining the values to add to keep it simple:
// Constants for the bytecode program
double constants[] = {
10.0,
20.0,
};
PUSH AND POP for the Stack
// Function to push a value onto the stack
void push(double value) {
if (stackTop < STACK_SIZE) {
stack[stackTop++] = value;
} else {
printf("Stack overflow!\n");
}
}
// Function to pop a value from the stack
double pop() {
if (stackTop > 0) {
return stack[--stackTop];
} else {
printf("Stack underflow!\n");
return 0.0;
}
}
Lets start with the logic of this program
int ip = 0; // Instruction pointer
int main() {
while (1) {
OpCode instruction = bytecode[ip++];
switch (instruction) {
case LOAD_CONSTANT: {
int constantIndex = bytecode[ip++];
double constantValue = constants[constantIndex];
push(constantValue);
break;
}
case ADD: {
double b = pop();
double a = pop();
double result = a + b;
push(result);
break;
}
case PRINT: {
double value = pop();
printf("Result: %lf\n", value);
break;
}
case HALT: {
return 0; // Exit the program
}
}
}
return 0;
}
Explanation :
While Loop (while (1) { ... }):
- Imagine this loop as a never-ending cycle, like a carousel that keeps spinning.
- Inside this loop, our program will keep doing things repeatedly. Fetching Instructions (OpCode instruction = bytecode[ip++];):
Fetching Instructions (OpCode instruction = bytecode[ip++];):
- OpCode instruction is like a note that tells us what to do next.
- bytecode[ip++] is like turning the page in the recipe book to get the next step.
Switch Statement (switch (instruction) { ... }):
- We look at the instruction and decide which action to take.
LOAD_CONSTANT:
- This is like a step that tells us to remember a number, say, 10. int constantIndex is like remembering the page number where we found 10.
- double constantValue is like writing down the number 10 on a piece of paper.
- push(constantValue) is like putting that piece of paper in our pocket.
ADD:
- It's like a step that says, "Take two numbers and add them." double b = pop(); is like taking two pieces of paper with numbers written on them.
- double a = pop(); is like reading the numbers from those papers.
- double result = a + b; is like adding those numbers together and getting a new number.
- push(result) is like putting the new number on a new piece of paper and keeping it.
PRINT:
- It's like a step that says, "Tell me what number you have." double value = pop(); is like taking out the piece of paper with a number.
- printf("Result: %lf\n", value); is like showing that number to someone.
HALT:
- It's like the last step in the book that says, "We're done reading."
- return 0; is like leaving closing the book.
*Let's have a sample program : *
// The bytecode program
unsigned char bytecode[] = {
LOAD_CONSTANT, 0, // Load constant 10
LOAD_CONSTANT, 1, // Load constant 20
ADD, // Add the top two values on the stack
PRINT, // Print the result
HALT, // Halt the interpreter
};
// Constants for the bytecode program
double constants[] = {
10.0,
20.0,
};
Working of above code:
Start
---->
LOAD_CONSTANT (Load 10)
---->
LOAD_CONSTANT (Load 20)
---->
ADD (Add 10 and 20)
---->
PRINT (Print the result)
---->
HALT (Stop the interpreter)
---->
End
This is very simple interpreter, advanced ones use statements like jumps, loops, etc and advance concepts of Turing Machines ,which are different and can do even more than Stack based interpreters
As a beginner you can try to implement statements like :
- Jump
- Subtract
- Other mathematical operations
- Brainstorm more ideas ............
You can use this interpreter here, fork to experiment more :
Code is available here : Github
Thank you so much for reading.
Follow and Like for more .
- You can also follow me on LinkedIn, I think building connections is better
Top comments (0)