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 <stdarg.h>
  19 #include <libubox/utils.h>
  20
  21 #include "lexer.h"
  22 #include "parser.h"
  23
  24 static struct jp_opcode *op_pool = NULL;
  25 static struct jp_opcode *append_op(struct jp_opcode *a, struct jp_opcode *b);
  26
  27 int yyparse(struct jp_opcode **tree, const char **error);
  28 void yyerror(struct jp_opcode **expr, const char **error, const char *msg);
  29
  30 %}
  31
  32 %output  "parser.c"
  33 %defines "parser.h"
  34
  35 %parse-param { struct jp_opcode **expr }
  36 %parse-param { const char **error }
  37
  38 %code provides {
  39
  40 #ifndef JP_OPCODE
  41 # define JP_OPCODE
  42         struct jp_opcode {
  43                 int type;
  44                 struct jp_opcode *next;
  45                 struct jp_opcode *down;
  46                 struct jp_opcode *sibling;
  47                 char *str;
  48                 int num;
  49         };
  50 #endif
  51
  52 struct jp_opcode *_jp_alloc_op(int type, int num, char *str, ...);
  53 #define jp_alloc_op(type, num, str, ...) _jp_alloc_op(type, num, str, ##__VA_ARGS__, NULL)
  54
  55 struct jp_opcode *jp_parse(const char *expr, const char **error);
  56 void jp_free(void);
  57
  58 }
  59
  60 %union {
  61         struct jp_opcode *op;
  62 }
  63
  64
  65 %token T_ROOT T_THIS T_DOT T_BROPEN T_BRCLOSE
  66 %token T_OR T_AND T_LT T_LE T_GT T_GE T_EQ T_NE T_POPEN T_PCLOSE T_NOT
  67
  68 %token <op> T_BOOL T_NUMBER T_STRING T_LABEL T_WILDCARD
  69
  70 %type <op> expr path segments segment or_exps or_exp and_exps and_exp cmp_exp unary_exp
  71
  72 %error-verbose
  73
  74 %%
  75
  76 input
  77         : expr                                                  { *expr = $1; }
  78         ;
  79
  80 expr
  81         : T_LABEL T_EQ path                             { $1->down = $3; $$ = $1; }
  82         | path                                                  { $$ = $1; }
  83         ;
  84
  85 path
  86         : T_ROOT segments                               { $$ = jp_alloc_op(T_ROOT, 0, NULL, $2); }
  87         | T_THIS segments                               { $$ = jp_alloc_op(T_THIS, 0, NULL, $2); }
  88         ;
  89
  90 segments
  91         : segments segment                              { $$ = append_op($1, $2); }
  92         | segment                                               { $$ = $1; }
  93         ;
  94
  95 segment
  96         : T_DOT T_LABEL                                 { $$ = $2; }
  97         | T_DOT T_WILDCARD                              { $$ = $2; }
  98         | T_BROPEN or_exps T_BRCLOSE    { $$ = $2; }
  99         ;
 100
 101 or_exps
 102         : or_exp                                                { $$ = $1->sibling ? jp_alloc_op(T_OR, 0, NULL, $1) : $1; }
 103         ;
 104
 105 or_exp
 106         : or_exp T_OR and_exps                  { $$ = append_op($1, $3); }
 107         | and_exps                                              { $$ = $1; }
 108         ;
 109
 110 and_exps
 111         : and_exp                                               { $$ = $1->sibling ? jp_alloc_op(T_AND, 0, NULL, $1) : $1; }
 112         ;
 113
 114 and_exp
 115         : and_exp T_AND cmp_exp                 { $$ = append_op($1, $3); }
 116         | cmp_exp                                               { $$ = $1; }
 117         ;
 118
 119 cmp_exp
 120         : unary_exp T_LT unary_exp              { $$ = jp_alloc_op(T_LT, 0, NULL, $1, $3); }
 121         | unary_exp T_LE unary_exp              { $$ = jp_alloc_op(T_LE, 0, NULL, $1, $3); }
 122         | unary_exp T_GT unary_exp              { $$ = jp_alloc_op(T_GT, 0, NULL, $1, $3); }
 123         | unary_exp T_GE unary_exp              { $$ = jp_alloc_op(T_GE, 0, NULL, $1, $3); }
 124         | unary_exp T_EQ unary_exp              { $$ = jp_alloc_op(T_EQ, 0, NULL, $1, $3); }
 125         | unary_exp T_NE unary_exp              { $$ = jp_alloc_op(T_NE, 0, NULL, $1, $3); }
 126         | unary_exp                                             { $$ = $1; }
 127         ;
 128
 129 unary_exp
 130         : T_BOOL                                                { $$ = $1; }
 131         | T_NUMBER                                              { $$ = $1; }
 132         | T_STRING                                              { $$ = $1; }
 133         | T_WILDCARD                                    { $$ = $1; }
 134         | T_POPEN or_exps T_PCLOSE              { $$ = $2; }
 135         | T_NOT unary_exp                               { $$ = jp_alloc_op(T_NOT, 0, NULL, $2); }
 136         | path                                                  { $$ = $1; }
 137         ;
 138
 139 %%
 140
 141 void
 142 yyerror(struct jp_opcode **expr, const char **error, const char *msg)
 143 {
 144         *error = msg;
 145         jp_free();
 146 }
 147
 148 static struct jp_opcode *
 149 append_op(struct jp_opcode *a, struct jp_opcode *b)
 150 {
 151         struct jp_opcode *tail = a;
 152
 153         while (tail->sibling)
 154                 tail = tail->sibling;
 155
 156         tail->sibling = b;
 157
 158         return a;
 159 }
 160
 161 struct jp_opcode *
 162 _jp_alloc_op(int type, int num, char *str, ...)
 163 {
 164         va_list ap;
 165         char *ptr;
 166         struct jp_opcode *newop, *child;
 167
 168         newop = calloc_a(sizeof(*newop),
 169                          str ? &ptr : NULL, str ? strlen(str) + 1 : 0);
 170
 171         if (!newop)
 172         {
 173                 fprintf(stderr, "Out of memory\n");
 174                 exit(1);
 175         }
 176
 177         newop->type = type;
 178         newop->num = num;
 179
 180         if (str)
 181                 newop->str = strcpy(ptr, str);
 182
 183         va_start(ap, str);
 184
 185         while ((child = va_arg(ap, void *)) != NULL)
 186                 if (!newop->down)
 187                         newop->down = child;
 188                 else
 189                         append_op(newop->down, child);
 190
 191         va_end(ap);
 192
 193         newop->next = op_pool;
 194         op_pool = newop;
 195
 196         return newop;
 197 }
 198
 199 struct jp_opcode *
 200 jp_parse(const char *expr, const char **error)
 201 {
 202         void *buf;
 203         struct jp_opcode *tree;
 204
 205         buf = yy_scan_string(expr);
 206
 207         if (yyparse(&tree, error))
 208                 tree = NULL;
 209         else
 210                 *error = NULL;
 211
 212         yy_delete_buffer(buf);
 213         yylex_destroy();
 214
 215         return tree;
 216 }
 217
 218 void
 219 jp_free(void)
 220 {
 221         struct jp_opcode *op, *tmp;
 222
 223         for (op = op_pool; op;)
 224         {
 225                 tmp = op->next;
 226                 free(op);
 227                 op = tmp;
 228         }
 229
 230         op_pool = NULL;
 231 }