parser.y

   1 %{
   2 /*
   3  * Copyright (C) 2013 Jo-Philipp Wich <jow@openwrt.org>
   4  *
   5  * Permission to use, copy, modify, and/or distribute this software for any
   6  * purpose with or without fee is hereby granted, provided that the above
   7  * copyright notice and this permission notice appear in all copies.
   8  *
   9  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  10  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  11  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  12  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  13  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  14  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  15  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  16  */
  17
  18 #include <stdio.h>
  19 #include <stdlib.h>
  20 #include <stdarg.h>
  21 #include <string.h>
  22
  23 #include <libubox/utils.h>
  24
  25 #include "parser.h"
  26
  27 static struct jp_opcode *append_op(struct jp_opcode *a, struct jp_opcode *b);
  28
  29 int yylex(struct jp_state *s);
  30 void *yy_scan_string (const char *str);
  31 int yylex_destroy(void);
  32
  33 int yyparse(struct jp_state *s);
  34 void yyerror(struct jp_state *s, const char *msg);
  35
  36 %}
  37
  38 %output  "parser.c"
  39 %defines "parser.h"
  40
  41 %parse-param { struct jp_state *s }
  42 %lex-param { struct jp_state *s }
  43
  44 %code requires {
  45
  46 #ifndef __PARSER_H_
  47 #define __PARSER_H_
  48
  49 struct jp_opcode {
  50         int type;
  51         struct jp_opcode *next;
  52         struct jp_opcode *down;
  53         struct jp_opcode *sibling;
  54         char *str;
  55         int num;
  56 };
  57
  58 struct jp_state {
  59         struct jp_opcode *pool;
  60         struct jp_opcode *path;
  61         const char *error;
  62         char str_quote;
  63         char str_buf[128];
  64         char *str_ptr;
  65 };
  66
  67 struct jp_opcode *_jp_alloc_op(struct jp_state *s, int type, int num, char *str, ...);
  68 #define jp_alloc_op(type, num, str, ...) _jp_alloc_op(s, type, num, str, ##__VA_ARGS__, NULL)
  69
  70 struct jp_state *jp_parse(const char *expr);
  71 void jp_free(struct jp_state *s);
  72
  73 #endif
  74
  75 }
  76
  77 %union {
  78         struct jp_opcode *op;
  79 }
  80
  81
  82 %token T_ROOT T_THIS T_DOT T_BROPEN T_BRCLOSE
  83 %token T_OR T_AND T_LT T_LE T_GT T_GE T_EQ T_NE T_POPEN T_PCLOSE T_NOT T_UNION
  84
  85 %token <op> T_BOOL T_NUMBER T_STRING T_LABEL T_WILDCARD
  86
  87 %type <op> expr path segments segment union_exps union_exp or_exps or_exp and_exps and_exp cmp_exp unary_exp
  88
  89 %error-verbose
  90
  91 %%
  92
  93 input
  94         : expr                                                  { s->path = $1; }
  95         ;
  96
  97 expr
  98         : T_LABEL T_EQ path                             { $1->down = $3; $$ = $1; }
  99         | path                                                  { $$ = $1; }
 100         ;
 101
 102 path
 103         : T_ROOT segments                               { $$ = jp_alloc_op(T_ROOT, 0, NULL, $2); }
 104         | T_THIS segments                               { $$ = jp_alloc_op(T_THIS, 0, NULL, $2); }
 105         ;
 106
 107 segments
 108         : segments segment                              { $$ = append_op($1, $2); }
 109         | segment                                               { $$ = $1; }
 110         ;
 111
 112 segment
 113         : T_DOT T_LABEL                                 { $$ = $2; }
 114         | T_DOT T_WILDCARD                              { $$ = $2; }
 115         | T_BROPEN union_exps T_BRCLOSE { $$ = $2; }
 116         ;
 117
 118 union_exps
 119         : union_exp                                             { $$ = $1->sibling ? jp_alloc_op(T_UNION, 0, NULL, $1) : $1; }
 120         ;
 121
 122 union_exp
 123         : union_exp T_UNION or_exps             { $$ = append_op($1, $3); }
 124         | or_exps                                               { $$ = $1; }
 125         ;
 126
 127 or_exps
 128         : or_exp                                                { $$ = $1->sibling ? jp_alloc_op(T_OR, 0, NULL, $1) : $1; }
 129         ;
 130
 131 or_exp
 132         : or_exp T_OR and_exps                  { $$ = append_op($1, $3); }
 133         | and_exps                                              { $$ = $1; }
 134         ;
 135
 136 and_exps
 137         : and_exp                                               { $$ = $1->sibling ? jp_alloc_op(T_AND, 0, NULL, $1) : $1; }
 138         ;
 139
 140 and_exp
 141         : and_exp T_AND cmp_exp                 { $$ = append_op($1, $3); }
 142         | cmp_exp                                               { $$ = $1; }
 143         ;
 144
 145 cmp_exp
 146         : unary_exp T_LT unary_exp              { $$ = jp_alloc_op(T_LT, 0, NULL, $1, $3); }
 147         | unary_exp T_LE unary_exp              { $$ = jp_alloc_op(T_LE, 0, NULL, $1, $3); }
 148         | unary_exp T_GT unary_exp              { $$ = jp_alloc_op(T_GT, 0, NULL, $1, $3); }
 149         | unary_exp T_GE unary_exp              { $$ = jp_alloc_op(T_GE, 0, NULL, $1, $3); }
 150         | unary_exp T_EQ unary_exp              { $$ = jp_alloc_op(T_EQ, 0, NULL, $1, $3); }
 151         | unary_exp T_NE unary_exp              { $$ = jp_alloc_op(T_NE, 0, NULL, $1, $3); }
 152         | unary_exp                                             { $$ = $1; }
 153         ;
 154
 155 unary_exp
 156         : T_BOOL                                                { $$ = $1; }
 157         | T_NUMBER                                              { $$ = $1; }
 158         | T_STRING                                              { $$ = $1; }
 159         | T_WILDCARD                                    { $$ = $1; }
 160         | T_POPEN or_exps T_PCLOSE              { $$ = $2; }
 161         | T_NOT unary_exp                               { $$ = jp_alloc_op(T_NOT, 0, NULL, $2); }
 162         | path                                                  { $$ = $1; }
 163         ;
 164
 165 %%
 166
 167 void
 168 yyerror(struct jp_state *s, const char *msg)
 169 {
 170         s->error = msg;
 171 }
 172
 173 static struct jp_opcode *
 174 append_op(struct jp_opcode *a, struct jp_opcode *b)
 175 {
 176         struct jp_opcode *tail = a;
 177
 178         while (tail->sibling)
 179                 tail = tail->sibling;
 180
 181         tail->sibling = b;
 182
 183         return a;
 184 }
 185
 186 struct jp_opcode *
 187 _jp_alloc_op(struct jp_state *s, int type, int num, char *str, ...)
 188 {
 189         va_list ap;
 190         char *ptr;
 191         struct jp_opcode *newop, *child;
 192
 193         newop = calloc_a(sizeof(*newop),
 194                          str ? &ptr : NULL, str ? strlen(str) + 1 : 0);
 195
 196         if (!newop)
 197         {
 198                 fprintf(stderr, "Out of memory\n");
 199                 exit(127);
 200         }
 201
 202         newop->type = type;
 203         newop->num = num;
 204
 205         if (str)
 206                 newop->str = strcpy(ptr, str);
 207
 208         va_start(ap, str);
 209
 210         while ((child = va_arg(ap, void *)) != NULL)
 211                 if (!newop->down)
 212                         newop->down = child;
 213                 else
 214                         append_op(newop->down, child);
 215
 216         va_end(ap);
 217
 218         newop->next = s->pool;
 219         s->pool = newop;
 220
 221         return newop;
 222 }
 223
 224 struct jp_state *
 225 jp_parse(const char *expr)
 226 {
 227         struct jp_state *s;
 228
 229         s = calloc(1, sizeof(*s));
 230
 231         if (!s)
 232                 return NULL;
 233
 234         yy_scan_string(expr);
 235
 236         if (yyparse(s))
 237                 s->path = NULL;
 238
 239         yylex_destroy();
 240
 241         return s;
 242 }
 243
 244 void
 245 jp_free(struct jp_state *s)
 246 {
 247         struct jp_opcode *op, *tmp;
 248
 249         for (op = s->pool; op;)
 250         {
 251                 tmp = op->next;
 252                 free(op);
 253                 op = tmp;
 254         }
 255
 256         free(s);
 257 }