[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
21-fyi-initial-rule.patch
|
From: |
Akim Demaille |
|
Subject: |
21-fyi-initial-rule.patch |
|
Date: |
Thu, 27 Dec 2001 19:02:30 +0100 |
Index: ChangeLog
from Akim Demaille <address@hidden>
* src/LR0.c (new_state): Recognize the final state by the fact it
is reached by eoftoken.
(insert_start_shifting_state, insert_eof_shifting_state)
(insert_accepting_state, augment_automaton): Remove, since now
these states are automatically computed from the initial state.
(generate_states): Adjust.
* src/print.c: When reporting a rule number to the user, substract
1, so that the axiom rule is rule 0, and the first user rule is 1.
* src/reduce.c: Likewise.
* src/print_graph.c (print_core): For the time being, just as for
the report, depend upon --trace-flags to dump the full set of
items.
* src/reader.c (readgram): Once the grammar read, insert the rule
0: `$axiom: START-SYMBOL $'.
* tests/set.at: Adjust: rule 0 is now displayed, and since the
number of the states has changed (the final state is no longer
necessarily the last), catch up.
Index: src/LR0.c
--- src/LR0.c Thu, 27 Dec 2001 15:45:59 +0100 akim
+++ src/LR0.c Thu, 27 Dec 2001 17:08:12 +0100 akim
@@ -196,6 +196,10 @@
last_state = p;
nstates++;
+ /* If this is the eoftoken, then this is the final state. */
+ if (symbol == 0)
+ final_state = p->number;
+
return p;
}
@@ -321,184 +325,6 @@
}
-/*------------------------------------------------------------------.
-| Subroutine of augment_automaton. Create the next-to-final state, |
-| to which a shift has already been made in the initial state. |
-| |
-| The task of this state consists in shifting (actually, it's a |
-| goto, but shifts and gotos are both stored in SHIFTS) the start |
-| symbols, hence the name. |
-`------------------------------------------------------------------*/
-
-static void
-insert_start_shifting_state (void)
-{
- state_t *statep;
- shifts *sp;
-
- statep = STATE_ALLOC (0);
- statep->number = nstates++;
-
- /* The distinctive feature of this state from the
- eof_shifting_state, is that it is labeled as post-start-symbol
- shifting. I fail to understand why this state, and the
- post-start-start can't be merged into one. But it does fail if
- you try. --akim */
- statep->accessing_symbol = start_symbol;
-
- last_state->next = statep;
- last_state = statep;
-
- /* Make a shift from this state to (what will be) the final state. */
- sp = shifts_new (1);
- statep->shifts = sp;
- sp->shifts[0] = nstates;
-}
-
-
-/*-----------------------------------------------------------------.
-| Subroutine of augment_automaton. Create the final state, which |
-| shifts `0', the end of file. The initial state shifts the start |
-| symbol, and goes to here. |
-`-----------------------------------------------------------------*/
-
-static void
-insert_eof_shifting_state (void)
-{
- state_t *statep;
- shifts *sp;
-
- /* Make the final state--the one that follows a shift from the
- next-to-final state.
- The symbol for that shift is 0 (end-of-file). */
- statep = STATE_ALLOC (0);
- statep->number = nstates++;
-
- last_state->next = statep;
- last_state = statep;
-
- /* Make the shift from the final state to the termination state. */
- sp = shifts_new (1);
- statep->shifts = sp;
- sp->shifts[0] = nstates;
-}
-
-
-/*---------------------------------------------------------------.
-| Subroutine of augment_automaton. Create the accepting state. |
-`---------------------------------------------------------------*/
-
-static void
-insert_accepting_state (void)
-{
- state_t *statep;
-
- /* Note that the variable `final_state' refers to what we sometimes
- call the termination state. */
- final_state = nstates;
-
- /* Make the termination state. */
- statep = STATE_ALLOC (0);
- statep->number = nstates++;
- last_state->next = statep;
- last_state = statep;
-}
-
-
-
-
-
-/*------------------------------------------------------------------.
-| Make sure that the initial state has a shift that accepts the |
-| grammar's start symbol and goes to the next-to-final state, which |
-| has a shift going to the final state, which has a shift to the |
-| termination state. Create such states and shifts if they don't |
-| happen to exist already. |
-`------------------------------------------------------------------*/
-
-static void
-augment_automaton (void)
-{
- if (!first_state->shifts->nshifts)
- {
- /* The first state has no shifts. Make one shift, from the
- initial state to the next-to-final state. */
-
- shifts *sp = shifts_new (1);
- first_state->shifts = sp;
- sp->shifts[0] = nstates;
-
- /* Create the next-to-final state, with shift to
- what will be the final state. */
- insert_start_shifting_state ();
- }
- else
- {
- state_t *statep = first_state->next;
- /* The states reached by shifts from FIRST_STATE are numbered
- 1..(SP->NSHIFTS). Look for one reached by START_SYMBOL.
- This is typical of `start: start ... ;': there is a state
- with the item `start: start . ...'. We want to add a `shift
- on EOF to eof-shifting state here. */
- while (statep->accessing_symbol != start_symbol
- && statep->number < first_state->shifts->nshifts)
- statep = statep->next;
-
- if (statep->accessing_symbol == start_symbol)
- {
- /* We already have STATEP, a next-to-final state for `start:
- start . ...'. Make sure it has a shift to what will be
- the final state. */
- int i;
-
- /* Find the shift of the inital state that leads to STATEP. */
- shifts *sp = statep->shifts;
-
- shifts *sp1 = shifts_new (sp->nshifts + 1);
- statep->shifts = sp1;
- sp1->shifts[0] = nstates;
- for (i = sp->nshifts; i > 0; i--)
- sp1->shifts[i] = sp->shifts[i - 1];
-
- XFREE (sp);
-
- insert_eof_shifting_state ();
- }
- else
- {
- /* There is no state for `start: start . ...'. */
- int i, k;
- shifts *sp = first_state->shifts;
- shifts *sp1 = NULL;
-
- /* Add one more shift to the initial state, going to the
- next-to-final state (yet to be made). */
- sp1 = shifts_new (sp->nshifts + 1);
- first_state->shifts = sp1;
- /* Stick this shift into the vector at the proper place. */
- statep = first_state->next;
- for (k = 0, i = 0; i < sp->nshifts; k++, i++)
- {
- if (statep->accessing_symbol > start_symbol && i == k)
- sp1->shifts[k++] = nstates;
- sp1->shifts[k] = sp->shifts[i];
- statep = statep->next;
- }
- if (i == k)
- sp1->shifts[k++] = nstates;
-
- XFREE (sp);
-
- /* Create the next-to-final state, with shift to what will
- be the final state. Corresponds to `start: start . ...'. */
- insert_start_shifting_state ();
- }
- }
-
- insert_accepting_state ();
-}
-
-
/*----------------------------------------------------------------.
| Find which rules can be used for reduction transitions from the |
| current state and make a reductions structure for the state to |
@@ -508,12 +334,15 @@
static void
save_reductions (void)
{
- int count;
+ int count = 0;
int i;
- /* Find and count the active items that represent ends of rules. */
+ /* If this is the final state, we want it to have no reductions at
+ all, although it has one for `START_SYMBOL EOF .'. */
+ if (this_state->number == final_state)
+ return;
- count = 0;
+ /* Find and count the active items that represent ends of rules. */
for (i = 0; i < nitemset; ++i)
{
int item = ritem[itemset[i]];
@@ -593,9 +422,6 @@
/* discard various storage */
free_closure ();
free_storage ();
-
- /* set up initial and final states as parser wants them */
- augment_automaton ();
/* Set up STATE_TABLE. */
set_state_table ();
Index: src/print.c
--- src/print.c Thu, 27 Dec 2001 15:45:59 +0100 akim
+++ src/print.c Thu, 27 Dec 2001 16:44:08 +0100 akim
@@ -102,7 +102,7 @@
for (/* Nothing */; *sp >= 0; ++sp)
fprintf (out, " %s", escape (tags[*sp]));
- fprintf (out, _(" (rule %d)"), rule);
+ fprintf (out, _(" (rule %d)"), rule - 1);
fputc ('\n', out);
}
@@ -189,7 +189,7 @@
int rule = redp->rules[0];
int symbol = rule_table[rule].lhs;
fprintf (out, _(" $default\treduce using rule %d (%s)\n\n"),
- rule, escape (tags[symbol]));
+ rule - 1, escape (tags[symbol]));
return;
}
@@ -221,11 +221,11 @@
for (i = 0; i < ntokens; i++)
if (BITISSET (lookaheadset, i))
fprintf (out, _(" %-4s\t[reduce using rule %d (%s)]\n"),
- escape (tags[i]), default_rule,
+ escape (tags[i]), default_rule - 1,
escape2 (tags[rule_table[default_rule].lhs]));
fprintf (out, _(" $default\treduce using rule %d (%s)\n\n"),
- default_rule, escape (tags[rule_table[default_rule].lhs]));
+ default_rule - 1, escape (tags[rule_table[default_rule].lhs]));
}
else if (state->nlookaheads >= 1)
{
@@ -280,7 +280,7 @@
fprintf (out,
_(" %-4s\treduce using rule %d (%s)\n"),
escape (tags[i]),
- LAruleno[state->lookaheadsp + j],
+ LAruleno[state->lookaheadsp + j] - 1,
escape2
(tags[rule_table[LAruleno[state->lookaheadsp + j]].lhs]));
else
defaulted = 1;
@@ -293,13 +293,13 @@
fprintf (out,
_(" %-4s\treduce using rule %d (%s)\n"),
escape (tags[i]),
- LAruleno[default_LA],
+ LAruleno[default_LA] - 1,
escape2
(tags[rule_table[LAruleno[default_LA]].lhs]));
defaulted = 0;
fprintf (out,
_(" %-4s\t[reduce using rule %d (%s)]\n"),
escape (tags[i]),
- LAruleno[state->lookaheadsp + j],
+ LAruleno[state->lookaheadsp + j] - 1,
escape2
(tags[rule_table[LAruleno[state->lookaheadsp + j]].lhs]));
}
}
@@ -308,7 +308,8 @@
if (default_LA >= 0)
fprintf (out, _(" $default\treduce using rule %d (%s)\n"),
- default_rule, escape (tags[rule_table[default_rule].lhs]));
+ default_rule - 1,
+ escape (tags[rule_table[default_rule].lhs]));
}
}
@@ -323,9 +324,9 @@
if (shiftp->nshifts == 0 && redp->nreds == 0)
{
if (final_state == state->number)
- fprintf (out, _(" $default\taccept\n"));
+ fprintf (out, _(" $default\taccept\n"));
else
- fprintf (out, _(" NO ACTIONS\n"));
+ fprintf (out, _(" NO ACTIONS\n"));
return;
}
@@ -376,7 +377,7 @@
if (rule_table[i].useful)
{
fprintf (out, _(" %3d %3d %s ->"),
- i, rule_table[i].line, escape (tags[rule_table[i].lhs]));
+ i - 1, rule_table[i].line, escape (tags[rule_table[i].lhs]));
rule = &ritem[rule_table[i].rhs];
if (*rule >= 0)
while (*rule >= 0)
@@ -404,7 +405,7 @@
if (*rule == token_translations[i])
{
END_TEST (65);
- sprintf (buffer + strlen (buffer), " %d", j);
+ sprintf (buffer + strlen (buffer), " %d", j - 1);
break;
}
fprintf (out, "%s\n", buffer);
@@ -444,7 +445,7 @@
{
END_TEST (65);
if (rule_table[j].lhs == i)
- sprintf (buffer + strlen (buffer), " %d", j);
+ sprintf (buffer + strlen (buffer), " %d", j - 1);
}
}
@@ -460,7 +461,7 @@
if (*rule == i)
{
END_TEST (65);
- sprintf (buffer + strlen (buffer), " %d", j);
+ sprintf (buffer + strlen (buffer), " %d", j - 1);
break;
}
}
Index: src/print_graph.c
--- src/print_graph.c Thu, 27 Dec 2001 16:33:48 +0100 akim
+++ src/print_graph.c Thu, 27 Dec 2001 17:03:56 +0100 akim
@@ -53,9 +53,12 @@
int snitems = state->nitems;
/* Output all the items of a state, not only its kernel. */
- closure (sitems, snitems);
- sitems = itemset;
- snitems = nitemset;
+ if (trace_flag)
+ {
+ closure (sitems, snitems);
+ sitems = itemset;
+ snitems = nitemset;
+ }
obstack_fgrow1 (node_obstack, "state %2d\n", state->number);
for (i = 0; i < snitems; i++)
Index: src/reader.c
--- src/reader.c Thu, 27 Dec 2001 15:45:59 +0100 akim
+++ src/reader.c Thu, 27 Dec 2001 16:55:19 +0100 akim
@@ -71,6 +71,7 @@
static bucket *errtoken = NULL;
static bucket *undeftoken = NULL;
static bucket *eoftoken = NULL;
+static bucket *axiom = NULL;
static symbol_list *
symbol_list_new (bucket *sym)
@@ -1450,6 +1451,18 @@
t = lex ();
}
+ /* Insert the initial rule:
+
+ axiom: %start EOF. */
+ p = symbol_list_new (axiom);
+ p->next = symbol_list_new (startval);
+ p->next->next = symbol_list_new (eoftoken);
+ p->next->next->next = symbol_list_new (NULL);
+ p->next->next->next->next = grammar;
+ nrules += 1;
+ nitems += 3;
+ grammar = p;
+ startval = axiom;
/* grammar has been read. Do some checking */
@@ -1806,6 +1819,11 @@
/* Initialize the symbol table. */
tabinit ();
+
+ /* Construct the axiom symbol. */
+ axiom = getsym ("$axiom");
+ axiom->class = nterm_sym;
+ axiom->value = nvars++;
/* Construct the error token */
errtoken = getsym ("error");
Index: src/reduce.c
--- src/reduce.c Tue, 04 Dec 2001 14:02:26 +0100 akim
+++ src/reduce.c Thu, 27 Dec 2001 16:34:33 +0100 akim
@@ -435,7 +435,7 @@
if (!rule_table[i].useful)
{
rule r;
- fprintf (out, "#%-4d ", i);
+ fprintf (out, "#%-4d ", i - 1);
fprintf (out, "%s:", tags[rule_table[i].lhs]);
for (r = &ritem[rule_table[i].rhs]; *r >= 0; r++)
fprintf (out, " %s", tags[*r]);
Index: tests/sets.at
--- tests/sets.at Thu, 13 Dec 2001 10:51:57 +0100 akim
+++ tests/sets.at Thu, 27 Dec 2001 16:58:13 +0100 akim
@@ -38,48 +38,63 @@
e: 'e' | /* Nothing */;
]])
-AT_CHECK([[bison --trace input.y]], [], [],
+AT_CHECK([[bison --trace input.y]], [], [], [stderr])
+
+AT_CHECK([[sed 's/[ ]*$//' stderr]], [],
[[RITEM
- 'e' (rule 1)
- (rule 2)
+ e $ (rule 1)
+ 'e' (rule 2)
+ (rule 3)
DERIVES
+ $axiom derives
+ 1: e (rule 0)
e derives
- 1: 'e' (rule 1)
- 2: (rule 2)
+ 2: 'e' (rule 2)
+ 3: (rule 3)
Entering set_nullable
NULLABLE
+ $axiom: yes
e: yes
TC: Input BEGIN
- @&t@
- 0
- .-.
- 0| |
- `-'
+
+ 01
+ .--.
+ 0| 1|
+ 1| |
+ `--'
TC: Input END
TC: Output BEGIN
- @&t@
- 0
- .-.
- 0| |
- `-'
+
+ 01
+ .--.
+ 0| 1|
+ 1| |
+ `--'
TC: Output END
FIRSTS
+ $axiom firsts
+ 4 ($axiom)
+ 5 (e)
e firsts
- 4 (e)
+ 5 (e)
FDERIVES
+ $axiom derives
+ 1: e $
+ 2: 'e'
+ 3:
e derives
- 1: 'e'
- 2:
+ 2: 'e'
+ 3:
Processing state 0 (reached by $)
@@ -87,8 +102,9 @@ Closure: input
Closure: output
- 0: . 'e' (rule 1)
- 2: . (rule 2)
+ 0: . e $ (rule 1)
+ 3: . 'e' (rule 2)
+ 5: . (rule 3)
Entering new_itemsets, state = 0
@@ -96,22 +112,50 @@ Closure: output
Entering get_state, state = 0, symbol = 3 ('e')
Entering new_state, state = 0, symbol = 3 ('e')
Exiting get_state => 1
+Entering get_state, state = 0, symbol = 5 (e)
+Entering new_state, state = 0, symbol = 5 (e)
+Exiting get_state => 2
Processing state 1 (reached by 'e')
Closure: input
- 1: . (rule 1)
+ 4: . (rule 2)
Closure: output
- 1: . (rule 1)
+ 4: . (rule 2)
Entering new_itemsets, state = 1
Entering append_states, state = 1
+Processing state 2 (reached by e)
+Closure: input
+ 1: . $ (rule 1)
+
+
+Closure: output
+ 1: . $ (rule 1)
+
+
+Entering new_itemsets, state = 2
+Entering append_states, state = 2
+Entering get_state, state = 2, symbol = 0 ($)
+Entering new_state, state = 2, symbol = 0 ($)
+Exiting get_state => 3
+Processing state 3 (reached by $)
+Closure: input
+ 2: . (rule 1)
+
+
+Closure: output
+ 2: . (rule 1)
+
+
+Entering new_itemsets, state = 3
+Entering append_states, state = 3
transpose: input
- 0: @&t@
+ 0:
transpose: output
- 0: @&t@
+ 0:
]])
@@ -171,22 +215,23 @@ g: h
h: 'h'
]])
-AT_CHECK([bison --trace input.y 2>&1 |
- sed -n '/^TC: Output BEGIN/,/^TC: Output END/p'],
- [0],
+AT_CHECK([[bison --trace input.y]], [], [], [stderr])
+
+AT_CHECK([[sed -n 's/[ ]*$//;/^TC: Output BEGIN/,/^TC: Output END/p'
stderr]], [],
[[TC: Output BEGIN
- @&t@
- 01234567
- .--------.
- 0| 1111111|
- 1| 111111|
- 2| 11111|
- 3| 1111|
- 4| 111|
- 5| 11|
- 6| 1|
- 7| |
- `--------'
+
+ 012345678
+ .---------.
+ 0| 11111111|
+ 1| 1111111|
+ 2| 111111|
+ 3| 11111|
+ 4| 1111|
+ 5| 111|
+ 6| 11|
+ 7| 1|
+ 8| |
+ `---------'
TC: Output END
]])
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- 21-fyi-initial-rule.patch,
Akim Demaille <=