Why Linters Parse: Token Streams, Syntax Trees, and the Cost of Losing Layout

A search for the regular expression if\s*\([^)]*=[^=] finds assignments inside conditions. It also finds them inside string literals, inside comments, inside macro definitions, and in a dozen lines of generated code that no one will ever edit. Each of those matches is a report a human has to dismiss. The reason linters do not work this way is not that parsing is fast; it is that the unit of a lint rule is a syntactic construct, and text does not expose constructs.

The lexer decides what a word is

Before any tree exists, a lexer converts bytes into tokens. For a language in the C family the token kinds are roughly identifiers, keywords, literals, operators, and punctuation, with comments and whitespace handled separately. The separation is already a semantic act. if is a keyword only because the lexer has a table saying so; in a language where keywords are not reserved, the parser has to decide from context instead.

Two details in this stage matter later. The first is maximal munch: the lexer consumes the longest sequence that forms a valid token, so a+++b becomes a ++ + b and not a + ++b. The second is trivia. Most lexers record comments and whitespace as side channels rather than real tokens, because the parser does not need them. A style rule does. This is the first place where a design choice made for the parser constrains the linter: if the lexer throws trivia away, no later phase can recover it, and checks about comment placement, line length, or blank lines have to be implemented in the lexer or in a separate scan.

Numeric literals and string escapes add their own wrinkle: the token carries both the source spelling and a decoded value. A rule that flags 0x1F for style needs the spelling, while a rule that folds constants needs the value. Storing only one of them forces re-lexing the token text later.

Concrete and abstract trees are different products

A parser accepts the token stream and builds a tree. The tree that preserves every token, including whitespace and comments, is a concrete syntax tree. The tree that keeps only the constructs the language semantics care about is an abstract syntax tree. The distinction is not academic: it determines which rules the tool can express.

In an abstract tree, parentheses vanish. The expression (a + b) * c and a + b * c have different shapes, so precedence survives, but the explicit parentheses do not. A rule that asks for redundant parentheses cannot work on this tree unless the parser records their presence as a flag on the node. Similarly, an abstract tree usually normalises a.b.c into nested member accesses, drops trailing commas, and may desugar constructs such as compound assignment. Formatting-sensitive rules therefore need either a lossless tree or a token stream kept alongside the abstract one.

Most production linters keep both: a typed abstract tree for semantic rules, and a token list with byte ranges for style rules and for printing fixes. The two are linked by source ranges. That link is also what makes a diagnostic point at the right place, a problem taken up in Diagnostic Spans and the Encoding Problem.

The memory bill is real. A token list plus a lossless tree can be several times the size of the source file, and an abstract tree with parent pointers and resolved references more again. On a large file set, peak memory rather than CPU time is often what limits parallelism, which is why analyzers process files in isolated workers and stream results rather than holding a whole program’s trees.

A rule matches a shape, not a spelling

With a tree, a rule is a predicate over nodes. A check for assignment in a condition becomes: find a node of kind if, inspect its condition subtree, and report if the outermost operator is an assignment rather than a comparison. String literals and comments are not in the tree at all, so they cannot produce a match. That single change removes most of the noise in the regular-expression version.

Matching is usually expressed as a visitor or as a pattern with metavariables. A pattern such as $X == null binds $X to an arbitrary subtree and matches any expression compared with the null literal, regardless of formatting. Patterns compose: $X != null && $X.foo binds the same $X in two positions, which is a form of equality constraint on subtrees. This is cheap and local, and it covers a large fraction of lint rules.

What it does not cover is anything requiring knowledge of what a name means. foo() matches a call to any function named foo; deciding whether it is the deprecated one requires a symbol table and an import graph, which is the subject of Scope Chains and Name Resolution. The tree gives syntax; it does not give binding.

Where parsing stops paying

Three language features break the clean picture. The first is textual macro systems. C and C++ are preprocessed before parsing, so a linter sees either the unexpanded source, where constructs do not parse, or the expanded source, where the ranges no longer correspond to what the programmer wrote. Tools choose one and accept the loss. Clang’s approach is to parse with a preprocessor that tracks macro expansion locations, so a diagnostic can point at the invocation as well as the definition; that machinery is a substantial part of why a C++ front end is large.

The second is dialects and version skew. A parser built for one language version rejects syntax from the next, and a linter that cannot parse a file reports nothing at all rather than reporting less. Error-tolerant parsers address this by inserting error nodes and continuing. Tree-sitter, designed for editors, does exactly this and supports incremental re-parsing of the edited region, which is why it is common in editor integrations where the buffer is syntactically invalid most of the time.

The third is generated code. A file produced by a schema compiler can be syntactically valid and semantically uninteresting. Linters usually exclude it by path or by a generated-code marker in the header, because analyzing it costs time and produces findings nobody can act on.

import ast

class ComparisonVisitor(ast.NodeVisitor):
    def visit_If(self, node):
        test = node.test
        # Only a bare comparison is interesting; "a = b" is a syntax error
        # in Python, so the analogous case is "a == b" used as a truth test.
        if isinstance(test, ast.Compare):
            print(f"comparison in condition at line {node.lineno}")
        self.generic_visit(node)

tree = ast.parse("if x == None:\n    pass\n")
ComparisonVisitor().visit(tree)

The Python example exposes both the strength and the limit. ast.parse gives a precise node type and a line number, and the visitor cannot be fooled by a string containing if x == None. But ast.parse raises on incomplete input, so an editor cannot use this path on a buffer being typed; it needs a parser that produces partial trees. The abstract tree also discards the parentheses around (x == None), so a rule about redundant parentheses needs the token stream.

Layout is information, and it is expensive to keep

The practical conclusion is that a linter’s architecture follows from the rules it must run. Semantic rules want a small, normalized, typed tree plus name resolution. Style rules want tokens with exact ranges and trivia. Fixes want both, plus a printer that can reproduce untouched source byte for byte, because a fix that reformats an unrelated line is a fix that gets reverted.

Keeping layout is not free: it increases memory, complicates every tree transformation, and makes the tree depend on lexical details the semantics do not care about. Dropping it is cheaper but forecloses a class of rules permanently. Most mature tools split the difference with a lossless tree and a typed view over it, paying the memory cost in exchange for not having to decide, at parser construction time, which kinds of rules will ever be written.