Recommendation for building search parser

You can get quite a long way just using the Elixir lexer. Especially now that in Elixir 1.16 its lexing errors are better for user experience.

Example

iex> Code.string_to_quoted "(\"Modesty Blase\" or \"Willie Garvin\")"
{:ok, {:or, [line: 1], ["Modesty Blase", "Willie Garvin"]}}

iex> Code.string_to_quoted "a or (b and c)"
{:ok,
 {:or, [line: 1],
  [
    {:a, [line: 1], nil},
    {:and, [line: 1], [{:b, [line: 1], nil}, {:c, [line: 1], nil}]}
  ]}}

iex> Code.string_to_quoted "a or (b and c"
{:error,
 {[opening_delimiter: :"(", line: 1, column: 14],
  "missing terminator: ) (for \"(\" starting at line 1)", ""}}

You would then need a parser to ensure you have a valid expression for your query language but I think thats really quite easy compared to the lexical part given your reasonably straight forward requirements.

Hmmm, interesting idea! Unfortunately, it does not solve certain edge cases out of the box, e.g.:

iex> Code.string_to_quoted(~s{"Modesty Blaze" AND "Willie Garvin"})
{:error, {[line: 1, column: 17], "syntax error before: ", "'AND'"}}

Didn’t have time to inspect further since I ended up with a solution that just scans the input, see next answers.

This idea to just implement binary pattern matching got me thinking. I couldn’t find a way to actually do that. But, during the study of the issue, decided to go with simple scan approach. E.g. just go over each character, split on spaces and count parenthesis and quotes. I have the working solution at Boolean query lexer (not AST unfortunately) · GitHub if you care to take a look. Not simple though and likely hard to debug too. But this bought time so I can try and implement this via some other mechanism.

Good point about silently ignoring grammar errors! Haven’t considered that one and it does make sense. E.g. given search for Modesty Blase OR Willie Garvin AND it makes sense to drop the last AND since it does not serve any purpose.

Would love to formalize requirements but unfortunately this will go the “let’s see how it works and then we’ll improve” way. Not that this is bad, just that it does not yield to formalization well

So for the time being I used a plain approach, scanning the input. See the gist link in reply above. This solution does that, ignores certain input errors (drops tailing operators, uses only the last operator if more than one are supplied, …). It does not say at which character e.g. unclosed parenthesis started, but it should be fairly simple to add that too (it is scanning so counting should not be an issue).

I do plan to try some/all of those solutions and see if I can get a more maintainable solution after all. Hope it will be possible to also ignore certain “invalid” input and have nice enough error reporting.

Thanks for the idea!

That’s because the AND is uppercased, might be a simple fix with a String.replace ?

Yep, replacing would work for operators. Mind you, this is user input so we could expect also things like aNd, And etc. and need to support another language too. But it could be done.

Unfortunately, apart from quoted terms, it needs to support non-quoted multi-word ones, e.g.:

iex(1)> Code.string_to_quoted(~s{SAP ABAP})
{:error, {[line: 1, column: 5], "syntax error before: ", "'ABAP'"}}

This case breaks it because those terms are indeed user input and not part of any dictionary, so have to take it in and parse as-is (no transformation/downcasing).

If strings can be unquoted then it will become ambiguous grammer right? For example how should FOO AND BAR be parsed? It can be both a boolean expression and a single multi word string.

@elvanja You can take a look at what I have done here predicated/lib/predicated/query/parser.ex at main · themusicman/predicated · GitHub.

Here are some examples in the limited tests: predicated/test/predicated/query/parser_test.exs at main · themusicman/predicated · GitHub

I am stuck at the moment on supporting parans and nesting.

Well, I had a break through last night and added support for grouping and nested grouping. Might be some bugs in there but I think it generally works.

https://github.com/themusicman/predicated/commit/cca03c4e15206cdb7d1bf409f4d9c322b8106c29#diff-2291a21e493bd663ef36b5e16bfdf8a6a09ae25a2fa5d26dbed6a970969db52cR1

Well, we can make some assumptions here, I think. E.g. if user would enter “SAP BW OR Java” in search engine I would assume the user wanted someone with “SAP BW” OR “Java”. The way I decided to interpret unquoted searches basically boils down to considering everything between boolean operators (AND, OR, NOT, AND NOT, …) to be a “keyword” term which can be a single or multi word in nature. One needs to be careful with quoted terms of course (e.g. to take "Bang AND Olufsen" - quoted - as is).