Leaf

Cloverleaf: Start with an expression parser

I thought a good way to start Cloverleaf would be to write a simple expression parser. In a language expressions are those collection of symbols which result in a particular value. This is in contrast to a full statement which may include an assignment, a declaration, or something else. For example, the below is an expression:

(a + b) * c

The expression parser is something which takes this and converts it to an abstract syntax tree form. That may look something like this:

multiply
- add
- - a
- - b
- c

Revision 34 of the code has a basic functioning expression parser. Refer to the <src/lang/expr_test.cpp> code for the tests.

Precedence and Associativity

The two major hurdles an expression parser has to overcome are precedence and associativity. Math has some basic rules about this and most programmers expect them to be followed in the code. These rules are also extended, starting with C, to support additional programming constructs. Languages like Lisp and Smalltalk don’t have such rules, which in my opinion makes them very unnatural and bulky.

By example, precedence is what in the below says the multiplication happens before the addition:

a + b * c

This is interpreted as:

a + (b * c)

Associativity is either left or right and is essentially what happens when multiple operators have the same precedence. It takes an expression like this:

a + b + c

And interprets it as:

(a + b) + c

Whereas exponents are right-associative:

a ^ b ^ c

Is calculated as:

a ^ (b ^ c)

Using just these two basic rules of precedence and associativity you can parse generally any expression. I did this in my code using a simple two stack system, where values get pushed to one, and operators to the other. This is basically how the Shunting yard algorithm works but I adapted it to directly produce trees instead of RPN.

Tuples

I want the language to make heavy use of tuples. This is something that has been introduced to C++ and exists natively in a lot of other languages now. In Cloverleaf these will be native constructs and used everywhere it makes sense.

For example, we might want to concatenate two tuples together. I’m not positive on the exact syntax, but the semantics should be supported. Currently the parser understands this:

{1,2,c} ++ {3,5}

Which would result in the tuple:

{1,2,c,3,5}

Any value in a tuple is again a full expression, thus tuples may reside inside tuples:

{ { 1, 2,3 }, 1, {} }

Note that an empty tuple is supported. It just seems natural, and is required for how I do functions.

Functions

The basic C function call syntax will be supported. I find this to be a very natural way to call a function, and is also the syntax used in mathematics. For example:

sin(x)

This is the sine of the value x, where x is said to be a parameter to the function.

Now, parameters are really nothing more than a tuple with a slightly different syntax. I wish to formalize this relationship. The above is then seen as calling the “sin” function with the tuple “{x}”. In Cloverleaf syntax I’m using the “<-” operator to mean this:

sin <- { x }

This code and the previous mean the exact same thing in Cloverleaf. This second form however provides a feature which is often sot when using tuples. You can now call functions using a tuple variable rather than an explicit parameter list. For example, this will be possible:

params = { x }
sin <- params

Next

I will continue to work on this expression parser for a while. I want to experiment with how much syntax I can easily support before moving on to doing some kind of statements or execution.

3 replies »

    • This is a good observation. It is on the list of things I have to write about “Why am I donig my own parser generator?” In brief, I’ve used a few before, and I always end up spending too much time fighting with the tool. Worse, the languages I was parsing always end up limited to what the tool provides — thus not the syntax I actually desired.

    • I actually had the same experience when I developed an interpreter for a very simple DSL. It too took my hours to fix my grammar, so that ANTLR was able to parse it correctly. But my attempt to build a language parser from scratch in php failed before. I hope that you’ll have more success with your parser and that I’m able to learn from your code.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s