In my previous post, I described “blang”, the beginnings of a BASIC interpreter with access to its VM. I presented jumps and some stack operations.
Let’s build it up a little, so that we can do addition and subtraction. We want to print arithmetic expressions. Let’s write a little program, expr.bas, as an example:
push 30+10+2 # expect 42 call print push 30 + 40 -5 - 7 + 100 # expect 158 call print halt
Here are the changes in the grammar:
rule push { 'push' <expr> }
rule expr { <expr-p> ( <add-sub> <expr-p> { add-sub $<add-sub>;} )* }
token add-sub { '+' | '-' }
rule expr-p { <int> { bpush Push, $<int>.Int; }}
There’s an auxiliary sub so as to keep the grammar more compact-looking:
sub add-sub($op) { if $op eq '+' { bpush0 Add; } else { bpush0 Sub; } }
There might be better ways of doing it, but I don’t know how. Suggestions are welcome.
Now, Raku does have an interspersing operator, like so:
rule expr { <expr-p> % ('+'|'-) }
but I don’t think it is useful for us. We need to ensure that the correct Add and Sub instructions are put in the right place. I couldn’t figure out how to do it with this operator, so I resorted to a longer, but correct, expression.
Here’s a disassembly of the Basic program:
0 Push 30 1 Push 10 2 Add 0 3 Push 2 4 Add 0 5 Call print 6 Push 30 7 Push 40 8 Add 0 9 Push 5 10 Sub 0 11 Push 7 12 Sub 0 13 Push 100 14 Add 0 15 Call print 16 Halt 0
Looks good to me.
Now that’s out of the way, my next step is to implement multiplication, division, bracketing, and unary minus, all with the correct operator precedence, of course.
My aim throughout is to avoid the use of a separate action class. I think this will make the code shorter, and eliminate the need to actually walk the syntax tree. To do that, I need to emit the VM bytecodes in the right order.
In my spreadsheet project, neoleo, I store a cell’s formula as a syntax tree. However, I’m now thinking that a bytecode implementation may be better, and eliminate the need for walking the tree as part of the syntax analysis phase.
I think it has implications for the way that interpreters can be constructed. No need for syntax trees, just produce the bytecodes as a stream. Maybe.
Now, you may think that I’ll come unstuck when I try to implement block-oriented structures like if/thens or loops. But I have a cunning plan.
The adventure continues.
Update 1 (01-Nov-2020):
Added a PRINT statement. You can now print constant strings:
print “hello world”
or expressions:
print 40+2
An ability to print strings is highly useful, as you can print out what you expect to happen.
Pingback: 2020.44 Comma Comma – Rakudo Weekly News
Pingback: #rakulang blang: implementing if statement | Mark Carter's blog
hi @mark – I have had great success with Action classes with my Grammars – suggest you take another look when you have a chance…