parser.php

<?php

class Parser {
	/**
	 * @var integer
	 */
	protected $point = 0;

	/**
	 * @var
	 */
	protected $text;

	/**
	 * @var
	 */
	protected $context;

	/**
	 * 	def parse_logical_expr(s):
	 *		    global text, point
	 *		    text = s.rstrip()
	 *		    point = 0
	 *
	 *		    result = expr()
	 *		    if point < len(text):
	 *		        raise SyntaxError("extra stuff after expression")
	 *		    return result
	 */
	public function parse($expression, $context) {
		$this->context = array(
			'x' => 1,
			'y' => 0,
			'z' => 1,
			'w' => 0
		);
		$this->text = $expression;
		$this->point = 0;
		$this->log('parsing: ' . $this->text);
		return $this->parseExpression();
	}

	public function log($message) {
		// echo $message . '<br />';
	}

	/**
	 * token_re = re.compile(r'\s*([A-Za-z]+|.?)')
	 *
	 * def peek():
	 *     return token_re.match(text, point).group(1)
	 */
	public function peek() {
		preg_match('/\s*([A-Za-z]+|.?)/', substr($this->text, $this->point), $matches);
		$this->log('peek found a new target "' . $matches[1] . '" starting at ' . $this->point . ', remaining expression "' . substr($this->text, $this->point) . '"');
		return $matches[1];
	}

	/**
	 * def consume(x):
	 *    global point
	 *    m = token_re.match(text, point)
	 *    if m.group(1) != x:
	 *        raise SyntaxError("expected " + x)
	 *    point = m.end()
	 */
	public function consume($x) {
		// preg_match('/\s*([A-Za-z]+|.?)/', $this->text, $matches, $this->point);
		// var_dump('foo', strpos($this->text, $x, $this->point));
		$this->point= strpos($this->text, $x, $this->point) + strlen($x);
		$this->log('consume "' . $x . '", now at ' . $this->point);
	}

	/**
	 * 	def expr():
	 *	    x = and_expr()
	 *	    while peek() == 'or':
	 *	        consume('or')
	 *	        y = and_expr()
	 *	        x = OR(x, y)
	 *	    return x
	 */
	public function parseExpression() {
		$this->log('parseExpression');
		$x = $this->parseAndExpression();
		while ($this->peek() == 'or') {
			$this->consume('or');
			$y = $this->parseAndExpression();
			$x = $this->evaluateOr($x, $y);
		}
		return $x;
	}

	/**
	 * def and_expr():
	 *    x = not_expr()
	 *    while peek() == 'and':
	 *        consume('and')
	 *        y = not_expr()
	 *        x = AND(x, y)
	 *    return x
	 */
	public function parseAndExpression() {
		$this->log('parseAndExpression');
		$x = $this->parseNotExpression();
		while ($this->peek() == 'and') {
			$this->consume('and');
			$y = $this->parseNotExpression();
			$x = $this->evaluateAnd($x, $y);
		}
		return $x;
	}

	/**
	 * def not_expr():
	 *    if peek() == 'not':
	 *        consume('not')
	 *        x = not_expr()
	 *        return NOT(x)
	 *    else:
	 *        return simple_expr()
	 */
	public function parseNotExpression() {
		$this->log('parseNotExpression');
		if ($this->peek() == 'not') {
			$this->consume('not');
			$x = $this->parseNotExpression();
			return $this->evaluateNot($x);
		}

		return $this->parseSimpleExpression();
	}

	/**
	 * def simple_expr():
	 *    t = peek()
	 *    if t == '(':
	 *        consume('(')
	 *        result = expr()
	 *        consume(')')
	 *        return result
	 *    elif is_term(t):
	 *        consume(t)
	 *        return TERM(t)
	 *    else:
	 *        raise SyntaxError("expected term or (")
	 */
	public function parseSimpleExpression() {
		$this->log('parseSimpleExpression');
		$t = $this->peek();
		if ($t == '(') {
			$this->consume('(');
			$result = $this->parseExpression();
			$this->consume(')');
			return $result;
		}

		if ($this->isTerm($t)) {
			$this->consume($t);
			return $this->evaluateTerm($t);
		}

		throw \Exception('end of line');
	}

	/**
	 * def is_term(x):
	 *    return x.isalpha() and x not in ('and', 'or', 'not')
	 */
	public function isTerm($x) {
		if (in_array($x, array('and', 'or', 'not'))) {
			return FALSE;
		}

		return is_string($x);
	}

	/**
	 * def AND(x, y): return x and y
	 */
	public function evaluateAnd($x, $y) {
		return $x && $y;
	}

	/**
	 * def OR(x, y): return x or y
	 */
	public function evaluateOr($x, $y) {
		return $x || $y;
	}

	/**
	 * def NOT(x): return not x
	 */
	public function evaluateNot($x) {
		return !$x;
	}

	/**
	 * def TERM(v): return variables[v]
	 */
	public function evaluateTerm($x) {
		return $this->context[$x];
	}
}

$parser = new Parser();

$tests = array(
	'(((x)))',
	'w and not z',
	'x and z and not y',
	'w',
	'(x or w) and (x or y) and (y or z)'
);

foreach ($tests as $test) {
	echo '"' . $test . '": ';
	var_dump($parser->parse($test, array(
		'x' => 1,
		'y' => 0,
		'z' => 1,
		'w' => 0
	)));
}