bnf.c

   1 #include <grammar.h>
   2 #include <rdp.h>
   3 #include <scanner.h>
   4 #include <assert.h>
   5 #include <fcntl.h>
   6 #include <unistd.h>
   7 #include <stdlib.h>
   8
   9 typedef enum
  10   {
  11     NONE = 0,
  12     EQUAL = 1,
  13     ID = 2,
  14     STRING = 3,
  15     EOL = 4
  16   } token_t;
  17
  18 static gint bnf_scanner_next (scanner_t* scanner, GString** val)
  19 {
  20
  21   int state;
  22   int start;
  23   int stop;
  24   int i;
  25   gchar* buffer;
  26   GString* lexeme;
  27
  28   state = NONE;
  29   start = 0;
  30   stop = 0;
  31   buffer = malloc (256);
  32
  33   for (i = 0; stop == 0; i++)
  34     {
  35
  36       gchar c;
  37
  38       if (scanner->buffer->len == i)
  39         {
  40           int r;
  41           r = scanner->cb (scanner->data, buffer, 256);
  42           if (r == 0)
  43             g_string_append_c (scanner->buffer, 0);
  44           else
  45             g_string_append_len (scanner->buffer, buffer, r);
  46         }
  47
  48       c = scanner->buffer->str[i];
  49
  50       switch (state)
  51         {
  52         case NONE:
  53           if (g_ascii_isalpha (c))
  54             {
  55               start = i;
  56               state = ID;
  57               break;
  58             }
  59           else if (g_ascii_isspace (c))
  60             {
  61               if (c == '\n')
  62                 {
  63                   start = i;
  64                   state = EOL;
  65                 }
  66               break;
  67             }
  68           else if (c == ':')
  69             {
  70               start = i;
  71               state = EQUAL;
  72               break;
  73             }
  74           else if (c == '"')
  75             {
  76               start = i;
  77               state = STRING;
  78               break;
  79             }
  80           else if (c == 0)
  81             {
  82               stop = i;
  83               break;
  84             }
  85         case ID:
  86           if (g_ascii_isalnum (c))
  87             {
  88               break;
  89             }
  90           else if (g_ascii_isspace (c) || c == 0)
  91             {
  92               stop = i;
  93               break;
  94             }
  95         case EOL:
  96         case EQUAL:
  97           stop = i;
  98           break;
  99         case STRING:
 100           if (c == '"')
 101             stop = i+1;
 102           break;
 103         }
 104
 105     }
 106
 107   free (buffer);
 108
 109   g_string_erase (scanner->buffer, 0, start);
 110   lexeme = g_string_new_len (scanner->buffer->str, stop - start);
 111   g_string_erase (scanner->buffer, 0, stop - start);
 112
 113   if (val)
 114     {
 115       *val = lexeme;
 116     }
 117   else
 118     {
 119       g_string_free (lexeme, TRUE);
 120     }
 121
 122   return state;
 123
 124 }
 125
 126 enum
 127   {
 128     BNF_GRAMMAR = 1,
 129     BNF_RULES,
 130     BNF_RULE,
 131     BNF_LEFT,
 132     BNF_RIGHT,
 133     BNF_SYMBOL,
 134     BNF_TERMINAL,
 135     BNF_NONTERMINAL
 136   };
 137
 138 void grammar_tree (grammar_t* grammar, GNode* tree)
 139 {
 140
 141   GNode* child_rules;
 142   GNode* child_rule;
 143   GNode* child_left;
 144   GNode* child_right;
 145   GNode* child_symbol;
 146   GNode* child_nonterminal;
 147   GNode* child_terminal;
 148   GNode* child;
 149   symbol_t* symbol;
 150   rule_t* rule;
 151   GString* sym;
 152   GQuark value;
 153
 154   assert (G_NODE_IS_LEAF(tree) == FALSE);
 155   symbol = tree->data;
 156   assert (symbol->value == BNF_GRAMMAR);
 157
 158   child_rules = tree->children;
 159
 160   while (child_rules->children != NULL)
 161     {
 162
 163       assert (G_NODE_IS_LEAF(child_rules) == FALSE);
 164       symbol = child_rules->data;
 165       assert (symbol->value == BNF_RULES);
 166
 167       child_rule = child_rules->children;
 168       assert (G_NODE_IS_LEAF(child_rule) == FALSE);
 169       symbol = child_rule->data;
 170       assert (symbol->value == BNF_RULE);
 171
 172       child_left = child_rule->children;
 173       assert (G_NODE_IS_LEAF (child_left) == FALSE);
 174       symbol = child_left->data;
 175       assert (symbol->value == BNF_LEFT);
 176
 177       child_nonterminal = child_left->children;
 178       assert (G_NODE_IS_LEAF (child_nonterminal) == FALSE);
 179       symbol = child_nonterminal->data;
 180       assert (symbol->value == BNF_NONTERMINAL);
 181       assert (child_nonterminal->next == NULL);
 182
 183       child = child_nonterminal->children;
 184       assert (G_NODE_IS_LEAF (child));
 185       sym = child->data;
 186
 187       /* Create new rule */
 188       value = g_quark_from_string (sym->str);
 189       rule = grammar_rule_new (grammar, symbol_new (FALSE, value));
 190
 191       child_right = child_left->next->next;
 192       while (child_right->children != NULL)
 193         {
 194
 195           assert (G_NODE_IS_LEAF(child_right) == FALSE);
 196           symbol = child_right->data;
 197           assert (symbol->value == BNF_RIGHT);
 198
 199           child_symbol = child_right->children;
 200           assert (G_NODE_IS_LEAF(child_symbol) == FALSE);
 201           symbol = child_symbol->data;
 202           assert (symbol->value == BNF_SYMBOL);
 203
 204           child = child_symbol->children;
 205           symbol = child->data;
 206           if (symbol->value == BNF_NONTERMINAL)
 207             {
 208               child_nonterminal = child;
 209               assert (G_NODE_IS_LEAF (child_nonterminal) == FALSE);
 210               assert (child_nonterminal->next == NULL);
 211               child = child_nonterminal->children;
 212               assert (G_NODE_IS_LEAF (child));
 213               sym = child->data;
 214               /* Append nonterminal to rule */
 215               value = g_quark_from_string (sym->str);
 216               rule_append (rule, symbol_new (FALSE, value));
 217             }
 218           else if (symbol->value == BNF_TERMINAL)
 219             {
 220               child_terminal = child;
 221               assert (G_NODE_IS_LEAF (child_terminal) == FALSE);
 222               assert (child_terminal->next == NULL);
 223               child = child_terminal->children;
 224               assert (G_NODE_IS_LEAF (child));
 225               sym = child->data;
 226               /* Append terminal to rule */
 227               value = g_quark_from_string (sym->str);
 228               rule_append (rule, symbol_new (TRUE, value));
 229             }
 230           else
 231             {
 232               assert (TRUE);
 233             }
 234
 235           child_right = child_symbol->next;
 236
 237         }
 238
 239       child_rules = child_rule->next;
 240
 241     }
 242
 243 }
 244
 245 grammar_t* grammar_load (char* filename)
 246 {
 247
 248   grammar_t* grammar;
 249   rule_t* rule;
 250
 251   scanner_t* scanner;
 252   rdp_t* parser;
 253   GNode* tree;
 254
 255   int fd;
 256
 257   fd = open (filename, O_RDONLY);
 258
 259   scanner = scanner_new (read, fd);
 260
 261   grammar = grammar_new ();
 262   parser = rdp_new (bnf_scanner_next, scanner, BNF_GRAMMAR, grammar);
 263
 264   rule = grammar_rule_new (grammar, symbol_new (FALSE, BNF_GRAMMAR));
 265   rule_append (rule, symbol_new (FALSE, BNF_RULES));
 266   rule = grammar_rule_new (grammar, symbol_new (FALSE, BNF_RULES));
 267   rule_append (rule, symbol_new (FALSE, BNF_RULE));
 268   rule_append (rule, symbol_new (FALSE, BNF_RULES));
 269   rule = grammar_rule_new (grammar, symbol_new (FALSE, BNF_RULES));
 270   rule = grammar_rule_new (grammar, symbol_new (FALSE, BNF_RULE));
 271   rule_append (rule, symbol_new (FALSE, BNF_LEFT));
 272   rule_append (rule, symbol_new (TRUE, EQUAL));
 273   rule_append (rule, symbol_new (FALSE, BNF_RIGHT));
 274   rule_append (rule, symbol_new (TRUE, EOL));
 275   rule = grammar_rule_new (grammar, symbol_new (FALSE, BNF_LEFT));
 276   rule_append (rule, symbol_new (FALSE, BNF_NONTERMINAL));
 277   rule = grammar_rule_new (grammar, symbol_new (FALSE, BNF_RIGHT));
 278   rule_append (rule, symbol_new (FALSE, BNF_SYMBOL));
 279   rule_append (rule, symbol_new (FALSE, BNF_RIGHT));
 280   rule = grammar_rule_new (grammar, symbol_new (FALSE, BNF_RIGHT));
 281   rule = grammar_rule_new (grammar, symbol_new (FALSE, BNF_SYMBOL));
 282   rule_append (rule, symbol_new (FALSE, BNF_TERMINAL));
 283   rule = grammar_rule_new (grammar, symbol_new (FALSE, BNF_SYMBOL));
 284   rule_append (rule, symbol_new (FALSE, BNF_NONTERMINAL));
 285   rule = grammar_rule_new (grammar, symbol_new (FALSE, BNF_TERMINAL));
 286   rule_append (rule, symbol_new (TRUE, STRING));
 287   rule = grammar_rule_new (grammar, symbol_new (FALSE, BNF_NONTERMINAL));
 288   rule_append (rule, symbol_new (TRUE, ID));
 289
 290   tree = rdp_build (parser);
 291
 292   close (fd);
 293   scanner_delete (scanner);
 294   rdp_delete (parser);
 295   grammar_delete (grammar);
 296
 297   if (tree == NULL)
 298     {
 299       return NULL;
 300     }
 301   else
 302     {
 303       grammar_t* gr;
 304       gr = grammar_new ();
 305       grammar_tree (gr, tree);
 306       return gr;
 307     }
 308
 309 }