--- /dev/null
+#include <grammar.h>
+#include <rdp.h>
+#include <scanner.h>
+#include <assert.h>
+#include <fcntl.h>
+#include <unistd.h>
+#include <stdlib.h>
+
+static gint scanner_next (scanner_t* scanner, GString** val)
+{
+
+ int state;
+ int start;
+ int stop;
+ int i;
+ gchar* buffer;
+ GString* lexeme;
+
+ state = NONE;
+ start = 0;
+ stop = 0;
+ buffer = malloc (256);
+
+ for (i = 0; stop == 0; i++)
+ {
+
+ gchar c;
+
+ if (scanner->buffer->len == 0)
+ {
+ int r;
+ r = scanner->cb (scanner->data, buffer, 256);
+ if (r == 0)
+ g_string_append_c (scanner->buffer, 0);
+ else
+ g_string_append_len (scanner->buffer, buffer, r);
+ }
+
+ c = scanner->buffer->str[i];
+
+ switch (state)
+ {
+ case NONE:
+ if (g_ascii_isalpha (c))
+ {
+ start = i;
+ state = ID;
+ break;
+ }
+ else if (g_ascii_isspace (c))
+ {
+ if (c == '\n')
+ {
+ start = i;
+ state = EOL;
+ }
+ break;
+ }
+ else if (c == ':')
+ {
+ start = i;
+ state = EQUAL;
+ break;
+ }
+ else if (c == '"')
+ {
+ start = i;
+ state = STRING;
+ break;
+ }
+ else if (c == 0)
+ {
+ stop = i;
+ break;
+ }
+ case ID:
+ if (g_ascii_isalnum (c))
+ {
+ break;
+ }
+ else if (g_ascii_isspace (c) || c == 0)
+ {
+ stop = i;
+ break;
+ }
+ case EOL:
+ case EQUAL:
+ stop = i;
+ break;
+ case STRING:
+ if (c == '"')
+ stop = i+1;
+ break;
+ }
+
+ }
+
+ free (buffer);
+
+ g_string_erase (scanner->buffer, 0, start);
+ lexeme = g_string_new_len (scanner->buffer->str, stop - start);
+ g_string_erase (scanner->buffer, 0, stop - start);
+
+ if (val)
+ {
+ *val = lexeme;
+ }
+ else
+ {
+ g_string_free (lexeme, TRUE);
+ }
+
+ return state;
+
+}
+
+enum
+ {
+ BNF_GRAMMAR = 1,
+ BNF_RULES,
+ BNF_RULE,
+ BNF_LEFT,
+ BNF_RIGHT,
+ BNF_SYMBOL,
+ BNF_TERMINAL,
+ BNF_NONTERMINAL
+ };
+
+void grammar_tree (grammar_t* grammar, GNode* tree)
+{
+
+ GNode* child_rules;
+ GNode* child_rule;
+ GNode* child_left;
+ GNode* child_right;
+ GNode* child_symbol;
+ GNode* child_nonterminal;
+ GNode* child_terminal;
+ GNode* child;
+ symbol_t* symbol;
+ rule_t* rule;
+ GString* sym;
+ GQuark value;
+
+ assert (G_NODE_IS_LEAF(tree) == FALSE);
+ symbol = tree->data;
+ assert (symbol->value == BNF_GRAMMAR);
+
+ child_rules = tree->children;
+
+ while (child_rules->children != NULL)
+ {
+
+ assert (G_NODE_IS_LEAF(child_rules) == FALSE);
+ symbol = child_rules->data;
+ assert (symbol->value == BNF_RULES);
+
+ child_rule = child_rules->children;
+ assert (G_NODE_IS_LEAF(child_rule) == FALSE);
+ symbol = child_rule->data;
+ assert (symbol->value == BNF_RULE);
+
+ child_left = child_rule->children;
+ assert (G_NODE_IS_LEAF (child_left) == FALSE);
+ symbol = child_left->data;
+ assert (symbol->value == BNF_LEFT);
+
+ child_nonterminal = child_left->children;
+ assert (G_NODE_IS_LEAF (child_nonterminal) == FALSE);
+ symbol = child_nonterminal->data;
+ assert (symbol->value == BNF_NONTERMINAL);
+ assert (child_nonterminal->next == NULL);
+
+ child = child_nonterminal->children;
+ assert (G_NODE_IS_LEAF (child));
+ sym = child->data;
+
+ /* Create new rule */
+ value = g_quark_from_string (sym->str);
+ rule = grammar_rule_new (grammar, symbol_new (FALSE, value));
+
+ child_right = child_left->next->next;
+ while (child_right->children != NULL)
+ {
+
+ assert (G_NODE_IS_LEAF(child_right) == FALSE);
+ symbol = child_right->data;
+ assert (symbol->value == BNF_RIGHT);
+
+ child_symbol = child_right->children;
+ assert (G_NODE_IS_LEAF(child_symbol) == FALSE);
+ symbol = child_symbol->data;
+ assert (symbol->value == BNF_SYMBOL);
+
+ child = child_symbol->children;
+ symbol = child->data;
+ if (symbol->value == BNF_NONTERMINAL)
+ {
+ child_nonterminal = child;
+ assert (G_NODE_IS_LEAF (child_nonterminal) == FALSE);
+ assert (child_nonterminal->next == NULL);
+ child = child_nonterminal->children;
+ assert (G_NODE_IS_LEAF (child));
+ sym = child->data;
+ /* Append nonterminal to rule */
+ value = g_quark_from_string (sym->str);
+ rule_append (rule, symbol_new (FALSE, value));
+ }
+ else if (symbol->value == BNF_TERMINAL)
+ {
+ child_terminal = child;
+ assert (G_NODE_IS_LEAF (child_terminal) == FALSE);
+ assert (child_terminal->next == NULL);
+ child = child_terminal->children;
+ assert (G_NODE_IS_LEAF (child));
+ sym = child->data;
+ /* Append terminal to rule */
+ value = g_quark_from_string (sym->str);
+ rule_append (rule, symbol_new (TRUE, value));
+ }
+ else
+ {
+ assert (TRUE);
+ }
+
+ child_right = child_symbol->next;
+
+ }
+
+ child_rules = child_rule->next;
+
+ }
+
+}
+
+grammar_t* grammar_load (char* filename)
+{
+
+ grammar_t* grammar;
+ rule_t* rule;
+
+ scanner_t* scanner;
+ rdp_t* parser;
+ GNode* tree;
+
+ int fd;
+
+ fd = open (filename, O_RDONLY);
+
+ scanner = scanner_new (read, fd);
+
+ grammar = grammar_new ();
+ parser = rdp_new (scanner_next, scanner, BNF_GRAMMAR, grammar);
+
+ rule = grammar_rule_new (grammar, symbol_new (FALSE, BNF_GRAMMAR));
+ rule_append (rule, symbol_new (FALSE, BNF_RULES));
+ rule = grammar_rule_new (grammar, symbol_new (FALSE, BNF_RULES));
+ rule_append (rule, symbol_new (FALSE, BNF_RULE));
+ rule_append (rule, symbol_new (FALSE, BNF_RULES));
+ rule = grammar_rule_new (grammar, symbol_new (FALSE, BNF_RULES));
+ rule = grammar_rule_new (grammar, symbol_new (FALSE, BNF_RULE));
+ rule_append (rule, symbol_new (FALSE, BNF_LEFT));
+ rule_append (rule, symbol_new (TRUE, EQUAL));
+ rule_append (rule, symbol_new (FALSE, BNF_RIGHT));
+ rule_append (rule, symbol_new (TRUE, EOL));
+ rule = grammar_rule_new (grammar, symbol_new (FALSE, BNF_LEFT));
+ rule_append (rule, symbol_new (FALSE, BNF_NONTERMINAL));
+ rule = grammar_rule_new (grammar, symbol_new (FALSE, BNF_RIGHT));
+ rule_append (rule, symbol_new (FALSE, BNF_SYMBOL));
+ rule_append (rule, symbol_new (FALSE, BNF_RIGHT));
+ rule = grammar_rule_new (grammar, symbol_new (FALSE, BNF_RIGHT));
+ rule = grammar_rule_new (grammar, symbol_new (FALSE, BNF_SYMBOL));
+ rule_append (rule, symbol_new (FALSE, BNF_TERMINAL));
+ rule = grammar_rule_new (grammar, symbol_new (FALSE, BNF_SYMBOL));
+ rule_append (rule, symbol_new (FALSE, BNF_NONTERMINAL));
+ rule = grammar_rule_new (grammar, symbol_new (FALSE, BNF_TERMINAL));
+ rule_append (rule, symbol_new (TRUE, STRING));
+ rule = grammar_rule_new (grammar, symbol_new (FALSE, BNF_NONTERMINAL));
+ rule_append (rule, symbol_new (TRUE, ID));
+
+ tree = rdp_build (parser);
+
+ close (fd);
+ scanner_delete (scanner);
+ rdp_delete (rdp);
+ grammar_delete (grammar);
+
+ if (tree == NULL)
+ {
+ return NULL;
+ }
+ else
+ {
+ grammar_t* gr;
+ gr = g_object_new (GRAMMAR_TYPE, NULL);
+ grammar_tree (gr, tree);
+ return gr;
+ }
+
+}
--- /dev/null
+#ifndef BNF_H
+#define BNF_H
+
+#include <grammar.h>
+
+grammar_t* grammar_load (char* filename);
+
+#endif
* We should iterate through the rules for each nonterminal until only
* terminals are known to be in the first set of it.
*/
-GHashTable* grammar_first (Grammar* grammar)
+GHashTable* grammar_first (grammar_t* grammar)
{
GHashTable* first;
gboolean stop;
#include <grammar.h>
-GHashTable* grammar_first (Grammar*);
+GHashTable* grammar_first (grammar_t*);
GList* first_get (GHashTable*, symbol_t*);
GList* first_rule (GHashTable*, rule_t*);
g_free (list);
}
-static void grammar_init (GTypeInstance* instance, gpointer g_class)
+grammar_t* grammar_new ()
{
- Grammar* self = GRAMMAR(instance);
+ grammar_t* grammar;
+ grammar = g_malloc (sizeof (grammar_t*));
self->grammar = g_hash_table_new_full (symbol_hash, symbol_equal,
g_free,
(GDestroyNotify) rules_delete);
+ return grammar;
}
-static void grammar_finalize (GObject* obj)
+void grammar_delete (grammar_t* grammar)
{
- GrammarClass* klass;
- GObject* parent_class;
- Grammar* self;
- self = GRAMMAR(obj);
- g_hash_table_destroy (self->grammar);
- klass = GRAMMAR_GET_CLASS(obj);
- parent_class = g_type_class_peek_parent (klass);
- G_OBJECT_CLASS(parent_class)->finalize (obj);
+ g_hash_table_destroy (grammar->grammar);
+ g_free (grammar);
}
-static void grammar_class_init (GrammarClass* klass)
-{
- GObjectClass* gobj_class = G_OBJECT_CLASS(klass);
- gobj_class->finalize = grammar_finalize;
-}
-
-GType grammar_get_type ()
-{
- static GType type = 0;
- if (type == 0)
- {
- static const GTypeInfo info =
- {
- sizeof (GrammarClass),
- NULL,
- NULL,
- (GClassInitFunc)grammar_class_init,
- NULL,
- NULL,
- sizeof (Grammar),
- 0,
- grammar_init
- };
- type = g_type_register_static (G_TYPE_OBJECT, "GrammarType", &info, 0);
- }
- return type;
-}
-
-rule_t* grammar_rule_new (Grammar* grammar, symbol_t* left)
+rule_t* grammar_rule_new (grammar_t* grammar, symbol_t* left)
{
GList** l;
}
-GList* grammar_get_rules (Grammar* grammar, symbol_t* left)
+GList* grammar_get_rules (grammar_t* grammar, symbol_t* left)
{
GList** l;
if (!g_hash_table_lookup_extended (grammar->grammar,
#define GRAMMAR_H
#include <glib.h>
-#include <glib-object.h>
-
-#define GRAMMAR_TYPE (grammar_get_type ())
-#define GRAMMAR(obj) (G_TYPE_CHECK_INSTANCE_CAST ((obj), \
- GRAMMAR_TYPE, Grammar))
-#define GRAMMAR_CLASS(klass) (G_TYPE_CHECK_CLASS_CAST ((klass), \
- GRAMMAR_TYPE, GrammarClass))
-#define IS_GRAMMAR(obj) (G_TYPE_CHECK_INSTANCE_TYPE ((obj), \
- GRAMMAR_TYPE))
-#define IS_GRAMMAR_CLASS(klass) (G_TYPE_CHECK_CLASS_TYPE ((klass), \
- GRAMMAR_TYPE))
-#define GRAMMAR_GET_CLASS(obj) (G_TYPE_INSTANCE_GET_CLASS ((obj), \
- GRAMMAR_TYPE, GrammarClass))
-
typedef gint (*nextcb) (gpointer, gpointer*);
typedef struct _rule rule_t;
typedef struct
{
- GObject parent;
GHashTable* grammar;
-} Grammar;
-typedef struct
-{
- GObjectClass parent;
-} GrammarClass;
-
-GType grammar_get_type ();
+} grammar_t;
symbol_t* symbol_new (gboolean, GQuark);
symbol_t* symbol_copy (symbol_t*);
void rule_append (rule_t*, symbol_t*);
void rule_delete (rule_t*);
-
-rule_t* grammar_rule_new (Grammar*, symbol_t*);
-GList* grammar_get_rules (Grammar*, symbol_t*);
+grammar_t* grammar_new ();
+rule_t* grammar_rule_new (grammar_t*, symbol_t*);
+GList* grammar_get_rules (grammar_*, symbol_t*);
GList* grammar_get_rule (rule_t*);
+void grammar_delete (grammar_t*);
#endif
}
-void item_set_closure_step (GHashTable* item_set, Grammar* grammar,
+void item_set_closure_step (GHashTable* item_set, grammar_t* grammar,
GHashTable* first, item_t* item)
{
if (item->dot != NULL)
}
}
-GHashTable* item_set_closure (GHashTable* item_set, Grammar* grammar,
+GHashTable* item_set_closure (GHashTable* item_set, grammar_t* grammar,
GHashTable* first)
{
int size;
return item_set;
}
-GHashTable* item_set_goto (GHashTable* item_set, Grammar* grammar,
+GHashTable* item_set_goto (GHashTable* item_set, grammar_t* grammar,
GHashTable* first, symbol_t* symbol)
{
GList* l;
* In fact, the counter may be the hash table size.
*/
-typedef struct
-{
- GHashTable* symbols;
- gint code;
-} state_t;
-
-state_t* state_new (gint code)
-{
- state_t* state;
- state = g_malloc (sizeof (state_t));
- state->code = code;
- state->symbols = g_hash_table_new_full (symbol_hash, symbol_equal,
- g_free, NULL);
- return state;
-}
-
-void state_delete (state_t* state)
-{
- g_hash_table_destroy (state->symbols);
- g_free (state);
-}
-
GHashTable* item_collection_new ()
{
return g_hash_table_new_full (item_set_hash, item_set_equal,
- g_hash_table_destroy, state_delete);
+ g_hash_table_destroy, g_hash_table_destroy);
}
-gboolean item_collection_add (GHashTable* collection, GHashTable* item_set)
+gboolean item_collection_add (GHashTable* collection, GHashTable* item_set,
+ GHashTable** key)
{
- if (!g_hash_table_lookup_extended (collection, item_set, NULL, NULL))
+ if (!g_hash_table_lookup_extended (collection, item_set,
+ (gpointer*)key, NULL))
{
- state_t* state;
- state = state_new (g_hash_table_size (collection));
- g_hash_table_insert (collection, item_set, state);
+ GHashTable* symbols;
+ symbols = g_hash_table_new_full (symbol_hash, symbol_equal,
+ g_free, NULL);
+ g_hash_table_insert (collection, item_set, symbols);
return TRUE;
}
return FALSE;
}
-state_t* item_collection_lookup (GHashTable* collection,
- GHashTable* item_set)
+GHashTable* item_collection_lookup (GHashTable* collection,
+ GHashTable* item_set)
{
- state_t* state;
+ GHashTable* symbols;
if (!g_hash_table_lookup_extended (collection, item_set,
- NULL, (gpointer*)&state))
+ NULL, (gpointer*)&symbols))
{
return NULL;
}
- return state;
+ return symbols;
}
+#define HASH_ITEM_SET(item_set) (((GPOINTER_TO_INT(item_set) & 0x3f00) >> 8))
#ifdef DEBUG
void item_collection_print_each (gpointer key, gpointer val, gpointer data)
{
GHashTable* item_set;
- state_t* state;
item_set = (GHashTable*) key;
- state = (state_t*) val;
- fprintf (stdout, "Item %d:\n", state->code);
+ fprintf (stdout, "Item %x:\n", HASH_ITEM_SET(key));
item_set_print (item_set);
fprintf (stdout, "\n");
}
void item_set_print_goto (gpointer key, gpointer val, gpointer data)
{
symbol_t* symbol;
- gint code;
- state_t* state;
symbol = (symbol_t*) key;
- code = GPOINTER_TO_INT (val);
- state = (state_t*) data;
- fprintf (stdout, "GOTO (%d, %s) =\t %d\n", state->code,
- g_quark_to_string (symbol->value), code);
+ fprintf (stdout, "GOTO (%x, %s) =\t %x\n", HASH_ITEM_SET(data),
+ g_quark_to_string (symbol->value), HASH_ITEM_SET(val));
}
void item_collection_print_goto (gpointer key, gpointer val, gpointer data)
{
- state_t* state;
- state = (state_t*) val;
- g_hash_table_foreach (state->symbols, item_set_print_goto, state);
+ GHashTable* symbols;
+ symbols = (GHashTable*) val;
+ g_hash_table_foreach (symbols, item_set_print_goto, key);
fprintf (stdout, "\n");
}
}
#endif
-GHashTable* item_collection_goto (GHashTable* collection, Grammar* grammar,
+GHashTable* item_collection_goto (GHashTable* collection, grammar_t* grammar,
GHashTable* first, GHashTable* item_set,
symbol_t* symbol)
{
- state_t* state;
- state_t* goto_state;
+ GHashTable* symbols;
GHashTable* newitem_set;
GHashTable* goto_item_set;
- GHashTable* return_item_set;
+ GHashTable* old_item_set;
newitem_set = item_set_copy (item_set);
- if (!item_collection_add (collection, newitem_set))
+ if (!item_collection_add (collection, newitem_set, NULL))
{
g_hash_table_destroy (newitem_set);
}
- state = item_collection_lookup (collection, item_set);
- if (g_hash_table_lookup_extended (state->symbols, symbol, NULL, NULL))
+ symbols = item_collection_lookup (collection, item_set);
+ if (g_hash_table_lookup_extended (symbols, symbol, NULL, NULL))
{
return NULL;
}
goto_item_set = item_set_goto (item_set, grammar, first, symbol);
- if (!item_collection_add (collection, goto_item_set))
- return_item_set = NULL;
+ if (!item_collection_add (collection, goto_item_set, &old_item_set))
+ {
+ g_hash_table_insert (symbols, symbol, old_item_set);
+ g_hash_table_destroy (goto_item_set);
+ return NULL;
+ }
else
- return_item_set = goto_item_set;
- goto_state = item_collection_lookup (collection, goto_item_set);
- g_hash_table_insert (state->symbols, symbol,
- GINT_TO_POINTER (goto_state->code));
- return return_item_set;
+ {
+ g_hash_table_insert (symbols, symbol, goto_item_set);
+ return goto_item_set;
+ }
}
-void item_set_collection (Grammar* grammar, GHashTable* first, symbol_t* start)
+void item_set_collection (grammar_t* grammar, GHashTable* first, symbol_t* start)
{
GHashTable* collection;
GHashTable* item_set;
item_set_closure (item_set, grammar, first);
collection = g_hash_table_new_full (item_set_hash, item_set_equal,
g_hash_table_destroy, NULL);
- item_collection_add (collection, item_set);
+ item_collection_add (collection, item_set, NULL);
new_item_sets = g_list_append (NULL, item_set);
while (new_item_sets != NULL)
{
g_node_destroy (tree);
}
-static void rdp_init (GTypeInstance* instance, gpointer g_class)
+rdp_t* rdp_new (nextcb cb, gpointer data, gint value, grammar_t* grammar)
{
- Rdp* self = RDP(instance);
- self->cb = NULL;
- self->data = NULL;
- self->buffer = NULL;
- self->start = NULL;
-}
-static void rdp_finalize (GObject* obj)
-{
- RdpClass* klass;
- GObject* parent_class;
- Rdp* self;
- self = RDP(obj);
- g_free (self->start);
- klass = RDP_GET_CLASS(obj);
- parent_class = g_type_class_peek_parent (klass);
- G_OBJECT_CLASS(parent_class)->finalize (obj);
-}
+ rdp_t* parser;
-static void rdp_class_init (RdpClass* klass)
-{
- GObjectClass* gobj_class = G_OBJECT_CLASS(klass);
- gobj_class->finalize = rdp_finalize;
-}
-
-GType rdp_get_type ()
-{
- static GType type = 0;
- if (type == 0)
- {
- static const GTypeInfo info =
- {
- sizeof (RdpClass),
- NULL,
- NULL,
- (GClassInitFunc)rdp_class_init,
- NULL,
- NULL,
- sizeof (Rdp),
- 0,
- rdp_init
- };
- type = g_type_register_static (GRAMMAR_TYPE, "RdpType", &info, 0);
- }
- return type;
-}
-
-Rdp* rdp_new (nextcb cb, gpointer data, gint value)
-{
-
- Rdp* parser;
-
- parser = g_object_new (RDP_TYPE, NULL);
+ parser = g_malloc (sizeof (rdp_t));
parser->cb = cb;
parser->data = data;
parser->start = symbol_new (FALSE, value);
+ parser->grammar = grammar;
parser->buffer = g_list_append (NULL, NULL);
}
-void rdp_delete (Rdp* parser)
+void rdp_delete (rdp_t* rdp)
{
-
- g_object_unref (parser);
-
+ g_free (rdp->start);
}
-symbol_t* buffer_next (Rdp* parser, gpointer* attrib)
+symbol_t* buffer_next (rdp_t* parser, gpointer* attrib)
{
buffer_t* buffer;
}
-gboolean rdp_step (Rdp* parser, symbol_t* symbol, gpointer* attrib)
+gboolean rdp_step (rdp_t* parser, symbol_t* symbol, gpointer* attrib)
{
GList* l;
return TRUE;
}
- for (l = grammar_get_rules (parser, symbol); l != NULL; l = g_list_next (l))
+ l = grammar_get_rules (parser->grammar, symbol);
+ for (; l != NULL; l = g_list_next (l))
{
rule_t* rule;
}
-gpointer rdp_build (Rdp* parser)
+gpointer rdp_build (rdp_t* parser)
{
gpointer attrib;
#include <grammar.h>
-#define RDP_TYPE (rdp_get_type ())
-#define RDP(obj) (G_TYPE_CHECK_INSTANCE_CAST ((obj), \
- RDP_TYPE, Rdp))
-#define RDP_CLASS(klass) (G_TYPE_CHECK_CLASS_CAST ((klass), \
- RDP_TYPE, RdpClass))
-#define IS_RDP(obj) (G_TYPE_CHECK_INSTANCE_TYPE ((obj), \
- RDP_TYPE))
-#define IS_RDP_CLASS(klass) (G_TYPE_CHECK_CLASS_TYPE ((klass), \
- RDP_TYPE))
-#define RDP_GET_CLASS(obj) (G_TYPE_INSTANCE_GET_CLASS ((obj), \
- RDP_TYPE, RdpClass))
-
-
typedef struct _buffer buffer_t;
typedef struct
{
- Grammar parent;
nextcb cb;
gpointer data;
GList* buffer;
symbol_t* start;
-} Rdp;
-
-typedef struct
-{
- GrammarClass parent;
-} RdpClass;
-
-GType rdp_get_type ();
+ grammar_t* grammar;
+} rdp_t;
-Rdp* rdp_new (nextcb, gpointer, gint);
-void rdp_delete (Rdp*);
-gpointer rdp_build (Rdp*);
+rdp_t* rdp_new (nextcb, gpointer, gint, grammar_t*);
+void rdp_delete (rdp_t*);
+gpointer rdp_build (rdp_t*);
#endif
projects / cascardo / grammar.git / commitdiff