bnf.c

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