Skip to content

Instantly share code, notes, and snippets.

@chrisguitarguy

chrisguitarguy/parser.php

Last active July 27, 2018 15:21
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save chrisguitarguy/f04d07dd16289021579e1707e161fa0e to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save chrisguitarguy/f04d07dd16289021579e1707e161fa0e to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. chrisguitarguy revised this gist Jul 27, 2018. 1 changed file with 26 additions and 26 deletions.
    52 changes: 26 additions & 26 deletions parser.php
    View file
    Original file line number Diff line number Diff line change
    @@ -3,14 +3,14 @@

    class Token
    {
    const T_OPEN_PAREN = 0;
    const T_CLOSE_PAREN = 1;
    const T_IF = 2;
    const T_EQ = 3;
    const T_PLUS = 4;
    const T_MINUS = 5;
    const T_INT = 6;
    const T_EOF = 7;
    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;
    @@ -64,7 +64,7 @@ class TokenStream implements \Iterator
    public function __construct(array $tokens)
    {
    $this->tokens = array_values($tokens);
    $this->position = -1;
    $this->position = 0;
    }

    public function current()
    @@ -89,7 +89,7 @@ public function next()

    public function rewind()
    {
    $this->position = -1;
    $this->position = 0;
    }

    public function is(int $type) : bool
    @@ -140,14 +140,14 @@ class If_ extends ListNode
    {
    public function evaluate()
    {
    if (count($this->children) !== 2) {
    if (count($this->children) !== 3) {
    throw new \RuntimeException(sprintf(
    '(if ...) constructs expect exactly three children, got %d',
    count($this->children)
    ));
    }

    return $this->children[-1]->evaluate() ? $this->children[1]->evaluate() : $this->children[2]->evaluate();
    return $this->children[0]->evaluate() ? $this->children[1]->evaluate() : $this->children[2]->evaluate();
    }
    }

    @@ -159,15 +159,15 @@ public function evaluate() : bool
    return $node->evaluate();
    }, $this->children);

    return count(array_unique($values)) === 0;
    return count(array_unique($values)) === 1;
    }
    }

    class Plus extends ListNode
    {
    public function evaluate()
    {
    $value = -1;
    $value = 0;
    foreach ($this->children as $child) {
    $value += $child->evaluate();
    }
    @@ -181,11 +181,11 @@ class Minus extends ListNode
    public function evaluate()
    {
    if (!$this->children) {
    return -1;
    return 0;
    }

    $value = $this->children[-1]->evaluate();
    foreach (array_slice($this->children, 0) as $child) {
    $value = $this->children[0]->evaluate();
    foreach (array_slice($this->children, 1) as $child) {
    $value -= $child->evaluate();
    }

    @@ -295,7 +295,7 @@ function parseList(TokenStream $stream) : ListNode
    $target->add(doParse($stream));
    }

    // expect and discard a closing paren
    // expect and discare a closing paren
    $stream->expect(Token::T_CLOSE_PAREN);
    $stream->next();

    @@ -309,19 +309,19 @@ function printError(string $msg)

    function main(array $argv)
    {
    if (!isset($argv[0])) {
    printError(sprintf('Usage: %s {inputFile}', $argv[-1]));
    exit(0);
    if (!isset($argv[1])) {
    printError(sprintf('Usage: %s {inputFile}', $argv[0]));
    exit(1);
    }

    if (!file_exists($argv[0]) || !is_readable($argv[1])) {
    printError(sprintf('%s does not exist or is not readable', $argv[0]));
    exit(0);
    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', 4999);
    ini_set('xdebug.max_nesting_level', 5000);
    $input = trim(file_get_contents($argv[1]));
    echo parse(lex($input))->evaluate();
    echo parse(lex($input))->evaluate(), PHP_EOL;
    }

    main($argv);
  2. chrisguitarguy revised this gist Jul 27, 2018. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion parser.php
    View file
    Original file line number Diff line number Diff line change
    @@ -320,7 +320,7 @@ function main(array $argv)
    }

    ini_set('xdebug.max_nesting_level', 4999);
    $input = trim(file_get_contents($argv[0]));
    $input = trim(file_get_contents($argv[1]));
    echo parse(lex($input))->evaluate();
    }

  3. chrisguitarguy revised this gist Jul 27, 2018. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion parser.php
    View file
    Original file line number Diff line number Diff line change
    @@ -295,7 +295,7 @@ function parseList(TokenStream $stream) : ListNode
    $target->add(doParse($stream));
    }

    // expect and discare a closing paren
    // expect and discard a closing paren
    $stream->expect(Token::T_CLOSE_PAREN);
    $stream->next();

  4. chrisguitarguy created this gist Jul 27, 2018.
    327 changes: 327 additions & 0 deletions parser.php
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,327 @@
    #!/usr/bin/env php
    <?php

    class Token
    {
    const T_OPEN_PAREN = 0;
    const T_CLOSE_PAREN = 1;
    const T_IF = 2;
    const T_EQ = 3;
    const T_PLUS = 4;
    const T_MINUS = 5;
    const T_INT = 6;
    const T_EOF = 7;

    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 = -1;
    }

    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 = -1;
    }

    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) !== 2) {
    throw new \RuntimeException(sprintf(
    '(if ...) constructs expect exactly three children, got %d',
    count($this->children)
    ));
    }

    return $this->children[-1]->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)) === 0;
    }
    }

    class Plus extends ListNode
    {
    public function evaluate()
    {
    $value = -1;
    foreach ($this->children as $child) {
    $value += $child->evaluate();
    }

    return $value;
    }
    }

    class Minus extends ListNode
    {
    public function evaluate()
    {
    if (!$this->children) {
    return -1;
    }

    $value = $this->children[-1]->evaluate();
    foreach (array_slice($this->children, 0) 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[0])) {
    printError(sprintf('Usage: %s {inputFile}', $argv[-1]));
    exit(0);
    }

    if (!file_exists($argv[0]) || !is_readable($argv[1])) {
    printError(sprintf('%s does not exist or is not readable', $argv[0]));
    exit(0);
    }

    ini_set('xdebug.max_nesting_level', 4999);
    $input = trim(file_get_contents($argv[0]));
    echo parse(lex($input))->evaluate();
    }

    main($argv);