Re: syntactic completion

[Hans Aberg]

You might be able to generate "completions" by taking the set of valid
lookahead tokens in any state. The parser has a code segment looking
something like (this is from a C++ parser; names are somewhat different in
the C parser):
  // Backup.
yybackup:

  // Try to make a decision without lookahead:
  n_ = pact_[state_];
  if (n_ == pact_ninf_)
    goto yydefault;

  // Read a lookahead token.
  if (lookahead_ == empty_) {
        // Hold here.
    YYCDEBUG << "Reading a token: ";
    lex_();
  }

Right before lex_() is called again (at "Hold here"), you can compute the
set of all possible 1-lookahead completions by looking at the current state
(state_ above). The set of valid 1-lookahead tokens are listed in the file
.output that Bison writes with the --verbose option on. These valid
lookahead tokens are also listed in the form of numbers in one of the Bison
tables (though I do not know right on which one). These numbers can then be
translated using another table into the token names you have chosen in your
.y grammar. If you write say
  %token NUMBER "<number>"
then this translation will produce the C-string "<number>", which will then
be indicated as a completion.

One problem with the LALR(1) algorithm is that rather than indicating an
error right away, it may introduce a $default symbol, representing all
remaining token in the grammar. It will then reduce, and the error will be
discovered in a later state. This happens because of the technique used to
compact LR(1). It could happen that a LR(1) parser is better for this kind
of tweaks, but Bison does not support that (yet).

When you have figured out what modifications your parser needs, modify its
skeleton file to make your own and invoke it using --skeleton option.

At 15:15 -0700 2004/07/28, Murray Hayes wrote:
>I am trying to write a completion generator function for the gnu
>readline library that uses an existing grammar file to generate
>suggestions based on the syntax that has already been entered.
>
>I have gone through the help archives and found some very helpful
>articles that contain source code for listing all the possible
>satisfying rules:
>
>http://lists.gnu.org/archive/html/help-bison/2002-11/msg00006.html
>
>
>I have put these code snippets into a complete working program to
>experiment with but I am still having some problems getting the
>information I need.
>
>The code referenced above places the expect function in the debug
>section which doesn't seem to be run unless there is a problem.  The
>information that I will be getting from readline is a text string that
>holds the line as it has so far been entered and two integers start and
>end which represent where the word to be completed start and end in the
>string.
>
>>From what I have read in the bison manual, it looks like I will have to
>implement an action in every rule to call expect() to extract the rules
>that can satisfy the grammar at the arbitrary point indicated by start.
>Is this true or is there an easier way to interrupt the parsing process
>at a specified point (perhaps with the lexical analyzer)?
>
>I can supply more information including the program I have that
>implements the expect() function I copied from the archives.  Also, here
>is a link to the relevant manual section on readline:
>
>http://cnswww.cns.cwru.edu/~chet/readline/readline.html#SEC44
>
>
>TIA for any help you can offer.
>
>
>--
>address@hidden
>
>
>
>_______________________________________________
>address@hidden http://lists.gnu.org/mailman/listinfo/help-bison