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:
[sourcecode]
(a + b) * c
[/sourcecode]
The expression parser is something which takes this and converts it to an abstract syntax tree form. That may look something like this:
[sourcecode]
multiply
– add
– – a
– – b
– c
[/sourcecode]
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.
