lib/command_parse.y

   1 /*
   2  * Command format string parser.
   3  *
   4  * Turns a command definition into a DFA that together with the functions
   5  * provided in command_match.c may be used to map command line input to a
   6  * function.
   7  *
   8  * @author Quentin Young <qlyoung@cumulusnetworks.com>
   9  */
  10
  11 %{
  12 extern int yylex(void);
  13 extern void yyerror(const char *);
  14
  15 // compile with debugging facilities
  16 #define YYDEBUG 1
  17 %}
  18 %code requires {
  19   #include "command.h"
  20   #include "command_graph.h"
  21   #include "memory.h"
  22 }
  23 %code provides {
  24   extern void
  25   set_buffer_string(const char *);
  26   struct graph_node *
  27   parse_command_format(struct graph_node *, struct cmd_element *);
  28 }
  29
  30
  31 /* valid types for tokens */
  32 %union{
  33   signed long long integer;
  34   char *string;
  35   struct graph_node *node;
  36 }
  37
  38 /* some helpful state variables */
  39 %{
  40 struct graph_node *startnode,       // command root node
  41                   *currnode,        // current node
  42                   *seqhead;         // sequence head
  43
  44
  45 struct graph_node *optnode_start,   // start node for option set
  46                   *optnode_end;     // end node for option set
  47
  48 struct graph_node *selnode_start,   // start node for selector set
  49                   *selnode_end;     // end node for selector set
  50
  51 struct cmd_element *command;        // command we're parsing
  52 %}
  53
  54 %token <string> WORD
  55 %token <string> IPV4
  56 %token <string> IPV4_PREFIX
  57 %token <string> IPV6
  58 %token <string> IPV6_PREFIX
  59 %token <string> VARIABLE
  60 %token <string> RANGE
  61 %token <integer> NUMBER
  62
  63 %type <node> start
  64 %type <node> sentence_root
  65 %type <node> literal_token
  66 %type <node> placeholder_token
  67 %type <node> option
  68 %type <node> option_token
  69 %type <node> option_token_seq
  70 %type <node> selector
  71 %type <node> selector_element_root
  72 %type <node> selector_token
  73 %type <node> selector_token_seq
  74
  75 %defines "command_parse.h"
  76 %output "command_parse.c"
  77
  78 /* grammar proper */
  79 %%
  80
  81 start: sentence_root
  82        cmd_token_seq
  83 {
  84   // create leaf node
  85   struct graph_node *end = new_node(END_GN);
  86   end->element = command;
  87
  88   // add node
  89   if (add_node(currnode, end) != end)
  90   {
  91     yyerror("Duplicate command.");
  92     YYABORT;
  93   }
  94   fprintf(stderr, "Parsed full command successfully.\n");
  95 }
  96
  97 sentence_root: WORD
  98 {
  99   struct graph_node *root = new_node(WORD_GN);
 100   root->text = XSTRDUP(MTYPE_CMD_TOKENS, $1);
 101
 102   currnode = add_node(startnode, root);
 103   if (currnode != root)
 104     free (root);
 105
 106   free ($1);
 107   $$ = currnode;
 108 };
 109
 110 /* valid top level tokens */
 111 cmd_token:
 112   placeholder_token
 113 {
 114   currnode = add_node(currnode, $1);
 115   if (currnode != $1)
 116     free_node ($1);
 117 }
 118 | literal_token
 119 {
 120   currnode = add_node(currnode, $1);
 121   if (currnode != $1)
 122     free_node ($1);
 123 }
 124 /* selectors and options are subgraphs with start and end nodes */
 125 | selector
 126 {
 127   add_node(currnode, $1);
 128   currnode = selnode_end;
 129   selnode_start = selnode_end = NULL;
 130 }
 131 | option
 132 {
 133   add_node(currnode, $1);
 134   currnode = optnode_end;
 135   optnode_start = optnode_end = NULL;
 136 }
 137 ;
 138
 139 cmd_token_seq:
 140   %empty
 141 | cmd_token_seq cmd_token
 142 ;
 143
 144 placeholder_token:
 145   IPV4
 146 {
 147   $$ = new_node(IPV4_GN);
 148   $$->text = XSTRDUP(MTYPE_CMD_TOKENS, $1);
 149   free ($1);
 150 }
 151 | IPV4_PREFIX
 152 {
 153   $$ = new_node(IPV4_PREFIX_GN);
 154   $$->text = XSTRDUP(MTYPE_CMD_TOKENS, $1);
 155   free ($1);
 156 }
 157 | IPV6
 158 {
 159   $$ = new_node(IPV6_GN);
 160   $$->text = XSTRDUP(MTYPE_CMD_TOKENS, $1);
 161   free ($1);
 162 }
 163 | IPV6_PREFIX
 164 {
 165   $$ = new_node(IPV6_PREFIX_GN);
 166   $$->text = XSTRDUP(MTYPE_CMD_TOKENS, $1);
 167   free ($1);
 168 }
 169 | VARIABLE
 170 {
 171   $$ = new_node(VARIABLE_GN);
 172   $$->text = XSTRDUP(MTYPE_CMD_TOKENS, $1);
 173   free ($1);
 174 }
 175 | RANGE
 176 {
 177   $$ = new_node(RANGE_GN);
 178   $$->text = XSTRDUP(MTYPE_CMD_TOKENS, $1);
 179
 180   // get the numbers out
 181   strsep(&yylval.string, "(-)");
 182   char *endptr;
 183   $$->min = strtoll( strsep(&yylval.string, "(-)"), &endptr, 10 );
 184   $$->max = strtoll( strsep(&yylval.string, "(-)"), &endptr, 10 );
 185
 186   free ($1);
 187 }
 188 ;
 189
 190 literal_token:
 191   WORD
 192 {
 193   $$ = new_node(WORD_GN);
 194   $$->text = XSTRDUP(MTYPE_CMD_TOKENS, $1);
 195   free ($1);
 196 }
 197 | NUMBER
 198 {
 199   $$ = new_node(NUMBER_GN);
 200   $$->value = yylval.integer;
 201 }
 202 ;
 203
 204 /* <selector|set> productions */
 205 selector:
 206   '<' selector_part '|' selector_element '>'
 207 {
 208   // all the graph building is done in selector_element,
 209   // so just return the selector subgraph head
 210   $$ = selnode_start;
 211 };
 212
 213 selector_part:
 214   selector_part '|' selector_element
 215 | selector_element
 216 ;
 217
 218 selector_element:
 219   selector_element_root selector_token_seq
 220 {
 221   // if the selector start and end do not exist, create them
 222   if (!selnode_start || !selnode_end) {     // if one is null
 223     assert(!selnode_start && !selnode_end); // both should be null
 224     selnode_start = new_node(SELECTOR_GN);  // diverging node
 225     selnode_end = new_node(NUL_GN);         // converging node
 226     selnode_start->end = selnode_end;       // duh
 227   }
 228
 229   // add element head as a child of the selector
 230   add_node(selnode_start, $1);
 231
 232   if ($2->type != NUL_GN) {
 233     add_node($1, seqhead);
 234     add_node($2, selnode_end);
 235   }
 236   else
 237     add_node($1, selnode_end);
 238
 239   seqhead = NULL;
 240 }
 241
 242 selector_token_seq:
 243   %empty { $$ = new_node(NUL_GN); }
 244 | selector_token_seq selector_token
 245 {
 246   // if the sequence component is NUL_GN, this is a sequence start
 247   if ($1->type == NUL_GN) {
 248     assert(!seqhead); // sequence head should always be null here
 249     seqhead = $2;
 250   }
 251   else // chain on new node
 252     add_node($1, $2);
 253
 254   $$ = $2;
 255 }
 256 ;
 257
 258 selector_element_root:
 259   literal_token
 260 | placeholder_token
 261 ;
 262
 263 selector_token:
 264   selector_element_root
 265 | option
 266 ;
 267
 268 /* [option|set] productions */
 269 option: '[' option_part ']'
 270 {
 271   // add null path
 272   struct graph_node *nullpath = new_node(NUL_GN);
 273   add_node(optnode_start, nullpath);
 274   add_node(nullpath, optnode_end);
 275
 276   $$ = optnode_start;
 277 };
 278
 279 option_part:
 280   option_part '|' option_element
 281 | option_element
 282 ;
 283
 284 option_element:
 285   option_token_seq
 286 {
 287   if (!optnode_start || !optnode_end) {
 288     assert(!optnode_start && !optnode_end);
 289     optnode_start = new_node(OPTION_GN);
 290     optnode_end = new_node(NUL_GN);
 291   }
 292
 293   add_node(optnode_start, seqhead);
 294   add_node($1, optnode_end);
 295 }
 296
 297 option_token_seq:
 298   option_token
 299 { $$ = seqhead = $1; }
 300 | option_token_seq option_token
 301 { $$ = add_node($1, $2); }
 302 ;
 303
 304 option_token:
 305   literal_token
 306 | placeholder_token
 307 ;
 308
 309 %%
 310
 311 void yyerror(char const *message) {
 312   // fail on bad parse
 313   fprintf(stderr, "Grammar error: %s\n", message);
 314   fprintf(stderr, "Token on error: ");
 315   if (yylval.string) fprintf(stderr, "%s\n", yylval.string);
 316   else if (yylval.node) fprintf(stderr, "%s\n", yylval.node->text);
 317   else fprintf(stderr, "%lld\n", yylval.integer);
 318
 319 }
 320
 321 struct graph_node *
 322 parse_command_format(struct graph_node *start, struct cmd_element *cmd)
 323 {
 324   fprintf(stderr, "parsing: %s\n", cmd->string);
 325
 326   /* clear state pointers */
 327   startnode = start;
 328   currnode = seqhead = NULL;
 329   selnode_start = selnode_end = NULL;
 330   optnode_start = optnode_end = NULL;
 331
 332   // trace parser
 333   yydebug = 0;
 334   // command string
 335   command = cmd;
 336   // make flex read from a string
 337   set_buffer_string(command->string);
 338   // parse command into DFA
 339   yyparse();
 340   // startnode points to command DFA
 341   return startnode;
 342 }