"Expected token" using lemon parser generator

Question

Is there a known way to generate an "Expected token" list when a syntax error happens ? I'm using Lemon as parser generator.

Answer 1

This seems to work:

%syntax_error { 
        int n = sizeof(yyTokenName) / sizeof(yyTokenName[0]);
        for (int i = 0; i < n; ++i) {
                int a = yy_find_shift_action(yypParser, (YYCODETYPE)i);
                if (a < YYNSTATE + YYNRULE) {
                        printf("possible token: %s\n", yyTokenName[i]);
                }
        }
}

It tries all possible tokens and prints those that are applicable in the current parser state.

Note that when an incorrect token comes, the parser doesn't immediately call syntax_error, but it tries to reduce what's on stack hoping the token can be shifted afterwards. Only when nothing else can be reduced and the current token cannot be shifted, the parser calls syntax_error. The reductions will change parser state, which means that you may see less tokens than would have been applicable before the reductions. It should be sufficient for error reporting though.

Answer 2

There is no direct method to generate such list in Lemon. But you can try do this using debug output of Lemon tool and debug trace of generated parser. After call to ParseTrace function generated parser prints list of Shifts and Reduces it applies to the input stream. The last Shift before syntax error contains number of current state before the error. Find this state in *.out file for your parser and see list of expected tokens for it.

Answer 3

The modern versions of Lemon use something like the following:

%syntax_error {
    for (int32_t i = 1, a = 0; i < YYNTOKEN; ++i) {
        a = yy_find_shift_action((YYCODETYPE)i, yypParser->yytos->stateno);
        if (a != YY_ERROR_ACTION) {
            // 'a' is a valid token.
        }
    }
}