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

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

  • AndryG

    Сообщения: 237 Репутация: N Группа: Адекваты

    Spritz 30 сентября 2009 г. 20:56, спустя 20 часов 47 минут 9 секунд

    Доброго.

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

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

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

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

    Сообщения: 5305 Репутация: N Группа: в ухо

    Spritz 22 сентября 2009 г. 15:00, спустя 18 часов 3 минуты 34 секунды

    если я правильно понял то тебе хоцца написать калькулятор
    попробуй взять за основу вот этот
    http://www.benjoffe.com/code/tools/functions3d/parse.js
    источник
    http://www.benjoffe.com/code/tools/functions3d/
    Спустя 55 сек.
    он там считает выражения типа
    (1 - x^2 - y^2) ^ (1/2)
  • phpdude

    Сообщения: 26646 Репутация: N Группа: в ухо

    Spritz 22 сентября 2009 г. 23:37, спустя 8 часов 37 минут 45 секунд

    считается это все методом "обратной польской ротации/записи" насколько я помню :)
    Сапожник без сапог
  • AndryG

    Сообщения: 237 Репутация: N Группа: Адекваты

    Spritz 29 сентября 2009 г. 20:36, спустя 6 дней 20 часов 58 минут

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

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

    Сообщения: 26646 Репутация: N Группа: в ухо

    Spritz 25 сентября 2009 г. 11:42, спустя 15 часов 5 минут 54 секунды

    AndryG, и?
    Сапожник без сапог
  • AndryG

    Сообщения: 237 Репутация: N Группа: Адекваты

    Spritz 25 сентября 2009 г. 18:22, спустя 6 часов 39 минут 32 секунды

    И первым делом мы напишем простенький лексический анализатор.
    <?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']; }
    }
    Спустя 225 сек.
    Попытался заложить в класс расширяемость в сторону определения "простых" лексем. Простыми я называю лексемы в пару символов по типу "<= && ^ и т.д."

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

    Сообщения: 4761 Репутация: N Группа: в ухо

    Spritz 25 сентября 2009 г. 18:25, спустя 3 минуты 41 секунду

    AndryG, с именованием переменных и методов у тебя проблемы…..
  • AndryG

    Сообщения: 237 Репутация: N Группа: Адекваты

    Spritz 25 сентября 2009 г. 18:36, спустя 11 минут 13 секунд

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

    Сообщения: 26646 Репутация: N Группа: в ухо

    Spritz 25 сентября 2009 г. 18:54, спустя 17 минут 8 секунд

    убило вот ето ..

    if( $this->lxEof()){}
    Сапожник без сапог
  • NRG

    Сообщения: 4761 Репутация: N Группа: в ухо

    Spritz 25 сентября 2009 г. 18:58, спустя 4 минуты 7 секунд

    вот такая конструкция тоже ниче….
    if(    $this->lxEof()){}
    elseif($this->lxShortLex()){}
    elseif($this->lxNumber()){}
    else $this->lxUnknow();
    Спустя 177 сек.
    название метода должно отвечать на вопрос что сделать.
    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']; }


    что делает метод type ?
    если это геттер, то и пиши getType, а еще лучше пиши тайп чего он возвращает, типа getSymbolType или что там у тебя….
  • AndryG

    Сообщения: 237 Репутация: N Группа: Адекваты

    Spritz 25 сентября 2009 г. 19:06, спустя 8 минут 17 секунд

    phpdude, меня тоже улыбнуло. Не придумал слету. Как такую логику впихнуть аккуратно.
    NRG, по первому куску уже сказал.
    По второму … верно Вы говорите. Но не хочется потом длинными методами оперировать … и в коде это будет более-менее
    if('lxNumber' == $lex->type()){

  • AndryG

    Сообщения: 237 Репутация: N Группа: Адекваты

    Spritz 28 сентября 2009 г. 20:17, спустя 3 дня 1 час 10 минут

    Вот и вычислитель. На входе берет выражение в обр. польской записи.
    /**
    * Вычислитель строки-выражения обратной польской записи
    * Входной формат:
    * Строка
    * с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);
  • Trej Gun

    Сообщения: 5305 Репутация: N Группа: в ухо

    Spritz 28 сентября 2009 г. 23:03, спустя 2 часа 45 минут 52 секунды

    где спер?
  • AndryG

    Сообщения: 237 Репутация: N Группа: Адекваты

    Spritz 29 сентября 2009 г. 16:03, спустя 16 часов 59 минут 59 секунд

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

    Сообщения: 5147 Репутация: N Группа: в ухо

    Spritz 29 сентября 2009 г. 16:22, спустя 19 минут 27 секунд

    то есть осталось перевести "нормальное" выражение в ОПН?
    возможно пригодится: http://www.javatalks.ru/ftopic5515.php
    ιιlllιlllι унц-унц

Пожалуйста, авторизуйтесь, чтобы написать комментарий!