[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
lalr: more debug traces
From: |
Akim Demaille |
Subject: |
lalr: more debug traces |
Date: |
Mon, 25 Feb 2019 06:21:13 +0100 |
commit 59bec5fade53bb6d84754457b43b49e037616a48
Author: Akim Demaille <address@hidden>
Date: Sun Feb 24 19:00:41 2019 +0100
lalr: more debug traces
I need to be able to read includes and goto_follows.
* src/relation.h, src/relation.c (relation_print): Provide a means to
pretty-print the nodes of the relation.
* src/lalr.c (goto_print, follows_print): New.
(set_goto_map): Use goto_print.
(build_relations): Show INCLUDES.
(compute_FOLLOWS): Rename as...
(compute_follows): this.
Show FOLLOWS.
diff --git a/src/ielr.c b/src/ielr.c
index 47ce38c3..a1f146b9 100644
--- a/src/ielr.c
+++ b/src/ielr.c
@@ -198,7 +198,7 @@ ielr_compute_internal_follow_edges (bitset
ritem_sees_lookahead_set,
if (trace_flag & trace_ielr)
{
fprintf (stderr, "internal_follow_edges:\n");
- relation_print (*edgesp, ngotos, stderr);
+ relation_print (*edgesp, ngotos, NULL, stderr);
}
}
@@ -305,7 +305,7 @@ ielr_compute_always_follows (goto_number ***edgesp,
if (trace_flag & trace_ielr)
{
fprintf (stderr, "always follow edges:\n");
- relation_print (*edgesp, ngotos, stderr);
+ relation_print (*edgesp, ngotos, NULL, stderr);
fprintf (stderr, "always_follows:\n");
debug_bitsetv (*always_followsp);
}
diff --git a/src/lalr.c b/src/lalr.c
index 40f1502d..46cf01e5 100644
--- a/src/lalr.c
+++ b/src/lalr.c
@@ -67,6 +67,15 @@ size_t nLA;
static goto_number **includes;
static goto_list **lookback;
+static void
+goto_print (goto_number i, FILE* out)
+{
+ const state_number src = from_state[i];
+ const state_number dst = to_state[i];
+ symbol_number var = states[dst]->accessing_symbol;
+ fprintf (out,
+ "goto[%ld] = (%d, %s, %d)", i, src, symbols[var]->tag, dst);
+}
void
set_goto_map (void)
@@ -117,6 +126,13 @@ set_goto_map (void)
}
free (temp_map);
+
+ if (trace_flag & trace_automaton)
+ for (int i = 0; i < ngotos; ++i)
+ {
+ goto_print (i, stderr);
+ fputc ('\n', stderr);
+ }
}
@@ -140,7 +156,7 @@ map_goto (state_number src, symbol_number sym)
}
}
-
+/* Build goto_follows. */
static void
initialize_F (void)
{
@@ -181,7 +197,6 @@ initialize_F (void)
for (goto_number i = 0; i < ngotos; ++i)
free (reads[i]);
-
free (reads);
free (edge);
}
@@ -198,7 +213,8 @@ add_lookback_edge (state *s, rule const *r, goto_number
gotono)
}
-
+/* Compute INCLUDES and LOOKBACK. Corresponds to step E in Sec. 6 of
+ [DeRemer 1982]. */
static void
build_relations (void)
{
@@ -265,18 +281,42 @@ build_relations (void)
free (path);
relation_transpose (&includes, ngotos);
+ if (trace_flag & trace_automaton)
+ {
+ fprintf (stderr, "includes:\n");
+ relation_print (includes, ngotos, goto_print, stderr);
+ }
}
+/* Print FOLLOWS for debugging. */
+static void
+follows_print (FILE* out)
+{
+ for (goto_number i = 0; i < ngotos; ++i)
+ {
+ fputs ("FOLLOWS[", out);
+ goto_print (i, out);
+ fputs ("] =", out);
+ bitset_iterator iter;
+ symbol_number sym;
+ BITSET_FOR_EACH (iter, goto_follows[i], sym, 0)
+ {
+ fputc (' ', out);
+ symbol_print (symbols[sym], out);
+ }
+ fputc ('\n', out);
+ }
+}
-
+/* Compute FOLLOWS from INCLUDES, and free INCLUDES. */
static void
-compute_FOLLOWS (void)
+compute_follows (void)
{
relation_digraph (includes, ngotos, &goto_follows);
-
+ if (trace_flag & trace_sets)
+ follows_print (stderr);
for (goto_number i = 0; i < ngotos; ++i)
free (includes[i]);
-
free (includes);
}
@@ -291,7 +331,6 @@ compute_lookahead_tokens (void)
/* Free LOOKBACK. */
for (size_t i = 0; i < nLA; ++i)
LIST_FREE (goto_list, lookback[i]);
-
free (lookback);
}
@@ -421,7 +460,7 @@ lalr (void)
initialize_F ();
lookback = xcalloc (nLA, sizeof *lookback);
build_relations ();
- compute_FOLLOWS ();
+ compute_follows ();
compute_lookahead_tokens ();
if (trace_flag & trace_sets)
diff --git a/src/lalr.h b/src/lalr.h
index 84a66f7c..1ef3c40c 100644
--- a/src/lalr.h
+++ b/src/lalr.h
@@ -102,5 +102,4 @@ goto_number map_goto (state_number src, symbol_number sym);
/* goto_follows[i] is the set of tokens following goto i. */
extern bitsetv goto_follows;
-
#endif /* !LALR_H_ */
diff --git a/src/relation.c b/src/relation.c
index abee524d..57c14292 100644
--- a/src/relation.c
+++ b/src/relation.c
@@ -27,14 +27,25 @@
#include "relation.h"
void
-relation_print (relation r, relation_node size, FILE *out)
+relation_print (relation r, relation_node size,
+ relation_node_print print, FILE *out)
{
- for (relation_node i = 0; i < size; ++i)
+ for (size_t i = 0; i < size; ++i)
{
- fprintf (out, "%3lu: ", (unsigned long) i);
+ if (print)
+ print (i, out);
+ else
+ fprintf (out, "%3lu", (unsigned long) i);
+ fputc (':', out);
if (r[i])
for (relation_node j = 0; r[i][j] != END_NODE; ++j)
- fprintf (out, "%3lu ", (unsigned long) r[i][j]);
+ {
+ fputc (' ', out);
+ if (print)
+ print (r[i][j], out);
+ else
+ fprintf (out, "%3lu", (unsigned long) r[i][j]);
+ }
fputc ('\n', out);
}
fputc ('\n', out);
@@ -58,10 +69,8 @@ static bitsetv F;
static void
traverse (relation_node i)
{
- relation_node height;
-
vertices[++top] = i;
- indexes[i] = height = top;
+ relation_node height = indexes[i] = top;
if (R[i])
for (relation_node j = 0; R[i][j] != END_NODE; ++j)
@@ -116,30 +125,30 @@ relation_digraph (relation r, relation_node size, bitsetv
*function)
`-------------------------------------------*/
void
-relation_transpose (relation *R_arg, relation_node n)
+relation_transpose (relation *R_arg, relation_node size)
{
relation r = *R_arg;
if (trace_flag & trace_sets)
{
fputs ("relation_transpose: input\n", stderr);
- relation_print (r, n, stderr);
+ relation_print (r, size, NULL, stderr);
}
/* Count. */
/* NEDGES[I] -- total size of NEW_R[I]. */
- size_t *nedges = xcalloc (n, sizeof *nedges);
- for (relation_node i = 0; i < n; i++)
+ size_t *nedges = xcalloc (size, sizeof *nedges);
+ for (relation_node i = 0; i < size; i++)
if (r[i])
for (relation_node j = 0; r[i][j] != END_NODE; ++j)
++nedges[r[i][j]];
/* Allocate. */
/* The result. */
- relation new_R = xnmalloc (n, sizeof *new_R);
+ relation new_R = xnmalloc (size, sizeof *new_R);
/* END_R[I] -- next entry of NEW_R[I]. */
- relation end_R = xnmalloc (n, sizeof *end_R);
- for (relation_node i = 0; i < n; i++)
+ relation end_R = xnmalloc (size, sizeof *end_R);
+ for (relation_node i = 0; i < size; i++)
{
relation_node *sp = NULL;
if (nedges[i] > 0)
@@ -152,7 +161,7 @@ relation_transpose (relation *R_arg, relation_node n)
}
/* Store. */
- for (relation_node i = 0; i < n; i++)
+ for (relation_node i = 0; i < size; i++)
if (r[i])
for (relation_node j = 0; r[i][j] != END_NODE; ++j)
*end_R[r[i][j]]++ = i;
@@ -161,14 +170,14 @@ relation_transpose (relation *R_arg, relation_node n)
free (end_R);
/* Free the input: it is replaced with the result. */
- for (relation_node i = 0; i < n; i++)
+ for (relation_node i = 0; i < size; i++)
free (r[i]);
free (r);
if (trace_flag & trace_sets)
{
fputs ("relation_transpose: output\n", stderr);
- relation_print (new_R, n, stderr);
+ relation_print (new_R, size, NULL, stderr);
}
*R_arg = new_R;
diff --git a/src/relation.h b/src/relation.h
index e6b59ff8..0edf59e1 100644
--- a/src/relation.h
+++ b/src/relation.h
@@ -33,9 +33,11 @@ typedef size_t relation_node;
typedef relation_node *relation_nodes;
typedef relation_nodes *relation;
+typedef void (relation_node_print) (relation_node node, FILE* out);
/* Report a relation R that has SIZE vertices. */
-void relation_print (relation r, relation_node size, FILE *out);
+void relation_print (relation r, size_t size,
+ relation_node_print print, FILE *out);
/* Compute the transitive closure of the FUNCTION on the relation R
with SIZE vertices.
@@ -44,7 +46,7 @@ void relation_print (relation r, relation_node size, FILE
*out);
(unioned) with FUNCTION[NODE - 2]. */
void relation_digraph (relation r, relation_node size, bitsetv *function);
-/* Destructively transpose *R_ARG, of size N. */
-void relation_transpose (relation *R_arg, relation_node n);
+/* Destructively transpose *R_ARG, of size SIZE. */
+void relation_transpose (relation *R_arg, relation_node size);
#endif /* ! RELATION_H_ */
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- lalr: more debug traces,
Akim Demaille <=