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

Недавно мне нужно было написать парсер для строки поиска, который приводит строки вида
(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 "%бала бала бла%"), короче можно и без нее.

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

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

Теперь осталось все это реализовать. Не думаю что интересно как я кодил, поэтому не томя читателя выложу конечный код, замечу лишь что в нем не реализован поиск синтаксических ошибок (Хотя душа заболела и разбор пары самых вопиющих ошибок я все же добавил в код).

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