From 30171f79ab0aaad06b88a66653789691c4ed4f2c Mon Sep 17 00:00:00 2001 From: Akim Demaille Date: Thu, 27 Dec 2001 18:13:47 +0000 Subject: [PATCH] * 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. --- ChangeLog | 20 +++++ src/LR0.c | 194 +++------------------------------------------- src/print.c | 29 +++---- src/print_graph.c | 9 ++- src/reader.c | 18 +++++ src/reduce.c | 2 +- tests/sets.at | 123 +++++++++++++++++++---------- 7 files changed, 154 insertions(+), 241 deletions(-) diff --git a/ChangeLog b/ChangeLog index 5c2bd8f4..71ca161b 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,23 @@ +2001-12-27 Akim Demaille + + * 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. + 2001-12-27 Akim Demaille Try to make the use of the eoftoken valid. Given that its value diff --git a/src/LR0.c b/src/LR0.c index 9f019223..c1a0a8c1 100644 --- a/src/LR0.c +++ b/src/LR0.c @@ -196,6 +196,10 @@ new_state (int symbol) 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 @@ save_shifts (void) } -/*------------------------------------------------------------------. -| 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 @@ augment_automaton (void) 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]]; @@ -594,9 +423,6 @@ generate_states (void) free_closure (); free_storage (); - /* set up initial and final states as parser wants them */ - augment_automaton (); - /* Set up STATE_TABLE. */ set_state_table (); } diff --git a/src/print.c b/src/print.c index dea92aca..b893c5c9 100644 --- a/src/print.c +++ b/src/print.c @@ -102,7 +102,7 @@ print_core (FILE *out, state_t *state) 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 @@ print_reductions (FILE *out, state_t *state) 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 @@ print_reductions (FILE *out, state_t *state) 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 @@ print_reductions (FILE *out, state_t *state) 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 @@ print_reductions (FILE *out, state_t *state) 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 @@ print_reductions (FILE *out, state_t *state) 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])); } } @@ -322,9 +323,9 @@ print_actions (FILE *out, state_t *state) 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; } @@ -375,7 +376,7 @@ print_grammar (FILE *out) 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) @@ -403,7 +404,7 @@ print_grammar (FILE *out) 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); @@ -443,7 +444,7 @@ print_grammar (FILE *out) { END_TEST (65); if (rule_table[j].lhs == i) - sprintf (buffer + strlen (buffer), " %d", j); + sprintf (buffer + strlen (buffer), " %d", j - 1); } } @@ -459,7 +460,7 @@ print_grammar (FILE *out) if (*rule == i) { END_TEST (65); - sprintf (buffer + strlen (buffer), " %d", j); + sprintf (buffer + strlen (buffer), " %d", j - 1); break; } } diff --git a/src/print_graph.c b/src/print_graph.c index 55e4b379..0cdba5a1 100644 --- a/src/print_graph.c +++ b/src/print_graph.c @@ -53,9 +53,12 @@ print_core (state_t *state, struct obstack *node_obstack) 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++) diff --git a/src/reader.c b/src/reader.c index 2f583f1e..5ee5093d 100644 --- a/src/reader.c +++ b/src/reader.c @@ -71,6 +71,7 @@ static int lastprec; 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 @@ readgram (void) 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 */ @@ -1807,6 +1820,11 @@ reader (void) /* 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"); errtoken->class = token_sym; diff --git a/src/reduce.c b/src/reduce.c index d8ea5ed6..89ff3c3b 100644 --- a/src/reduce.c +++ b/src/reduce.c @@ -435,7 +435,7 @@ reduce_output (FILE *out) 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]); diff --git a/tests/sets.at b/tests/sets.at index 7fa8d1f7..a0740790 100644 --- a/tests/sets.at +++ b/tests/sets.at @@ -38,48 +38,63 @@ AT_DATA([[input.y]], 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 @@ Entering append_states, state = 0 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 ]]) -- 2.45.2