parsing maxscript - problem with newlines

I am trying to create parser for MAXScript language using their official grammar description of the language. I use flex and bison to create the lexer and parser.

However, I have run into following problem. In traditional languages (e.g. C) statements are separated by a special token (; in C). But in MAXScript expressions inside a compound expression can be separated either by ; or newline. There are other languages that use whitespace characters in their parsers, like Python. But Python is much more strict about the placement of the newline, and following program in Python is invalid:

# compile error
def 
foo(x):
  print(x)

# compile error
def bar
(x):
  foo(x)

However in MAXScript following program is valid:

fn
foo x =
(              // parenthesis start the compound expression
   a = 3 + 2;  // the semicolon is optional
   print x
)

fn bar
x =
   foo x

And you can even write things like this:

for
x
in
#(1,2,3,4)
do
format "%," x

Which will evaluate fine and print 1,2,3,4, to the output. So newlines can be inserted into many places with no special meaning.

However if you insert one more newline in the program like this:

for
x
in
#(1,2,3,4)
do
format "%,"
x

You will get a runtime error as format function expects to have more than one parameter passed.

Here is part of the bison input file that I have:

expr:
    simple_expr
|   if_expr
|   while_loop
|   do_loop
|   for_loop
|   expr_seq

expr_seq:
    "(" expr_semicolon_list ")"

expr_semicolon_list:
    expr
|   expr TK_SEMICOLON expr_semicolon_list
|   expr TK_EOL expr_semicolon_list

if_expr:
    "if" expr "then" expr "else" expr
|   "if" expr "then" expr
|   "if" expr "do" expr

// etc.

This will parse only programs which use newline only as expression separator and will not expect newlines to be scattered in other places in the program.

My question is: Is there some way to tell bison to treat a token as an optional token? For bison it would mean this:

If you find newline token and you can shift with it or reduce, then do so.
Otherwise just discard the newline token and continue parsing.

Because if there is no way to do this, the only other solution I can think of is modifying the bison grammar file so that it expects those newlines everywhere. And bump the precedence of the rule where newline acts as an expression separator. Like this:

%precedence EXPR_SEPARATOR   // high precedence

%%

// w = sequence of whitespace tokens
w:  %empty    // either nothing
|   TK_EOL w  // or newline followed by other whitespace tokens

expr:
    w simple_expr w
|   w if_expr w
|   w while_loop w
|   w do_loop w
|   w for_loop w
|   w expr_seq w

expr_seq:
    w "(" w expr_semicolon_list w ")" w

expr_semicolon_list:
    expr
|   expr w TK_SEMICOLON w expr_semicolon_list
|   expr TK_EOL w expr_semicolon_list           %prec EXPR_SEPARATOR

if_expr:
    w "if" w expr w "then" w expr w "else" w expr w
|   w "if" w expr w "then" w expr w
|   w "if" w expr w "do" w expr w

// etc.

However this looks very ugly and error-prone, and I would like to avoid such solution if possible.

Solution

My question is: Is there some way to tell bison to treat a token as an optional token?

No, there isn't. (See below for a longer explanation with diagrams.)

Still, the workaround is not quite as ugly as you think, although it's not without its problems.

In order to simplify things, I'm going to assume that the lexer can be convinced to produce only a single '\n' token regardless of how many consecutive newlines appear in the program text, including the case where there are comments scattered among the blank lines. That could be achieved with a complex regular expression, but a simpler way to do it is to use a start condition to suppress \n tokens until a regular token is encountered. The lexer's initial start condition should be the one which suppresses newline tokens, so that blank lines at the beginning of the program text won't confuse anything.

Now, the key insight is that we don't have to insert "maybe a newline" markers all over the grammar, since every newline must appear right after some real token. And that means that we can just add one non-terminal for every terminal:

tok_id: ID | ID '\n'
tok_if: "if" | "if" '\n'
tok_then: "then" | "then" '\n'
tok_else: "else" | "else" '\n'
tok_do: "do" | "do" '\n'
tok_semi: ';' | ';' '\n'
tok_dot: '.' | '.' '\n'
tok_plus: '+' | '+' '\n'
tok_dash: '-' | '-' '\n'
tok_star: '*' | '*' '\n'
tok_slash: '/' | '/' '\n'
tok_caret: '^' | '^' '\n'
tok_open: '(' | '(' '\n'
tok_close: ')' | ')' '\n'
tok_openb: '[' | '[' '\n'
tok_closeb: ']' | ']' '\n'
/* Etc. */

Now, it's just a question of replacing the use of a terminal with the corresponding non-terminal defined above. (No w non-terminal is required.) Once we do that, bison will report a number of shift-reduce conflicts in the non-terminal definitions just added; any terminal which can appear at the end of an expression will instigate a conflict, since the newline could be absorbed either by the terminal's non-terminal wrapper or by the expr_semicolon_list production. We want the newline to be part of expr_semicolon_list, so we need to add precedence declarations starting with newline, so that it is lower precedence than any other token.

That will most likely work for your grammar, but it is not 100% certain. The problem with precedence-based solutions is that they can have the effect of hiding real shift-reduce conflict issues. So I'd recommend running bison on the grammar and verifying that all the shift-reduce conflicts appear where expected (in the wrapper productions) before adding the precedence declarations.

Why token fallback is not as simple as it looks

In theory, it would be possible to implement a feature similar to the one you suggest. [Note 1]

But it's non-trivial, because of the way the LALR parser construction algorithm combines states. The result is that the parser might not "know" that the lookahead token cannot be shifted until it has done one or more reductions. So by the time it figures out that the lookahead token is not valid, it has already performed reductions which would have to be undone in order to continue the parse without the lookahead token.

Most parser generators compound the problem by removing error actions corresponding to a lookahead token if the default action in the state for that token is a reduction. The effect is again to delay detection of the error until after one or more futile reductions, but it has the benefit of significantly reducing the size of the transition table (since default entries don't need to be stored explicitly). Since the delayed error will be detected before any more input is consumed, the delay is generally considered acceptable. (Bison has an option to prevent this optimisation, however.)

As a practical illustration, here's a very simple expression grammar with only two operators:

prog: expr '\n' | prog expr '\n'
expr: prod      | expr '+' prod
prod: term      | prod '*' term
term: ID        | '(' expr ')'

That leads to this state diagram [Note 2]:

Let's suppose that we wanted to ignore newlines pythonically, allowing the input

( 
  a + b
)

That means that the parser must ignore the newline after the b, since the input might be

(
  a + b
  * c
)

(Which is fine in Python but not, if I understand correctly, in MAXScript.)

Of course, the newline would be recognised as a statement separator if the input were not parenthesized:

a + b

Looking at the state diagram, we can see that the parser will end up in State 15 after the b is read, whether or not the expression is parenthesized. In that state, a newline is marked as a valid lookahead for the reduction action, so the reduction action will be performed, presumably creating an AST node for the sum. Only after this reduction will the parser notice that there is no action for the newline. If it now discards the newline character, it's too late; there is now no way to reduce b * c in order to make it an operand of the sum.

Bison does allow you to request a Canonical LR parser, which does not combine states. As a result, the state machine is much, much bigger; so much so that Canonical-LR is still considered impractical for non-toy grammars. In the simple two-operator expression grammar above, asking for a Canonical LR parser only increases the state count from 16 to 26, as shown here:

In the Canonical LR parser, there are two different states for the reduction term: term '+' prod. State 16 applies at the top-level, and thus the lookahead includes newline but not ) Inside parentheses the parser will instead reach state 26, where ) is a valid lookahead but newline is not. So, at least in some grammars, using a Canonical LR parser could make the prediction more precise. But features which are dependent on the use of a mammoth parsing automaton are not particularly practical.

One alternative would be for the parser to react to the newline by first simulating the reduction actions to see if a shift would eventually succeed. If you request Lookahead Correction (%define parse.lac full), bison will insert code to do precisely this. This code can create significant overhead, but many people request it anyway because it makes verbose error messages more accurate. So it would certainly be possible to repurpose this code to do token fallback handling, but no-one has actually done so, as far as I know.

Notes:

A similar question which comes up from time to time is whether you can tell bison to cause a token to be reclassified to a fallback token if there is no possibility to shift the token. (That would be useful for parsing languages like SQL which have a lot of non-reserved keywords.)

I generated the state graphs using Bison's -g option:

bison -o ex.tab.c --report=all -g ex.y
dot -Tpng -oex.png ex.dot

To produce the Canonical LR, I defined lr.type to be canonical-lr:

bison -o ex_canon.c --report=all -g -Dlr.type=canonical-lr ex.y
dot -Tpng -oex_canon.png ex_canon.dot