How to work with whitespaces within grammar?

Question

I want to create parser/lexer for simplified version of LISP. Here is bison/lexer specs:

/* Lexer file */
"(" {return OP;}
")" {return CP;}
[0-9]+ {return NUM;}
["][a-zA-Z]*["] { return STR; }
[ \n\r\f]     { /*do nothing*/}
. {return INVALID_TOKEN;}

/* Bison file */
start_expr: components_list

components_list : /*nothing*/
     | components_list component

 component : OP STR NUM CP

Such string conforms to grammar ("f" 1) ("f"1)( "f" 1)( "f" 1 ). But expression ("f"1) looks pretty awful for me, I decided to add explitily delimiters to grammar (usage of WHITESPACE token of kind [ \n\r\f]+). Something like that:

opt_wspace : /*nothing*/
   | WHITESPACE

start_expr: components_list

components_list : /*nothing*/
     | components_list component

 component : OP opt_wspace STR WHITESPACE NUM opt_wspace CP

But now (as for me) grammar looks terrible, but expressions of kind ("f"1) are disallowed. Another moment is that now I can easyly make mistake in grammar. For example such expressions will not be parsed ("f" 1) ("f" 1) (I forgot to add usage of opt_wspace in components_list).

So my basic question is how to work with delimiters/whitespaces in grammar? I looked grammar of python (https://github.com/python/cpython/blob/master/Grammar/Grammar) but it seems like it has no mention of whitespace expressions/tokens. Here is minor quote:

stmt: simple_stmt | compound_stmt

simple_stmt: small_stmt (';' small_stmt)* [';'] NEWLINE

small_stmt: (expr_stmt | del_stmt | pass_stmt | flow_stmt | import_stmt | global_stmt | nonlocal_stmt | assert_stmt)

expr_stmt: testlist_star_expr (annassign | augassign (yield_expr|testlist) | [('=' (yield_expr|testlist_star_expr))+ [TYPE_COMMENT]] )

sepp2k sepp2k · Accepted Answer · 2019-05-17T11:23:15

None of the lisps I know (or really programming languages in general) force you to put spaces between tokens like that. For example, things like (display"hello") or (format t"~d"42) work fine in Scheme and Common Lisp respectively. So what you're trying to do isn't commonly done and I would recommend just not doing it.

That said, if you do want to enforce white space between certain tokens, your two options are to either keep doing what you're doing or to define a rule for invalid tokens that matches any sequence of tokens that you want to disallow. Something like this:

[0-9]+ {return NUM;}
["][^"]*["] { return STR; }
(["][^"]*["]|[0-9]+){2,} { return INVALID_TOKEN; }

So INVALID_TOKEN would be generated whenever multiple strings or numbers appear next to each other without anything in between. The pattern for this will grow more and more complicated as you add more types of tokens that you don't want to allow next to each other (such as identifiers).

PS: It is very unusual to only allow letters in strings, which is why I've changed the regex for string literals in the above. You'll probably want to adjust it further to allow for escaped double quotes inside the string.

How to work with whitespaces within grammar?

1 Answers