PHP, БНФ It's my web

PHP, БНФ

25
Янв2

Немного отойду от тематики монетизации, настройки и раскрутки сайтов и расскажу о том, как я писал по заданной БНФ программу, которая её будет реализовывать.
Википедия гласит, что БНФ(Форма Бэкуса-Наура) - это формальная система описания синтаксиса, в которой одни синтаксические категории последовательно определяются через другие категории. БНФ используется для описания контекстно-свободных формальных грамматик.

Итак была дана БНФ:

Язык = “Start” Оператор”;”…Оператор Сочетание…Сочетание “Stop”
Сочетание = “Real” Перем…Перем ! “Int” Перем…Перем ! “Label” Цел…Цел
Оператор = </ Метка…Метка “:”/> Перем “=” Прав.часть
Прав.часть = </ “-” /> Бл1 зн1…Бл1
зн1 = “+” ! “-“
Бл1 = Бл2 зн2…Бл2
зн2 = “*” ! “/”
Бл2 = Бл3 зн3…Бл3
зн3 = “^”
Бл3 = </ фун…фун /> Бл4
фун = “cos” ! “sin” ! “tg”
Бл4 = Перем ! Вещ ! Цел ! “[” Прав.часть “]”
Прем = ББЦЦЦ
Метка = Цел
Б = “a” ! “b” !… “z”
Ц = “0” ! “1” ! “2” !… “9”
Вещ = Цел “.” Цел
Цел = Ц…Ц

Программа должна была считать математические действия, выводить список ошибок, если что-то было не так. Оставалось дело за малым - написать программу. Я её писал на php.

Начнём…

Так как я как раз уже сдал несколько работ, то и эту работу решил так же делать на php. Требовалось написать класс, который бы обрабатывал нашу БНФ, проверял ошибки. А в index-странице я уже через js выделял кусок с ошибкой(если таковая имелась).
Создадим файл parser.php, где будет наш класс и объвим некоторые переменные в конструкторе:

class MegaParser
{
    public function __construct($string)
    {
        $this->string = $string; //наша строка
        $this->offset = 0; //общее смещение
        $this->line = 1; // номер строки
        $this->position = 0; // позиция в строке
        $this->var_use = array(); //массив переменных и значений(смотреть return_value)
        $this->flag = 0; //нужно для проверки после "Stop"
    }
}

Класс создан. Чтобы тестировать наш парсер мы будем использовать функцию:

function parse($str)
{
    $p = new MegaParser($str);
    return $p->parse();
}
Создали фукнцию, которая будет запускать наш парсер. Дальше создадим методы класса:

который будет запускать наш парсер(как раз она используется в функции выше)

public function parse()
    {
        $this->skip_whitespace();
        return $this->lang();
    }

который будет пропускать пробелы

protected function skip_whitespace()
    {
        while(true)
        {
            $c = $this->nextchar();

            if(preg_match('/^\s$/', $c) == 0)
                return;

            $this->skipchar();
        }
    }

который будет брать следующий символ

 protected function nextchar()
{
return $this->string[$this->offset];
}

который будет брать следующие n символов

protected function nextchars($len)
{
return substr($this->string, $this->offset, $len);
}

который будет пропускать следующий символ

protected function skipchar()
    {
        if($this->nextchar() == "\n")
        {
            $this->line ++;
            $this->position = 0;
        } else{
            $this->position ++;
            }
        $this->offset++;
    }

который будет пропускать следующие n символов

protected function skipchars($len)
    {
        $this->offset=$this->offset+$len;
    }

который будет проверять на терминал

protected function check_term($term)
    {
        return $this->nextchars(strlen($term)) == $term;
    }

который будет пропускать терминал(если он правильный)

protected function skip_term($term)
    {
        if($this->check_term($term)) {
            for($i = 0; $i < strlen($term); ++$i)                 $this->skipchar();
        }
        else
        {
            switch($term){
            case ';':
                $this->fail("Текст ошибки:
Ожидается \";\" или знак(+,-,^,/) или тригонометрические функции(cos, sin, tan)",2,strlen($term)-1);
            break;
            case ':':
                $this->fail("Текст ошибки:
Ожидается \":\" или метка( целочисленная )",2,strlen($term)-1);
            break;
            case 'Stop':
                if($this->flag==1 || $this->flag==2)
                $this->fail("Текст ошибки:
Ожидается \"Stop\" или переменная( должна состоять из 2-х букв и 3-х цифр )",2,strlen($term)-1);
                else $this->fail("Текст ошибки:
Ожидается \"Stop\" или целое число",2,strlen($term)-1);
            break;
            case ']':
                $this->fail("Текст ошибки:
Ожидается \"]\" или знак(+,-,^,/) ",2,strlen($term)-1);
            break;
            default: $this->fail("Текст ошибки:
Ожидается \"".$term."\"",2,strlen($term)-1); break;
            }
        }
        $this->skip_whitespace();
        return $term;
    }

Теперь попробуем разобраться в самом начале. У нас в методе(parse) класса запускается метод lang(). Который и запускает всю работу парсера с самого начала.

Рассмотрим метод lang():

protected function lang()
    {
        $this->skip_term("Start");
        while(true)
        {
            $this->oper();
            if($this->nextchar() == ';') {
                $this->skip_term(";");
                $this->skip_whitespace();
            }
            else
                break;
        };
        while(true) { $this->sochetanie(); if($this->check_term("Stop")) break;
        if(!$this->check_term("Int") && !$this->check_term("Label") && !$this->check_term("Real") && !$this->check_term("Stop"))
        $this->fail("Текст ошибки:
Ожидается \"Int\" или \"Real\" или \"Label\" или Stop",3,4);
        }
        $this->skip_term("Stop");
        $this->result();
    }

Из этого метода мы запускаем методы: oper, sochetanie.
Глянем на них:

protected function oper()
    {
        if (!$this->next_token_is_a_variable() && !$this->next_token_is_a_number())
        {
            $this->fail("Текст ошибки:
Ожидается метка или переменная( должна состоять из 2-х букв и 3-х цифр )",3,2);
        }
        else
        {
            $this->labels();
        }
        $key = $this->is_perem();
        $this->skip_term("=");
        $value = $this->right_part();
        $this->var_use[$key] = $value;
        echo "\n";
    }

     protected function sochetanie()
    {
        $this->skip_whitespace();
        if($this->check_term("Int"))
        {
            $this->flag = 1;
            $this->skip_term("Int");
            $this->skip_whitespace();
            while($this->next_token_is_a_variable()){$this->is_perem();}
            $this->skip_whitespace();
            return 1;
        }
        elseif($this->check_term("Real"))
        {
            $this->flag = 2;
            $this->skip_term("Real");
            $this->skip_whitespace();
            while($this->next_token_is_a_variable()){$this->is_perem();}
            $this->skip_whitespace();
            return 1;
        }
        elseif($this->check_term("Label"))
        {
            $this->flag = 3;
            $m = 0;
            $this->skip_term("Label");
            $this->skip_whitespace();
            while($this->number_check_2()){$this->skip_whitespace();$m++;}
            if($m=='0') $this->fail("Текст ошибки:
Ожидаются целые цифры",3,0);
            $this->skip_whitespace();
            return 1;
        }
        else $this->fail("Текст ошибки:
Ожидается \"Int\" или \"Real\" или \"Label\" или знак(+,-,^,/) или  \";\"",3,4);
    }

Тут мы уже используем новые нам методы:

next_token_is_a_variable(проверка на переменную, 2 буквы и 3 цифры)

protected function next_token_is_a_variable()
    {
        return preg_match("/^[a-z]{2}\d{3}/", $this->nextchars(5)) != 0;
    }

next_token_is_a_number(проверка на число)

protected function next_token_is_a_number()
    {
        return is_numeric($this->nextchar());
    }

is_perem(проверка на переменную с переходом через символы(можно было и не использовать эту функцию)

protected function is_perem()
    {
        $this->skip_whitespace();
        $str = '';
        for($i = 0; $i < 5; ++$i){
            $str .= $this->nextchar();
            $this->skipchar();
        }
        $this->skip_whitespace();
        if(!preg_match("/^[a-z]{2}\d{3}/",$str))
        {
        $this->offset = $this->offset - 6;
        $this->fail("Текст ошибки:
Ожидается переменная( должна состоять из 2-х букв и 3-х цифр )",1,5);
        }
        else
        return $str;
    }

number_check_2

protected function number_check_2()
    {
        $cs = '';
        $i = 0;
        while(true)
        {
            $c = $this->nextchar();
            if(is_numeric($c) || ($i==0 && $c=='-'))
                $cs .= $c;
            else
                break;
            $i++;
            $this->skipchar();
        }

        if(strlen($cs) > 0)
            return true;
        else return false;
    }

right_part(правая часть)

protected function right_part()
    {
        if($this->nextchar() == '-') {
            $this->skipchar();
            $out = -$this->block_1();
        }
        else
            $out = $this->block_1();

        while(true)
        {
            $this->skip_whitespace();
            switch($this->nextchar())
            {
            case '+':
                $this->skipchar();
                $this->skip_whitespace();
                $out += $this->block_1();
                break;

            case '-':
                $this->skipchar();
                $this->skip_whitespace();
                $out -= $this->block_1();
                break;

            default:
                return $out;
            }
        }
    }

    protected function block_1()
    {
        $out = $this->block_2();

        while(true)
        {
            $this->skip_whitespace();
            switch($this->nextchar())
            {
            case '*':
                $this->skipchar();
                $this->skip_whitespace();
                $out *= $this->block_2();
                break;

            case '/':
                $this->skipchar();
                $this->skip_whitespace();
                if($this->nextchar()=='0')
                $this->fail("Текст ошибки:
Деление на нуль запрещено",4,1);
                else
                $out /= $this->block_2();;
                break;

            default:
                return $out;
            }
        }
    }

    protected function block_2()
    {
        $out = $this->block_3();

        while(true)
        {
            $this->skip_whitespace();
            switch($this->nextchar())
            {
            case '^':
                $this->skipchar();
                $this->skip_whitespace();
                $out = pow($out, $this->block_3());
                break;

            default:
                return $out;
            }
        }
    }

    protected function block_3()
    {
        $this->skip_whitespace();
        switch($this->nextchars(3))
        {
        case 'sin':
            $this->skip_term("sin");
            $this->skip_whitespace();
            return sin($this->block_3());
        case 'cos':
            $this->skip_term("cos");
            $this->skip_whitespace();
            return cos($this->block_3());
        case 'tan':
            $this->skip_term("tan");
            $this->skip_whitespace();
            return tan($this->block_3());
        default:
            return $this->block_4();
        }
    }

    protected function block_4()
    {
        if($this->nextchar() == '[')
        {
            $this->skipchar();
            $temp = $this->right_part();
            $this->skip_term(']');
            return $temp;
        }
        elseif ($this->next_token_is_a_variable())
        {
           return $this->return_value($this->nextchars(5));
        }
        else
        return $this->number();
    }

    protected function return_value($name_var)
    {
        $m = 0;
        foreach($this->var_use as $key => $value)
        {
            if($key == $name_var) { $this->skipchars(5); return $value; $m = 1;}
        }
        if($m==0)
        {
            $this->offset = $this->offset - 1;
            $this->fail("Текст ошибки:
Такой переменной не существует, используйте  цифры или тригонометрические функции(cos, sin, tan)",1,5);
        }
    }

Наш парсер уже практически готов. Вторая часть состоит из нескольких блоков, которые почти похожи - решают обычные арифметические действия. return_value - для того, чтобы можно было использовать имена переменных в другом арифметическом выражении.

Результат выводим в методе result:

protected function result()
    {
        foreach($this->var_use as $key => $value)
        {
            echo $key." = ".$value."
";
        }
        die();
    }

Ну и на последок метод для ошибок - fail. Специально оставил под конец(p.s. надо убрать перед input пробел - парсер вордпресса съедает):

protected function fail($error,$type,$len)
    {
        switch($type){
        case '1':
            $begin_error = $this->offset-$this->line+2;
            $end_error = $this->offset+$len-$this->line+2;
            echo "
< input onclick="\"SelectText({$begin_error},{$end_error})\"" type="\"button\"" value="\"Выделить" />

";
        break;
        case '2':
            $begin_error = $this->offset-($this->line-1);
            $end_error = $this->offset+$len-$this->line+2;
            echo "
< input onclick="\"SelectText({$begin_error},{$end_error})\"" type="\"button\"" value="\"Выделить" />

";
        break;
        case '3':
            $begin_error = $this->offset-$this->line+1;
            $end_error = $this->offset+$len-$this->line+2;
            echo "
< input onclick="\"SelectText({$begin_error},{$end_error})\"" type="\"button\"" value="\"Выделить" />

";
        break;
        case '4':
            $begin_error = $this->offset+1-$this->line;
            $end_error = $this->offset+$len+1-$this->line;
            echo "
< input onclick="\"SelectText({$begin_error},{$end_error})\"" type="\"button\"" value="\"Выделить" />

";
        break;
        case '5':
            $begin_error = $this->offset-$this->line-1;
            $end_error = $this->offset+$len-$this->line-1;
            echo "
< input onclick="\"SelectText({$begin_error},{$end_error})\"" type="\"button\"" value="\"Выделить" />

";
        break;
        default:
            $begin_error = $this->offset-$this->line+2;
            $end_error = $this->offset+$len-$this->line+2;
            echo "
< input onclick="\"SelectText({$begin_error},{$end_error})\"" type="\"button\"" value="\"Выделить" />
";
        break;
        }
        die($error);
    }

С html+js страничкой для запуска всего этого - думаю разберётесь(если нет - воспросы и предложения как всегда в коментарии).

Скачать парсер БНФ на php

Метки: PHP, бнф, парсер

Комментарии (2)

Отзывов: 2

Kuroki Kaze
15:27 на 29 Янв 2010
Гм, может действительно проще было бы разделить это на явные лексер и парсер? Имхо вышло бы элегантнее. А то тут одновременно и то и другое происходит.
krim
15:25 на 30 Янв 2010
можно было бы=) я предложил свой вариант)

It's my web Php, Ruby, Rails, Drupal, Wordpress, JS, SEO…

PHP, БНФ

Итак была дана БНФ:

Рассмотрим метод lang():

Тут мы уже используем новые нам методы:

Отзывов: 2

Ваш отзыв

Рубрики

Метки

Последние записи

Последние комментарии

Похожие статьи