7
$\begingroup$

What are the pros and cons of including whitespace and comments as tokens in the tokenizer output?

For example:

value=  6+ 7 // A comment

Would result in these tokens without whitespace/comments:

identifier  'value'
assign      '='
integer     '6'
plus        '+'
integer     '7'

But would result in this with whitespace and comments included:

identifier  'value'
assign      '='
whitespace  '  '
integer     '6'
plus        '+'
whitespace  ' '
integer     '7'
whitespace  ' '
comment     '// A comment'

Not including comments and whitespace has the advantage of producing much more concise token output. Thus, is there any reason to use the longer version that keeps whitespace/comments as tokens (in a non-indent-based language)?

What are the pros and cons of including whitespace/comments as tokens?

$\endgroup$
6
  • 1
    $\begingroup$ I'm afraid this is a bit opinion-based. Whether you want whitespace included or not depends on what this is for and what you and the users of your language prefer. $\endgroup$
    – user
    Jul 9, 2023 at 20:53
  • $\begingroup$ It also depends on the internal structure and the syntax of the language $\endgroup$
    – Seggan
    Jul 9, 2023 at 20:55
  • 5
    $\begingroup$ Surely its a pro-cons question. Granted we probably have too many of those but why single this one out? $\endgroup$ Jul 9, 2023 at 23:04
  • 2
    $\begingroup$ @BruceAdams pros/cons questions are quite useful imo, I'm glad we have them on this site $\endgroup$ Jul 11, 2023 at 15:20
  • 1
    $\begingroup$ Your two options are "no trivia" and "trivia is a kind of token" but you've missed the third option: trivia is a part of the token. In the C# and VB compilers every token has a "leading trivia" and "trailing trivia" list which gives you the best of both worlds; the parser ignores the trivia, the formatter and linter pay attention to it. $\endgroup$ Jul 18, 2023 at 13:38

7 Answers 7

9
$\begingroup$

You must retain comments somehow, if only their source locations, in order to implement a source formatter or documentation generator. They don’t need to be considered proper tokens themselves, although they can be.

My preference is to produce a pair of outputs from the tokeniser: the “in-band” tokens, and a “side band” for comments and formatting information. If you have documentation comments like Rust, then they go in the token channel, because they’re a syntactic form: non-doc comments are purely lexical, but doc comments are a type of annotation that can only be attached to a definition. They’re just fashioned to look the same, for the sake of familiarity.

If you also retain whitespace, then you can do exact printing: your compiler can read a source file, parse it, apply a modification to it, and print it out again using the original formatting, without needing to reformat the whole file. That ability is helpful, too, for implementing “code actions” in the Language Server Protocol, because the API is textual, not structural—it only offers the ability to replace a range of text with a different string of text.

$\endgroup$
1
  • $\begingroup$ ANTLR takes this approach $\endgroup$
    – Seggan
    Jul 15, 2023 at 0:58
4
$\begingroup$

I would expect a modern compiler to be designed as a set of small libraries that can be reused to implement interactive things like LSP or parsers for code formatters. As such I would rather have the tokenizer keep all the details about the original text, so that it is possible to output the text back how it was originally, or with slight modifications (reformat code except sections that are explicitly ignored with special commands like clang off).

A difficulty comes from the fact that comments can happen almost everywhere, and that means your internal representation built from those tokens could be "polluted" by a lot of extra nodes. That's why you generally find a Concrete Syntax Tree for comments etc. and an Abstract Syntax Tree for the semantics (with traceability information pointing back to the CST).

$\endgroup$
4
$\begingroup$

They should not be ignored, although the modern convention is to treat all consecutive whitespace and comments as a single space. (I took you as asking about this, but some people consider filtering out whitespace a separate earlier step.) So, most programmers would expect foo bar foo/**/bar and foo /**/ bar to be equivalent to each other, and not to foobar. In some languages, whitespace has no function but to separate tokens and can always be filtered out of the token stream, but there are languages where that is not true.

Haskell, for example, inserts delimiters into the token stream to open and close blocks determined by whitespace. Another interesting example is Fortress, in which it is a syntax error for whitespace to imply an incorrect order of operations, such as a+b * c. Modern compilers typically at least warn about code like this, even when the language allows it:

if p
    doSomething();
    oopsIsThisSupposedToRunUnconditionally();

There’s a famous story about a bug found by Fred Webb in a code review at NASA in 1963, with the code for the Mercury space capsule. (An urban legend, which I myself have read in textbooks and repeated in the past, mixes this up with a different bug that caused the Mariner I space probe to explode.) Webb, posting in the Usenet newsgroup comp.risks in 1990, recalled seeing the line of code

DO 10 I = 1.10

which was an obvious typo for the loop instruction

DO 10 I = 1, 10

In that version of Fortran, there were no reserved keywords, whitespace was ignored (as programmers often did not waste lines on their punch cards with it) and variables could be created implicitly by assigning to them, so the compiler correctly interpreted this line as

DO10I = 1.10

which implicitly declared a REAL variable named DO10I and initialized it to 1.1. Although this didn’t cause any catastropic failures in a space flight, it became a well-known cautionary tale, repeated in many textbooks. As a result, mainstream languages since then, including ANSI Fortran, reserve keywords and parse whitespace.

For a long time, it was also fashionable for languages to force programmers to declare all variables at the beginning of their scope (either in a special section like in COBOL or the start of their local block in the Algol family, including classic C). However, modern languages want it to be possible to write static single assignments, so the current trend is to allow variables to be declared almost anywhere, but using a keyword (like auto in C++17, or let in Rust) to prevent accidentally declaring a variable with a typo. Today’s compilers will also warn you when a variable is declared but not subsequently used.

$\endgroup$
4
  • $\begingroup$ I strongly dispute this comment - "As a result, all mainstream languages since then reserve keywords and tokenize whitespace". Whitespace is typically consumed by the lexer of most mainstream languages. $\endgroup$ Jul 9, 2023 at 23:06
  • $\begingroup$ @BruceAdams I think you were interpreting the scope of the question differently than I was. I changed the first paragraph. $\endgroup$
    – Davislor
    Jul 9, 2023 at 23:14
  • 3
    $\begingroup$ Nice to see Fortress mentioned. It was an interesting point in the language design space that I, as a PL nerd, would have liked to see explored further. Gone too soon. $\endgroup$ Jul 10, 2023 at 12:30
  • $\begingroup$ @MarcellPerger Appreciate the edit suggestion. I think it comes down to how you define “mainstream.” I compromised by taking out “all,” but “most” on top of “mainstream” feels redundant to me. $\endgroup$
    – Davislor
    Jul 10, 2023 at 18:19
4
$\begingroup$

The problem with including whitespace and comment tokens in the output of the lexer is that this stream of tokens is typically fed to the parser directly.

Those tokens need to be filtered out. If you don't it the makes the grammar the parsing stage uses much more complex.

It really depends on if you have a practical use for those tokens. This is typically not the case, however:

  • I am a fan of retaining comments and attaching them the things they comment. This can be good for document generators.

  • Whitespace tokens might be useful for inferring intention if there is a syntax error.

  • You could just have the parsing stage skip them or filter them out.

I'm not sure I would keep the whitespace tokens even in an indent sensitive language. It would typically be better to keep track of the indent level itself instead. You could provide it as an attribute if your parser uses an attribute grammar or you could convert it into a more meaningful "indent" tokens equivalent to a "begin" and "end" or open and close brackets.

$\endgroup$
4
  • $\begingroup$ Swift is sensitive to mid-line whitespace: langdev.stackexchange.com/a/100/15 Wouldn't that require whitespace be kept for the parser? $\endgroup$
    – Bbrk24
    Jul 9, 2023 at 21:29
  • 2
    $\begingroup$ I wasn't aware of that but I think you could probably do it in the lexer just fine. For example " * ", " *" and "* " coud be different tokens - infix star, prefix star, postfix star $\endgroup$ Jul 9, 2023 at 23:09
  • $\begingroup$ How much would a parser be complicated by having two forms of each token--one with preceding whitespace and one without, and having a front end on the lexer which replaces whitespace with the "with preceding whitespace" version of whatever follows it? Such a design would allow a compiler to accept 1.2E+5 as a "partial float constant with trailing E" token, followed by "plus with no preceding white space" and "decimal literal with no preceding white space", but interpret 0x1E+3 as hex literal, plus with optional whitespace, and decimal literal with optional white space. $\endgroup$
    – supercat
    Aug 9, 2023 at 17:44
  • $\begingroup$ Its possily not as bad as it sounds. For the swift example that would occur at the lexical analysis stage. Will users like or get used to a syntax that behaves that way is a different question. Perhaps one to ask the swift community. $\endgroup$ Aug 9, 2023 at 20:31
3
$\begingroup$

One reason why you might want the tokenizer to include white-space and comments is that it enables more nuanced/detailed static analysis of the code.

For example, PHP CodeSniffer is a tool to report on code-style issues, via static analysis of the code files. It needs to include white-space and comments in the token stream so that individual 'Sniffs' can report on incorrect use of white-space (e.g. use of tabs instead of spaces, incorrect indentation level, etc.) or issues in comments (e.g. spelling errors, bad formatting, etc.).

As far as I am aware, this uses PHP's own tokenizer. If the PHP tokenizer didn't include these symbols, then it would effectively mean the functionality has to be re-implemented in userland, with all the risk of inconsistencies that would bring.

$\endgroup$
0
2
$\begingroup$

It depends on what you're doing with the tokens.

If you want to implement something like BASIC's LIST command, you'll probably want to preserve the original formatting and comments. If you're implementing a documentation generator like Doxygen, you might not care about whitespace, but you'll need to preserve the comments in order to extract tagged documentation.

OTOH, if all you want to do is run a program in your language, then “no-op” tokens such as whitespace and comments can be safely ignored.

If you're writing a generic parsing library that can be used for either purpose, you might want to provide two versions of your tokenizing routine: One that includes the “no-op” tokens, and one that filters them out.

$\endgroup$
1
$\begingroup$

Retaining white space, or at least information about its presence or absence, until parsing, would make it possible for a language to accept 1.2E+3 but reject 1.2E+ 3, without having to complicate the language with concepts like "pp-numbers" that make it necessary for programmers to add whitespace to constructs like 0x1E -x to avoid having the preprocessor glom the -x into the same token as the hex constant.

$\endgroup$
3
  • $\begingroup$ 1.2E+3 vs 1.2E+ 3 is a lexical problem, since lexer would expect exponent until closing float token. $\endgroup$ Jan 30 at 20:06
  • $\begingroup$ @ivanjermakov: The only circumstances in which it would matter whether a floating-point constant which contains non-alphanumeric characters is a single token, or is subdivided into tokens by the non-alphanumeric characters, are those where a period is immediately followed by E or e. If 1.23E+4 is treated as 5 tokens, then the grammar would need to have a rule that a simple decimal constant, followed by a period, a decimal constant with E suffix, an optional + or - sign, and another simple decimal constant, would all combine to yield a floating-point constant. No need for the... $\endgroup$
    – supercat
    Jan 30 at 20:56
  • $\begingroup$ ...preprocessor to understand anything about floating-point constants at all. A preprocessor that was completely oblivious to floating-point formats might expand a macro E, if one were defined, while processing 1.E+2, but specifying that compilers may perform or block such expansions at their leisure would have affected fewer programs than mandating that compilers break 0x1E-x. $\endgroup$
    – supercat
    Jan 30 at 20:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .