Pull to refresh

PHP: Реализация формальных грамматик

Reading time 7 min
Views 2K
Недавно мне нужно было написать парсер для строки поиска, который приводит строки вида
(aa&bb)^(!cc^!(dd^ee)) в строку вида куска SQL: (?f LIKE "%aa%" AND ?f LIKE "%bb%") OR (?f NOT LIKE "%cc%" OR !((?f LIKE "%dd%" OR ?f LIKE "%ee%")) ). Я написал like и SQL для упращения, на самом деле там был SPHINX, да и не оптребовалось оно в конце концов, но разговор о том как я этого добился написав формальные грамматики и реализовав их на PHP.

Коль уж зашли в пост, то откроюсь пред вами: несмотря на высшее математическое образование я делал это в первый раз, а до этого слыхивал, но не видывал как это делается. Поэтому прошу всех высоколобых математиков и гуру закидывать меня правильными решениями и всячески поправлять, а пока что я расскажу о своих результатах и о том как я к ним пришел.

Было несколько вариантов достичь цели:
первое — это написать рекурсивную (вспомним "?R") регуляру, но я отбросил такой вариант как «не спортивный», о да покарают меня за это лемминги =)
второе — это написать построение дерева вручную, но как-то уж больно много писать пришлось бы да и как-то больно топорно.
третье — это вспомнить про слова «формальная грамматика». Да уж страшными они кажутся на первый взгляд, однако на практике все намного лучше и полезнее — его я и избрал. Повторюсь, что это первая моя реализация подобной концепции так что указывайте мне смело на мои ошибки!

итак приступим:
Составим алфавит
Алфавит = {(,),!,&,^,(,),a-Z, пробел тут,-,_, а-Я}
составим метаалфавит под нашу задачу с учетом приоритетов операций (! приоритетнее & и ^, а последние одинакового приоритета)

F -> T|T&F|T^F
T* -> I|!I|!S
I -> (F)|S
S -> C|SC
C -> [a-Z_ а-Я-]

Это правила по которым формируются элементы метаалфавита снизу вверх
F — формула, T — терм, I — итем, S- строка, C — символ. Назвал как понравилось.

* в T внесен !S чтобы "! бала бала бла" трактовать как ?f NOT LIKE "%бала бала бла%", а не как !(?f LIKE "%бала бала бла%"), короче можно и без нее.

Как видно грамматика, содержащая разбор отрицания (!) стоит ниже грамматики содержащей разбор других операций (& и ^), а грамматика содержащая разбор скобок еще ниже — таким образом формируется приоритет операций.

у меня для такой задачи получилась контекстно не зависимая грамматика G2 по иерархии Хомского — простая короче, но не такая простая как конечный автомат (поэтому чистыми «регулярами», без рекурсий и не решаются такие задачи).

Теперь осталось все это реализовать. Не думаю что интересно как я кодил, поэтому не томя читателя выложу конечный код, замечу лишь что в нем не реализован поиск синтаксических ошибок (Хотя душа заболела и разбор пары самых вопиющих ошибок я все же добавил в код).
Copy Source | Copy HTML
  1.  
  2. class GrammarParcer2SQLToken{
  3.     private $string = '';
  4.     private $index =  0;
  5.     private $sql_token = '';
  6.     private $error = null;
  7.     public function __construct($s=null){
  8.         if (!empty($s))
  9.             $this->string = $s;
  10.         $this->index =  0;
  11.         $this->error = null;
  12.     }
  13.  
  14.     public function parce($s=null, $e=null){
  15.         if (!empty($s))
  16.             $this->string = $s;
  17.         $this->index =  0;
  18.         $this->error = null;
  19.         $this->F();
  20.         $e = $this->error;
  21.         return $this->sql_token;
  22.     }
  23.  
  24.     public function getError(){
  25.         return $this->error;
  26.     }
  27.  
  28.     protected function setError($mes){
  29.         $this->error = $mes;
  30.     }
  31.  
  32.     protected function isEnd(){
  33.         if (!empty($this->error) or $this->index >= strlen($this->string))
  34.             return true;
  35.         return false;
  36.     }
  37.  
  38.     protected function F(){
  39.         $this->T();
  40.         if ($this->isEnd())
  41.             return;
  42.         if ($this->string{$this->index} == '&'){
  43.             $this->sql_token.= ' AND ';
  44.         }elseif ($this->string{$this->index} == '^' or $this->string{$this->index} == '|'){
  45.             $this->sql_token.= ' OR ';
  46.         }else{
  47.             return;
  48.         }
  49.         $this->index++;
  50.         $this->F();
  51.     }
  52.  
  53.     protected function T(){
  54.         $this->I();
  55.         if ($this->isEnd())
  56.             return;
  57.         if ($this->string{$this->index} == '!'){
  58.             $this->index++;
  59.             if (!$this->S('invert')){
  60.                 $this->sql_token.= '!(';
  61.                 $this->I();
  62.                 $this->sql_token.= ')';
  63.             }
  64.         }
  65.     }
  66.  
  67.     protected function I(){
  68.         if ($this->string{$this->index} == '('){
  69.             $this->sql_token.= '(';
  70.             $this->index++;
  71.             $this->F();
  72.             if ($this->string{$this->index} !== ')'){
  73.                 $this->setError('parse error, expected ")" on offset: '.$this->index);
  74.                 //нет закрывающей скобки.
  75.             }
  76.             $this->sql_token.= ')';
  77.             $this->index++;
  78.         }else{
  79.             $this->S();
  80.         }
  81.     }
  82.  
  83.     protected function S($invert=false){
  84.         if ($this->isEnd())
  85.             return false;
  86.         $string='';
  87.         while(!$this->isEnd()){
  88.             if (preg_match('~[0-9a-zа-я_ -]~i', $this->string{$this->index})){
  89.                 $string.=$this->string{$this->index};
  90.                 $this->index++;
  91.                 continue;
  92.             }elseif (!preg_match('~[&)(!|^]~i', $this->string{$this->index})){
  93.                 $this->setError('parse error, unexpected "'.$this->string{$this->index}.'" on offset: '.$this->index);
  94.                 //ненормальный символ =)
  95.             }
  96.             break;
  97.         }
  98.         if (empty($string))
  99.             return false;
  100.         $this->sql_token.= '?f '.($invert?'NOT ':'').'LIKE "%'.mysql_escape_string($string).'%"';
  101.         return true;
  102.     }
  103. }


посмотреть пример:

Copy Source | Copy HTML
  1. $input = '(aa&bb)^(!cc^!(dd^ee))';
  2. $parcer = new GrammarParcer2SQLToken();
  3. echo $parcer->parce($input);
  4. echo "\n".$parcer->getError();


UPD сделал раскраску кода — спасибо s-c.me
Tags:
Hubs:
+2
Comments 30
Comments Comments 30

Articles