Switch to sqlite3's lemon parser generator.
[oweals/jsonpath.git] / parser.y
index 513fea6..9c06c07 100644 (file)
--- a/parser.y
+++ b/parser.y
@@ -1,4 +1,3 @@
-%{
 /*
  * Copyright (C) 2013-2014 Jo-Philipp Wich <jow@openwrt.org>
  *
  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  */
 
-#include <stdio.h>
+%token_type {struct jp_opcode *}
+%extra_argument {struct jp_state *s}
+
+%left T_AND.
+%left T_OR.
+%left T_UNION.
+%nonassoc T_EQ T_NE T_GT T_GE T_LT T_LE.
+%right T_NOT.
+
+%include {
+#include <assert.h>
+#include <stddef.h>
 #include <stdlib.h>
-#include <stdarg.h>
 #include <string.h>
 
-#include <libubox/utils.h>
-
+#include "ast.h"
+#include "lexer.h"
 #include "parser.h"
 
-static struct jp_opcode *append_op(struct jp_opcode *a, struct jp_opcode *b);
-
-int yylex(struct jp_state *s);
-void *yy_scan_string (const char *str);
-int yylex_destroy(void);
-
-int yyparse(struct jp_state *s);
-void yyerror(struct jp_state *s, const char *msg);
-
-%}
-
-%output  "parser.c"
-%defines "parser.h"
-
-%parse-param { struct jp_state *s }
-%lex-param { struct jp_state *s }
-
-%code requires {
-
-#ifndef __PARSER_H_
-#define __PARSER_H_
-
-struct jp_opcode {
-       int type;
-       struct jp_opcode *next;
-       struct jp_opcode *down;
-       struct jp_opcode *sibling;
-       char *str;
-       int num;
-};
-
-struct jp_state {
-       struct jp_opcode *pool;
-       struct jp_opcode *path;
-       char *error;
-       char str_quote;
-       char str_buf[128];
-       char *str_ptr;
-};
-
-struct jp_opcode *_jp_alloc_op(struct jp_state *s, int type, int num, char *str, ...);
-#define jp_alloc_op(type, num, str, ...) _jp_alloc_op(s, type, num, str, ##__VA_ARGS__, NULL)
-
-struct jp_state *jp_parse(const char *expr);
-void jp_free(struct jp_state *s);
-
-#endif
+#define alloc_op(type, num, str, ...) \
+       jp_alloc_op(s, type, num, str, ##__VA_ARGS__, NULL)
 
 }
 
-%union {
-       struct jp_opcode *op;
-}
-
-
-%token T_ROOT T_THIS T_DOT T_BROPEN T_BRCLOSE
-%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
-
-%token <op> T_BOOL T_NUMBER T_STRING T_LABEL T_WILDCARD
-
-%type <op> expr path segments segment union_exps union_exp or_exps or_exp and_exps and_exp cmp_exp unary_exp
-
-%error-verbose
-
-%%
-
-input
-       : expr                                                  { s->path = $1; }
-       ;
-
-expr
-       : T_LABEL T_EQ path                             { $1->down = $3; $$ = $1; }
-       | path                                                  { $$ = $1; }
-       ;
-
-path
-       : T_ROOT segments                               { $$ = jp_alloc_op(T_ROOT, 0, NULL, $2); }
-       | T_THIS segments                               { $$ = jp_alloc_op(T_THIS, 0, NULL, $2); }
-       ;
-
-segments
-       : segments segment                              { $$ = append_op($1, $2); }
-       | segment                                               { $$ = $1; }
-       ;
-
-segment
-       : T_DOT T_LABEL                                 { $$ = $2; }
-       | T_DOT T_WILDCARD                              { $$ = $2; }
-       | T_BROPEN union_exps T_BRCLOSE { $$ = $2; }
-       ;
-
-union_exps
-       : union_exp                                             { $$ = $1->sibling ? jp_alloc_op(T_UNION, 0, NULL, $1) : $1; }
-       ;
-
-union_exp
-       : union_exp T_UNION or_exps             { $$ = append_op($1, $3); }
-       | or_exps                                               { $$ = $1; }
-       ;
+%syntax_error {
+       int n = sizeof(tokennames) / sizeof(tokennames[0]);
+       int l = strlen("Expecting ");
+       int c = 0;
+       int i;
 
-or_exps
-       : or_exp                                                { $$ = $1->sibling ? jp_alloc_op(T_OR, 0, NULL, $1) : $1; }
-       ;
-
-or_exp
-       : or_exp T_OR and_exps                  { $$ = append_op($1, $3); }
-       | and_exps                                              { $$ = $1; }
-       ;
-
-and_exps
-       : and_exp                                               { $$ = $1->sibling ? jp_alloc_op(T_AND, 0, NULL, $1) : $1; }
-       ;
-
-and_exp
-       : and_exp T_AND cmp_exp                 { $$ = append_op($1, $3); }
-       | cmp_exp                                               { $$ = $1; }
-       ;
-
-cmp_exp
-       : unary_exp T_LT unary_exp              { $$ = jp_alloc_op(T_LT, 0, NULL, $1, $3); }
-       | unary_exp T_LE unary_exp              { $$ = jp_alloc_op(T_LE, 0, NULL, $1, $3); }
-       | unary_exp T_GT unary_exp              { $$ = jp_alloc_op(T_GT, 0, NULL, $1, $3); }
-       | unary_exp T_GE unary_exp              { $$ = jp_alloc_op(T_GE, 0, NULL, $1, $3); }
-       | unary_exp T_EQ unary_exp              { $$ = jp_alloc_op(T_EQ, 0, NULL, $1, $3); }
-       | unary_exp T_NE unary_exp              { $$ = jp_alloc_op(T_NE, 0, NULL, $1, $3); }
-       | unary_exp                                             { $$ = $1; }
-       ;
-
-unary_exp
-       : T_BOOL                                                { $$ = $1; }
-       | T_NUMBER                                              { $$ = $1; }
-       | T_STRING                                              { $$ = $1; }
-       | T_WILDCARD                                    { $$ = $1; }
-       | T_POPEN or_exps T_PCLOSE              { $$ = $2; }
-       | T_NOT unary_exp                               { $$ = jp_alloc_op(T_NOT, 0, NULL, $2); }
-       | path                                                  { $$ = $1; }
-       ;
-
-%%
-
-void
-yyerror(struct jp_state *s, const char *msg)
-{
-       s->error = strdup(msg);
-}
-
-static struct jp_opcode *
-append_op(struct jp_opcode *a, struct jp_opcode *b)
-{
-       struct jp_opcode *tail = a;
-
-       while (tail->sibling)
-               tail = tail->sibling;
-
-       tail->sibling = b;
-
-       return a;
-}
-
-struct jp_opcode *
-_jp_alloc_op(struct jp_state *s, int type, int num, char *str, ...)
-{
-       va_list ap;
-       char *ptr;
-       struct jp_opcode *newop, *child;
-
-       newop = calloc_a(sizeof(*newop),
-                        str ? &ptr : NULL, str ? strlen(str) + 1 : 0);
-
-       if (!newop)
+       for (i = 0; i < n; i++)
        {
-               fprintf(stderr, "Out of memory\n");
-               exit(127);
+               if (yy_find_shift_action(yypParser, (YYCODETYPE)i) < YYNSTATE + YYNRULE)
+                       l += strlen(tokennames[i]) + 4;
        }
 
-       newop->type = type;
-       newop->num = num;
-
-       if (str)
-               newop->str = strcpy(ptr, str);
-
-       va_start(ap, str);
+       s->error = malloc(l);
 
-       while ((child = va_arg(ap, void *)) != NULL)
-               if (!newop->down)
-                       newop->down = child;
-               else
-                       append_op(newop->down, child);
+       if (s->error)
+       {
+               s->erroff = s->off;
+               strcpy(s->error, "Expecting ");
+
+               for (i = 0; i < n; i++)
+               {
+                       if (yy_find_shift_action(yypParser, (YYCODETYPE)i) < YYNSTATE + YYNRULE)
+                       {
+                               if (c++)
+                                       strcat(s->error, " or ");
+
+                               strcat(s->error, tokennames[i]);
+                       }
+               }
+       }
+}
 
-       va_end(ap);
 
-       newop->next = s->pool;
-       s->pool = newop;
+input ::= expr(A).                                                                     { s->path = A; }
 
-       return newop;
-}
+expr(A) ::= T_LABEL(B) T_EQ path(C).                           { A = B; B->down = C; }
+expr(A) ::= path(B).                                                           { A = B; }
 
-struct jp_state *
-jp_parse(const char *expr)
-{
-       struct jp_state *s;
+path(A) ::= T_ROOT segments(B).                                                { A = alloc_op(T_ROOT, 0, NULL, B); }
+path(A) ::= T_THIS segments(B).                                                { A = alloc_op(T_THIS, 0, NULL, B); }
 
-       s = calloc(1, sizeof(*s));
+segments(A) ::= segments(B) segment(C).                                { A = append_op(B, C); }
+segments(A) ::= segment(B).                                                    { A = B; }
 
-       if (!s)
-               return NULL;
+segment(A) ::= T_DOT T_LABEL(B).                                       { A = B; }
+segment(A) ::= T_DOT T_WILDCARD(B).                                    { A = B; }
+segment(A) ::= T_BROPEN union_exps(B) T_BRCLOSE.       { A = B; }
 
-       yy_scan_string(expr);
+union_exps(A) ::= union_exp(B).                                                { A = B->sibling ? alloc_op(T_UNION, 0, NULL, B) : B; }
 
-       if (yyparse(s))
-               s->path = NULL;
+union_exp(A) ::= union_exp(B) T_UNION or_exps(C).      { A = append_op(B, C); }
+union_exp(A) ::= or_exps(B).                                           { A = B; }
 
-       yylex_destroy();
+or_exps(A) ::= or_exp(B).                                                      { A = B->sibling ? alloc_op(T_OR, 0, NULL, B) : B; }
 
-       return s;
-}
+or_exp(A) ::= or_exp(B) T_OR and_exps(C).                      { A = append_op(B, C); }
+or_exp(A) ::= and_exps(B).                                                     { A = B; }
 
-void
-jp_free(struct jp_state *s)
-{
-       struct jp_opcode *op, *tmp;
+and_exps(A) ::= and_exp(B).                                                    { A = B->sibling ? alloc_op(T_AND, 0, NULL, B) : B; }
 
-       for (op = s->pool; op;)
-       {
-               tmp = op->next;
-               free(op);
-               op = tmp;
-       }
+and_exp(A) ::= and_exp(B) T_AND cmp_exp(C).                    { A = append_op(B, C); }
+and_exp(A) ::= cmp_exp(B).                                                     { A = B; }
 
-       if (s->error)
-               free(s->error);
+cmp_exp(A) ::= unary_exp(B) T_LT unary_exp(C).         { A = alloc_op(T_LT, 0, NULL, B, C); }
+cmp_exp(A) ::= unary_exp(B) T_LE unary_exp(C).         { A = alloc_op(T_LE, 0, NULL, B, C); }
+cmp_exp(A) ::= unary_exp(B) T_GT unary_exp(C).         { A = alloc_op(T_GT, 0, NULL, B, C); }
+cmp_exp(A) ::= unary_exp(B) T_GE unary_exp(C).         { A = alloc_op(T_GE, 0, NULL, B, C); }
+cmp_exp(A) ::= unary_exp(B) T_EQ unary_exp(C).         { A = alloc_op(T_EQ, 0, NULL, B, C); }
+cmp_exp(A) ::= unary_exp(B) T_NE unary_exp(C).         { A = alloc_op(T_NE, 0, NULL, B, C); }
+cmp_exp(A) ::= unary_exp(B).                                           { A = B; }
 
-       free(s);
-}
+unary_exp(A) ::= T_BOOL(B).                                                    { A = B; }
+unary_exp(A) ::= T_NUMBER(B).                                          { A = B; }
+unary_exp(A) ::= T_STRING(B).                                          { A = B; }
+unary_exp(A) ::= T_WILDCARD(B).                                                { A = B; }
+unary_exp(A) ::= T_POPEN or_exps(B) T_PCLOSE.          { A = B; }
+unary_exp(A) ::= T_NOT unary_exp(B).                           { A = alloc_op(T_NOT, 0, NULL, B); }
+unary_exp(A) ::= path(B).                                                      { A = B; }