<p>Suppose you want to build an IDE-grade parser for a language with highly uniform and nestable syntax (e.g. Lisp). Without a lot of &quot;special&quot; constructs like top-level functions, you can't use <a href="https://matklad.github.io/2023/05/21/resilient-ll-parsing-tutorial.html" rel="noreferrer">standard techniques</a> like bailing out until a known synchronization point.</p>
<p>For example in Lisp, without doing anything special, an unmatched <code>(</code> in the middle of a function can easily make the parser think the missing <code>)</code> is at the end of the file. However a human looking at the code would use indentation as a heuristic to isolate the mismatch to the offending block. And in the presence of multiple bracket types, you may be able to narrow the possibilities if all the other bracket types are well-matched.</p>
<p>Are there any known algorithms or prior art implementations for this kind of parsing? Even better would be algorithms that can handle incremental updates to the source and can avoid a full reparse in many cases.</p>

<parsing><lisp><ide>
Techniques for resilient parsing in the face of mismatched brackets?
CC BY-SA 4.0
2023-08-19T16:42:12.283Z
You may be interested in: [eclector](https://github.com/s-expressionists/eclector).
Moonchild
CC BY-SA 4.0
2023-11-14T10:13:20.763Z
Lisp has syntax for built-in special operators (LET, ...) and various macros. That could be used.
Rainer Joswig
<h1>Use newlines and indentation as a hint</h1>
<p>LISP and other languages use punctuation as the ultimate decider of nesting and statement breaks, but there's still a convention for indentation which more or less gives you an idea of the layout of code. This convention is a lot more complicated than syntax, not set-in-stone, and varies between projects; presumably why most languages use punctuation. But a few rules give you a fuzzy idea of where missing/extra parentheses go.</p>
<hr />
<p>Consider this code (<a href="https://en.wikipedia.org/wiki/Scheme_(programming_language)#Block_structure" rel="nofollow noreferrer">from Wikipedia</a>):</p>
<pre class="lang-scheme prettyprint-override"><code>;; Calculation of Hofstadter's male and female sequences as a list of pairs

(define (hofstadter-male-female n)
  (letrec ((female (lambda (n)
             (if (= n 0)
             1
             (- n (male (female (- n 1)))))))
       (male (lambda (n)
           (if (= n 0)
               0
               (- n (female (male (- n 1))))))))
    (let loop ((i 0))
      (if (&gt; i n)
      '()
      (cons (cons (female i)
              (male i))
        (loop (+ i 1)))))))

(hofstadter-male-female 8)
</code></pre>
<p>In almost all cases, <strong>every line is indented to be later than the last-open parenthesis (e.g. unclosed parenthesis at column 42 -&gt; next line starts at column &gt;42)</strong>. The one exception is <code>lambda</code> blocks in a <code>letrec</code>, where the next line starts after the second-last-open parenthesis; you could assume that <code>let</code>/<code>lambda</code> is the only exception to this rule.</p>
<p>This means that if there's an unclosed parenthesis, the parser can infer that the parenthesis was meant to be closed when indentation reverted to before a parentheses which was still open, e.g. in</p>
<pre class="lang-scheme prettyprint-override"><code>(foo (bar
        baz (qux abc
                 def
                 ghi
        jkl))
</code></pre>
<p>You can infer that line 4 (<code>ghi</code>) has the unclosed parenthesis.</p>
<hr />
<p>That Wikipedia example was unusually badly formatted, and there's still a rule which is consistent enough that you can write a simple handler for it. If you adhere to a <a href="http://community.schemewiki.org/?scheme-style" rel="nofollow noreferrer">strict style guide</a>, there will be even more conventions to make ambiguous syntax errors un-ambiguous. But even without a defined, common style, the rule &quot;no indentation before unclosed parenthesis&quot; is almost universal in LISP.</p>

CC BY-SA 4.0
2023-08-20T02:21:44.237Z
2023-08-20T02:21:44.237Z
tarzh
CC BY-SA 4.0
2023-08-20T13:39:48.597Z
Yeah, the heuristic is straightforward, the question is how to write an efficient parsing algorithm for this. (Parallel parsing of the different possibilities as soon as you see suspicious indentation could easily become exponential on the input length.)
Ken Micklas
CC BY-SA 4.0
2023-08-20T14:24:26.240Z
You could remember the columns of the parentheses on each line which are open without closing a parenthesis on the same line, and mark the lines when the column of the first non-whitespace character is before those columns and if so, how many. After parsing, if there are unclosed parentheses, insert them before each of the marked lines: specifically, insert `n` parentheses on a marked line if the first non-whitespace column is before `n` open parentheses columns, until you run out of unclosed parentheses to insert. Then re-parse. This would be 2 passes and linear to the number of lines.
tarzh
CC BY-SA 4.0
2023-08-20T14:28:01.027Z
When parsing close parentheses without a prior open parenthesis you could just remove them.
tarzh
CC BY-SA 4.0
2023-08-20T17:36:11.343Z
Thanks, that looks like a viable algorithm. Can you add it to the answer?
Ken Micklas
# Techniques for resilient parsing in the face of mismatched brackets?
Posted by: username_0 on 2023-08-19
Suppose you want to build an IDE-grade parser for a language with highly uniform and nestable syntax (e.g. Lisp). Without a lot of "special" constructs like top-level functions, you can't use [standard techniques](https://matklad.github.io/2023/05/21/resilient-ll-parsing-tutorial.html) like bailing out until a known synchronization point.

For example in Lisp, without doing anything special, an unmatched `(` in the middle of a function can easily make the parser think the missing `)` is at the end of the file. However a human looking at the code would use indentation as a heuristic to isolate the mismatch to the offending block. And in the presence of multiple bracket types, you may be able to narrow the possibilities if all the other bracket types are well-matched.

Are there any known algorithms or prior art implementations for this kind of parsing? Even better would be algorithms that can handle incremental updates to the source and can avoid a full reparse in many cases.
**Tags:** parsing lisp ide
> **Comments:**
> **username_1**: You may be interested in: [eclector](https://github.com/s-expressionists/eclector).  
> **username_2**: Lisp has syntax for built-in special operators (LET, ...) and various macros. That could be used.  
---
## 1 answers
### Answer by username_3 on 2023-08-20. Score: 2
Use newlines and indentation as a hint
LISP and other languages use punctuation as the ultimate decider of nesting and statement breaks, but there's still a convention for indentation which more or less gives you an idea of the layout of code. This convention is a lot more complicated than syntax, not set-in-stone, and varies between projects; presumably why most languages use punctuation. But a few rules give you a fuzzy idea of where missing/extra parentheses go.

Consider this code (from Wikipedia):
;; Calculation of Hofstadter's male and female sequences as a list of pairs

(define (hofstadter-male-female n)
  (letrec ((female (lambda (n)
             (if (= n 0)
             1
             (- n (male (female (- n 1)))))))
       (male (lambda (n)
           (if (= n 0)
               0
               (- n (female (male (- n 1))))))))
    (let loop ((i 0))
      (if (> i n)
      '()
      (cons (cons (female i)
              (male i))
        (loop (+ i 1)))))))

(hofstadter-male-female 8)

In almost all cases, every line is indented to be later than the last-open parenthesis (e.g. unclosed parenthesis at column 42 -> next line starts at column >42). The one exception is lambda blocks in a letrec, where the next line starts after the second-last-open parenthesis; you could assume that let/lambda is the only exception to this rule.
This means that if there's an unclosed parenthesis, the parser can infer that the parenthesis was meant to be closed when indentation reverted to before a parentheses which was still open, e.g. in
(foo (bar
        baz (qux abc
                 def
                 ghi
        jkl))

You can infer that line 4 (ghi) has the unclosed parenthesis.

That Wikipedia example was unusually badly formatted, and there's still a rule which is consistent enough that you can write a simple handler for it. If you adhere to a strict style guide, there will be even more conventions to make ambiguous syntax errors un-ambiguous. But even without a defined, common style, the rule "no indentation before unclosed parenthesis" is almost universal in LISP.
> **Comments:**
> **username_0** (2023-08-20): Yeah, the heuristic is straightforward, the question is how to write an efficient parsing algorithm for this. (Parallel parsing of the different possibilities as soon as you see suspicious indentation could easily become exponential on the input length.)  
> **username_3** (2023-08-20): You could remember the columns of the parentheses on each line which are open without closing a parenthesis on the same line, and mark the lines when the column of the first non-whitespace character is before those columns and if so, how many. After parsing, if there are unclosed parentheses, insert them before each of the marked lines: specifically, insert `n` parentheses on a marked line if the first non-whitespace column is before `n` open parentheses columns, until you run out of unclosed parentheses to insert. Then re-parse. This would be 2 passes and linear to the number of lines.  
> **username_3** (2023-08-20): When parsing close parentheses without a prior open parenthesis you could just remove them.  
> **username_0** (2023-08-20): Thanks, that looks like a viable algorithm. Can you add it to the answer?  
---
