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 provides {
  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_buf[128];
  63         char *str_ptr;
  64 };
  65
  66 struct jp_opcode *_jp_alloc_op(struct jp_state *s, int type, int num, char *str, ...);
  67 #define jp_alloc_op(type, num, str, ...) _jp_alloc_op(s, type, num, str, ##__VA_ARGS__, NULL)
  68
  69 struct jp_state *jp_parse(const char *expr);
  70 void jp_free(struct jp_state *s);
  71
  72 #endif
  73
  74 }
  75
  76 %union {
  77         struct jp_opcode *op;
  78 }
  79
  80
  81 %token T_ROOT T_THIS T_DOT T_BROPEN T_BRCLOSE
  82 %token T_OR T_AND T_LT T_LE T_GT T_GE T_EQ T_NE T_POPEN T_PCLOSE T_NOT
  83
  84 %token <op> T_BOOL T_NUMBER T_STRING T_LABEL T_WILDCARD
  85
  86 %type <op> expr path segments segment or_exps or_exp and_exps and_exp cmp_exp unary_exp
  87
  88 %error-verbose
  89
  90 %%
  91
  92 input
  93         : expr                                                  { s->path = $1; }
  94         ;
  95
  96 expr
  97         : T_LABEL T_EQ path                             { $1->down = $3; $$ = $1; }
  98         | path                                                  { $$ = $1; }
  99         ;
 100
 101 path
 102         : T_ROOT segments                               { $$ = jp_alloc_op(T_ROOT, 0, NULL, $2); }
 103         | T_THIS segments                               { $$ = jp_alloc_op(T_THIS, 0, NULL, $2); }
 104         ;
 105
 106 segments
 107         : segments segment                              { $$ = append_op($1, $2); }
 108         | segment                                               { $$ = $1; }
 109         ;
 110
 111 segment
 112         : T_DOT T_LABEL                                 { $$ = $2; }
 113         | T_DOT T_WILDCARD                              { $$ = $2; }
 114         | T_BROPEN or_exps T_BRCLOSE    { $$ = $2; }
 115         ;
 116
 117 or_exps
 118         : or_exp                                                { $$ = $1->sibling ? jp_alloc_op(T_OR, 0, NULL, $1) : $1; }
 119         ;
 120
 121 or_exp
 122         : or_exp T_OR and_exps                  { $$ = append_op($1, $3); }
 123         | and_exps                                              { $$ = $1; }
 124         ;
 125
 126 and_exps
 127         : and_exp                                               { $$ = $1->sibling ? jp_alloc_op(T_AND, 0, NULL, $1) : $1; }
 128         ;
 129
 130 and_exp
 131         : and_exp T_AND cmp_exp                 { $$ = append_op($1, $3); }
 132         | cmp_exp                                               { $$ = $1; }
 133         ;
 134
 135 cmp_exp
 136         : unary_exp T_LT unary_exp              { $$ = jp_alloc_op(T_LT, 0, NULL, $1, $3); }
 137         | unary_exp T_LE unary_exp              { $$ = jp_alloc_op(T_LE, 0, NULL, $1, $3); }
 138         | unary_exp T_GT unary_exp              { $$ = jp_alloc_op(T_GT, 0, NULL, $1, $3); }
 139         | unary_exp T_GE unary_exp              { $$ = jp_alloc_op(T_GE, 0, NULL, $1, $3); }
 140         | unary_exp T_EQ unary_exp              { $$ = jp_alloc_op(T_EQ, 0, NULL, $1, $3); }
 141         | unary_exp T_NE unary_exp              { $$ = jp_alloc_op(T_NE, 0, NULL, $1, $3); }
 142         | unary_exp                                             { $$ = $1; }
 143         ;
 144
 145 unary_exp
 146         : T_BOOL                                                { $$ = $1; }
 147         | T_NUMBER                                              { $$ = $1; }
 148         | T_STRING                                              { $$ = $1; }
 149         | T_WILDCARD                                    { $$ = $1; }
 150         | T_POPEN or_exps T_PCLOSE              { $$ = $2; }
 151         | T_NOT unary_exp                               { $$ = jp_alloc_op(T_NOT, 0, NULL, $2); }
 152         | path                                                  { $$ = $1; }
 153         ;
 154
 155 %%
 156
 157 void
 158 yyerror(struct jp_state *s, const char *msg)
 159 {
 160         s->error = msg;
 161 }
 162
 163 static struct jp_opcode *
 164 append_op(struct jp_opcode *a, struct jp_opcode *b)
 165 {
 166         struct jp_opcode *tail = a;
 167
 168         while (tail->sibling)
 169                 tail = tail->sibling;
 170
 171         tail->sibling = b;
 172
 173         return a;
 174 }
 175
 176 struct jp_opcode *
 177 _jp_alloc_op(struct jp_state *s, int type, int num, char *str, ...)
 178 {
 179         va_list ap;
 180         char *ptr;
 181         struct jp_opcode *newop, *child;
 182
 183         newop = calloc_a(sizeof(*newop),
 184                          str ? &ptr : NULL, str ? strlen(str) + 1 : 0);
 185
 186         if (!newop)
 187         {
 188                 fprintf(stderr, "Out of memory\n");
 189                 exit(1);
 190         }
 191
 192         newop->type = type;
 193         newop->num = num;
 194
 195         if (str)
 196                 newop->str = strcpy(ptr, str);
 197
 198         va_start(ap, str);
 199
 200         while ((child = va_arg(ap, void *)) != NULL)
 201                 if (!newop->down)
 202                         newop->down = child;
 203                 else
 204                         append_op(newop->down, child);
 205
 206         va_end(ap);
 207
 208         newop->next = s->pool;
 209         s->pool = newop;
 210
 211         return newop;
 212 }
 213
 214 struct jp_state *
 215 jp_parse(const char *expr)
 216 {
 217         struct jp_state *s;
 218
 219         s = calloc(1, sizeof(*s));
 220
 221         if (!s)
 222                 return NULL;
 223
 224         yy_scan_string(expr);
 225
 226         if (yyparse(s))
 227                 s->path = NULL;
 228
 229         yylex_destroy();
 230
 231         return s;
 232 }
 233
 234 void
 235 jp_free(struct jp_state *s)
 236 {
 237         struct jp_opcode *op, *tmp;
 238
 239         for (op = s->pool; op;)
 240         {
 241                 tmp = op->next;
 242                 free(op);
 243                 op = tmp;
 244         }
 245
 246         free(s);
 247 }