Parrot Virtual Machine/Building A Compiler

HLL Compilers

Now that we know NQP and PGE, we have the tools that we need to start writing a compiler for our favorite language. Let's review the steps to creating a compiler:

1. Write Grammar using PGE
2. Write Actions using NQP
3. Actions create PAST tree
4. PCT converts PAST into PIR
5. Parrot converts PIR into bytecode.

After step 5, if we have done everything correctly, we should have a working compiler. Of course, there is a lot of work to do before we reach step 5. Lucky for us, however, steps 4 and 5 are automated by the build process, so we only need to worry about 1, 2, and 3. In the Tutorials section we are going to have several language-building tutorials that you can follow.

Creating a PAST Tree

PAST nodes are objects that your NQP Action methods must create. PCT automatically inserts these nodes into the tree once you create them. PAST nodes are complex objects with an array and a hash component. The array stores a list of references to the children nodes, and the hash stores information about the node itself. Creating the past tree means that we create nodes in lower-rules, and insert them into the array for higher rules. As we go, we set the necessary options for each rule, so that PCT can generate the appropriate code.

There is a reference for the various types of PAST nodes available in the appendix.

PAST::Node is the base class from which the other PAST node types are derived. The other types are PAST::Stmts, PAST::Val, PAST::Var, PAST::Op, and PAST::Block.

PAST::Op

PAST::Op nodes are operations that need to be performed.

PAST::Val

PAST::VAL nodes are constant values like integers or strings

PAST::Var

PAST::Var nodes are variables

PAST::Block

PAST::Block nodes are used for lexically scoping variables and defining subroutines. They keep other nodes together.

PAST::Stmts

PAST::Stmts nodes are just groups of other nodes, and perform no task besides basic organization.

Once you have created the necessary node, you insert it into the parse tree with the keyword make.

The Match Object

The Match object is a special object that contains a hash. The match object hash contains information about the matched rule. Each element in the hash is named after one of the sub-rules in the rule. For instance, if we have the following rule:

rule sentence { 
  <adjective> <noun> <adverb> <verb>
}

Then the match rule would have entries "adjective", "noun", "adverb", and "verb". The value of the hash for each of these keys are the values that were returned from the subrules using the make command, if any. So, we would have the following fields:

$<adjective>
$<noun>
$<adverb>
$<verb>

We would then use the values of each of these to produce and make a node for the sentence rule. If each of these fields return PAST nodes of their own, we should push those

Examples

We are going to show some very small examples here to demonstrate the basic compiler construction method. More advanced tutorials are provided in the Tutorials section.

Example: Basic Calculator

Problem

We want to create a basic calculator program that can perform addition and subtraction on integers. The calculator should print the result to the screen.

Solution

We start by running mk_language_shell.pl to create a basic language framework. This also produces a builtin function called say. We are going to use the say function to print results to the screen. We are going to use a basic top-down parser for this, we are not going to use an optable.

We create a basic grammar for our calculator:

rule TOP {
  <expression>
  {*}
}

rule expression {
  <term> <operation> <term>
  {*}
}

token operation { '+' | '-' }

token term { \d+ }

We now need to create two actions, one for TOP and the other for expression. The TOP method should take the value of the parsed expression and pass that to the say function. The expression function should generate the necessary PIR operations, and insert the term values into these operations. Here is a basic actions file to do this:

method TOP($/) {
  my $past := PAST::Op.new(:pasttype('inline'));
  my $expr := $( $<expression> );
  $past.inline('say(%0)');
  $past.unshift($expr);
  make $past;
}

method expression($/) {
  my $left := $( $<term>[0] );
  my $right := $( $<term>[1] );
  my $op := $( $<operation> );
  my $pirop := "sub_n";
  if $op eq "+" {
    my $pirop := "add_n";
  }
  my $past := PAST::Op.new(:pasttype('pirop'), :pirop($pirop));
  $past.unshift($left);
  $past.unshift($right);
  make $past;
}