BNF_NONTERMINAL
};
-void grammar_tree (Grammar* grammar, GNode* tree)
+void grammar_tree (grammar_t* grammar, GNode* tree)
{
GNode* child_rules;
}
-Grammar* grammar_load (char* filename)
+grammar_t* grammar_load (char* filename)
{
- Grammar* grammar;
+ grammar_t* grammar;
rule_t* rule;
scanner_t* scanner;
- Rdp* parser;
+ rdp_t* parser;
GNode* tree;
int fd;
scanner = scanner_new (read, fd);
- parser = rdp_new (bnf_scanner_next, scanner, BNF_GRAMMAR);
- grammar = (Grammar*) parser;
+ grammar = grammar_new ();
+ parser = rdp_new (bnf_scanner_next, scanner, BNF_GRAMMAR, grammar);
rule = grammar_rule_new (grammar, symbol_new (FALSE, BNF_GRAMMAR));
rule_append (rule, symbol_new (FALSE, BNF_RULES));
close (fd);
scanner_delete (scanner);
+ rdp_delete (parser);
+ grammar_delete (grammar);
if (tree == NULL)
{
}
else
{
- Grammar* gr;
- gr = g_object_new (GRAMMAR_TYPE, NULL);
+ grammar_t* gr;
+ gr = grammar_new ();
grammar_tree (gr, tree);
return gr;
}
#include <grammar.h>
-Grammar* grammar_load (char* filename);
+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);
- self->grammar = g_hash_table_new_full (symbol_hash, symbol_equal,
- g_free,
- (GDestroyNotify) rules_delete);
+ grammar_t* grammar;
+ grammar = g_malloc (sizeof (grammar_t*));
+ grammar->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_t*, symbol_t*);
GList* grammar_get_rule (rule_t*);
+void grammar_delete (grammar_t*);
#endif
#include <grammar.h>
+#include <first.h>
+#include <item.h>
#ifdef DEBUG
#include <stdio.h>
#endif
-typedef struct
-{
- symbol_t* left;
- rule_t* right;
- GList* dot;
-} item_t;
-
-item_t* item_new (symbol_t* left, rule_t* right)
+item_t* item_new (symbol_t* left, rule_t* right, symbol_t* lookahead)
{
item_t* item;
item = g_malloc (sizeof (item_t));
item->left = left;
item->right = right;
item->dot = grammar_get_rule (right);
+ item->lookahead = lookahead;
return item;
}
{
item_t* newitem;
int n;
- newitem = item_new (symbol_copy (item->left), rule_copy (item->right));
+ newitem = item_new (symbol_copy (item->left), rule_copy (item->right),
+ symbol_copy (item->lookahead));
n = g_list_position (grammar_get_rule (item->right), item->dot);
newitem->dot = g_list_nth (grammar_get_rule (newitem->right), n);
return newitem;
return c;
if ((c = rule_cmp (a->right, b->right)) != 0)
return c;
+ if ((c = symbol_cmp (a->lookahead, b->lookahead)) != 0)
+ return c;
na = g_list_position (grammar_get_rule (a->right), a->dot);
nb = g_list_position (grammar_get_rule (b->right), b->dot);
if (na < nb)
guint hash;
item = (item_t*) data;
hash = rule_hash (item->right) * 37 + symbol_hash (item->left);
+ hash = hash * 37 + symbol_hash (item->lookahead);
return hash;
}
{
g_free (item->left);
rule_delete (item->right);
+ g_free (item->lookahead);
g_free (item);
}
{
fprintf (stdout, ".");
}
- fprintf (stdout, "\n");
+ fprintf (stdout, ", %s\n", g_quark_to_string (item->lookahead->value));
}
#endif
}
#endif
-void item_set_closure_step (GHashTable* item_set, Grammar* grammar,
- item_t* item)
+rule_t* rule_new_item (item_t* item)
+{
+
+ rule_t* rule;
+ GList* l;
+ rule = rule_new ();
+ l = g_list_next (item->dot);
+ while (l != NULL)
+ {
+ rule_append (rule, symbol_copy (l->data));
+ l = g_list_next (l);
+ }
+ rule_append (rule, symbol_copy (item->lookahead));
+ return rule;
+
+}
+
+void item_set_closure_step (GHashTable* item_set, grammar_t* grammar,
+ GHashTable* first, item_t* item)
{
if (item->dot != NULL)
{
if (symbol->terminal == FALSE)
{
GList* rules;
+ GList* terminals;
+ rule_t* rule;
+ rule = rule_new_item (item);
+ terminals = first_rule (first, rule);
+ rule_delete (rule);
rules = grammar_get_rules (grammar, symbol);
while (rules != NULL)
{
- rule_t* rule;
- item_t* newitem;
- rule = rule_copy (rules->data);
- newitem = item_new (symbol_copy (symbol), rule);
- if (!item_set_add (item_set, newitem))
- item_delete (newitem);
+ GList* lookahead;
+ lookahead = terminals;
+ while (lookahead != NULL)
+ {
+ rule_t* rule;
+ item_t* newitem;
+ rule = rule_copy (rules->data);
+ newitem = item_new (symbol_copy (symbol), rule,
+ symbol_copy (lookahead->data));
+ if (!item_set_add (item_set, newitem))
+ item_delete (newitem);
+ lookahead = g_list_next (lookahead);
+ }
rules = g_list_next (rules);
}
+ g_list_free (terminals);
}
}
}
-GHashTable* item_set_closure (GHashTable* item_set, Grammar* grammar)
+GHashTable* item_set_closure (GHashTable* item_set, grammar_t* grammar,
+ GHashTable* first)
{
int size;
int last_size;
g_hash_table_foreach (item_set, put_key_on_list, &l);
while (l != NULL)
{
- item_set_closure_step (item_set, grammar, l->data);
+ item_set_closure_step (item_set, grammar, first, l->data);
l = g_list_next (l);
}
g_list_free (l);
return item_set;
}
-GHashTable* item_set_goto (GHashTable* item_set, Grammar* grammar,
- symbol_t* symbol)
+GHashTable* item_set_goto (GHashTable* item_set, grammar_t* grammar,
+ GHashTable* first, symbol_t* symbol)
{
GList* l;
GHashTable* newitem_set;
}
l = g_list_next (l);
}
- return item_set_closure (newitem_set, grammar);
+ return item_set_closure (newitem_set, grammar, first);
}
}
#endif
-GHashTable* item_collection_goto (GHashTable* collection, Grammar* grammar,
- GHashTable* item_set, symbol_t* symbol)
+GHashTable* item_collection_goto (GHashTable* collection, grammar_t* grammar,
+ GHashTable* first, GHashTable* item_set,
+ symbol_t* symbol)
{
GHashTable* symbols;
GHashTable* newitem_set;
{
return NULL;
}
- goto_item_set = item_set_goto (item_set, grammar, symbol);
+ goto_item_set = item_set_goto (item_set, grammar, first, symbol);
if (!item_collection_add (collection, goto_item_set, &old_item_set))
{
g_hash_table_insert (symbols, symbol, old_item_set);
}
}
-void item_set_collection (Grammar* grammar, symbol_t* start)
+GHashTable* item_set_collection (grammar_t* grammar, GHashTable* first,
+ symbol_t* start)
{
GHashTable* collection;
GHashTable* item_set;
GList* new_item_sets;
rule = rule_new ();
rule_append (rule, symbol_copy (start));
- item = item_new (symbol_new (FALSE, -1), rule);
+ item = item_new (symbol_new (FALSE, -1), rule, symbol_new (TRUE, 0));
item_set = item_set_new ();
item_set_add (item_set, item);
- item_set_closure (item_set, grammar);
+ 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, NULL);
{
symbol = (symbol_t*) item->dot->data;
if ((new_item_set =
- item_collection_goto (collection, grammar,
+ item_collection_goto (collection, grammar, first,
next_item_set, symbol)) != NULL)
{
g_list_append (new_item_sets, new_item_set);
#ifdef DEBUG
item_collection_print (collection);
#endif
- g_hash_table_destroy (collection);
+ return collection;
}
--- /dev/null
+#ifndef ITEM_H
+#define ITEM_H
+
+#include <grammar.h>
+#include <glib.h>
+
+typedef struct
+{
+ symbol_t* left;
+ rule_t* right;
+ GList* dot;
+ symbol_t* lookahead;
+} item_t;
+
+GHashTable* item_set_collection (grammar_t*, GHashTable*, symbol_t*);
+
+#endif
--- /dev/null
+#include <grammar.h>
+#include <stdlib.h>
+#include <lr1.h>
+
+enum { PARSER_SHIFT, PARSER_REDUCE, PARSER_ACCEPT };
+
+struct _transition_t
+{
+ gint action;
+ gint state;
+ symbol_t* left;
+ rule_t* right;
+};
+
+struct _lr1_t
+{
+ nextcb cb;
+ gpointer data;
+ GHashTable* table;
+ GList* stack;
+};
+
+typedef struct
+{
+ gint state;
+ gpointer attrib;
+} state_t;
+
+transition_t* transition_shift_new (gint state)
+{
+ transition_t* transition;
+ transition = g_malloc (sizeof (transition_t));
+ transition->action = PARSER_SHIFT;
+ transition->state = state;
+ transition->left = NULL;
+ transition->right = NULL;
+ return transition;
+}
+
+transition_t* transition_reduce_new (symbol_t* left, rule_t* right)
+{
+ transition_t* transition;
+ transition = g_malloc (sizeof (transition_t));
+ transition->action = PARSER_REDUCE;
+ transition->state = 0;
+ transition->left = left;
+ transition->right = right;
+ return transition;
+}
+
+transition_t* transition_accept_new ()
+{
+ transition_t* transition;
+ transition = g_malloc (sizeof (transition_t));
+ transition->action = PARSER_ACCEPT;
+ transition->state = 0;
+ transition->left = NULL;
+ transition->right = NULL;
+ return transition;
+}
+
+void transition_delete (transition_t* transition)
+{
+ if (transition->left != NULL)
+ g_free (transition->left);
+ if (transition->right != NULL)
+ rule_delete (transition->right);
+ g_free (transition);
+}
+
+void lr1_push (lr1_t* parser, gint st, gpointer attrib)
+{
+ state_t* state;
+ state = g_malloc (sizeof (state_t));
+ state->state = st;
+ state->attrib = attrib;
+ parser->stack = g_list_prepend (parser->stack, state);
+}
+
+static gboolean lr1_pop (lr1_t* parser, gpointer* attrib)
+{
+
+ GList* l;
+ state_t* state;
+ if ((l = g_list_first (parser->stack)) == NULL)
+ return FALSE;
+ parser->stack = g_list_remove_link (l, l);
+ state = (state_t*) l->data;
+ if (attrib)
+ *attrib = state->attrib;
+ g_free (state);
+ g_list_free (l);
+ return TRUE;
+
+}
+
+lr1_t* lr1_new (nextcb cb, gpointer data)
+{
+
+ lr1_t* parser;
+
+ parser = g_malloc (sizeof (lr1_t));
+ parser->cb = cb;
+ parser->data = data;
+
+ parser->stack = NULL;
+ parser->table = g_hash_table_new_full (g_direct_hash, g_direct_equal,
+ NULL, g_hash_table_destroy);
+
+ return parser;
+
+}
+
+void lr1_delete (lr1_t* parser)
+{
+
+ GList* l;
+
+ for (l = g_list_first (parser->stack); l != NULL; l = g_list_next (l))
+ {
+ g_free (l->data);
+ }
+
+ g_list_free (parser->stack);
+
+ g_hash_table_destroy (parser->table);
+
+ g_free (parser);
+
+}
+
+gboolean lr1_add (lr1_t* parser, gint state, symbol_t* symbol,
+ transition_t* transition)
+{
+
+ GHashTable* table;
+
+ if (!g_hash_table_lookup_extended (parser->table, GINT_TO_POINTER(state),
+ NULL, (gpointer*) &table))
+ {
+ table = g_hash_table_new_full (symbol_hash, symbol_equal,
+ g_free, transition_delete);
+ g_hash_table_insert (parser->table, GINT_TO_POINTER(state), table);
+ }
+
+ if (g_hash_table_lookup_extended (table, symbol, NULL, NULL))
+ {
+ return FALSE;
+ }
+
+ g_hash_table_insert (table, symbol, transition);
+ return TRUE;
+
+}
+
+gboolean lr1_lookup (lr1_t* parser, gint state, symbol_t* symbol,
+ transition_t** transition)
+{
+
+ GHashTable* table;
+ transition_t* trans;
+
+ if (!g_hash_table_lookup_extended (parser->table, GINT_TO_POINTER(state),
+ NULL, (gpointer*) &table))
+ {
+ return FALSE;
+ }
+
+ if (!g_hash_table_lookup_extended (table, symbol,
+ NULL, (gpointer*) &trans))
+ {
+ return FALSE;
+ }
+
+ if (transition)
+ *transition = trans;
+
+ return TRUE;
+
+}
+
+static gpointer leaf_new (gpointer data)
+{
+ return g_node_new (data);
+}
+
+static gpointer tree_new (rule_t* rule)
+{
+ return g_node_new (rule);
+}
+
+static gpointer tree_add (gpointer tree, gpointer data)
+{
+ return g_node_prepend (tree, data);
+}
+
+gpointer lr1_build (lr1_t* parser)
+{
+
+ state_t* state;
+ symbol_t* symbol;
+ transition_t* transition;
+ gpointer attrib;
+ GList* l;
+
+ symbol = g_malloc (sizeof (symbol_t));
+
+ symbol->value = parser->cb (parser->data, &attrib);
+ symbol->terminal = TRUE;
+
+ while (1)
+ {
+
+ l = g_list_first (parser->stack);
+ state = (state_t*) l->data;
+ if (!lr1_lookup (parser, state->state, symbol, &transition))
+ return NULL;
+
+ if (transition->action == PARSER_SHIFT)
+ {
+ gint st;
+ lr1_push (parser, transition->state, leaf_new (attrib));
+ symbol->value = parser->cb (parser->data, &attrib);
+ symbol->terminal = TRUE;
+ }
+
+ else if (transition->action == PARSER_REDUCE)
+ {
+
+ state_t* state;
+ transition_t* trans;
+ GList* l;
+ gpointer attrib;
+
+ attrib = tree_new (symbol_copy (transition->left));
+
+ for (l = grammar_get_rule (transition->right);
+ l != NULL;
+ l = g_list_next (l))
+ {
+ gpointer attr;
+ if (!lr1_pop (parser, &attr))
+ return NULL;
+ tree_add (attrib, attr);
+ }
+
+ l = g_list_first (parser->stack);
+ state = (state_t*) l->data;
+ lr1_lookup (parser, state->state, transition->left, &trans);
+ lr1_push (parser, trans->state, attrib);
+
+ }
+
+ else if (transition->action == PARSER_ACCEPT)
+ {
+ l = g_list_first (parser->stack);
+ state = (state_t*) l->data;
+ return state->attrib;
+ }
+
+ }
+
+ return NULL;
+
+}
--- /dev/null
+#ifndef LR1_H
+#define LR1_H
+
+#include <grammar.h>
+
+typedef struct _transition_t transition_t;
+typedef struct _lr1_t lr1_t;
+
+transition_t* transition_shift_new (gint);
+transition_t* transition_reduce_new (symbol_t*, rule_t*);
+transition_t* transition_accept_new ();
+void transition_delete (transition_t*);
+lr1_t* lr1_new (nextcb, gpointer);
+void lr1_delete (lr1_t*);
+gboolean lr1_add (lr1_t*, gint, symbol_t*, transition_t*);
+void lr1_push (lr1_t*, gint, gpointer);
+gpointer lr1_build (lr1_t*);
+
+#endif
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