Tuesday, September 20, 2011

ELENA Virtual Machine Script: BF interpreter

In the previous post I showed some basic things about the terminal script. After several changes the current system of commands looks like this:

  • -q - quit
  • -h - help
  • -ton - trace mode is on
  • -toff - trace mode is off
  • -l[path] - load a script from file
  • -n[path] - load an inline script from file
  • -c[path] - load DSA script from file
  • -i[inline script] - execute inline script\n"
  • -g[dsa rule] - define dsa rule; they should be separated by a semicolon except the last rule\n"
  • -pX - select parse mode (0 - standard, 1 - simple)

Note that there are two parse modes: standard and simple. Presume we have to parse the following expression: "23 * 4". In Standard mode it will be parsed as three terminal symbols: "23", "*" and "4". But in simple mode every character will be a separate terminal symbol. This mode will be used in our BF interpreter.

Despite I called it interpreter it is actually just-in-time compiler. The script tape generated by ELENA Script Engine is translated into byte-codes and executed like "normal" code.

The DSA script looks like this:

statement  ::= next;
statement  ::= next;
statement  ::= prev;
statement  ::= inc;
statement  ::= dec;
statement  ::= out;
statement  ::= in;
statement  ::= "[" while;
statement  ::= idle;

next       ::= ">";
prev       ::= "<";
inc        ::= "+";
dec        ::= "-";
out        ::= ".";
in         ::= ",";
idle       ::= $any;

while      ::= statement while_r;

while_r    ::= "]";
while_r    ::= statement while_r;

tape       ::= statement statements;

statements ::= statement statements;
statements ::= $eps;

start      ::= tape;

tape       =>  &union
                  &group 1024 += &std'dictionary'count += *=
                  &group { 0 std'basic'widecharvar } += &std'basic'factories'onnew += *=
               std'basic'factories'newinitializedarray 0 ^refer $body;
next       => 1 &std'dictionary'index ^^append $body;
prev       => 1 &std'dictionary'index ^^reduce $body;
inc        => 1 ^append $body;
dec        => 1 ^reduce $body;
out        => &nil 'program'output &previous ^write . $body;
in         => &nil 'program'input &nil ^get ^write $body;

while      => &group
                &previous +=
                &std'patterns'ewhilenotzero +=
                { $body } ^run .;

As you may already know the script consists of two type of rules: grammar and DSA ones. Grammar rules allow us to generate a derivation tree and DSA ones are used to build the code (list of VM instructions, so-called a script tape) based on that tree. DSA rule is applied for the grammar one with the same name.

I think grammar rules are quite simple so we begin with DSA ones. The first rule which is invoked right after the start is tape. In this rule we create an array of widechar objects.

tape       =>  &union
                  &group 1024 += &std'dictionary'count += *=
                  &group { 0 std'basic'widecharvar } += &std'basic'factories'onnew += *=
               std'basic'factories'newinitializedarray 0 ^refer $body;

The equivalent ELENA code will look like this:

std'basic'factories'newinitializedarray::&count:1024 
&onnew: (=> std'basic'widecharvar::0) @ 0

Note that { 0 std'basic'widecharvar } is an action symbol (compare with => std'basic'widecharvar::0 in ELENA code). To pass several parameters to newinitializedarray we use a union of group objects.

&group 1024 += &std'dictionary'count += *=

is in fact equivalent to

{ count = 1024. }

where std'dictionary'count is a subject symbol, &group is an instance of the $elean'group class and command += adds the object to the group.

To understand how it works I will remind about subject symbols. Every time a new subject is declared the appropriate subject class is auto-generated as well. This class contains "subject'get" method returning self variable. A union is a week group type. It means that self variable points to the group member rather than to the group itself. So the following expression

#union(#group(std'dictionary'count,1024),#group(std'basic'factories'onnew,...)) std'dictionary'count

will return a count group. As a result this union of groups is equvivalent to

{ std'dictionary'count = 1024. std'basic'factories'onnew = ... }

Other rules are quite simple. For example rule next:

next       => 1 &std'dictionary'index ^^append $body;

is similar to

... index'append:1

Note that &std'dictionary'index is a subject symbol used as multiple dispatcher: ^^ is equivalent to &: operator.

And finally let's consider the simple echo program:

-p1
,[.,]

It will be translated into the following inline code:

@new $elena'$union
@new $elena'$group
@push 1024
@group-add
@push std'dictionary'count
@group-add
@union-add
@new $elena'$group
@sub
  @push 0
  @call std'basic'widecharvar
@end
@group-add
@push std'basic'factories'onnew
@group-add
@union-add
@call std'basic'factories'newinitializedarray
@push 0
@send refer
@push $elena'$nil
@call 'program'input
@push $elena'$nil
@send get
@send write
@new $elena'$group
@copy 1
@group-add
@push std'patterns'ewhilenotzero
@group-add
@sub
  @push $elena'$nil
  @call 'program'output
  @copy 1
  @send write
  @pop
  @push $elena'$nil
  @call 'program'input
  @push $elena'$nil
  @send get
  @send write
@end
@send run
@pop

No comments:

Post a Comment