From 1d8e2bcf9ec46a1f9bd88db48f49203f69e75a58 Mon Sep 17 00:00:00 2001 From: Thadeu Lima de Souza Cascardo Date: Sun, 2 Oct 2005 19:36:51 +0000 Subject: [PATCH] LR1 Items with lookahead instead of LR0 items Replaced LR(0) with LR(1) with a lookahead in the items and a new closure function, and a first hash table used to calculate it. git-archimport-id: cascardo@tlscascardo--private/libgrammatic--lr1--0.1--patch-1 --- item.c | 82 +++++++++++++++++++++++++++++++++++++++++++--------------- 1 file changed, 61 insertions(+), 21 deletions(-) diff --git a/item.c b/item.c index 9c05e06..3eb8fe3 100644 --- a/item.c +++ b/item.c @@ -1,4 +1,5 @@ #include +#include #ifdef DEBUG #include #endif @@ -8,15 +9,17 @@ typedef struct symbol_t* left; rule_t* right; GList* dot; + symbol_t* lookahead; } 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; } @@ -24,7 +27,8 @@ item_t* item_copy (item_t* 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; @@ -39,6 +43,8 @@ gint item_cmp (const item_t* a, const item_t* b) 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) @@ -59,6 +65,7 @@ guint item_hash (gconstpointer data) 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; } @@ -66,6 +73,7 @@ void item_delete (item_t* item) { g_free (item->left); rule_delete (item->right); + g_free (item->lookahead); g_free (item); } @@ -90,7 +98,7 @@ void item_print (item_t* item) { fprintf (stdout, "."); } - fprintf (stdout, "\n"); + fprintf (stdout, ", %s\n", g_quark_to_string (item->lookahead->value)); } #endif @@ -173,8 +181,25 @@ void item_set_print (GHashTable* item_set) } #endif +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* grammar, - item_t* item) + GHashTable* first, item_t* item) { if (item->dot != NULL) { @@ -183,22 +208,36 @@ void item_set_closure_step (GHashTable* item_set, Grammar* grammar, 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* grammar, + GHashTable* first) { int size; int last_size; @@ -211,7 +250,7 @@ GHashTable* item_set_closure (GHashTable* item_set, Grammar* grammar) 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); @@ -221,7 +260,7 @@ GHashTable* item_set_closure (GHashTable* item_set, Grammar* grammar) } GHashTable* item_set_goto (GHashTable* item_set, Grammar* grammar, - symbol_t* symbol) + GHashTable* first, symbol_t* symbol) { GList* l; GHashTable* newitem_set; @@ -244,7 +283,7 @@ GHashTable* item_set_goto (GHashTable* item_set, Grammar* grammar, } l = g_list_next (l); } - return item_set_closure (newitem_set, grammar); + return item_set_closure (newitem_set, grammar, first); } @@ -352,7 +391,7 @@ void item_set_print_goto (gpointer key, gpointer val, gpointer data) gint code; state_t* state; symbol = (symbol_t*) key; - code = GINT_TO_POINTER (val); + 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); @@ -374,7 +413,8 @@ void item_collection_print (GHashTable* collection) #endif GHashTable* item_collection_goto (GHashTable* collection, Grammar* grammar, - GHashTable* item_set, symbol_t* symbol) + GHashTable* first, GHashTable* item_set, + symbol_t* symbol) { state_t* state; state_t* goto_state; @@ -391,7 +431,7 @@ GHashTable* item_collection_goto (GHashTable* collection, Grammar* grammar, { 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)) return_item_set = NULL; else @@ -402,7 +442,7 @@ GHashTable* item_collection_goto (GHashTable* collection, Grammar* grammar, return return_item_set; } -void item_set_collection (Grammar* grammar, symbol_t* start) +void item_set_collection (Grammar* grammar, GHashTable* first, symbol_t* start) { GHashTable* collection; GHashTable* item_set; @@ -411,10 +451,10 @@ void item_set_collection (Grammar* grammar, symbol_t* start) 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); @@ -436,7 +476,7 @@ void item_set_collection (Grammar* grammar, symbol_t* start) { 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); -- 2.20.1