Пишем интерпретатор логических выражений (для разгр. прав)

Доброго.

Писать в одиночку скучно. Может кто мысль подкинет…

Опыта в разборе выражений у меня не много. Посему ("по Макаренко") определим дальние и ближние цели.

Волна_1 простой вычислитель простых выражений с минимумом операций.
Только целые числа.
Арифметические, логические и битовые операции.
Добавлено 30.09.2009
Здесь точка выполнения первой волны и пример расширения возможностей

Волна_2 добавим макрооперации для удобной записи проверки бит.
Сократим запись "VAR & 3 == 3" до, например, "[VAR&=1,2]" и т.п. ("(VAR & 3) > 0" => [VAR&3])
Волна_3 перестраиваем наш вычислитель в генератор бай-кода.
Добавляем оптимизацию выражений.
Строим "виртуальную машину" для выполнения сего байт-кода.
Подумаем над реализацией сей машины на других языках программирования.

Разминка
Для начала попробуем создать очень простой калькулятор.
Из доступных операций: плюс/минус/разделить/умножить и скобки.
БНФ нашей грамматики будет выглядеть так:

<expr_1>    ::= <expr_2> { <oper_1> <expr_2>}
<oper_1>    ::= "+" | "-"
<expr_2>    ::= <expr_3> { <oper_2> <expr_3>}
<oper_2>    ::= "*" | "/" | "%" 
<expr_3>    ::= <operand>
<operand>   ::= <number> | "(" <expression_1> ")"
<number>    ::= <digit> { <digit> }
<digit>     ::= "0" | .. | "9"

Работать будем только с целыми числами, поэтому деления у нас два: целочисленное деление и остаток.

И первым делом мы напишем простенький лексический анализатор.

<?php                         
class lex {
  /**
  * Список полей записи лексемы и значение по умолчанию
  * 
  * @var array
  */
  protected $fields = array('type'=>'lxUnknow','value'=>null,'str'=>null,'pos'=>null);
  
  /**
  * Массив "коротких" лексем, которые можно определить без подробного разбора
  * 
  * @var mixed
  */
  protected $shortLex = array(
    'one' => array( // Лексемы в один символ
      'lxPlus'     => '+',
      'lxMinus'    => '-',
      'lxDiv'      => '/',
      'lxMod'      => '%',
      'lxAsterisk' => '*',
      'lxBracketL' => '(',
      'lxBracketR' => ')',
    )
  );
  
  /**
  * Строка для разбора
  * @var string
  */
  private $expression;
  
  /**
  * Текущая распознанная лексема
  * @var array
  */
  protected $current;
  
  /**
  * Указатель текущей позиции разбора
  * 
  * @var integer
  */
  protected $position;
  
  public function __construct($expression){
    $this->position = 1;
    $this->expression = strtolower($expression);
    $this->next();
  }
  
  
  /**
  * Функция - координатор запуска отдельных распознователей
  */
  protected function extract(){
    $this->lxSpace();
    $this->current = array('pos'=>$this->position);
    if(    $this->lxEof()){}
    elseif($this->lxShortLex()){}
    elseif($this->lxNumber()){}
    else   $this->lxUnknow();    
  }
  
  /**
  * Поисковик по массиву "коротких лексем"
  * 
  */
  protected function lxShortLex(){
    foreach($this->shortLex as $k=>$list){
      if(0 == ($length = strlen(reset($list)))){
        continue;
      }
      if($str = array_search($tmp_ = substr($this->expression,0,$length),$list)){
        $this->current['type'] = $str;
        $this->current['str']  = $list[$str];
        $this->expression = substr($this->expression,$tmp = $length);
        $this->position  += $length;
        return true;
      }
    }
  }
  
  /**
  * Определяем конец строки
  */
  protected function lxEof(){
    if(empty($this->expression)){
      $this->current['type'] = 'lxEof';
      return true;
    }
  }
  
  /**
  * Распознователь разделителей
  */
  protected function lxSpace(){
    if(preg_match('/^[\s]+/',$this->expression,$matches)){
      $this->expression = substr($this->expression, $tmp = strlen($matches[0]));
      $this->position  += $tmp;
      return true;
    }
  }
  
  /**
  * Распознает "неизвестную" лексему
  */
  protected function lxUnknow(){
    preg_match('/^[\S]*/',$this->expression,$matches);
    $this->current['type']  ='lxUnknow';
    $this->current['value'] = $this->current['str'] = isset($matches[0]) ? $matches[0] : null;
    $this->expression       = substr($this->expression,$tmp = strlen($this->current['value']));
    $this->position        += $tmp;
    return true;
  }                                                                                                   
  
  /**
  * Распознователь 
  *  <number>    ::= <digit> { <digit> }
  *  <digit>     ::= "0" | .. | "9"
  */
  protected function lxNumber(){
    if(preg_match('/^[0-9]+/',$this->expression,$matches)){
      $this->current['type']  = 'lxNumber';
      $this->current['value'] = $this->current['str']   = $matches[0];
      $this->expression       = substr($this->expression,$tmp = strlen($matches[0]));
      $this->position        += $tmp;
      return true;
    }
  }
    

  public function next(){
    $this->extract();
    // приводим к общему виду.
    $this->current = array_merge($this->fields,$this->current);
  }
    
  public function eof(){
    return $this->type() == 'lxEof';
  }
  
  public function current(){
    return $this->current;
  }
  
  public function type() { return $this->current['type']; }
  public function value(){ return $this->current['value'];}
  public function str()  { return $this->current['str'];  }
  public function pos()  { return $this->current['pos'];  }  
}

Попытался заложить в класс расширяемость в сторону определения "простых" лексем. Простыми я называю лексемы в пару символов по типу "<= && ^ и т.д."

Попробовать сей код можно на страничке http://andryg.sumy.ua/musor/lex_demo.php

А подробней? Что именно не так?

phpdude, меня тоже улыбнуло. Не придумал слету. Как такую логику впихнуть аккуратно.
NRG, по первому куску уже сказал.
По второму … верно Вы говорите. Но не хочется потом длинными методами оперировать … и в коде это будет более-менее

if('lxNumber' == $lex->type()){
…

Вот и вычислитель. На входе берет выражение в обр. польской записи.

/**
* Вычислитель строки-выражения обратной польской записи
* Входной формат:
*  Строка
*    с1 с2 p+
*      с1 - константа "1"
*      p+ - операция "+"
* Массив array(item,item,…)
* item  => aray(code,value)
* code  => 'c' - константа, 
*          'p' - операция
* value => значение константы или код операции (+ - / и т.д.)
*/
class calc {
  /**
  * Список унарных операций
  * 
  * Операции, при которых из стека нужно извлекать только один операнд
  * @var array
  */
  protected $unaryOperations = array('!','~','u-','u+');
  
  /**
  * Стек вычислителя
  * 
  * @var array
  */
  protected $stack;
  
  /**
  * Проверка "стек пустой"
  * @return bool
  */
  protected function stackEmpty(){
    return empty($this->stack);
  }
  
  /**
  * Помещает элемент в стек
  * 
  * @param mixed $data
  */
  protected function push($data){
    $this->stack[] = (integer)$data;
  }
  
  /**
  * Извлекает элемент из стека
  * @return integer
  */
  protected function pop(){
    $tmp = array_pop($this->stack);
    if(is_null($tmp)){
      throw new Exception('Попытка извлечения из пустого стека.');
    }
    return $tmp;
  }
  
  /**
  * Выполняет указанную операцию над операндами из вершины стека.
  * Результат помещается в стек
  * 
  * @param string $operation
  */
  protected function operation($operation){
    $a = $this->pop();
    //Для унарных операций опускаем чтение второго операнда
    if(!in_array($operation,$this->unaryOperations)){
      $b = $this->pop();
    }
    switch($operation){
      // унарный знак
      case 'u+' :$r = $a;       break;
      case 'u-' :$r = -$a;      break;
      // арифметические
      case '+'  :$r = $b + $a;  break;
      case '-'  :$r = $b - $a;  break;
      case '*'  :$r = $b * $a;  break;
      case '%'  :$r = $b % $a;  break;
      case '/'  :$r = (int)($b / $a);
                                break;
      // логические
…
      // битовые
…
      // неизвестная операция
      default:
        throw new Exception("Неизвестная операция [$operation]");
    } // switch
    $this->push($r);
  }
  
  /**
  * Вычисляет выражение, представленное строкой
  * 
  * @param string $byteCode
  * @return integer
  */
  public function calcString($byteCode){
    $code = array();
    foreach(explode(' ',$byteCode) as $item){
      $code[] = array(0 => substr($item,0,1), 1 => substr($item,1));
    }
    return $this->calcArray($code);
  }
  
  /**
  * Вычисляет выражение, представленное массивом
  * 
  * @param array $byteCode
  * @return integer
  */  
  public function calcArray($byteCode){
    foreach($byteCode as $index=>$item){
      switch($item[0]){
        case 'c': // константа (число)
          $this->push($item[1]);
        break;
        case 'p': // операция
          $this->operation($item[1]);
        break;
        default:
          throw new Exception("Неизвестный код [${item[0]}]");
      }
    }
    $result = $this->pop();
    if(!$this->stackEmpty()){
      throw new Exception('Непустой стек при окончании вычислений.');
    }
    return $result;
  }
}

Пример использования:

 // 5 * -(2*3 + 1) 
 $str = 'c5 c2 c3 p* c1 p+ pu- p*';
 $calc = new calc();
 echo $calc->calcString($str);

Алгоритм
Реализация моя.