7
$\begingroup$

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 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.

$\endgroup$
2
  • $\begingroup$ You may be interested in: eclector. $\endgroup$
    – Moonchild
    Aug 19, 2023 at 16:42
  • $\begingroup$ Lisp has syntax for built-in special operators (LET, ...) and various macros. That could be used. $\endgroup$ Nov 14, 2023 at 10:13

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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.) $\endgroup$ Aug 20, 2023 at 13:39
  • $\begingroup$ 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. $\endgroup$
    – tarzh
    Aug 20, 2023 at 14:24
  • $\begingroup$ When parsing close parentheses without a prior open parenthesis you could just remove them. $\endgroup$
    – tarzh
    Aug 20, 2023 at 14:28
  • $\begingroup$ Thanks, that looks like a viable algorithm. Can you add it to the answer? $\endgroup$ Aug 20, 2023 at 17:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .