GerHobbelt
commented
11 years ago TL;DR: not a jison bug but a grammar bug.
In bison, parse rules are run before the next token is pulled, which allows this to work.
Unless I'm completely mistaken, this is very strange, as it would mean that bison would perform deep semantic analysis of the action code -- last time I looked, it didn't.
What you probably mean is that, if you want this classic 'lexer hack' (better known as 'lexical tie-in'; not to be mistaken with 'the lexer hack') to work in the bison/yacc family, you can place action code blocks inside the rule (a.k.a. 'mid-rule action') at a place where you know that no look-ahead is required to reduce the rule up to that point, i.e.
e
: START { yy.lexer.begin('numMode'); } numbers
{ $$ = $2;}
;This way of coding the grammar would/should work, as now the grammar generator can run the action, which switches lexer mode, when the START rule has reduced to that point without the need for any 'look-ahead'.
Actions, by definition, can only be run when the matching rule has been completely matched (reduced) up to that point, which in this grammar's case means you require the lexer+parser to 'look-ahead' after START to match the numbers rule. That's how LR(k) / LALR(k) / etc. for any k works.
Unfortunately, jison doesn't support mid-rule actions like the example above so you need to rewrite the grammar manually to provide a rule set that is LA(0) (i.e. 'no look-ahead required to reduce the rule') at the appropriate places. (You'll need to be careful anyway, because what you're doing is the equivalent of a lexical tie-in, which is also documented in the bison manual here: http://www.gnu.org/software/bison/manual/html_node/Lexical-Tie_002dins.html#Lexical-Tie_002dins and don't forget to read the next section in that manual as well: that should make you realize that even if jison had mid-rule action support, it doesn't necessarily make it easier for you.
Here's a potential rewrite (untested, hence 'potential'), where the important rules have been marked LA(0).
Also note that your sample grammar is 'odd' in the sense of 'human reader being able to discern what's legal from the grammar definition' as it /seems/ legal from only reading the grammar rules to feed it input @@ 1 @@ 1 which should produce the token stream START NUMBER END NUMBER but can't do that as the END token in the current grammar would 'pop' the lexer state so the real token stream is this: START NUMBER END INVALID.
Another seemingly viable input is @@ 1 @@ @@ which would cause some very curious activity as the recursion in the numbers rule suggests that this is legal, while two END tokens surely will nuke your lexer stack, particularly when you do it like that in a more complex grammar.
If your intent was to produce a grammar which munches tokens (numbers and text) delineated by @@ you'ld be best served with pulling the END outside the recursive rule. This addition/change is also reflected in the grammar below.
If you want a grammar where the sentinel is optional, then you will have to 'tolerate' a delayed lexer hack due to the LA(1) situation when a sentinel is missing to clearly delineate the section which required the lexer hack or come up with another 'tweak' to ensure proper lexing/parsing operation. (OT: This is why I augmented the jison lexer with minimal 'backtracking' support.)
%lex
%x numMode
%%
\s+ /* skip whitespace */
@@ return 'START';
<numMode>[0-9]+("."[0-9]+)?\b return 'NUMBER';
<numMode>@@ return 'END';
<numMode>. return 'TEXT';
<<EOF>> return 'EOF';
. return 'INVALID';
/lex
%start expressions
%% /* language grammar */
expressions
: e EOF
{ typeof console !== 'undefined' ? console.log($1) : print($1);
return $1; }
;
/* The way the `e` rule and its subrules are written ensure that
* `start` and `sentinel/end` rules wil reduce without the need
* for any look-ahead: that's what is needed to make any
* lexer hack work, anywhere */
e
: start_number_detection numbers sentinel /* !!! create rules so you can use them for action code exec */
{ $$ = $2;}
;
start_number_detection /* LA(0) --> action code executes before next token is fetched */
: START
{ yy.lexer.begin('numMode'); }
;
sentinel /* LA(0) */
: END
{ yy.lexer.popState(); }
;
numbers
: numbers NUMBER
{ $$ = $1 + $2; }
| numbers TEXT
{ $$ = $1 + $2; }
| NUMBER
{ $$ = $1 + $2; }
| TEXT
{ $$ = $1 + $2; }
;
srathbun
If your lexer has multiple states available to it, then these can be changed from within the parser rules by
yy.lexer.begin('state');. However, the generated parser pulls the next token before running the code associated with a parse rule.This offsets when the state change occurs by one. The parser may expect the correct token, but the lexer cannot return it, since it has not switched state yet. Same for switching out of a state.
In bison, parse rules are run before the next token is pulled, which allows this to work. I've attached an example grammar, to demonstrate the problem.