2

I am trying to parse a "rules string" provided over an API in PHP.

Given that I have an array of items such as

$items = [41, 42, 51, 54, 65, 12];

I wish to evaluate this expression

({41} AND {51}) OR ({31} AND {42})

In this instance it should return true, since the $items array has both the 41 and 51 items.

I started with creating a tokenizer using the https://github.com/nette/tokenizer library and currently have it parsing the string into an array of tokens.

array:25 [
  0 => array:3 [
    0 => "("
    1 => 0
    2 => 1
  ]
  1 => array:3 [
    0 => "{"
    1 => 1
    2 => 2
  ]
  2 => array:3 [
    0 => "41"
    1 => 2
    2 => 3
  ]
  3 => array:3 [
    0 => "}"
    1 => 4
    2 => 4
  ]
  4 => array:3 [
    0 => " "
    1 => 5
    2 => 8
  ]
  5 => array:3 [
    0 => "AND"
    1 => 6
    2 => 5
  ]
  6 => array:3 [
    0 => " "
    1 => 9
    2 => 8
  ]
  7 => array:3 [
    0 => "{"
    1 => 10
    2 => 2
  ]
  8 => array:3 [
    0 => "51"
    1 => 11
    2 => 3
  ]
  9 => array:3 [
    0 => "}"
    1 => 13
    2 => 4
  ]
  10 => array:3 [
    0 => ")"
    1 => 14
    2 => 7
  ]
  11 => array:3 [
    0 => " "
    1 => 15
    2 => 8
  ]
  12 => array:3 [
    0 => "OR"
    1 => 16
    2 => 6
  ]
  13 => array:3 [
    0 => " "
    1 => 18
    2 => 8
  ]
  14 => array:3 [
    0 => "("
    1 => 19
    2 => 1
  ]
  15 => array:3 [
    0 => "{"
    1 => 20
    2 => 2
  ]
  16 => array:3 [
    0 => "31"
    1 => 21
    2 => 3
  ]
  17 => array:3 [
    0 => "}"
    1 => 23
    2 => 4
  ]
  18 => array:3 [
    0 => " "
    1 => 24
    2 => 8
  ]
  19 => array:3 [
    0 => "AND"
    1 => 25
    2 => 5
  ]
  20 => array:3 [
    0 => " "
    1 => 28
    2 => 8
  ]
  21 => array:3 [
    0 => "{"
    1 => 29
    2 => 2
  ]
  22 => array:3 [
    0 => "42"
    1 => 30
    2 => 3
  ]
  23 => array:3 [
    0 => "}"
    1 => 32
    2 => 4
  ]
  24 => array:3 [
    0 => ")"
    1 => 33
    2 => 7
  ]
]

However this is where my talent runs out and I am not sure how to process the tokens so that I can run the condition against my $items array.

It could be that I am approaching this completely wrong.

Simon Bowen
  • 31
  • 1
  • 3
  • See my SO answers on how to build a parser, and how to build an expression evaluator: http://stackoverflow.com/questions/2245962/is-there-an-alternative-for-flex-bison-that-is-usable-on-8-bit-embedded-systems/2336769#2336769 – Ira Baxter Jan 07 '17 at 16:16
  • Hi @IraBaxter, I've had a look at some of your answers and am struggling trying to apply what you have written with my question. – Simon Bowen Jan 07 '17 at 17:19
  • 1) write a grammar. 2) Then write a recursive descent parser for that grammar. 3) Then extend it to evaluate expressions. If you can't do step 1, you're probably not going to succeed at all. My answer(s) tells you how to do steps 2 and 3. – Ira Baxter Jan 07 '17 at 17:22
  • @IraBaxter I was hoping to have some feedback on whether the current direction I have gone in was correct, and some pointers on where to head next. Was I right in tokenizing my expressions first and then processing these? – Simon Bowen Jan 07 '17 at 17:27
  • A parser swallows a series of tokens, one at a time in order from the beginning of the text being parsed to the end. Whether you build that series before you invoke the parser, or whether the parser, on "fetching" a token causes the next one to be produced, isn't normally a big issue in implmenting a parser. Either way will work. The easy way with the kind of recursive parsers (RD) I suggest, is to produce tokens on demand from the parser. In fact, the RD parser structure is organized as subroutines that recognize a code structure; it is trivial to write subroutines to recognized tokens. – Ira Baxter Jan 07 '17 at 17:47
  • @IraBaxter Looks as though I've got some reading to do. Thanks for the direction, seems as though this isn't as easy as I thought it would be. – Simon Bowen Jan 07 '17 at 17:52
  • Actually, it is easy. This will become more obvious as you work your way through it. I end up coding one of these probably every 3 months, and costs me a few hours tops. – Ira Baxter Jan 07 '17 at 18:20
  • Sorry, I'll rephrase that. It's not easy for me, since I clearly have never written a parser before. I'm sure it's stupendously easy for you, especially if you're writing a parser every 3 months. Jeez. – Simon Bowen Jan 07 '17 at 18:23
  • Yes, experience does matter, but in the case I think I've recorded the essentials to make you successful. Don't take my experience as a disabling issue for you. Working on it will help clear up the issues. – Ira Baxter Jan 07 '17 at 18:57

0 Answers0