From 478bdaeb3b9699d2ceaa9607ef37166e7ca69faf Mon Sep 17 00:00:00 2001 From: Quentin Young Date: Sun, 17 Jul 2016 21:49:16 +0000 Subject: [PATCH] lib: Finish implementing grammar, DFA construction Signed-off-by: Quentin Young --- lib/cmdtree.h | 13 ++- lib/command_parse.y | 236 ++++++++++++++++++++++++++---------------- lib/grammar_sandbox.c | 56 ++++------ 3 files changed, 177 insertions(+), 128 deletions(-) diff --git a/lib/cmdtree.h b/lib/cmdtree.h index cdcf347006..e9a10d7ec5 100644 --- a/lib/cmdtree.h +++ b/lib/cmdtree.h @@ -20,13 +20,24 @@ struct graph_node { enum graph_node_type type; vector children; - int is_leaf, is_root; + int is_root; // true if first token in command + int is_leaf; // true if last token in command + int (*func)(struct vty *, int, const char *[]); + + /* various data fields for nodes */ + char* text; // for words and variables + int value; // for numbers + int start, end; // for ranges }; /* * Adds a child to a node. If the node already has the exact same * child, nothing is done. + * @param[in] parent node + * @param[in] child node + * @return the new child, or the existing child if the parent already has the + * new child */ extern struct graph_node * add_node(struct graph_node *, struct graph_node *); diff --git a/lib/command_parse.y b/lib/command_parse.y index e7efb0d5a8..1f519e27fa 100644 --- a/lib/command_parse.y +++ b/lib/command_parse.y @@ -3,12 +3,14 @@ extern int yylex(void); extern void yyerror(const char *); -extern int cmd_parse_format(const char *, const char *); -extern void set_buffer_string(const char *); // compile with debugging facilities #define YYDEBUG 1 %} +%code provides { +extern struct graph_node *cmd_parse_format_new(const char *, const char *); +extern void set_buffer_string(const char *); +} %union{ int integer; @@ -18,37 +20,39 @@ extern void set_buffer_string(const char *); %{ // last top-level node -struct graph_node *topnode, // command root node - *currnode; // current node +struct graph_node *startnode, // command root node + *currnode, // current node + *tmpnode, // temp node pointer + *seqhead; // sequence head + -struct graph_node *optnode_start, // start node for option set - *optnode_end, // end node for option set - *optnode_el; // start node for an option set element +struct graph_node *optnode_start = NULL, // start node for option set + *optnode_end = NULL; // end node for option set -struct graph_node *selnode_start, // start node for selector set - *selnode_end, // end node for selector set - *selnode_el; // start node for an selector set element +struct graph_node *selnode_start = NULL, // start node for selector set + *selnode_end = NULL; // end node for selector set %} -%token WORD -%token IPV4 -%token IPV4_PREFIX -%token IPV6 -%token IPV6_PREFIX -%token VARIABLE -%token RANGE -%token NUMBER +%token WORD +%token IPV4 +%token IPV4_PREFIX +%token IPV6 +%token IPV6_PREFIX +%token VARIABLE +%token RANGE +%token NUMBER %type start %type sentence_root %type literal_token %type placeholder_token -%type option_token -%type selector_token %type option +%type option_token +%type option_token_seq %type selector +%type selector_root +%type selector_token %type selector_token_seq -%type option_token_seq %defines "command_parse.h" %output "command_parse.c" @@ -60,28 +64,31 @@ start: sentence_root cmd_token_seq; sentence_root: WORD - { - currnode = new_node(WORD_GN); - currnode->is_root = 1; - add_node(topnode, currnode); - }; +{ + currnode = new_node(WORD_GN); + currnode->is_root = 1; + add_node(startnode, currnode); +}; /* valid top level tokens */ cmd_token: placeholder_token - { currnode = add_node(currnode, $1); } +{ currnode = add_node(currnode, $1); } | literal_token - { currnode = add_node(currnode, $1); } +{ currnode = add_node(currnode, $1); } +/* selectors and options are subgraphs with start and end nodes */ | selector - { - add_node(currnode, selnode_start); - currnode = selnode_end; - } +{ + add_node(currnode, $1); + currnode = selnode_end; + selnode_start = selnode_end = NULL; +} | option - { - add_node(currnode, optnode_start); - currnode = optnode_end; - } +{ + add_node(currnode, $1); + currnode = optnode_end; + optnode_start = optnode_end = NULL; +} ; cmd_token_seq: @@ -90,26 +97,52 @@ cmd_token_seq: ; placeholder_token: - IPV4 {$$ = new_node(IPV4_GN);} -| IPV4_PREFIX {$$ = new_node(IPV4_PREFIX_GN);} -| IPV6 {$$ = new_node(IPV6_GN);} -| IPV6_PREFIX {$$ = new_node(IPV6_PREFIX_GN);} -| VARIABLE {$$ = new_node(VARIABLE_GN);} -| RANGE {$$ = new_node(RANGE_GN);} + IPV4 +{ $$ = new_node(IPV4_GN); } +| IPV4_PREFIX +{ $$ = new_node(IPV4_PREFIX_GN); } +| IPV6 +{ $$ = new_node(IPV6_GN); } +| IPV6_PREFIX +{ $$ = new_node(IPV6_PREFIX_GN); } +| VARIABLE +{ $$ = new_node(VARIABLE_GN); } +| RANGE +{ + $$ = new_node(RANGE_GN); + + // get the numbers out + strsep(&yylval.string, "(-)"); + $$->start = atoi( strsep(&yylval.string, "(-)") ); + strsep(&yylval.string, "(-)"); + $$->end = atoi( strsep(&yylval.string, "(-)") ); + + // we could do this a variety of ways with either + // the lexer or the parser, but this is the simplest + // and involves the least amount of free() +} ; literal_token: - WORD {$$ = new_node(WORD_GN);} -| NUMBER {$$ = new_node(NUMBER_GN);} + WORD +{ + $$ = new_node(WORD_GN); + $$->text = strdup(yylval.string); +} +| NUMBER +{ + $$ = new_node(NUMBER_GN); + $$->value = yylval.integer; +} ; /* productions */ selector: - '<' selector_part '|' - selector_element '>' + '<' selector_part '|' selector_element '>' { - $$ = new_node(SELECTOR_GN); - // attach subtree here + // all the graph building is done in selector_element, + // so just return the selector subgraph head + $$ = selnode_start; }; selector_part: @@ -118,90 +151,115 @@ selector_part: ; selector_element: - WORD selector_token_seq; + selector_root selector_token_seq +{ + // if the selector start and end do not exist, create them + if (!selnode_start || !selnode_end) { // if one is null + assert(!selnode_start && !selnode_end); // both should be null + selnode_start = new_node(SELECTOR_GN); // diverging node + selnode_end = new_node(NUL_GN); // converging node + } + + // add element head as a child of the selector + add_node(selnode_start, $1); + + if ($2->type != NUL_GN) { + add_node($1, seqhead); + add_node($2, selnode_end); + } + else + add_node($1, selnode_end); + + seqhead = NULL; +} selector_token_seq: - %empty {$$ = NULL;} + %empty { $$ = new_node(NUL_GN); } | selector_token_seq selector_token { - currnode = add_node(currnode, $2); + // if the sequence component is NUL_GN, this is a sequence start + if ($1->type == NUL_GN) { + assert(!seqhead); // sequence head should always be null here + seqhead = $2; + } + else // chain on new node + add_node($1, $2); + + $$ = $2; } ; -selector_token: +selector_root: literal_token | placeholder_token +; + +selector_token: + selector_root | option ; /* [option|set] productions */ option: '[' option_part ']' -{ - $$ = new_node(OPTION_GN); - // attach subtree here -}; +{ $$ = optnode_start; }; option_part: - option_part '|' option_token_seq -| option_token_seq + option_part '|' option_element +| option_element ; -option_token_seq: - option_token_seq option_token -| option_token +option_element: + option_token_seq { - printf("Matched singular option token in sequence, type: %d\n", $1->type); + if (!optnode_start || !optnode_end) { + assert(!optnode_start && !optnode_end); + optnode_start = new_node(OPTION_GN); + optnode_end = new_node(NUL_GN); + } + + add_node(optnode_start, seqhead); + add_node($1, optnode_end); } + +option_token_seq: + option_token +{ $$ = seqhead = $1; } +| option_token_seq option_token +{ $$ = add_node($1, $2); } ; option_token: literal_token -{ - // optnode_el points to root of option element - if (optnode_el == NULL) { - optnode_el = $1; - currnode = $1; - } - else - add_node(currnode, $1); -} | placeholder_token -{ - // optnode_el points to root of option element - if (optnode_el == NULL) { - optnode_el = $1; - currnode = $1; - } - else - add_node(currnode, $1); -} ; %% - +/* int main (void) { - yydebug = 1; const char* input = "show [random conf NAME] thing"; printf("Parsing:\n\t%s\n", input); - return cmd_parse_format(input, "description"); + return cmd_parse_format_new(input, "description"); } - +*/ void yyerror(char const *message) { printf("Grammar error: %s\n", message); exit(EXIT_FAILURE); } -int -cmd_parse_format(const char *string, const char *desc) +struct graph_node * +cmd_parse_format_new(const char *string, const char *desc) { + fprintf(stderr, "parsing: %s\n", string); + + yydebug = 1; // make flex read from a string set_buffer_string(string); // initialize the start node of this command dfa - topnode = new_node(NUL_GN); + startnode = new_node(NUL_GN); // parse command into DFA yyparse(); - // topnode points to command DFA - return 0; + // startnode points to command DFA + return startnode; } diff --git a/lib/grammar_sandbox.c b/lib/grammar_sandbox.c index c19be7f934..fd0eec02d6 100644 --- a/lib/grammar_sandbox.c +++ b/lib/grammar_sandbox.c @@ -1,53 +1,33 @@ #include "command.h" +#include "command_parse.h" #define GRAMMAR_STR "CLI grammar sandbox\n" -DEFUN (grammar_midkey_test, - grammar_midkey_test_cmd, - "grammar {one|two} test", +DEFUN (grammar_test, + grammar_test_cmd, + "grammar .COMMAND", GRAMMAR_STR - "First option\n" - "Second option\n" - "Test parameter to end string\n") + "command to pass to new parser\n") { - return CMD_SUCCESS; -} + size_t linesize = 0; + for (int i = 0; i < argc; i++) + linesize += strlen(argv[i]) + 1; -DEFUN (grammar_onemidkey_test, - grammar_onemidkey_test_cmd, - "grammar {onekey} test", - GRAMMAR_STR - "First option\n" - "Test parameter to end string\n") -{ - return CMD_SUCCESS; -} + char* cat = malloc(linesize); + cat[0] = '\0'; + for (int i = 0; i < argc; i++) { + strcat(cat, argv[i]); + if (i != argc) + strcat(cat, " "); + } -DEFUN (grammar_smashmouth_test, - grammar_smashmouth_test_cmd, - "grammar {smash MOUTH} test", - GRAMMAR_STR - "It ain't easy bein' cheesy\n" - "Test parameter to end string\n") -{ - return CMD_SUCCESS; -} + cmd_parse_format_new((const char*) cat, "lol"); -DEFUN (grammar_midopt_test, - grammar_midopt_test_cmd, - "grammar [option] test", - GRAMMAR_STR - "optional argument\n" - "Test parameter to end string\n") -{ - return CMD_SUCCESS; + return CMD_SUCCESS; } void grammar_sandbox_init(void); void grammar_sandbox_init() { - install_element (ENABLE_NODE, &grammar_midkey_test_cmd); - install_element (ENABLE_NODE, &grammar_onemidkey_test_cmd); - install_element (ENABLE_NODE, &grammar_midopt_test_cmd); - install_element (ENABLE_NODE, &grammar_smashmouth_test_cmd); + install_element (ENABLE_NODE, &grammar_test_cmd); } -- 2.39.5