Making Languages

Part 4: Abstract Syntax Tree

← Back | Forward →

An Abstract Syntax Tree is a hierarchical structure (like a Parse Tree). It represents all the operations or constructs as objects in the language of the compiler. The difference is subtle but important:

$parseTree = [
['assign', [
['number', '1'],
['number', '2']
]]
];

$abstractSyntaxTree = [
new Assign(new Number(1), new Number(2))
];

An Abstract Syntax tree allows individual constructs to handle their own processing. That’s what we’re going to use it for…

Creating Abstract Syntax Trees

Before we can change a Parse Tree into an Abstract Syntax Tree; we need special classes for numbers and addition:

class Number
{
/**
* @var int
*/
protected $value;

/**
* @param int $value
*
* @return Number
*/
public function __construct($value)
{
$this->value = $value;
}
}
This is from Number.php
class Addition
{
/**
* @var Addition|Number
*/
protected $left;

/**
* @var Addition|Number
*/
protected $right;

/**
* @param Addition|Number $left
* @param Addition|Number $right
*
* @return Addition
*/
public function __construct($left, $right)
{
$this->left = $left;
$this->right = $right;
}
}
This is from Addition.php
$addition = new Addition(
new Addition(
new Number(1), new Number(2)
),
new Number(3)
);

We also need to add a Parser method for converting individual arrays into nodes:

/**
* @param array $node
*
* @return Addition|Number
*/
protected function parseNode(array $node)
{
if ($node[0] == 'addition') {
return new Addition(
$this->parseNode($node[1][0]),
$this->parseNode($node[1][1])
);
}

if ($node[0] == 'number') {
return new Number($node[1]);
}
}
This is from Parser.php

It’s possible to nest Addition operations within Addition operations. In that case, we need to recursively parse arrays until we get a Number in $left and $right. We can also add a method for converting the whole Parse Tree:

/**
* @param array $parse
*
* @return array
*/
public function parse(array $parse = [])
{
$nodes = [];

foreach ($parse as $i => $item) {
$parsed = $this->parseNode($item);

if ($parsed) {
array_push($nodes, $parsed);
unset($parse[$i]);
}
}

return [$nodes, $parse];
}
This is from Parser.php

We match each node, remove it from the Parse Tree and add it to the Abstract Syntax Tree. We can use it like this:

$parse = [
['addition', [
['addition', [
['number', 1],
['number', 2]
]],
['number', 3]
]]
];

$parser = new Parser();
$parser->parse($parse); // [[Addition Object => ...

← Back | Forward →

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.