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

[Nils Hasler]

Hi Chris.

Sorry, this took a few days...

I attached a simple calculator-grammar, which supports the expect() 
function. After bisoning it I changed the calc.tab.c according to the 
calc.diff.

Incremental parsing is possible with bison too, but *.tab.c has to be 
changed a lot more.
1. yyparse() has to be seperated into 2 functions. a start-function 
which only does the initialization of all those local variables. the 
other one yycontinue() does all the parsing.
2. the stacks have to be allocated from the heap instead of the stack, 
since yycontinue() may return without being finished.
3. a metatoken has to be defined, which means that the cursor was hit 
and yycontinue() is supposed to return with some return-code (!error && 
!success).
if the cursor advances yycontinue() can simply be called again and will 
continue parsing where it left off.
expect() or a similar function can be used at anytime to figure out what 
valid tokens can follow the current state.

Nils

--- calc.tab.c  Sun Oct 27 12:37:04 2002
+++ calc.c      Sun Oct 27 12:39:25 2002
@@ -730,6 +730,8 @@
   int yyerrstatus;
   /* Lookahead token as an internal (translated) token number.  */
   int yychar1 = 0;
+  /* state in which last token was read */
+  int yylexstate;
 
   /* Three stacks and their tools:
      `yyss': related to states,
@@ -886,6 +888,7 @@
     {
       YYDPRINTF ((stderr, "Reading a token: "));
       yychar = YYLEX;
+      yylexstate = yystate;
     }
 
   /* Convert token to internal form (in yychar1) for indexing tables with.  */
@@ -1020,6 +1023,7 @@
        YYFPRINTF (stderr, " %d", *++yyssp1);
       YYFPRINTF (stderr, "\n");
     }
+    expect(yylexstate, yyssp);
 #endif
 
   *++yyvsp = yyval;

%token NUMBER UMINUS

%{
#define DEBUG           1
#define YYDEBUG         1
#define YYERROR_VERBOSE 1
#include <stdio.h>

void expect(int state, short *yyssp);
%}

%start statement

%%

statement
        : expr
        | expr error
        ;

expr
        : mult_expr
        | expr '+' mult_expr
        | expr '-' mult_expr
        ;

mult_expr
        : conj_expr
        | mult_expr '*' conj_expr
        | mult_expr '/' conj_expr
        | mult_expr conj_expr
        ;

conj_expr
        : pow_expr
        | pow_expr '_'
        ;

pow_expr
        : unary_expr
        | pow_expr '^' unary_expr
        ;

unary_expr
        : primary_expr
        | UMINUS primary_expr
        ;

primary_expr
        : NUMBER
        | '(' expr ')'
        | '(' expr error
        ;

%%

extern char **str;
char wasop = 1;

//
// simple lexer
//
int yylex()
{
        int type;
        while(**str == ' ')
                (*str)++;

        if(isalpha(**str))
                 return 0;
        if(isdigit(**str) || **str == '.') {
                double r;
                int n;
                wasop = 0;
                sscanf(*str, "%f%n", &r, &n);
                *str += n;
                return NUMBER;
        }
        switch(**str) {
        case '\r':
        case '\n':
        case ';':
        case '0':
                return 0;
        default:
                type = **str;
                if(wasop && type == '-') {
                        if(*(*str + 1) >= '0' && *(*str + 1) <= '9') {
                                double r;
                                int n;
                                (*str)++;
                                sscanf(*str, "%f%n", &r, &n);
                                *str += n;
                                return NUMBER;
                        }
                        type = UMINUS;
                }
                (*str)++;
                if(type == '*' && **str == '*') {
                        (*str)++;
                        type = '^';
                }
                wasop = 1;
                return type;
        }
}

int yyerror(char *error)
{
        fprintf(stderr, "%s\n", error);
}

void expect(int state, short *yyssp)
{
        short *stack = yyssp;
        int yyn, yyx, yycount = 0;
        int len;
        char *yyp;

        while(1) {
                /* First try to decide what to do without reference to 
lookahead token. */
                yyn = yypact[state];
/*                if(yyn != YYFLAG) {
                        for(x = (yyn < 0 ? -yyn : 0); yytname[x] != 0; x++) {
                                if(yycheck[x + yyn] == x) {
                                        if(count == 0)
                                                printf("expecting %s", 
yytname[x]);
                                        else
                                                printf(", %s", yytname[x]);
                                        count++;
                                }
                        }
                }*/
                for(yyx = yyn < 0 ? -yyn : 0;
                    yyx < (int) (sizeof (yytname) / sizeof (char *)); yyx++) {
                        if (yycheck[yyx + yyn] == yyx && yyx != YYTERROR) {
                                const char *yyq = ! yycount ? "expecting" : ",";
                                printf("%s %s", yyq, yytname[yyx]);
                                yycount++;
                        }
                }

                yyn = yydefact[state];
                if(yyn == 0)
                        break;

                len = yyr2[yyn]; // default reduction

                stack -= len; // reduce the stacks
                yyn = yyr1[yyn]; // shift the result of the reduction

                state = yypgoto[yyn - YYNTOKENS] + *stack;
                if(state >= 0 && state <= YYLAST && yycheck[state] == *stack)
                        state = yytable[state];
                else
                        state = yydefgoto[yyn - YYNTOKENS];
                stack++; // we push the new state
        }

        printf("\n");
}