Condition string to tokens

[tilz0R]

Delam aplikacijo, kjer imam tabelo z podatki. Rad bi naredil filter, da bi se v tabeli prikazale samo vrstice, ki gredo skozi filter. Podobno, kot ima to wireshark - njihovo kodo sem analiziral in je super kompleksna.

Trenutno imam narejen simple regex-match filter, ki ima znak podpičje za separator, med njimi naredi AND:
param1=abc;param2=^4(.*)5$

Kar v tem primeru pomeni, spusti skozi vrstico, če ima "abc" nekje v param1 in vrednost param2, ki se začne na 4 in konča z 5 (vmes nas ne zanima).

Ciljam nekaj, kar bi mi omogočalo nesting, ala:

param1=abc OR param2=^4(.*)5$ OR (param3=34 AND param4=etwas)

Pozna kdo kakšno knjižnico (C ali python je oboje OK), ki to sparsa, in vrne nek nested array/JSON, kako je treba sparsati?
Nekaj v smislu:

Koda: Izberi vse

"conditions": {
    "OR" {
        "param1":"abc",
        "param2":"^4(.*)5$",
        "AND": [
            {"OR": {"param3": "34", "param4":"etwas"}}
        ]
    }
}


Temu bi se naj reklo "Parsing expression Grammar", a nisem nič pametnega našel.

[Kroko]

Ne vem , če sem prav razumel ampak mogoče takole:
1. narediš funkcijo/operator, ki vrne true/false, če vrstica ustreza regex filtru.
2. narediš expression evaluator za AND, OR (in mogoče še kaj).
3. spustiš vrtico skozi evaluator in preveriš, če ustreza vsem pogojem.

Ali so "param1", "param2",... stolpci?

Takole bi izgledala izgledala sintaxa v mojem evaluatorju, samo funkcija match mi manjka še:
result = match("kloabcedanje", "abc") OR match("123456", "^4(.*)5$") OR (match("12345", "34") AND match("blabla", "etwas"));

[tilz0R]

Točno tako. Ideja je, da se omogoči tudi ostale ukaze, ala ! (NOT), greater-than, lower-than. Imena parametrov so stolpci, vsi lowercase, no spaces.

Rad bi se izognil eval ukazu v pythonu. Moram še malo raziskati

[Kroko]

evo, cem naredil še match funkcijo.

Koda: Izberi vse

result = match("kloabcedanje", "abc") || match("123456", "^4(.*)5$") || (match("12345", "34") && match("blabla", "etwas"));

mi vrne true, se pravi bi vrstico prikazalo.

Koda: Izberi vse

result = match("kloabcedanje", "efg") || match("123456", "^4(.*)5$") || (match("12345", "34") && match("blabla", "etwas"));

mi vrne false

Koda: Izberi vse

result = match("kloabcedanje", "efg") || match("43212345", "^4(.*)5$") || (match("12345", "34") && match("blabla", "etwas"));

vrne true

Koda: Izberi vse

result = match("kloabcedanje", "efg") || match("123456", "^4(.*)5$") || (match("12345", "34") && match("das is etwas gud", "etwas"));

mi vrne true

Koda: Izberi vse

result = match("kloabcedanje", "efg") || match("123456", "^4(.*)5$") || (match("123", "34") && match("das is etwas gud", "etwas"));

mi vrne false

Žal kode za moj evaluator ne morem deliti, pa tudi sicer je overblown.
Se pa implemetira precej preprosto. parsaš levi in desni operator in glede na precedenco odlagaš stvari v stack.

[tilz0R]

Match funkcija je simple. Bolj je kako efektivno moj string input pretvoriti v lepšo obliko za match. Da bo pidpiral je samo param1=nekaj, ampak tudi "param1 is null".

[Kroko]

Ni to noben problem oziroma ga ne vidim. Lahko ti naredim psevdokodo.

[Kroko]

Takole res na hitro. Je skoraj copy paste iz enega mojega projekta.

Koda: Izberi vse

const int EXPRESSION_STACK = 7; ta mora biti toliko velik kot imaš razlišnih precedenc na operatorjih. Jaz jih imam 7
double values[EXPRESSION_STACK];
BinaryOperatorEnum operators[EXPRESSION_STACK];
      
read_value(values[0]);
read_operator(operators[0]);

parse(string line)
{
   int stack_index = 1;
   while (operators[0] != BinaryOperatorEnum::CloseBracket)
   {
      read_value(line, values[stack_index]);
      read_operator(line, operators[stack_index]);
      if (precedence(operators[stack_index]) > precedence(operators[stack_index - 1]))
      {
         stack_index++;
         assert(stack_index < EXPRESSION_STACK);
      }
      else
      {
         while (precedence(operators[stack_index]) <= precedence(operators[stack_index - 1]))
         {
            exec_binary(values[stack_index - 1], operators[stack_index - 1], values[stack_index]));
            operators[stack_index - 1] = operators[stack_index];
            if ((stack_index > 1) && (precedence(operators[stack_index - 1]) <= precedence(operators[stack_index - 2])))
               stack_index--;
            else
               break;
         }
      }
   }
   result = values[0];
}

void read_value(string line, double& value)
{
   parse next token from line
   if (token is number)
      value = token
      return;
      
   if (token is '(')
      read newline until matching ')'
      parse(newline)
      return;
   
   switch (token)
   case "match"
      parse and execute match function
   case "isnull"
      parse and execute isnull function

}
void read_operator(string line, BinaryOperatorEnum& oper)
{
   parse next token from line
   
   switch (token)
   case "OR": oper = OR
   case "AND": oper = AND
}

int precedence(BinaryOperatorEnum oper)
{
   switch (oper)
   case OR: return 2
   case ANd: return 3
}

void exec_binary(double& left, BinaryOperatorEnum oper, double right)
{
   switch (oper)
   case OR: left = (left || right);
   case ANd: left = (left && right);      
}


[tilz0R]

Tvoj koncept mi je všeč.

Medtem je glava bolj sveža, in sem razmišljal, da bi namesto "column1 is null and column2 gt 3" naredil kot ima Excel, ala: AND(ISNULL(column1),GT(column2,3))

Tako bi bila sintaksa zelo dobro definirana, poleg tega večina programerjev/engineerjev pozna excel (jim sintaksa ni tuja), in se tudi znebiš random string processing.

Kaj praviš?

[Kroko]

To je sicer povsem OK in tudi jaz imam vse binarne operatorje implementirane tudi kot funkcije.
Je pa mnogo bolj nepregledno in težje za sestavljat. Če bodo izrazi kompleksni potem so klasični binarni operatorji lažji za delo z njimi.

Tole:
ISNULL(column1) && (column2 > 3)
je veliko bolj pregledno kot:
AND(ISNULL(column1),GT(column2,3))

Dela pa ni toliko več. v read_value funkciji je vse to implementirano:
String bereš znan po znak in ignoriraš whitespace. Zapomniš si trenutno pozicijo. se pravi če imaš:

Koda: Izberi vse

double read_value()
{
   while (iswhitespace(line[pos]))
     pos++;
    
   if (line[pos] == '+' && isdigit(line[pos+1])) //read numbers with + in front
   {
      pos++;
      result = read_value();
      return;
   }
   
   if (line[pos] == '-' && isdigit(line[pos+1])) //read numbers with - in front
   {
      pos++;
      result = -read_value();
      return;
   }
   
   if (line[pos] == '(')
   {
      result = parse(); // to funkcijo imam jaz poimenovano read_expression
      return;
   }
   
   if (isletter(line[pos]))
   {
      result = read_function();
      return;
   }
   
   result = read_number();
}

double read_number()
{
   while(isdigit(line[pos])
   {
      add digit to result
      upoštevaj še decimalno piko
      pos++;
   }
   return result
}

double read_function()
{
   while(isletter(line[pos])
   {
      functionname += line[pos];
      pos++;
   }
   
   switch (functionname)
   case "and":
     function = AND;
     numargs = 2;
   case "isnull":
     function = ISNULL;
     numargs = 1;
   
   while (iswhitespace(line[pos]))
     pos++;
    
   if (line[pos] != '(')
     ERROR;
    
   pos++; 
    
   //exec function
   double args[MAX];
   while (i < numargs)
   {
      while (iswhitespace(line[pos]))
         pos++;
       
      args[i] = read_value();
       
      while (iswhitespace(line[pos]))
         pos++;
    
      i++;
   }
   
   if (line[pos] != ')')
     ERROR;
    
   switch (function)
   case AND: result = args[0] && args[1];
   case ISNULL: result = std::isfinite(args[0]);
      
   pos++;
   
   return result;
}



[Kroko]

Lahko si narediš tak generičen evaluator, ki ima implementirane vse matematične operatorje in funkcije in ti bo služil celo življenje. Samo dodajaš funkcije po potrebi.

[tilz0R]

Tak na hitro - konceptualno, sem naredil en parser, ki sparsa mojo sintakso (ala Excel).

Koda: Izberi vse

#include <stdint.h>
#include <stdio.h>

#define GET_CH()                                                               \
  do {                                                                         \
    c_prev = c;                                                                \
    c = **str;                                                                 \
    (*str)++;                                                                  \
  } while (0)

void parse_condition_string(const char **str, uint32_t level) {
  const char *start = *str;
  char c, c_prev;
  char tok[30];
  size_t tok_index = 0;
  size_t argument_index = 0;

  while (**str != 0) {
    GET_CH();

    if (c == '(') {
      printf("%.*s%.*s(\r\n", (int)level, "\t\t\t\t\t\t\t\t", *str - start - 1,
             start);
      start = *str;
      parse_condition_string(str, level + 1);
      printf("%.*s)\r\n", (int)level, "\t\t\t\t\t\t\t\t");
      start = *str;
    } else if (c == ')') {
      size_t len = *str - start - 1;
      if (len > 0) {
        printf("%.*s%.*s\r\n", (int)level, "\t\t\t\t\t\t\t\t", len, start);
      }
      return;
    } else if (c == ',') {
      size_t len = *str - start - 1;
      if (len > 0) {
        printf("%.*s%.*s\r\n", (int)level, "\t\t\t\t\t\t\t\t", len, start);
      }
      ++argument_index;
      start = *str;
    } else if (c == '"') {
      tok[tok_index] = c;
      tok[++tok_index] = 0;
      do {
        GET_CH();
        tok[tok_index] = c;
        tok[++tok_index] = 0;
        if (c == '\0' || c == '"') {
          break;
        }
      } while (1);
      /* Parse as string util " is again detected...*/
    } else {
      tok[tok_index] = c;
      tok[++tok_index] = 0;
    }
    c_prev = c;
  }
}

int main(void) {
  const char *condition =
      "AND(EQUAL(column1,\"abc\"),NOTEMPTY(column2),ISBRS(),OR(MATCH(column3,"
      "\"^3(.*)$\",AND(ISEMPTY(column7),NOTEMPTY(column8)))))";
  const char *c = condition;
  printf("CONDITION: %s\r\n\r\n", condition);
  parse_condition_string(&c, 0);
  return 0;
}


Z vhodnim podatkom (isti kot na sliki):

Koda: Izberi vse

AND(EQUAL(column1,"abc"),NOTEMPTY(column2),ISBRS(),OR(MATCH(column3,"^3(.*)$",AND(ISEMPTY(column7),NOTEMPTY(column8)))))

Zgenerira:

Koda: Izberi vse

AND(
    EQUAL(
        column1
        "abc"
    )
    NOTEMPTY(
        column2
    )
    ISBRS(
    )
    OR(
        MATCH(
            column3
            "^3(.*)$"
            AND(
                ISEMPTY(
                    column7
                )
                NOTEMPTY(
                    column8
                )
            )
        )
    )
)


[Kroko]

Odlično!