From 335666b364746a70a6fdae72b4695db0c21b5b24 Mon Sep 17 00:00:00 2001 From: Thadeu Lima de Souza Cascardo Date: Sun, 23 Oct 2005 17:17:46 +0000 Subject: [PATCH] Added LR1 Parsing Algorithm LR(1) parsing algorithm is added to the library. git-archimport-id: cascardo@tlscascardo--private/libgrammatic--lr1--0.1--patch-3 --- lr1.c | 265 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ lr1.h | 18 ++++ 2 files changed, 283 insertions(+) create mode 100644 lr1.c create mode 100644 lr1.h diff --git a/lr1.c b/lr1.c new file mode 100644 index 0000000..d7f2d98 --- /dev/null +++ b/lr1.c @@ -0,0 +1,265 @@ +#include +#include + +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); +} + +static 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; + lr1_push (parser, 0, 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_previous (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; + +} diff --git a/lr1.h b/lr1.h new file mode 100644 index 0000000..89de8ce --- /dev/null +++ b/lr1.h @@ -0,0 +1,18 @@ +#ifndef LR1_H +#define LR1_H + +#include + +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*); +void lr1_add (lr1_t*, gint, symbol_t*, transition_t*); +gpointer lr1_build (lr1_t*); + +#endif -- 2.20.1