flowchart TB
partas["Partas.Solid.CodeMirror<br/>(F# bindings, future)"]
solidcm["solid-codemirror<br/>(SolidJS wrapper)"]
cmlang["@codemirror/language<br/>(language support infrastructure)"]
lezerlr["@lezer/lr<br/>(incremental LR parser runtime)"]
lezercommon["@lezer/common<br/>(tree representation, cursors)"]
partas --> solidcm --> cmlang --> lezerlr --> lezercommon
Understanding Lezer is relevant for Atelier's planned features:
- Writing language support for F#
- Interpreting syntax trees for features like code folding
- Debugging highlighting issues
- Performance tuning for large files
Lezer is an incremental LR parser generator. It compiles grammar files to compact parse tables (JavaScript modules), which the runtime uses to produce concrete syntax trees.
Key distinction from traditional parsers: Lezer builds a concrete syntax tree (CST), not an abstract syntax tree (AST). The tree preserves all tokens, positions, and structure, which is what you need for editor features. Semantic analysis comes from the LSP.
When a user types, Lezer doesn't re-parse the entire file. It:
- Receives tree fragments from the previous parse
- Maps document changes to tree positions
- Reuses unchanged subtrees
- Re-parses only affected regions
flowchart TB
subgraph doc["Document: 'let x = 1\\nlet y = 2\\nlet z = 3'"]
edit["User types here ↑"]
end
subgraph tree["Previous Tree"]
let1["LetBinding (let x = 1)<br/>← reused"]
let2["LetBinding (let y = 2)<br/>← re-parsed"]
let3["LetBinding (let z = 3)<br/>← reused (positions shifted)"]
end
Balanced subtrees from repeat operators (*, +) enable fine-grained reuse. A change inside one function doesn't trigger re-parsing of sibling functions.
Lezer grammars define both the parser and tokenizer:
@top Program { statement* }
statement {
LetBinding |
FunctionDef |
Expression ";"
}
LetBinding {
kw<"let"> pattern "=" Expression
}
pattern {
Identifier |
TuplePattern
}
TuplePattern { "(" pattern ("," pattern)* ")" }
@tokens {
Identifier { $[a-zA-Z_] $[a-zA-Z0-9_]* }
Number { $[0-9]+ ("." $[0-9]+)? }
String { '"' (!["\\] | "\\" _)* '"' }
space { $[ \t\n\r]+ }
}
@skip { space | LineComment | BlockComment }
LineComment { "//" ![\n]* }
BlockComment { "/*" blockCommentContent* "*/" }
blockCommentContent { ![*] | "*" ![/] }
kw<term> { @specialize[@name={term}]<Identifier, term> }
@precedence {
call,
unary @right,
mult @left,
add @left,
compare @left
}
| Element | Purpose |
|---|---|
@top |
Entry point rule |
| Capitalized names | Create tree nodes |
| Lowercase names | Internal rules (no nodes) |
@tokens |
Lexer definitions (DFA-based) |
@skip |
Whitespace/comment handling |
@specialize |
Keywords overlapping identifiers |
@precedence |
Operator precedence/associativity |
@external |
Custom tokenizers (for complex cases) |
Lezer trees optimize for memory and locality:
flowchart LR
subgraph packed["Packed Buffer (small subtrees)"]
direction LR
buf["| type | from | to | type | from | to | ... |<br/>64 bits per node, flat array"]
end
subgraph treenode["Tree Nodes (larger structures)"]
node["SyntaxNode<br/>- type: NodeType<br/>- from: number<br/>- to: number<br/>- children: []"]
end
Two interfaces for traversal:
SyntaxNode (object-based, convenient):
let node = tree.topNode
console.log(node.name, node.from, node.to)
for (let child of node.children) {
// ...
}TreeCursor (mutable, efficient for bulk traversal):
let cursor = tree.cursor()
do {
console.log(cursor.name, cursor.from, cursor.to)
} while (cursor.next())TreeCursor avoids object allocation during traversal, which is relevant for large files.
Lezer uses GLR (Generalized LR) parsing for error recovery. When encountering invalid input:
- Fork into multiple parse branches
- Apply recovery strategies:
- Skip unexpected tokens
- Insert expected tokens
- Force reduction of partial productions
- Score branches by "badness" (recovery actions increase badness)
- Prune branches exceeding threshold relative to best branch
- Continue with surviving branches
This produces usable trees from partial/invalid code, which is essential for editing.
Some languages require context-sensitive tokenization. Lezer supports external tokenizers written in JavaScript:
import { ExternalTokenizer } from "@lezer/lr"
const indentTokenizer = new ExternalTokenizer((input, stack) => {
// Access input stream and parser stack
// Return token type based on context
if (atLineStart && indentIncreased(input, stack)) {
input.acceptToken(Indent)
}
})F#'s significant whitespace would require this approach.
The following outlines potential approaches for F# support in Atelier.
Write a complete grammar for F#. Challenges include:
- Significant whitespace: Requires external tokenizer with indentation tracking
- Computation expressions: Context-dependent keywords (
let!,do!,return!) - Type syntax: Generic constraints, SRTPs, measure types
- Preprocessor directives:
#if,#else, conditional compilation
This is substantial work. OCaml has a Lezer grammar (via Tree-sitter) that could inform an F# implementation.
CodeMirror's @codemirror/legacy-modes supports TextMate grammars. F# has an existing TextMate grammar (used by VSCode).
import { StreamLanguage } from "@codemirror/language"
import { fSharp } from "@codemirror/legacy-modes/mode/mllike"
const fsharpLanguage = StreamLanguage.define(fSharp)Produces a flat token stream, not a tree. Sufficient for basic highlighting.
FSNAC provides semantic token information. CodeMirror can display these:
import { lspSemanticTokens } from "@codemirror/lsp-client"
// Semantic tokens from LSP override local highlighting
const extensions = [
fsharpLanguage, // Basic highlighting (TextMate)
lspSemanticTokens() // Enhanced highlighting from FSNAC
]This layers LSP intelligence over basic highlighting.
The current thinking favors a phased approach:
- Start with TextMate: Immediate basic highlighting
- Add LSP semantic tokens: FSNAC provides accurate highlighting
- Consider Lezer grammar later: If tree-based features (smart folding, structural navigation) prove valuable
The LSP already provides semantic understanding. A Lezer grammar could add local, offline tree access; useful but not essential for an initial implementation.
When wrapping CodeMirror in Partas.Solid, these Lezer-related APIs become relevant:
// Language definition
import { LRLanguage, LanguageSupport } from "@codemirror/language"
const fsharpLanguage = LRLanguage.define({
parser: fsharpParser, // From Lezer grammar
languageData: {
commentTokens: { line: "//" },
closeBrackets: { brackets: ["(", "[", "{", '"'] }
}
})
// Tree access in extensions
import { syntaxTree } from "@codemirror/language"
const myExtension = EditorView.updateListener.of(update => {
const tree = syntaxTree(update.state)
// Walk tree for custom features
})F# bindings could expose these as:
module CodeMirror.Language
let syntaxTree (state: EditorState) : Tree =
jsNative
let defineLanguage (parser: Parser) (data: LanguageData) : LRLanguage =
jsNative| Operation | Complexity | Notes |
|---|---|---|
| Initial parse | O(n) | Full document, LR parsing |
| Incremental parse | O(changed) | Reuses unchanged subtrees |
| Tree traversal | O(nodes visited) | TreeCursor avoids allocation |
| Node lookup by position | O(log n) | Binary search in sorted nodes |
For a 10,000-line file with a single character edit, incremental parsing typically touches <1% of nodes.
- Previous: 06_partas_solid.md: Partas.Solid, F# to SolidJS compilation
- Next: 08_tooling_integration.md: Performance Tooling Integration