Aragon Online

Go Back   Aragon Online > Discussion > Programmer's Cubicle

Programmer's Cubicle A place where some code snippets and other nerdy things will be posted for the general programmer community's benefit.
Note that this is not a programming HELP forum. Posts not about the code here will be deleted or moved.

Reply
 
Thread Tools Display Modes
  #1  
Old 05-30-2009, 09:54 PM
Merlin's Avatar
Merlin Merlin is offline
Supreme Wizard
Administrator
 
City: Riverton
Race: Human
Wealth: 870,002
Population: 1,582
 
Join Date: Dec 2003
Location: The deepest dark of Oregon
Posts: 3,265
Merlin is on a distinguished road
Default A PHP Recursive Descent Parser for expression evaluation

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:
PHP Code:
round(rand(-100) + ($population_adult $population_old 4
    * (
$health min(75$morale) - 200 rand(020)) / 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:
PHP Code:
    // 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); 
PHP Code:
<?
/* 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($v1);
            
$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;
    }

}
?>
__________________
Do not meddle in the affairs of wizards, for they are subtle and quick to anger.
The Lord of the Rings
Gildor, Chapter 'Three is Company'.
Reply With Quote
Reply

Bookmarks

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT. The time now is 09:11 PM.


Powered by vBulletin® Version 3.8.5
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Copyright ©2003 - 2012 by Unintended Features