The parser
The lexer, the layout pass and the recursive-descent parser, how they report mistakes and read past them, and the corpus they are tested on
The parser (compiler/Nanyx.Parser) reads a file in three steps: a lexer turns the text into tokens, a layout pass
makes the block structure that indentation gives them explicit, and a hand-written recursive-descent parser reads the
tokens into the syntax tree (Ast.fs). The parser in Work in progress says what is still
open.
- The lexer (
Lexer.fs): text in, tokens out, each with its offsets and its leading and trailing trivia, lossless whatever the text. A string with holes is aStringStart, the hole’s tokens, aStringMiddlebetween holes and aStringEnd. Operators come fromOperators.binaryOperators, and keywords fromKeywords.reserved, the one list of reserved words, so a keyword is never read as part of a longer name. - The layout pass (
Layout.fs): the lexer’s tokens in, the same tokens out withIndent,NewlineandDedentamong them, each at the offset of the code token after it, by the rules below. The parser never measures indentation itself. - The recursive-descent parser (
DescentCursor.fsand a file per part of the grammar:DescentTypes.fs,DescentLiterals.fs,DescentPatterns.fs,DescentExpressions.fs,DescentBlocks.fs,DescentControl.fsandDescentTopLevel.fs).DescentCursorhas the cursor, which reads the layout pass’s tokens and goes back for an alternative (NoMatch, whichCursor.Attemptcatches), and the side state kept beside the tree (ParseState): the names nodes declare, where documentable constructs start,module name =blocks, comments from the lexer’s trivia, and string texts. The files read, in order: types, with a field’s default and awhereconstraint read as expressions; literals, with a+or-written straight before a number as its sign and1.as a float, though the lexer reads both apart; patterns, with a guard’s lambda and a custom pattern’s arguments read as expressions; expressions, with the binary operators and ranges read by precedence climbing overbinaryOperators, either going on after an operator at the end of a line (Crossing) or, for a statement, not (Inline), andvalue is patternread there as an operator too (isOperator), made a match whose arm istrueand whose wildcard arm, made up at the pattern, isfalse(IsSyntax.test), with what anandafter it chains put in that arm in place oftrue, so the pattern’s names are in scope there (IsSyntax.andThen); lambdas, a def’s value written as an indented block, a match’s arms and the statements of a block, with destructuring defs desugared byDestructuring.fs; what starts with a keyword (match,if,for,while,do,use ... in,return,try,yield,name!,mut xas an argument andtype T), whereif value is patternis a match of the value against the pattern and_, and anifwhose condition’s chain of tests binds names stays anif, which the compiler checks and compiles as the matchIsSyntax.asMatchmakes of it, so the names are in scope in thethenbranch and theelsebranch is written once; and the top level, with its directives blanked (Directives.fs). The files beforeDescentControl.fsread lambdas, expressions, arms and what starts with a keyword through forward references (DescentCursor.Forward), whichDescentTopLevel.fillfills before anything is read.Api.runModuleParserreads a whole file (DescentTopLevel.tryReadModuleWithState), andparseTypeSignature, whichnanyx searchreads a query’s type with, reads a type alone (DescentTypes.readTypeSignature). - Its errors. A mistake the parser has a message of its own for is reported with that message where it is
(
Reported, raised byCursor.Report): an operator that isn’t spaced,&&, a prefix!, two operators that can’t be written side by side, a$before a type’s name, an escape that isn’t one, a_not between two digits, and the rest. The lexer’s own mistakes (a string or a block comment never closed) are reported as the lexer words them. Anything else is reported where the furthest reading failed, as what was expected there and what was found (Cursor.Unexpected): each reading notes what it expected when it fails (Cursor.Fail, andCursor.Expectfor a token), and those at the furthest token are listed. - Reading past mistakes. The compiler reads a file with
Api.parseModuleFileWithDocsRecovering(DescentTopLevel.readModuleRecovering), which goes on after a mistake: the top-level item it is in is left out, the error is noted, and reading goes on at the first line after the item’s start, from the error’s line on, that starts at the first column. An item read before the error that runs on into its line, asdef d = c +does into adefunder it, is left out with it. Every error is reported, the lexer’s too, except a parse error after the first of the lexer’s, which has taken the rest of its line or the file. The items that read are typed, so the editor has hover, completion and the outline around the mistake, but only the syntax errors are reported (compileChecked), as the errors that come of the items left out aren’t the user’s to fix, and the module can’t be run or imported. The language server reads such a compile only when no earlier text of the file parsed (OpenDocument.LastGood): while the user is typing, the item being typed is the one left out, and the last text that parsed still has it. The formatter reads withparseModuleWithTrivia, which stops at the first mistake, and leaves a file with one alone. - The corpus (
Corpus.fsincompiler/Nanyx.Parser.Corpus, a library only the test projects reference): every.nyxfile in the repository, every```nanyxblock in the docs, and every triple-quoted string in the test projects’ sources. The formatter’s corpus tests read it too. Listing it never entersbin,obj,node_modules,.gitor.claude, so a checkout’s worktrees cost nothing. Each test project parses the corpus once, in parallel, in a value its tests share, and the formatter’s tests format and re-parse each piece once the same way.CorpusTests.fschecks that every piece is written back exactly from its tokens, that every piece that parses lexes with no error, and that the layout pass gives every piece that parses the block structure its tree has (BlockStructure.fs: the items of each block, module block, match,except, multi-branchifand union type, each as the offset it starts at, keeping only the items that start their line and the groups of two items or more). A few pieces differ on purpose, each listed with why in the test. - The differential test (
Differential.fs, withCorpusTests.fsin the parser’s tests). It parses each piece with two parsers, in parallel, writes each result out with every span and without node ids (SyntaxDump.fs, which walks the tree by reflection), and reports the pieces whose trees, comments, blank lines or errors differ, each at its first differing line. It runs the parser against itself, so that a parse that depends on anything but its text shows up, and is there for a change to the parser to be checked against the parser before it.
The layout rules
Columns are counted from the start of the line, and a line is the first token on it and the tokens after it. An
opener is a token that can open a block, as the last token on its line: {, = (a def’s, a type’s or a module
block’s), -> (a lambda’s or an arm’s), then, else, do, in, or match with its scrutinee on the lines after
it. A keyword written straight after # or . is a name, as the tag #match is, and opens nothing. A block is a run of
items at one column; the pass keeps a stack of them, with the brackets and braces open inside them.
- The top level is a block at the column of the first token.
- An opener opens a block. After an opener, a line indented further than the innermost block opens a block at
its column, with an
Indentbefore it. After a{the block may be at any column, since the}closes it. - A match’s arms are a block. A line that starts with
|opens a block of arms at its column when it is indented further than the innermost block, or at the column of a block that isn’t arms, so that arms may line up with theirmatch. In[and]it doesn’t: a table’s rows start with|. - A line indented less than a block closes it, with a
Dedent, and then the next block out, while the line is indented less than each. So does a line at a block of arms’ column that doesn’t start with|. So a match nested in an arm ends at the next arm indented back to the outer one (#249). - A line at the innermost block’s column starts its next item, with a
Newlinebefore it, unless it starts withthenorelse, or the line before ends within: those continue the item, so anif’s branches may line up with it, and the body afteruse ... inmay be at theuse’s column (#673). Any other line, indented further than the block, continues the item it is in, with no layout token: a pipeline’s next step, and anandororon a line of its own (#617, #628). - Brackets have no layout in them. In
(and),[and], and a string’s holes, every line continues the item, and indentation closes no block outside them. A block opened inside them, after an opener or by arms, closes when they do, and a}closes the blocks opened inside its{, each with aDedent. A line that starts with a closing bracket or brace is part of what it closes, so a list’s]on its own line is no item (#248). - The end of the text closes every block but the top level’s.