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:
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:
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:
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:
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:
1 |
var filtered = new Stream.filter(filterFunction).toArray(); |
The grammar can be expanded with more operators and capabilities.