Tag Archives: peg.js

How to translate a search query into a JavaScript filtering function

Posted on by
Reply

In a project I had to translate a search query into a filtering function to apply to a stream of JavaScript objects. The query language was very simple, boolean expressions of property constraints, for example “name:john AND age:52” where the search should return all the objects with property “name” equals to “john” and property “age” equals to 52.

The first step was to parse the search query with a parser. You can write a parser by hand or your can use a parser generator like PEG.js. I prefered the second one.

With the online editor I’ve wrote the language grammar:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
start = andExpression
 
andExpression = orExpression (and andExpression)?
 
orExpression = expression (or andExpression)?
 
expression = string ':' string
 
string = char*
 
char = [a-zA-Z0-9]
 
and = ws 'AND'i ws
 
or = ws 'OR'i ws
 
ws = [ \t\n\r]*

The generated parser takes as input the text to parse and returns the parsed elements:

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
Output
[
   [
      [
         [
            "n",
            "a",
            "m",
            "e"
         ],
         ":",
         [
            "j",
            "o",
            "h",
            "n"
         ]
      ],
      null
   ],
   [
      [
         [
            " "
         ],
         "AND",
         [
            " "
         ]
      ],
      [
         [
            [
               [
                  "a",
                  "g",
                  "e"
               ],
               ":",
               [
                  "5",
                  "2"
               ]
            ],
            null
         ],
         null
      ]
   ]
]

The grammar can be changed to make the parser method return a boolean expression:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
{
  function combine(left, right) {
 
    if (right === null) return left;
  
    return left + " " + right[0] + " " +right[1];
  }
}
 
start = ex:andExpression
        {return 'return '+ex+';';}
 
andExpression = left:orExpression right:(and andExpression)?
                {return combine(left,right);}
 
orExpression = left:expression right:(or andExpression)?  
               {return combine(left,right);}
 
expression = name:string ':' value:string
             {return 'LangParser.hasKeyValue(obj,\''+name+'\', \''+value+'\')';}
 
string = chars:char*
         { return chars.join(""); }
 
char = [a-zA-Z0-9]
 
and = ws 'AND'i ws
      {return '&&';}
 
or = ws 'OR'i ws
     {return '||';}
 
ws = [ \t\n\r]*

The parser for a query like “name:john AND age:52” generates the following expression:

JavaScript
1
2
return LangParser.hasKeyValue(obj,'name', 'john')
        && LangParser.hasKeyValue(obj,'age', '52');

In the generated expression I’ve used an utility method that checks if the specified couple of name and value exists as property for the specified object:

JavaScript
1
2
3
4
5
6
7
8
9
10
/**
* Checks if the passed Object has the specified couple of key and value as property.
* @param obj the object to check.
* @param key the key.
* @param value the value-
* @returns {Boolean} <code>true</code> if the couple is found, <code>false</code> otherwise.
*/
LangParser.hasKeyValue = function (obj, key, value) {
    return obj.hasOwnProperty(key) && value === obj[key];
};

The expression can be then passed as parameter in the function constructor:

JavaScript
1
2
var expression = parser.parse(query);
var filterFunction = new Function("obj", expression);

Now you can use the new function as filter, for example with stream.js streams:

JavaScript
1
var filtered = new Stream.filter(filterFunction).toArray();

The grammar can be expanded with more operators and capabilities.