Skip to content

Instantly share code, notes, and snippets.

@chrisguitarguy
Last active July 27, 2018 15:21
Show Gist options
  • Save chrisguitarguy/f04d07dd16289021579e1707e161fa0e to your computer and use it in GitHub Desktop.
Save chrisguitarguy/f04d07dd16289021579e1707e161fa0e to your computer and use it in GitHub Desktop.
#!/usr/bin/env php
<?php
class Token
{
const T_OPEN_PAREN = 1;
const T_CLOSE_PAREN = 2;
const T_IF = 3;
const T_EQ = 4;
const T_PLUS = 5;
const T_MINUS = 6;
const T_INT = 7;
const T_EOF = 8;
private $type;
private $value;
public function __construct(int $type, $value=null)
{
$this->type = $type;
$this->value = $value;
}
public static function parse(string $raw)
{
switch ($raw) {
case '(';
return new self(self::T_OPEN_PAREN);
case ')':
return new self(self::T_CLOSE_PAREN);
case 'if':
return new self(self::T_IF);
case '=':
return new self(self::T_EQ);
case '+':
return new self(self::T_PLUS);
case '-':
return new self(self::T_MINUS);
}
if (!is_numeric($raw)) {
throw new \RuntimeException(sprintf('Could not parse: "%s"', $raw));
}
return new self(self::T_INT, intval($raw));
}
public function type() : int
{
return $this->type;
}
public function value()
{
return $this->value;
}
}
class TokenStream implements \Iterator
{
private $tokens;
private $position;
public function __construct(array $tokens)
{
$this->tokens = array_values($tokens);
$this->position = 0;
}
public function current()
{
return $this->tokens[$this->position];
}
public function key()
{
return $this->position;
}
public function valid()
{
return isset($this->tokens[$this->position]);
}
public function next()
{
++$this->position;
}
public function rewind()
{
$this->position = 0;
}
public function is(int $type) : bool
{
return $this->current()->type() === $type;
}
public function expect(int ...$types) : bool
{
if (!$this->valid()) {
throw new \RuntimeException(sprintf(
'TokenStream is not in a valid state: %d',
$this->position
));
}
$curType = $this->current()->type();
foreach ($types as $type) {
if ($curType === $type) {
return true;
}
}
throw new \RuntimeException(sprintf(
'Expected a token type of %d, got %d',
implode(' or ', $types),
$curType
));
}
}
abstract class Node
{
abstract public function evaluate();
}
abstract class ListNode extends Node
{
protected $children = [];
public function add(Node $child) : void
{
$this->children[] = $child;
}
}
class If_ extends ListNode
{
public function evaluate()
{
if (count($this->children) !== 3) {
throw new \RuntimeException(sprintf(
'(if ...) constructs expect exactly three children, got %d',
count($this->children)
));
}
return $this->children[0]->evaluate() ? $this->children[1]->evaluate() : $this->children[2]->evaluate();
}
}
class Eq extends ListNode
{
public function evaluate() : bool
{
$values = array_map(function (Node $node) {
return $node->evaluate();
}, $this->children);
return count(array_unique($values)) === 1;
}
}
class Plus extends ListNode
{
public function evaluate()
{
$value = 0;
foreach ($this->children as $child) {
$value += $child->evaluate();
}
return $value;
}
}
class Minus extends ListNode
{
public function evaluate()
{
if (!$this->children) {
return 0;
}
$value = $this->children[0]->evaluate();
foreach (array_slice($this->children, 1) as $child) {
$value -= $child->evaluate();
}
return $value;
}
}
class Int_ extends Node
{
private $value;
public function __construct(int $value)
{
$this->value = $value;
}
public function evaluate() : int
{
return $this->value;
}
}
class Program extends ListNode
{
public function evaluate()
{
$value = null;
foreach ($this->children as $child) {
$value = $child->evaluate();
}
return $value;
}
}
function lex(string $input) : TokenStream
{
$tokens = array_map(function (string $part) {
return Token::parse(trim($part));
}, array_filter(explode(' ', str_replace(
['(', ')'],
[' ( ', ' ) '],
$input
)), function ($val) {
return '' !== trim($val);
}));
$tokens[] = new Token(Token::T_EOF);
return new TokenStream($tokens);
}
function parse(TokenStream $stream) : Program
{
$program = new Program();
$stream->rewind();
while (null !== $node = doParse($stream)) {
$program->add($node);
}
return $program;
}
function doParse(TokenStream $stream) : ?Node
{
switch ($stream->current()->type()) {
case Token::T_OPEN_PAREN:
return parseList($stream);
case Token::T_INT:
$node = new Int_($stream->current()->value());
$stream->next();
return $node;
case Token::T_EOF:
$stream->next();
return null;
default:
throw new \RuntimeException('Unexpected token: %d', $stream->current()->type());
}
}
function parseList(TokenStream $stream) : ListNode
{
// make sure we have an open paren and discard it
$stream->expect(Token::T_OPEN_PAREN);
$stream->next();
switch ($stream->current()->type()) {
case Token::T_IF:
$target = new If_();
break;
case Token::T_EQ:
$target = new Eq();
break;
case Token::T_PLUS:
$target = new Plus();
break;
case Token::T_MINUS:
$target = new Minus();
break;
default:
throw new \RuntimeException(sprintf('Unexpected token: %d', $stream->current()->type()));
}
$stream->next(); // discard the target token
while (!$stream->is(Token::T_CLOSE_PAREN)) {
$target->add(doParse($stream));
}
// expect and discare a closing paren
$stream->expect(Token::T_CLOSE_PAREN);
$stream->next();
return $target;
}
function printError(string $msg)
{
fprintf(STDERR, $msg.PHP_EOL);
}
function main(array $argv)
{
if (!isset($argv[1])) {
printError(sprintf('Usage: %s {inputFile}', $argv[0]));
exit(1);
}
if (!file_exists($argv[1]) || !is_readable($argv[1])) {
printError(sprintf('%s does not exist or is not readable', $argv[1]));
exit(1);
}
ini_set('xdebug.max_nesting_level', 5000);
$input = trim(file_get_contents($argv[1]));
echo parse(lex($input))->evaluate(), PHP_EOL;
}
main($argv);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment