mirror of
https://github.com/carbon-language/carbon-lang.git
synced 2026-09-24 20:10:13 +01:00
Richard Smith
3bbc03f527
Adds an algorithm to compute where to insert brackets to repair bracketing mismatches during lexing. This takes indentation, as well as a number of other cues, into account to predict where the brackets should have gone. Detects when there is ambiguity between solutions and makes no suggestion in that case. Reduces the problem by splitting on properly bracketed top-level constructs, then uses a beam search to find good candidate solutions quickly. This includes both a fuzzer and an eval tool that can be used to determine how well the algorithm fares against a given corpus of valid Carbon code, by damaging it in various ways and seeing whether the algorithm can correctly fix it. On all the eval modes, this algorithm can correctly infer the positions for over 80% of lost brackets (and can correctly restore 95+% of brackets in some modes), with low rates of incorrect suggestions. See added documentation for full details. Assisted-by: Gemini via Antigravity, Claude via Claude Code
38 lines
1.2 KiB
Markdown
38 lines
1.2 KiB
Markdown
# Lex
|
|
|
|
<!--
|
|
Part of the Carbon Language project, under the Apache License v2.0 with LLVM
|
|
Exceptions. See /LICENSE for license information.
|
|
SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
|
|
-->
|
|
|
|
<!-- toc -->
|
|
|
|
## Table of contents
|
|
|
|
- [Overview](#overview)
|
|
- [Bracket matching](#bracket-matching)
|
|
- [Alternatives considered](#alternatives-considered)
|
|
|
|
<!-- tocstop -->
|
|
|
|
## Overview
|
|
|
|
Lexing converts input source code into tokenized output. Literals, such as
|
|
string literals, have their value parsed and form a single token at this stage.
|
|
|
|
## Bracket matching
|
|
|
|
The lexer handles matching for `()`, `[]`, and `{}`. When a bracket lacks a
|
|
match, it will insert a "recovery" token to produce a match. As a consequence,
|
|
the lexer's output should always have matched brackets, even with invalid code.
|
|
|
|
Where the missing bracket belongs is decided by a search over candidate repairs,
|
|
using indentation, structural facts about the language, and formatting
|
|
conventions as evidence. See
|
|
[mismatched bracket recovery](lex/mismatched_brackets.md).
|
|
|
|
## Alternatives considered
|
|
|
|
- [Bracket matching in parser](/proposals/p006716-move-toolchain-alternatives-to-proposals.md#bracket-matching-in-parser)
|