Dirty Approach To Write An Interpreter in C Part-A

Introduction

As of writing this article I was just completed some of hardcore CS theories as part of my academic courses. I was in pressure of mostly two courses,  Theory of Computation and Compiler design. While learning theories it was tough for me to try those theories on keyboard. I was very curious to learn that stuffs throw real programming.

At last those courses was ended and I got time to breathe. I had some time myself to think about those theories and try them out throw programming. But as soon as I start it was very tough for me to convert those weird maths and logics in reality. So I started search in internet. I found some great articles. I learned from that. But still I found this area is not much talked outside research papers. And if talked targeted audience was not a beginner.

So as the title says I will share my approach to write an interpreter in C and it might be helpful for people like me who want to see things in action.
Oboni

I thought I should give a name to my language. So I am calling it Oboni. A Oboni program will look like following-

var x

= x 1

when(< x 100){

    show x

    = x (+ x 1)

}

So what we have here?

• Keywords – var, when, if, show
• Assignment – =
• When construct (While construct)
• Conditional Operators
• Arithmetic Operators

Also you might notice that I tried to implement Polish prefix notation for equations or statements. Just to avoid most of the operator precedence. I dont want to do something very complicated. Because these is a huge subject. I want to start small. Later I will try to add new features if possible. Like in my to-do list I have plan to add support for functions. Then that “show” will not be a keyword anymore.

Grammar for Oboni

Oopss! this is the part where mind starts bending. But if I understand correctly it is far simpler that it looks at first glance. Oboni syntax, As I mentioned earlier there need to be a way to understand from a machine’s perspective. And here the grammar comes in.

A BNF grammar example from wikipedia

<postal-address> ::= <name-part> <street-address> <zip-part>

It simply means that a

<postal-address>

<name-part>

<street-address>

<zip-part>

For Oboni I needed to describe what an expression is. What a assignment consist of. I needed to answer those sort of questions. So my answer is written in form of a grammar.

<expression> ::= <statement> <expression_prime>
                | <control-flow> <expression_prime>
                | end-of-file
 
<expression_prime> ::= <statement> ‘\n’ <expression>
                      | <control-flow> ‘\n’ <expression>
                      | ‘\n’

<statement> ::= var identifier
              | ‘=’ identifier <term>
              | show <term>

<control-flow> ::= if ‘(’ <evaluation> ‘)’ <block>
                 | when ‘(’ <evaluation> ‘)’ <block>

<block> ::= ‘{’ <expression_prime> ‘}’ <expression_prime>

<term> ::= identifier
         | number
         | string
         | ‘(’ <evaluation> ‘)’ 

<evaluation> ::= operator <term> <term>

Thats some dirty grammar. Yeah it is. But not bad to start exploring. So while coding the interpreter I have to try my best to stick to this grammar. Otherwise I can get lost out there.

Steps of Interpreter

Lets define some dirty steps. An interpreter can have many phases. But I am going to stick to three.

Lexer -> Parser -> Interpret

In a full stack interpreter there can be many steps. Like optimizations. But I wanted to keep things under my ability. I don’t wanted to leave this project in middle when it gets too complicated with lots of plan.

The post Dirty Approach To Write An Interpreter in C Part-A appeared first on Shimul Chowdhury.