Re: Bison 1.50 question: Can it support Auto-Complete?

[Akim Demaille]

| > Date: Fri, 18 Oct 2002 11:56:14 -1000
| > From: Chris Hundhausen <address@hidden>
| > 
| > I'm trying to build "auto-complete" functionality into an interactive
| > development environment. The language I'm parsing is written in
| > flex/bison (probably v. 1.25). In other words, for incomplete sentences
| > in my language, I want to generate a complete list of valid next tokens.
| > Unfortunately, setting the VERBOSE flag in Bison doesn't do the job. I
| > do, indeed, receive *some* valid completions, but not all. As far as I
| > can tell, if multiple rules are tried, the verbose error message reports
| > only the next possible tokens in the _last_ rule attempted; possible
| > completions from previous rules are not reported.
| > 
| > So, I'm wondering if --report=THINGS does anything differently.  Is
| > 'itemset' a list of all next possible tokens?
| 
| Sorry, I'm not the right guy to ask about this (I could read the code,
| but then that wouldn't be more efficient than your doing it).
| 
| I'll CC: this to help-bison to see whether others can suggest more.

Hi there, 

I'm not sure I completely understand the question, in particular, it's
not clear to me whether you want to extract them from the verbose
output, or from the tables themselves.  In any case, Bison computes
the minimum set of lookahead for each state, i.e., the phenomenon you
describe is expected: lookaheads are computed _only_ if needed
(otherwise it just accepts any token and reports this as $default).
When a state needs no lookahead, it is said to be consistent.

Maybe you can force Bison to compute all the lookaheads.  I never
tried though.  Try to change these lines (lalr.c):


static int
state_lookaheads_count (state_t *state)
{
  int k;
  int nlookaheads = 0;
  reductions_t *rp = state->reductions;
  transitions_t *sp = state->transitions;

  /* We need a lookahead either to distinguish different
     reductions (i.e., there are two or more), or to distinguish a
     reduction from a shift.  Otherwise, it is straightforward,
     and the state is `consistent'.  */
  if (rp->num > 1
      || (rp->num == 1 && sp->num &&
          !TRANSITION_IS_DISABLED (sp, 0) && TRANSITION_IS_SHIFT (sp, 0)))
    nlookaheads += rp->num;
  else
    state->consistent = 1;

  for (k = 0; k < sp->num; k++)
    if (!TRANSITION_IS_DISABLED (sp, k) && TRANSITION_IS_ERROR (sp, k))
      {
        state->consistent = 0;
        break;
      }

  return nlookaheads;
}


Actually, I just tried on the simple calculator attached:

calc.y
Description: Text document

I replace with this code:

static int
state_lookaheads_count (state_t *state)
{
  int k;
  int nlookaheads = 0;
  reductions_t *rp = state->reductions;
  transitions_t *sp = state->transitions;

  /* We need a lookahead either to distinguish different
     reductions (i.e., there are two or more), or to distinguish a
     reduction from a shift.  Otherwise, it is straightforward,
     and the state is `consistent'.  */
  if (rp->num > 1
      || (rp->num == 1 && sp->num &&
          !TRANSITION_IS_DISABLED (sp, 0) && TRANSITION_IS_SHIFT (sp, 0)))
    nlookaheads += rp->num;
  else
    state->consistent = 1;

  for (k = 0; k < sp->num; k++)
    if (!TRANSITION_IS_DISABLED (sp, k) && TRANSITION_IS_ERROR (sp, k))
      {
        state->consistent = 0;
        break;
      }

  return nlookaheads;
}


and he is the comparison of the --report=all outputs:

tests/testsuite.dir/50 % diff orig.output new.output -u          nostromo Err 2
--- orig.output 2002-10-22 09:31:34.000000000 +0200
+++ new.output  2002-10-22 09:32:12.000000000 +0200
@@ -1,3 +1,8 @@
+Règles jamais réduites
+
+    0 $accept: input "end of input"
+
+
 Grammaire
 
     0 $accept: input "end of input"
@@ -80,7 +85,7 @@
 
 état 1
 
-    5 exp: "number" .
+    5 exp: "number" .  ['=', '-', '+', '*', '/', '^', '\n', ')']
 
     $défaut  réduction par utilisation de la règle 5 (exp)
 
@@ -108,7 +113,7 @@
 
 état 3
 
-    3 line: '\n' .
+    3 line: '\n' .  ["end of input", "number", '-', '\n', '(']
 
     $défaut  réduction par utilisation de la règle 3 (line)
 
@@ -165,7 +170,7 @@
 
 état 6
 
-    1 input: line .
+    1 input: line .  ["end of input", "number", '-', '\n', '(']
 
     $défaut  réduction par utilisation de la règle 1 (input)
 
@@ -239,14 +244,12 @@
 
 état 11
 
-    0 $accept: input "end of input" .
-
-    $défaut  accepter
+    0 $accept: input "end of input" .  []
 
 
 état 12
 
-    2 input: input line .
+    2 input: input line .  ["end of input", "number", '-', '\n', '(']
 
     $défaut  réduction par utilisation de la règle 2 (input)
 
@@ -379,21 +382,21 @@
 
 état 19
 
-    4 line: exp '\n' .
+    4 line: exp '\n' .  ["end of input", "number", '-', '\n', '(']
 
     $défaut  réduction par utilisation de la règle 4 (line)
 
 
 état 20
 
-   14 exp: '(' error ')' .
+   14 exp: '(' error ')' .  ['=', '-', '+', '*', '/', '^', '\n', ')']
 
     $défaut  réduction par utilisation de la règle 14 (exp)
 
 
 état 21
 
-   13 exp: '(' exp ')' .
+   13 exp: '(' exp ')' .  ['=', '-', '+', '*', '/', '^', '\n', ')']
 
     $défaut  réduction par utilisation de la règle 13 (exp)
 


So it does seem that you can force it to compute these guys.  Bad
news: you'll have to track down why now bison says:

tests/testsuite.dir/50 % LC_ALL=C ../../bison --report=all calc.y -o new.c 
calc.y:90.6-91.6: warning: rule never reduced because of conflicts: $accept: 
input "end of input"


which is quite a bad news: it says the entry point of the grammar can
never be used :) :) :)