PDA

View Full Version : A PHP Recursive Descent Parser for expression evaluation


Merlin
05-30-2009, 08:54 PM
I have been working on efficiency for quite some time, and wanted to eliminate calls to the PHP eval function. The eval function causes the PHP "compiler" to be invoked every time it is used, and the eval'ed code won't be cached. I had about 50 calls to eval in the city calculation code because I save the "formulas" used to calculate the city data in the database to make changes easier.

My solution was to write a recursive descent parser that evaluates those formulas. The evaluation routine has access to variables stored in the $vars array. There are two methods for adding variables to this array. I use quite a few PHP math functions, so I have included a sampling of those as well. I haven't attempted to do much more than I needed for this use, so there are some things missing, such as comparison operators. Those shouldn't be too hard to add - except that the tokenizer would have to be modified to allow for multiple character operators.

The evaluate class correctly handles complex formulas like this one:
round(rand(-10, 0) + ($population_adult - $population_old / 4)
* (2 * $health + min(75, $morale) - 200 + rand(0, 20)) / 10000)
+ min(0, ($food - $population) / 1000)Unlike most of the code I write, feel free to use this in your own projects and such. Email me if you do find this useful, and let me know what use has been made of this. If you make a significant improvement, or find a bug, I'd like to hear about it.

Use the add_eval_var and add_eval_array methods to add variables to the list that eval can access.

Instantiate it, and add your own functions, like this:

// Initialize the evaluation class
$eval = new Evaluate_Expression();

// Add your own custom functions
$f = array(
'die' => array('script_die', 1),
'city' => array('script_city', 1),
'city_data' => array('script_city_data', 1),
'other' => array('script_other', 1),
'other_data' => array('script_other_data', 1),
'is_npc' => array('is_npc', 1),

'city_cost' => array('script_city_cost', 0),
'random_city' => array('find_random_city', 2),
'win_loss' => array('script_win_loss', 0),
'power' => array('script_power', 0)
);

$eval->register_functions($f);
<?
/* Aragon Online - Copyright 2003-2009 by Russell Shilling */
/* Free to use for personal or commercial applications. All */
/* I ask is a link to this code: */
/* http://aragon-online.net/forums/showthread.php?t=530 */

/* cls_eval.php */

/**
* Class to safely evaluate expressions passed as string
*/
class Evaluate_Expression {

// Allowed functions
// Array values are actual function to call, followed by number of arguments
// Argument count can have multiple values, such as 2,3,4 for 2 to 4 arguments
var $functions = array(
'abs' => array('abs', 1),
'ceil' => array('ceil', 1),
'floor' => array('floor', 1),
'int' => array('intval', 1),
'max' => array('max', -1),
'min' => array('min', -1),
'rand' => array('rand', 2),
'round' => array('round', 1,2),
);


var $vars = array();

var $expr;

var $pos;
var $count;
var $tok;

var $err = array();

/**
* Return true if $c is numeric
*/
function is_num($c) {
return ($c == '.' || $c >= "0" && $c <= "9");
}
/**
* Return true if $c is an alpha
*/
function is_alpha($c) {
return ($c == "_"
|| $c >= "A" && $c <= "Z"
|| $c >= "a" && $c <= "z");
}
/**
* Return true if $c is an alphanumeric
*/
function is_alphanum($c) {
return ($this->is_num($c) || $this->is_alpha($c));
}

/**
* Tokenize the expression, returning an array of tokens
*/
function tokenize() {

$tokens = array('(',')','+','-','*','/',',');
$this->expr .= " "; // Sentinel character

$this->tok = array();
$i = 0;
while ($i < strlen($this->expr)) {

$c = $this->expr[$i];

// Token
if (in_array($c, $tokens)) {
$this->tok[] = $c;
++$i;

// String literal
} elseif ($c == '\'') {
$v = $c;
++$i;
while ($i < strlen($this->expr)) {
$v .= $this->expr[$i];
if ($this->expr[$i] == '\'') {
++$i;
break;
}
++$i;
}
$this->tok[] = $v;

// Variable
} elseif ($c == '$') {
$v = $c;
++$i;
while ($this->is_alphanum($this->expr[$i])) {
$v .= $this->expr[$i];
++$i;
}
$this->tok[] = $v;

// Function name
} elseif ($this->is_alpha($c)) {
$v = $c;
++$i;
while ($this->is_alphanum($this->expr[$i])) {
$v .= $this->expr[$i];
++$i;
}
$this->tok[] = $v;

// Number
} elseif ($this->is_num($c)) {
$v = $c;
++$i;
while ($this->is_num($this->expr[$i])) {
$v .= $this->expr[$i];
++$i;
}
$this->tok[] = $v;

} else {
++$i;
}
}
$this->count = count($this->tok);
}

/**
* Register user functions
* Pass $f in same format as the built-in functions
*/
function register_functions($f) {

$this->functions = array_merge($this->functions, $f);

}

/**
* Evaluate a function and return the result
*/
function eval_function($fn, &$args) {

$call_fn = $this->functions[$fn][0];
$value = null;

if (array_key_exists($fn, $this->functions)) {

if (function_exists($call_fn)) {

$args_required = array_slice($this->functions[$fn], 1);
$args_passed = is_array($args) ? count($args) : 0;

// Remove quotes from string args
for ($i = 0; $i < $args_passed; ++$i)
if ($args[$i][0] == "'")
$args[$i] = substr($args[$i],1,strlen($args[$i])-2);

// Call the function with the argument array
if (in_array(-1, $args_required)) {
$value = $call_fn($args);

// Call the function with the args passed
} elseif (in_array($args_passed, $args_required)) {

switch ($args_passed) {
case 0:
$value = $call_fn();
break;

case 1:
$value = $call_fn($args[0]);
break;

case 2:
$value = $call_fn($args[0],$args[1]);
break;

case 3:
$value = $call_fn($args[0],$args[1],$args[2]);
break;

default:
$this->err[] = "Error: Unsupported arg count: $fn(".implode(", ",$args).")";
}

} else {
$this->err[] = "Error: Incorrect arg count: $fn(".implode(", ",$args).")";
}

} else {
$this->err[] = "Error: Unknown called function: $fn -> $call_fn(".implode(", ",$args).")";
}

} else {
$this->err[] = "Error: Unknown function: $fn(".implode(", ",$args).")";
}

return $value;
}

/**
* Add an array to $this->vars
*/
function add_eval_array($a) {

$this->vars = array_merge($this->vars, $a);

}

/**
* Add a variable to $this->vars
*/
function add_eval_var($key, $value) {

$this->vars[$key] = $value;

}

/**
* Get the value of a variable from $this->vars
*/
function value($key) {

return $this->vars[$key];

}

/**
* Standard 3 function recursive descent parser
*/
function eval_factor() {

$v = $this->tok[$this->pos];
if ($this->is_num($v[0])) {

$value = $v;
++$this->pos;

// Variable
} elseif ($v[0] == '$') {

$v = substr($v, 1);
$value = $this->vars[$v];
++$this->pos;

// Function
} elseif ($this->is_alphanum($v[0])) {

$fn = $v;
++$this->pos;

$v = $this->tok[$this->pos];
if ($v == "(")
++$this->pos;
else
$this->err[] = "Error: Function Left-Paren not found";

$args = array();
if ($this->tok[$this->pos] != ")") {

$args[] = $this->eval_expr();

while ($this->pos < $this->count && $this->tok[$this->pos] == ",") {
++$this->pos;
$args[] = $this->eval_expr();
}
}
if ($this->tok[$this->pos] == ")") {
++$this->pos;
$value = $this->eval_function($fn, $args);
} else {
$this->err[] = "Error: Function Right-Paren not found";
}

// Expression
} elseif ($v == "(") {

++$this->pos;

$value = $this->eval_expr();
if ($this->tok[$this->pos] == ")")
++$this->pos;
else
$this->err[] = "Error: Expression Right-Paren not found";
}

return $value;
}

function eval_term() {

$value = $this->eval_factor();
$v = $this->tok[$this->pos];
while (($this->pos < $this->count) && ($v == "*" || $v == "/")) {
++$this->pos;

if ($v == "*")
$value *= $this->eval_factor();
else
$value /= $this->eval_factor();

$v = $this->tok[$this->pos];

if (count($this->err))
break;
}

return $value;
}

function eval_expr() {

// String literal
if ($this->tok[$this->pos][0] == "'") {

$value = $this->tok[$this->pos];
++$this->pos;

// Numeric expression
} else {
$sign = 1;
if ($this->tok[$this->pos] == "+" || $this->tok[$this->pos] == "-") {
if ($this->tok[$this->pos] == "-")
$sign = -1;
++$this->pos;
}
$value = $sign * $this->eval_term();

while ($this->pos < $this->count &&
($this->tok[$this->pos] == "+" || $this->tok[$this->pos] == "-")) {

$sign = 1;
if ($this->tok[$this->pos] == "-")
$sign = -1;
++$this->pos;

if ($sign > 0)
$value += $this->eval_term();
else
$value -= $this->eval_term();

if (count($this->err))
break;
}
}

return $value;
}

/**
* Evaluate an expression, returning the value
*/
function evaluate($expr) {

$this->expr = $expr;
$this->tokenize();
$this->pos = 0;
$this->err = array();

$value = $this->eval_expr();

return $value;
}

}
?>